Changeset 1717:75fe24093ded in lemon-0.x for lemon/radix_heap.h

Timestamp:

10/14/05 12:40:00 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2244

Message:

Added clear function to heaps and concept

File:

• lemon/radix_heap.h (modified) (8 diffs)

lemon/radix_heap.h

@@ -27 +27 @@
 namespace lemon {
 
-  /// \addtogroup auxdat
-  /// @{
-
   /// \brief Exception thrown by RadixHeap.
   ///  
@@ -44 +41 @@
   };
 
+  /// \ingroup auxdata
+  ///
   /// \brief A Radix Heap implementation.
   ///
@@ -109 +108 @@
     ///
     /// The constructor.
-    /// \param _iim should be given to the constructor, since it is used
-    /// internally to handle the cross references. The value of the map
-    /// should be PRE_HEAP (-1) for each element.
-    explicit RadixHeap(ItemIntMap &_iim) : iim(_iim) {
-      boxes.push_back(RadixBox(0, 1));
-      boxes.push_back(RadixBox(1, 1));
-    }
-
-    /// \brief The constructor.
-    ///
-    /// The constructor.
     ///
     /// \param _iim It should be given to the constructor, since it is used
@@ -125 +113 @@
     /// should be PRE_HEAP (-1) for each element.
     ///
+    /// \param minimal The initial minimal value of the heap.
     /// \param capacity It determines the initial capacity of the heap. 
-    RadixHeap(ItemIntMap &_iim, int capacity) : iim(_iim) {
-      boxes.push_back(RadixBox(0, 1));
-      boxes.push_back(RadixBox(1, 1));
-      while (upper(boxes.back(), capacity)) {
+    RadixHeap(ItemIntMap &_iim, int minimal = 0, int capacity = 0) 
+      : iim(_iim) {
+      boxes.push_back(RadixBox(minimal, 1));
+      boxes.push_back(RadixBox(minimal + 1, 1));
+      while (lower(boxes.size() - 1, capacity + minimal - 1)) {
         extend();
       }
@@ -142 +132 @@
     /// Returns \c true if and only if the heap stores no items.
     bool empty() const { return data.empty(); }
+
+    /// \brief Make empty this heap.
+    /// 
+    /// Make empty this heap.
+    void clear(int minimal = 0, int capacity = 0) { 
+      for (int i = 0; i < (int)data.size(); ++i) {
+        iim[data[i].item] = -2;
+      }
+      data.clear(); boxes.clear(); 
+      boxes.push_back(RadixBox(minimal, 1));
+      boxes.push_back(RadixBox(minimal + 1, 1));
+      while (lower(boxes.size() - 1, capacity + minimal - 1)) {
+        extend();
+      }
+    }
 
   private:
@@ -272 +277 @@
   public:
 
-    /// \brief Insert an item into the heap with the given heap.
+    /// \brief Insert an item into the heap with the given priority.
     ///    
     /// Adds \c i to the heap with priority \c p. 
@@ -293 +298 @@
     /// \pre The heap must be nonempty.  
     Item top() const {
-      const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
+      const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
       return data[boxes[0].first].item;
     }
@@ -302 +307 @@
     /// \pre The heap must be nonempty.
     Prio prio() const {
-      const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
+      const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
       return data[boxes[0].first].prio;
      }