Boost logo

Boost-Commit :

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 =


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk