[Boost-commit] svn:boost r51190 - trunk/boost/graph/detail

Subject: [Boost-commit] svn:boost r51190 - trunk/boost/graph/detail
From: jewillco_at_[hidden]
Date: 2009-02-10 17:08:41

Author: jewillco
Date: 2009-02-10 17:08:39 EST (Tue, 10 Feb 2009)
New Revision: 51190
URL: http://svn.boost.org/trac/boost/changeset/51190

Log:
Fixed error when popping the last element from the heap
Text files modified: 
   trunk/boost/graph/detail/d_ary_heap.hpp |    40 +++++++++++++++++++++++++++++++++-------
   1 files changed, 33 insertions(+), 7 deletions(-)

Modified: trunk/boost/graph/detail/d_ary_heap.hpp
==============================================================================
--- trunk/boost/graph/detail/d_ary_heap.hpp	(original)
+++ trunk/boost/graph/detail/d_ary_heap.hpp	2009-02-10 17:08:39 EST (Tue, 10 Feb 2009)
@@ -33,6 +33,27 @@
     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
@@ -73,8 +94,9 @@
 
     d_ary_heap_indirect(DistanceMap distance,
                         IndexInHeapPropertyMap index_in_heap,
-                        const Compare& compare = Compare())
-      : compare(compare), data(), distance(distance),
+                        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 */
@@ -105,11 +127,15 @@
 
     void pop() {
       put(index_in_heap, data[0], (size_type)(-1));
-      data[0] = data.back();
-      put(index_in_heap, data[0], 0);
-      data.pop_back();
-      preserve_heap_property_down();
-      verify_heap();
+      if (data.size() != 1) {
+        data[0] = data.back();
+        put(index_in_heap, data[0], 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