1.1 --- a/lemon/bin_heap.h Fri Oct 07 11:05:35 2005 +0000
1.2 +++ b/lemon/bin_heap.h Fri Oct 14 10:40:00 2005 +0000
1.3 @@ -109,6 +109,16 @@
1.4 /// Returns \c true if and only if the heap stores no items.
1.5 bool empty() const { return data.empty(); }
1.6
1.7 + /// \brief Make empty this heap.
1.8 + ///
1.9 + /// Make empty this heap.
1.10 + void clear() {
1.11 + for (int i = 0; i < (int)data.size(); ++i) {
1.12 + iim.set(data[i].first, POST_HEAP);
1.13 + }
1.14 + data.clear();
1.15 + }
1.16 +
1.17 private:
1.18 static int parent(int i) { return (i-1)/2; }
1.19 static int second_child(int i) { return 2*i+2; }
2.1 --- a/lemon/concept/heap.h Fri Oct 07 11:05:35 2005 +0000
2.2 +++ b/lemon/concept/heap.h Fri Oct 14 10:40:00 2005 +0000
2.3 @@ -61,15 +61,21 @@
2.4 /// should be PRE_HEAP (-1) for each element.
2.5 explicit Heap(ItemIntMap &_iim) {}
2.6
2.7 - /// The number of items stored in the heap.
2.8 + /// \brief The number of items stored in the heap.
2.9 ///
2.10 - /// \brief Returns the number of items stored in the heap.
2.11 + /// Returns the number of items stored in the heap.
2.12 int size() const { return 0; }
2.13 +
2.14 /// \brief Checks if the heap stores no items.
2.15 ///
2.16 /// Returns \c true if and only if the heap stores no items.
2.17 bool empty() const { return false; }
2.18
2.19 + /// \brief Makes empty this heap.
2.20 + ///
2.21 + /// Makes this heap empty.
2.22 + void clear();
2.23 +
2.24 /// \brief Insert an item into the heap with the given heap.
2.25 ///
2.26 /// Adds \c i to the heap with priority \c p.
2.27 @@ -189,6 +195,8 @@
2.28 state = _Heap::PRE_HEAP;
2.29 state = _Heap::IN_HEAP;
2.30 state = _Heap::POST_HEAP;
2.31 +
2.32 + heap.clear();
2.33 }
2.34
2.35 _Heap& heap;
3.1 --- a/lemon/fib_heap.h Fri Oct 07 11:05:35 2005 +0000
3.2 +++ b/lemon/fib_heap.h Fri Oct 14 10:40:00 2005 +0000
3.3 @@ -88,143 +88,125 @@
3.4 POST_HEAP = -2
3.5 };
3.6
3.7 - ///The constructor
3.8 -
3.9 - /**
3.10 - \c _iimap should be given to the constructor, since it is
3.11 - used internally to handle the cross references.
3.12 - */
3.13 + /// \brief The constructor
3.14 + ///
3.15 + /// \c _iimap should be given to the constructor, since it is
3.16 + /// used internally to handle the cross references.
3.17 explicit FibHeap(ItemIntMap &_iimap)
3.18 : minimum(0), iimap(_iimap), num_items() {}
3.19
3.20 - ///The constructor
3.21 -
3.22 - /**
3.23 - \c _iimap should be given to the constructor, since it is used
3.24 - internally to handle the cross references. \c _comp is an
3.25 - object for ordering of the priorities.
3.26 - */
3.27 + /// \brief The constructor
3.28 + ///
3.29 + /// \c _iimap should be given to the constructor, since it is used
3.30 + /// internally to handle the cross references. \c _comp is an
3.31 + /// object for ordering of the priorities.
3.32 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
3.33 iimap(_iimap), comp(_comp), num_items() {}
3.34
3.35 - ///The number of items stored in the heap.
3.36 -
3.37 - /**
3.38 - Returns the number of items stored in the heap.
3.39 - */
3.40 + /// \brief The number of items stored in the heap.
3.41 + ///
3.42 + /// Returns the number of items stored in the heap.
3.43 int size() const { return num_items; }
3.44
3.45 - ///Checks if the heap stores no items.
3.46 -
3.47 - /**
3.48 - Returns \c true if and only if the heap stores no items.
3.49 - */
3.50 + /// \brief Checks if the heap stores no items.
3.51 + ///
3.52 + /// Returns \c true if and only if the heap stores no items.
3.53 bool empty() const { return num_items==0; }
3.54
3.55 - ///\c item gets to the heap with priority \c value independently if \c item was already there.
3.56 + /// \brief Make empty this heap.
3.57 + ///
3.58 + /// Make empty this heap.
3.59 + void clear() {
3.60 + for (int i = 0; i < (int)container.size(); ++i) {
3.61 + iimap[container[i].name] = -2;
3.62 + }
3.63 + container.clear(); minimum = 0; num_items = 0;
3.64 + }
3.65
3.66 - /**
3.67 - This method calls \ref push(\c item, \c value) if \c item is not
3.68 - stored in the heap and it calls \ref decrease(\c item, \c value) or
3.69 - \ref increase(\c item, \c value) otherwise.
3.70 - */
3.71 + /// \brief \c item gets to the heap with priority \c value independently
3.72 + /// if \c item was already there.
3.73 + ///
3.74 + /// This method calls \ref push(\c item, \c value) if \c item is not
3.75 + /// stored in the heap and it calls \ref decrease(\c item, \c value) or
3.76 + /// \ref increase(\c item, \c value) otherwise.
3.77 void set (Item const item, PrioType const value);
3.78
3.79 - ///Adds \c item to the heap with priority \c value.
3.80 -
3.81 - /**
3.82 - Adds \c item to the heap with priority \c value.
3.83 - \pre \c item must not be stored in the heap.
3.84 - */
3.85 + /// \brief Adds \c item to the heap with priority \c value.
3.86 + ///
3.87 + /// Adds \c item to the heap with priority \c value.
3.88 + /// \pre \c item must not be stored in the heap.
3.89 void push (Item const item, PrioType const value);
3.90
3.91 - ///Returns the item with minimum priority relative to \c Compare.
3.92 -
3.93 - /**
3.94 - This method returns the item with minimum priority relative to \c
3.95 - Compare.
3.96 - \pre The heap must be nonempty.
3.97 - */
3.98 + /// \brief Returns the item with minimum priority relative to \c Compare.
3.99 + ///
3.100 + /// This method returns the item with minimum priority relative to \c
3.101 + /// Compare.
3.102 + /// \pre The heap must be nonempty.
3.103 Item top() const { return container[minimum].name; }
3.104
3.105 - ///Returns the minimum priority relative to \c Compare.
3.106 -
3.107 - /**
3.108 - It returns the minimum priority relative to \c Compare.
3.109 - \pre The heap must be nonempty.
3.110 - */
3.111 + /// \brief Returns the minimum priority relative to \c Compare.
3.112 + ///
3.113 + /// It returns the minimum priority relative to \c Compare.
3.114 + /// \pre The heap must be nonempty.
3.115 PrioType prio() const { return container[minimum].prio; }
3.116
3.117 - ///Returns the priority of \c item.
3.118 -
3.119 - /**
3.120 - This function returns the priority of \c item.
3.121 - \pre \c item must be in the heap.
3.122 - */
3.123 + /// \brief Returns the priority of \c item.
3.124 + ///
3.125 + /// This function returns the priority of \c item.
3.126 + /// \pre \c item must be in the heap.
3.127 PrioType& operator[](const Item& item) {
3.128 return container[iimap[item]].prio;
3.129 }
3.130
3.131 - ///Returns the priority of \c item.
3.132 -
3.133 - /**
3.134 - It returns the priority of \c item.
3.135 - \pre \c item must be in the heap.
3.136 - */
3.137 + /// \brief Returns the priority of \c item.
3.138 + ///
3.139 + /// It returns the priority of \c item.
3.140 + /// \pre \c item must be in the heap.
3.141 const PrioType& operator[](const Item& item) const {
3.142 return container[iimap[item]].prio;
3.143 }
3.144
3.145
3.146 - ///Deletes the item with minimum priority relative to \c Compare.
3.147 -
3.148 - /**
3.149 - This method deletes the item with minimum priority relative to \c
3.150 - Compare from the heap.
3.151 - \pre The heap must be non-empty.
3.152 - */
3.153 + /// \brief Deletes the item with minimum priority relative to \c Compare.
3.154 + ///
3.155 + /// This method deletes the item with minimum priority relative to \c
3.156 + /// Compare from the heap.
3.157 + /// \pre The heap must be non-empty.
3.158 void pop();
3.159
3.160 - ///Deletes \c item from the heap.
3.161 -
3.162 - /**
3.163 - This method deletes \c item from the heap, if \c item was already
3.164 - stored in the heap. It is quite inefficient in Fibonacci heaps.
3.165 - */
3.166 + /// \brief Deletes \c item from the heap.
3.167 + ///
3.168 + /// This method deletes \c item from the heap, if \c item was already
3.169 + /// stored in the heap. It is quite inefficient in Fibonacci heaps.
3.170 void erase (const Item& item);
3.171
3.172 - ///Decreases the priority of \c item to \c value.
3.173 -
3.174 - /**
3.175 - This method decreases the priority of \c item to \c value.
3.176 - \pre \c item must be stored in the heap with priority at least \c
3.177 - value relative to \c Compare.
3.178 - */
3.179 + /// \brief Decreases the priority of \c item to \c value.
3.180 + ///
3.181 + /// This method decreases the priority of \c item to \c value.
3.182 + /// \pre \c item must be stored in the heap with priority at least \c
3.183 + /// value relative to \c Compare.
3.184 void decrease (Item item, PrioType const value);
3.185
3.186 - ///Increases the priority of \c item to \c value.
3.187 -
3.188 - /**
3.189 - This method sets the priority of \c item to \c value. Though
3.190 - there is no precondition on the priority of \c item, this
3.191 - method should be used only if it is indeed necessary to increase
3.192 - (relative to \c Compare) the priority of \c item, because this
3.193 - method is inefficient.
3.194 - */
3.195 + /// \brief Increases the priority of \c item to \c value.
3.196 + ///
3.197 + /// This method sets the priority of \c item to \c value. Though
3.198 + /// there is no precondition on the priority of \c item, this
3.199 + /// method should be used only if it is indeed necessary to increase
3.200 + /// (relative to \c Compare) the priority of \c item, because this
3.201 + /// method is inefficient.
3.202 void increase (Item item, PrioType const value) {
3.203 erase(item);
3.204 push(item, value);
3.205 }
3.206
3.207
3.208 - ///Returns if \c item is in, has already been in, or has never been in the heap.
3.209 -
3.210 - /**
3.211 - This method returns PRE_HEAP if \c item has never been in the
3.212 - heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
3.213 - otherwise. In the latter case it is possible that \c item will
3.214 - get back to the heap again.
3.215 - */
3.216 + /// \brief Returns if \c item is in, has already been in, or has never
3.217 + /// been in the heap.
3.218 + ///
3.219 + /// This method returns PRE_HEAP if \c item has never been in the
3.220 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
3.221 + /// otherwise. In the latter case it is possible that \c item will
3.222 + /// get back to the heap again.
3.223 state_enum state(const Item &item) const {
3.224 int i=iimap[item];
3.225 if( i>=0 ) {
4.1 --- a/lemon/radix_heap.h Fri Oct 07 11:05:35 2005 +0000
4.2 +++ b/lemon/radix_heap.h Fri Oct 14 10:40:00 2005 +0000
4.3 @@ -26,9 +26,6 @@
4.4
4.5 namespace lemon {
4.6
4.7 - /// \addtogroup auxdat
4.8 - /// @{
4.9 -
4.10 /// \brief Exception thrown by RadixHeap.
4.11 ///
4.12 /// This Exception is thrown when a smaller priority
4.13 @@ -43,6 +40,8 @@
4.14 }
4.15 };
4.16
4.17 + /// \ingroup auxdata
4.18 + ///
4.19 /// \brief A Radix Heap implementation.
4.20 ///
4.21 /// This class implements the \e radix \e heap data structure. A \e heap
4.22 @@ -108,27 +107,18 @@
4.23 /// \brief The constructor.
4.24 ///
4.25 /// The constructor.
4.26 - /// \param _iim should be given to the constructor, since it is used
4.27 - /// internally to handle the cross references. The value of the map
4.28 - /// should be PRE_HEAP (-1) for each element.
4.29 - explicit RadixHeap(ItemIntMap &_iim) : iim(_iim) {
4.30 - boxes.push_back(RadixBox(0, 1));
4.31 - boxes.push_back(RadixBox(1, 1));
4.32 - }
4.33 -
4.34 - /// \brief The constructor.
4.35 - ///
4.36 - /// The constructor.
4.37 ///
4.38 /// \param _iim It should be given to the constructor, since it is used
4.39 /// internally to handle the cross references. The value of the map
4.40 /// should be PRE_HEAP (-1) for each element.
4.41 ///
4.42 + /// \param minimal The initial minimal value of the heap.
4.43 /// \param capacity It determines the initial capacity of the heap.
4.44 - RadixHeap(ItemIntMap &_iim, int capacity) : iim(_iim) {
4.45 - boxes.push_back(RadixBox(0, 1));
4.46 - boxes.push_back(RadixBox(1, 1));
4.47 - while (upper(boxes.back(), capacity)) {
4.48 + RadixHeap(ItemIntMap &_iim, int minimal = 0, int capacity = 0)
4.49 + : iim(_iim) {
4.50 + boxes.push_back(RadixBox(minimal, 1));
4.51 + boxes.push_back(RadixBox(minimal + 1, 1));
4.52 + while (lower(boxes.size() - 1, capacity + minimal - 1)) {
4.53 extend();
4.54 }
4.55 }
4.56 @@ -142,6 +132,21 @@
4.57 /// Returns \c true if and only if the heap stores no items.
4.58 bool empty() const { return data.empty(); }
4.59
4.60 + /// \brief Make empty this heap.
4.61 + ///
4.62 + /// Make empty this heap.
4.63 + void clear(int minimal = 0, int capacity = 0) {
4.64 + for (int i = 0; i < (int)data.size(); ++i) {
4.65 + iim[data[i].item] = -2;
4.66 + }
4.67 + data.clear(); boxes.clear();
4.68 + boxes.push_back(RadixBox(minimal, 1));
4.69 + boxes.push_back(RadixBox(minimal + 1, 1));
4.70 + while (lower(boxes.size() - 1, capacity + minimal - 1)) {
4.71 + extend();
4.72 + }
4.73 + }
4.74 +
4.75 private:
4.76
4.77 bool upper(int box, Prio prio) {
4.78 @@ -271,7 +276,7 @@
4.79
4.80 public:
4.81
4.82 - /// \brief Insert an item into the heap with the given heap.
4.83 + /// \brief Insert an item into the heap with the given priority.
4.84 ///
4.85 /// Adds \c i to the heap with priority \c p.
4.86 /// \param i The item to insert.
4.87 @@ -292,7 +297,7 @@
4.88 /// This method returns the item with minimum priority.
4.89 /// \pre The heap must be nonempty.
4.90 Item top() const {
4.91 - const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
4.92 + const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
4.93 return data[boxes[0].first].item;
4.94 }
4.95
4.96 @@ -301,7 +306,7 @@
4.97 /// It returns the minimum priority.
4.98 /// \pre The heap must be nonempty.
4.99 Prio prio() const {
4.100 - const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
4.101 + const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
4.102 return data[boxes[0].first].prio;
4.103 }
4.104