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

Subject: [Boost-commit] svn:boost r51021 - trunk/boost/graph/detail
From: jewillco_at_[hidden]
Date: 2009-02-04 16:01:28

Author: jewillco
Date: 2009-02-04 16:01:27 EST (Wed, 04 Feb 2009)
New Revision: 51021
URL: http://svn.boost.org/trac/boost/changeset/51021

Log:
Added ability to check whether an element is in the heap, and do conditional insert/update operations based on that
Text files modified: 
   trunk/boost/graph/detail/d_ary_heap.hpp |    17 +++++++++++++++++                       
   1 files changed, 17 insertions(+), 0 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-04 16:01:27 EST (Wed, 04 Feb 2009)
@@ -104,6 +104,7 @@
     }
 
     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();
@@ -120,6 +121,21 @@
       verify_heap();
     }
 
+    bool contains(const Value& v) const {
+      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();
+    }
+
     private:
     Compare compare;
     Container data;
@@ -211,6 +227,7 @@
     // 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 =