EIC code displayed by LXR master/​include/​boost/​graph/​detail/​d_ary_heap.hpp	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2025-01-18 09:37:10

 //
 //=======================================================================
 // Copyright 2009 Trustees of Indiana University
 // Authors: Jeremiah J. Willcock, Andrew Lumsdaine
 //
 // Distributed under the Boost Software License, Version 1.0. (See
 // accompanying file LICENSE_1_0.txt or copy at
 // http://www.boost.org/LICENSE_1_0.txt)
 //=======================================================================
 //
 #ifndef BOOST_D_ARY_HEAP_HPP
 #define BOOST_D_ARY_HEAP_HPP
 
 #include <vector>
 #include <cstddef>
 #include <algorithm>
 #include <utility>
 #include <boost/assert.hpp>
 #include <boost/static_assert.hpp>
 #include <boost/shared_array.hpp>
 #include <boost/property_map/property_map.hpp>
 
 // WARNING: it is not safe to copy a d_ary_heap_indirect and then modify one of
 // the copies.  The class is required to be copyable so it can be passed around
 // (without move support from C++11), but it deep-copies the heap contents yet
 // shallow-copies the index_in_heap_map.
 
 namespace boost
 {
 
 // Swap two elements in a property map without assuming they model
 // LvaluePropertyMap -- currently not used
 template < typename PropMap >
 inline void property_map_swap(PropMap prop_map,
     const typename boost::property_traits< PropMap >::key_type& ka,
     const typename boost::property_traits< PropMap >::key_type& kb)
 {
     typename boost::property_traits< PropMap >::value_type va
         = get(prop_map, ka);
     put(prop_map, ka, get(prop_map, kb));
     put(prop_map, kb, va);
 }
 
 namespace detail
 {
     template < typename Value > class fixed_max_size_vector
     {
         boost::shared_array< Value > m_data;
         std::size_t m_size;
 
     public:
         typedef std::size_t size_type;
         fixed_max_size_vector(std::size_t max_size)
         : m_data(new Value[max_size]), m_size(0)
         {
         }
         std::size_t size() const { return m_size; }
         bool empty() const { return m_size == 0; }
         Value& operator[](std::size_t i) { return m_data[i]; }
         const Value& operator[](std::size_t i) const { return m_data[i]; }
         void push_back(Value v) { m_data[m_size++] = v; }
         void pop_back() { --m_size; }
         Value& back() { return m_data[m_size - 1]; }
         const Value& back() const { return m_data[m_size - 1]; }
     };
 }
 
 // D-ary heap using an indirect compare operator (use identity_property_map
 // as DistanceMap to get a direct compare operator).  This heap appears to be
 // commonly used for Dijkstra's algorithm for its good practical performance
 // on some platforms; asymptotically, it has an O(lg N) decrease-key
 // operation while that can be done in constant time on a relaxed heap.  The
 // implementation is mostly based on the binary heap page on Wikipedia and
 // online sources that state that the operations are the same for d-ary
 // heaps.  This code is not based on the old Boost d-ary heap code.
 //
 // - d_ary_heap_indirect is a model of UpdatableQueue as is needed for
 //   dijkstra_shortest_paths.
 //
 // - Value must model Assignable.
 // - Arity must be at least 2 (optimal value appears to be 4, both in my and
 //   third-party experiments).
 // - IndexInHeapMap must be a ReadWritePropertyMap from Value to
 //   Container::size_type (to store the index of each stored value within the
 //   heap for decrease-key aka update).
 // - DistanceMap must be a ReadablePropertyMap from Value to something
 //   (typedef'ed as distance_type).
 // - Compare must be a BinaryPredicate used as a less-than operator on
 //   distance_type.
 // - Container must be a random-access, contiguous container (in practice,
 //   the operations used probably require that it is std::vector<Value>).
 //
 template < typename Value, std::size_t Arity, typename IndexInHeapPropertyMap,
     typename DistanceMap, typename Compare = std::less< Value >,
     typename Container = std::vector< Value > >
 class d_ary_heap_indirect
 {
     BOOST_STATIC_ASSERT(Arity >= 2);
 
 public:
     typedef typename Container::size_type size_type;
     typedef Value value_type;
     typedef typename boost::property_traits< DistanceMap >::value_type key_type;
     typedef DistanceMap key_map;
 
     d_ary_heap_indirect(DistanceMap distance,
         IndexInHeapPropertyMap index_in_heap,
         const Compare& compare = Compare(), const Container& data = Container())
     : compare(compare)
     , data(data)
     , distance(distance)
     , index_in_heap(index_in_heap)
     {
     }
     /* Implicit copy constructor */
     /* Implicit assignment operator */
 
     size_type size() const { return data.size(); }
 
     bool empty() const { return data.empty(); }
 
     void push(const Value& v)
     {
         size_type index = data.size();
         data.push_back(v);
         put(index_in_heap, v, index);
         preserve_heap_property_up(index);
         verify_heap();
     }
 
     Value& top()
     {
         BOOST_ASSERT(!this->empty());
         return data[0];
     }
 
     const Value& top() const
     {
         BOOST_ASSERT(!this->empty());
         return data[0];
     }
 
     void pop()
     {
         BOOST_ASSERT(!this->empty());
         put(index_in_heap, data[0], (size_type)(-1));
         if (data.size() != 1)
         {
             data[0] = data.back();
             put(index_in_heap, data[0], (size_type)(0));
             data.pop_back();
             preserve_heap_property_down();
             verify_heap();
         }
         else
         {
             data.pop_back();
         }
     }
 
     // This function assumes the key has been updated (using an external write
     // to the distance map or such)
     // See
     // http://coding.derkeiler.com/Archive/General/comp.theory/2007-05/msg00043.html
     void update(const Value& v)
     { /* decrease-key */
         size_type index = get(index_in_heap, v);
         preserve_heap_property_up(index);
         verify_heap();
     }
 
     bool contains(const Value& v) const
     {
         size_type index = get(index_in_heap, v);
         return (index != (size_type)(-1));
     }
 
     void push_or_update(const Value& v)
     { /* insert if not present, else update */
         size_type index = get(index_in_heap, v);
         if (index == (size_type)(-1))
         {
             index = data.size();
             data.push_back(v);
             put(index_in_heap, v, index);
         }
         preserve_heap_property_up(index);
         verify_heap();
     }
 
     DistanceMap keys() const { return distance; }
 
 private:
     Compare compare;
     Container data;
     DistanceMap distance;
     IndexInHeapPropertyMap index_in_heap;
 
     // The distances being compared using compare and that are stored in the
     // distance map
     typedef typename boost::property_traits< DistanceMap >::value_type
         distance_type;
 
     // Get the parent of a given node in the heap
     static size_type parent(size_type index) { return (index - 1) / Arity; }
 
     // Get the first child of a given node
     static size_type first_child(size_type index)
     {
         return index * Arity + 1;
     }
 
     // Swap two elements in the heap by index, updating index_in_heap
     void swap_heap_elements(size_type index_a, size_type index_b)
     {
         using std::swap;
         Value value_a = data[index_a];
         Value value_b = data[index_b];
         data[index_a] = value_b;
         data[index_b] = value_a;
         put(index_in_heap, value_a, index_b);
         put(index_in_heap, value_b, index_a);
     }
 
     // Emulate the indirect_cmp that is now folded into this heap class
     bool compare_indirect(const Value& a, const Value& b) const
     {
         return compare(get(distance, a), get(distance, b));
     }
 
     // Verify that the array forms a heap; commented out by default
     void verify_heap() const
     {
         // This is a very expensive test so it should be disabled even when
         // NDEBUG is not defined
 #if 0
       for (size_t i = 1; i < data.size(); ++i) {
         if (compare_indirect(data[i], data[parent(i)])) {
           BOOST_ASSERT (!"Element is smaller than its parent");
         }
       }
 #endif
     }
 
     // Starting at a node, move up the tree swapping elements to preserve the
     // heap property
     void preserve_heap_property_up(size_type index)
     {
         size_type orig_index = index;
         size_type num_levels_moved = 0;
         // The first loop just saves swaps that need to be done in order to
         // avoid aliasing issues in its search; there is a second loop that does
         // the necessary swap operations
         if (index == 0)
             return; // Do nothing on root
         Value currently_being_moved = data[index];
         distance_type currently_being_moved_dist
             = get(distance, currently_being_moved);
         for (;;)
         {
             if (index == 0)
                 break; // Stop at root
             size_type parent_index = parent(index);
             Value parent_value = data[parent_index];
             if (compare(
                     currently_being_moved_dist, get(distance, parent_value)))
             {
                 ++num_levels_moved;
                 index = parent_index;
                 continue;
             }
             else
             {
                 break; // Heap property satisfied
             }
         }
         // Actually do the moves -- move num_levels_moved elements down in the
         // tree, then put currently_being_moved at the top
         index = orig_index;
         for (size_type i = 0; i < num_levels_moved; ++i)
         {
             size_type parent_index = parent(index);
             Value parent_value = data[parent_index];
             put(index_in_heap, parent_value, index);
             data[index] = parent_value;
             index = parent_index;
         }
         data[index] = currently_being_moved;
         put(index_in_heap, currently_being_moved, index);
         verify_heap();
     }
 
     // From the root, swap elements (each one with its smallest child) if there
     // are any parent-child pairs that violate the heap property
     void preserve_heap_property_down()
     {
         if (data.empty())
             return;
         size_type index = 0;
         Value currently_being_moved = data[0];
         distance_type currently_being_moved_dist
             = get(distance, currently_being_moved);
         size_type heap_size = data.size();
         Value* data_ptr = &data[0];
         for (;;)
         {
             size_type first_child_index = first_child(index);
             if (first_child_index >= heap_size)
                 break; /* No children */
             Value* child_base_ptr = data_ptr + first_child_index;
             size_type smallest_child_index = 0;
             distance_type smallest_child_dist
                 = get(distance, child_base_ptr[smallest_child_index]);
             if (first_child_index + Arity <= heap_size)
             {
                 // Special case for a statically known loop count (common case)
                 for (size_t i = 1; i < Arity; ++i)
                 {
                     Value i_value = child_base_ptr[i];
                     distance_type i_dist = get(distance, i_value);
                     if (compare(i_dist, smallest_child_dist))
                     {
                         smallest_child_index = i;
                         smallest_child_dist = i_dist;
                     }
                 }
             }
             else
             {
                 for (size_t i = 1; i < heap_size - first_child_index; ++i)
                 {
                     distance_type i_dist = get(distance, child_base_ptr[i]);
                     if (compare(i_dist, smallest_child_dist))
                     {
                         smallest_child_index = i;
                         smallest_child_dist = i_dist;
                     }
                 }
             }
             if (compare(smallest_child_dist, currently_being_moved_dist))
             {
                 swap_heap_elements(
                     smallest_child_index + first_child_index, index);
                 index = smallest_child_index + first_child_index;
                 continue;
             }
             else
             {
                 break; // Heap property satisfied
             }
         }
         verify_heap();
     }
 };
 
 } // namespace boost
 
 #endif // BOOST_D_ARY_HEAP_HPP

This page was automatically generated by the 2.3.7 LXR engine. The LXR team