1.1 --- a/lemon/radix_heap.h Fri Oct 07 11:05:35 2005 +0000
1.2 +++ b/lemon/radix_heap.h Fri Oct 14 10:40:00 2005 +0000
1.3 @@ -26,9 +26,6 @@
1.4
1.5 namespace lemon {
1.6
1.7 - /// \addtogroup auxdat
1.8 - /// @{
1.9 -
1.10 /// \brief Exception thrown by RadixHeap.
1.11 ///
1.12 /// This Exception is thrown when a smaller priority
1.13 @@ -43,6 +40,8 @@
1.14 }
1.15 };
1.16
1.17 + /// \ingroup auxdata
1.18 + ///
1.19 /// \brief A Radix Heap implementation.
1.20 ///
1.21 /// This class implements the \e radix \e heap data structure. A \e heap
1.22 @@ -108,27 +107,18 @@
1.23 /// \brief The constructor.
1.24 ///
1.25 /// The constructor.
1.26 - /// \param _iim should be given to the constructor, since it is used
1.27 - /// internally to handle the cross references. The value of the map
1.28 - /// should be PRE_HEAP (-1) for each element.
1.29 - explicit RadixHeap(ItemIntMap &_iim) : iim(_iim) {
1.30 - boxes.push_back(RadixBox(0, 1));
1.31 - boxes.push_back(RadixBox(1, 1));
1.32 - }
1.33 -
1.34 - /// \brief The constructor.
1.35 - ///
1.36 - /// The constructor.
1.37 ///
1.38 /// \param _iim It should be given to the constructor, since it is used
1.39 /// internally to handle the cross references. The value of the map
1.40 /// should be PRE_HEAP (-1) for each element.
1.41 ///
1.42 + /// \param minimal The initial minimal value of the heap.
1.43 /// \param capacity It determines the initial capacity of the heap.
1.44 - RadixHeap(ItemIntMap &_iim, int capacity) : iim(_iim) {
1.45 - boxes.push_back(RadixBox(0, 1));
1.46 - boxes.push_back(RadixBox(1, 1));
1.47 - while (upper(boxes.back(), capacity)) {
1.48 + RadixHeap(ItemIntMap &_iim, int minimal = 0, int capacity = 0)
1.49 + : iim(_iim) {
1.50 + boxes.push_back(RadixBox(minimal, 1));
1.51 + boxes.push_back(RadixBox(minimal + 1, 1));
1.52 + while (lower(boxes.size() - 1, capacity + minimal - 1)) {
1.53 extend();
1.54 }
1.55 }
1.56 @@ -142,6 +132,21 @@
1.57 /// Returns \c true if and only if the heap stores no items.
1.58 bool empty() const { return data.empty(); }
1.59
1.60 + /// \brief Make empty this heap.
1.61 + ///
1.62 + /// Make empty this heap.
1.63 + void clear(int minimal = 0, int capacity = 0) {
1.64 + for (int i = 0; i < (int)data.size(); ++i) {
1.65 + iim[data[i].item] = -2;
1.66 + }
1.67 + data.clear(); boxes.clear();
1.68 + boxes.push_back(RadixBox(minimal, 1));
1.69 + boxes.push_back(RadixBox(minimal + 1, 1));
1.70 + while (lower(boxes.size() - 1, capacity + minimal - 1)) {
1.71 + extend();
1.72 + }
1.73 + }
1.74 +
1.75 private:
1.76
1.77 bool upper(int box, Prio prio) {
1.78 @@ -271,7 +276,7 @@
1.79
1.80 public:
1.81
1.82 - /// \brief Insert an item into the heap with the given heap.
1.83 + /// \brief Insert an item into the heap with the given priority.
1.84 ///
1.85 /// Adds \c i to the heap with priority \c p.
1.86 /// \param i The item to insert.
1.87 @@ -292,7 +297,7 @@
1.88 /// This method returns the item with minimum priority.
1.89 /// \pre The heap must be nonempty.
1.90 Item top() const {
1.91 - const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
1.92 + const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
1.93 return data[boxes[0].first].item;
1.94 }
1.95
1.96 @@ -301,7 +306,7 @@
1.97 /// It returns the minimum priority.
1.98 /// \pre The heap must be nonempty.
1.99 Prio prio() const {
1.100 - const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
1.101 + const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
1.102 return data[boxes[0].first].prio;
1.103 }
1.104