Changes in / [708:5d313b76f323:712:6d5f547e5bfb] in lemon-main
- Files:
-
- 6 edited
-
doc/groups.dox (modified) (2 diffs)
-
lemon/bin_heap.h (modified) (14 diffs)
-
lemon/bucket_heap.h (modified) (27 diffs)
-
lemon/concepts/heap.h (modified) (7 diffs)
-
lemon/fib_heap.h (modified) (12 diffs)
-
lemon/radix_heap.h (modified) (9 diffs)
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r663 r710 227 227 228 228 /** 229 @defgroup matrices Matrices230 @ingroup datas231 \brief Two dimensional data storages implemented in LEMON.232 233 This group contains two dimensional data storages implemented in LEMON.234 */235 236 /**237 229 @defgroup paths Path Structures 238 230 @ingroup datas … … 247 239 any kind of path structure. 248 240 249 \sa lemon::concepts::Path 241 \sa \ref concepts::Path "Path concept" 242 */ 243 244 /** 245 @defgroup heaps Heap Structures 246 @ingroup datas 247 \brief %Heap structures implemented in LEMON. 248 249 This group contains the heap structures implemented in LEMON. 250 251 LEMON provides several heap classes. They are efficient implementations 252 of the abstract data type \e priority \e queue. They store items with 253 specified values called \e priorities in such a way that finding and 254 removing the item with minimum priority are efficient. 255 The basic operations are adding and erasing items, changing the priority 256 of an item, etc. 257 258 Heaps are crucial in several algorithms, such as Dijkstra and Prim. 259 The heap implementations have the same interface, thus any of them can be 260 used easily in such algorithms. 261 262 \sa \ref concepts::Heap "Heap concept" 263 */ 264 265 /** 266 @defgroup matrices Matrices 267 @ingroup datas 268 \brief Two dimensional data storages implemented in LEMON. 269 270 This group contains two dimensional data storages implemented in LEMON. 250 271 */ 251 272 -
lemon/bin_heap.h
r683 r711 20 20 #define LEMON_BIN_HEAP_H 21 21 22 ///\ingroup auxdat22 ///\ingroup heaps 23 23 ///\file 24 ///\brief Binary Heap implementation.24 ///\brief Binary heap implementation. 25 25 26 26 #include <vector> … … 30 30 namespace lemon { 31 31 32 /// \ingroup auxdat32 /// \ingroup heaps 33 33 /// 34 /// \brief A Binary Heap implementation.34 /// \brief Binary heap data structure. 35 35 /// 36 ///This class implements the \e binary \e heap data structure. 36 /// This class implements the \e binary \e heap data structure. 37 /// It fully conforms to the \ref concepts::Heap "heap concept". 37 38 /// 38 ///A \e heap is a data structure for storing items with specified values 39 ///called \e priorities in such a way that finding the item with minimum 40 ///priority is efficient. \c CMP specifies the ordering of the priorities. 41 ///In a heap one can change the priority of an item, add or erase an 42 ///item, etc. 43 /// 44 ///\tparam PR Type of the priority of the items. 45 ///\tparam IM A read and writable item map with int values, used internally 46 ///to handle the cross references. 47 ///\tparam CMP A functor class for the ordering of the priorities. 48 ///The default is \c std::less<PR>. 49 /// 50 ///\sa FibHeap 51 ///\sa Dijkstra 39 /// \tparam PR Type of the priorities of the items. 40 /// \tparam IM A read-writable item map with \c int values, used 41 /// internally to handle the cross references. 42 /// \tparam CMP A functor class for comparing the priorities. 43 /// The default is \c std::less<PR>. 44 #ifdef DOXYGEN 45 template <typename PR, typename IM, typename CMP> 46 #else 52 47 template <typename PR, typename IM, typename CMP = std::less<PR> > 48 #endif 53 49 class BinHeap { 54 55 50 public: 56 ///\e 51 52 /// Type of the item-int map. 57 53 typedef IM ItemIntMap; 58 /// \e54 /// Type of the priorities. 59 55 typedef PR Prio; 60 /// \e56 /// Type of the items stored in the heap. 61 57 typedef typename ItemIntMap::Key Item; 62 /// \e58 /// Type of the item-priority pairs. 63 59 typedef std::pair<Item,Prio> Pair; 64 /// \e60 /// Functor type for comparing the priorities. 65 61 typedef CMP Compare; 66 62 67 /// \brief Type to represent the items states.68 /// 69 /// Each Item element have a state associated to it. It maybe "in heap",70 /// "pre heap" or "postheap". The latter two are indifferent from the63 /// \brief Type to represent the states of the items. 64 /// 65 /// Each item has a state associated to it. It can be "in heap", 66 /// "pre-heap" or "post-heap". The latter two are indifferent from the 71 67 /// heap's point of view, but may be useful to the user. 72 68 /// … … 85 81 86 82 public: 87 /// \brief The constructor. 88 /// 89 /// The constructor. 90 /// \param map should be given to the constructor, since it is used 91 /// internally to handle the cross references. The value of the map 92 /// must be \c PRE_HEAP (<tt>-1</tt>) for every item. 83 84 /// \brief Constructor. 85 /// 86 /// Constructor. 87 /// \param map A map that assigns \c int values to the items. 88 /// It is used internally to handle the cross references. 89 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 93 90 explicit BinHeap(ItemIntMap &map) : _iim(map) {} 94 91 95 /// \brief The constructor. 96 /// 97 /// The constructor. 98 /// \param map should be given to the constructor, since it is used 99 /// internally to handle the cross references. The value of the map 100 /// should be PRE_HEAP (-1) for each element. 101 /// 102 /// \param comp The comparator function object. 92 /// \brief Constructor. 93 /// 94 /// Constructor. 95 /// \param map A map that assigns \c int values to the items. 96 /// It is used internally to handle the cross references. 97 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 98 /// \param comp The function object used for comparing the priorities. 103 99 BinHeap(ItemIntMap &map, const Compare &comp) 104 100 : _iim(map), _comp(comp) {} 105 101 106 102 107 /// The number of items stored in the heap.108 /// 109 /// \brief Returns the number of items stored in the heap.103 /// \brief The number of items stored in the heap. 104 /// 105 /// This function returns the number of items stored in the heap. 110 106 int size() const { return _data.size(); } 111 107 112 /// \brief Check s if the heap stores no items.113 /// 114 /// Returns \c true if and only if the heap stores no items.108 /// \brief Check if the heap is empty. 109 /// 110 /// This function returns \c true if the heap is empty. 115 111 bool empty() const { return _data.empty(); } 116 112 117 /// \brief Make empty this heap. 118 /// 119 /// Make empty this heap. It does not change the cross reference map. 120 /// If you want to reuse what is not surely empty you should first clear 121 /// the heap and after that you should set the cross reference map for 122 /// each item to \c PRE_HEAP. 113 /// \brief Make the heap empty. 114 /// 115 /// This functon makes the heap empty. 116 /// It does not change the cross reference map. If you want to reuse 117 /// a heap that is not surely empty, you should first clear it and 118 /// then you should set the cross reference map to \c PRE_HEAP 119 /// for each item. 123 120 void clear() { 124 121 _data.clear(); … … 128 125 static int parent(int i) { return (i-1)/2; } 129 126 130 static int second _child(int i) { return 2*i+2; }127 static int secondChild(int i) { return 2*i+2; } 131 128 bool less(const Pair &p1, const Pair &p2) const { 132 129 return _comp(p1.second, p2.second); 133 130 } 134 131 135 int bubble _up(int hole, Pair p) {132 int bubbleUp(int hole, Pair p) { 136 133 int par = parent(hole); 137 134 while( hole>0 && less(p,_data[par]) ) { … … 144 141 } 145 142 146 int bubble _down(int hole, Pair p, int length) {147 int child = second _child(hole);143 int bubbleDown(int hole, Pair p, int length) { 144 int child = secondChild(hole); 148 145 while(child < length) { 149 146 if( less(_data[child-1], _data[child]) ) { … … 154 151 move(_data[child], hole); 155 152 hole = child; 156 child = second _child(hole);153 child = secondChild(hole); 157 154 } 158 155 child--; … … 172 169 173 170 public: 171 174 172 /// \brief Insert a pair of item and priority into the heap. 175 173 /// 176 /// Adds \c p.first to the heap with priority \c p.second. 174 /// This function inserts \c p.first to the heap with priority 175 /// \c p.second. 177 176 /// \param p The pair to insert. 177 /// \pre \c p.first must not be stored in the heap. 178 178 void push(const Pair &p) { 179 179 int n = _data.size(); 180 180 _data.resize(n+1); 181 bubble_up(n, p); 182 } 183 184 /// \brief Insert an item into the heap with the given heap. 185 /// 186 /// Adds \c i to the heap with priority \c p. 181 bubbleUp(n, p); 182 } 183 184 /// \brief Insert an item into the heap with the given priority. 185 /// 186 /// This function inserts the given item into the heap with the 187 /// given priority. 187 188 /// \param i The item to insert. 188 189 /// \param p The priority of the item. 190 /// \pre \e i must not be stored in the heap. 189 191 void push(const Item &i, const Prio &p) { push(Pair(i,p)); } 190 192 191 /// \brief Returns the item with minimum priority relative to \c Compare. 192 /// 193 /// This method returns the item with minimum priority relative to \c 194 /// Compare. 195 /// \pre The heap must be nonempty. 193 /// \brief Return the item having minimum priority. 194 /// 195 /// This function returns the item having minimum priority. 196 /// \pre The heap must be non-empty. 196 197 Item top() const { 197 198 return _data[0].first; 198 199 } 199 200 200 /// \brief Returns the minimum priority relative to \c Compare.201 /// 202 /// It returns the minimum priority relative to \c Compare.203 /// \pre The heap must be non empty.201 /// \brief The minimum priority. 202 /// 203 /// This function returns the minimum priority. 204 /// \pre The heap must be non-empty. 204 205 Prio prio() const { 205 206 return _data[0].second; 206 207 } 207 208 208 /// \brief Deletes the item with minimum priority relative to \c Compare. 209 /// 210 /// This method deletes the item with minimum priority relative to \c 211 /// Compare from the heap. 209 /// \brief Remove the item having minimum priority. 210 /// 211 /// This function removes the item having minimum priority. 212 212 /// \pre The heap must be non-empty. 213 213 void pop() { … … 215 215 _iim.set(_data[0].first, POST_HEAP); 216 216 if (n > 0) { 217 bubble _down(0, _data[n], n);217 bubbleDown(0, _data[n], n); 218 218 } 219 219 _data.pop_back(); 220 220 } 221 221 222 /// \brief Deletes \c i from the heap. 223 /// 224 /// This method deletes item \c i from the heap. 225 /// \param i The item to erase. 226 /// \pre The item should be in the heap. 222 /// \brief Remove the given item from the heap. 223 /// 224 /// This function removes the given item from the heap if it is 225 /// already stored. 226 /// \param i The item to delete. 227 /// \pre \e i must be in the heap. 227 228 void erase(const Item &i) { 228 229 int h = _iim[i]; … … 230 231 _iim.set(_data[h].first, POST_HEAP); 231 232 if( h < n ) { 232 if ( bubble _up(h, _data[n]) == h) {233 bubble _down(h, _data[n], n);233 if ( bubbleUp(h, _data[n]) == h) { 234 bubbleDown(h, _data[n], n); 234 235 } 235 236 } … … 237 238 } 238 239 239 240 /// \brief Returns the priority of \c i. 241 /// 242 /// This function returns the priority of item \c i. 243 /// \param i The item. 244 /// \pre \c i must be in the heap. 240 /// \brief The priority of the given item. 241 /// 242 /// This function returns the priority of the given item. 243 /// \param i The item. 244 /// \pre \e i must be in the heap. 245 245 Prio operator[](const Item &i) const { 246 246 int idx = _iim[i]; … … 248 248 } 249 249 250 /// \brief \c i gets to the heap with priority \c p independently 251 /// if \c i was already there. 252 /// 253 /// This method calls \ref push(\c i, \c p) if \c i is not stored 254 /// in the heap and sets the priority of \c i to \c p otherwise. 250 /// \brief Set the priority of an item or insert it, if it is 251 /// not stored in the heap. 252 /// 253 /// This method sets the priority of the given item if it is 254 /// already stored in the heap. Otherwise it inserts the given 255 /// item into the heap with the given priority. 255 256 /// \param i The item. 256 257 /// \param p The priority. … … 261 262 } 262 263 else if( _comp(p, _data[idx].second) ) { 263 bubble _up(idx, Pair(i,p));264 bubbleUp(idx, Pair(i,p)); 264 265 } 265 266 else { 266 bubble _down(idx, Pair(i,p), _data.size());267 } 268 } 269 270 /// \brief Decrease s the priority of \c i to \c p.271 /// 272 /// This method decreases the priority of item \c i to \c p.267 bubbleDown(idx, Pair(i,p), _data.size()); 268 } 269 } 270 271 /// \brief Decrease the priority of an item to the given value. 272 /// 273 /// This function decreases the priority of an item to the given value. 273 274 /// \param i The item. 274 275 /// \param p The priority. 275 /// \pre \c i must be stored in the heap with priority at least \c 276 /// p relative to \c Compare. 276 /// \pre \e i must be stored in the heap with priority at least \e p. 277 277 void decrease(const Item &i, const Prio &p) { 278 278 int idx = _iim[i]; 279 bubble _up(idx, Pair(i,p));280 } 281 282 /// \brief Increase s the priority of \c i to \c p.283 /// 284 /// This method sets the priority of item \c i to \c p.279 bubbleUp(idx, Pair(i,p)); 280 } 281 282 /// \brief Increase the priority of an item to the given value. 283 /// 284 /// This function increases the priority of an item to the given value. 285 285 /// \param i The item. 286 286 /// \param p The priority. 287 /// \pre \c i must be stored in the heap with priority at most \c 288 /// p relative to \c Compare. 287 /// \pre \e i must be stored in the heap with priority at most \e p. 289 288 void increase(const Item &i, const Prio &p) { 290 289 int idx = _iim[i]; 291 bubble _down(idx, Pair(i,p), _data.size());292 } 293 294 /// \brief Return s if \c item is in, has already been in, or has295 /// never been in the heap.296 /// 297 /// This method returns PRE_HEAP if \c item has never been in the298 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP299 /// otherwise. In the latter case it is possible that \c item will300 /// get backto the heap again.290 bubbleDown(idx, Pair(i,p), _data.size()); 291 } 292 293 /// \brief Return the state of an item. 294 /// 295 /// This method returns \c PRE_HEAP if the given item has never 296 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 297 /// and \c POST_HEAP otherwise. 298 /// In the latter case it is possible that the item will get back 299 /// to the heap again. 301 300 /// \param i The item. 302 301 State state(const Item &i) const { … … 307 306 } 308 307 309 /// \brief Set s the state of the \citem in the heap.310 /// 311 /// Sets the state of the \c item in the heap. It can be used to312 /// manually clear the heap when it is important to achive the313 /// better time complexity.308 /// \brief Set the state of an item in the heap. 309 /// 310 /// This function sets the state of the given item in the heap. 311 /// It can be used to manually clear the heap when it is important 312 /// to achive better time complexity. 314 313 /// \param i The item. 315 314 /// \param st The state. It should not be \c IN_HEAP. … … 328 327 } 329 328 330 /// \brief Replaces an item in the heap. 331 /// 332 /// The \c i item is replaced with \c j item. The \c i item should 333 /// be in the heap, while the \c j should be out of the heap. The 334 /// \c i item will out of the heap and \c j will be in the heap 335 /// with the same prioriority as prevoiusly the \c i item. 329 /// \brief Replace an item in the heap. 330 /// 331 /// This function replaces item \c i with item \c j. 332 /// Item \c i must be in the heap, while \c j must be out of the heap. 333 /// After calling this method, item \c i will be out of the 334 /// heap and \c j will be in the heap with the same prioriority 335 /// as item \c i had before. 336 336 void replace(const Item& i, const Item& j) { 337 337 int idx = _iim[i]; -
lemon/bucket_heap.h
r683 r711 20 20 #define LEMON_BUCKET_HEAP_H 21 21 22 ///\ingroup auxdat22 ///\ingroup heaps 23 23 ///\file 24 ///\brief Bucket Heap implementation.24 ///\brief Bucket heap implementation. 25 25 26 26 #include <vector> … … 54 54 } 55 55 56 /// \ingroup auxdat 57 /// 58 /// \brief A Bucket Heap implementation. 59 /// 60 /// This class implements the \e bucket \e heap data structure. A \e heap 61 /// is a data structure for storing items with specified values called \e 62 /// priorities in such a way that finding the item with minimum priority is 63 /// efficient. The bucket heap is very simple implementation, it can store 64 /// only integer priorities and it stores for each priority in the 65 /// \f$ [0..C) \f$ range a list of items. So it should be used only when 66 /// the priorities are small. It is not intended to use as dijkstra heap. 67 /// 68 /// \param IM A read and write Item int map, used internally 69 /// to handle the cross references. 70 /// \param MIN If the given parameter is false then instead of the 71 /// minimum value the maximum can be retrivied with the top() and 72 /// prio() member functions. 56 /// \ingroup heaps 57 /// 58 /// \brief Bucket heap data structure. 59 /// 60 /// This class implements the \e bucket \e heap data structure. 61 /// It practically conforms to the \ref concepts::Heap "heap concept", 62 /// but it has some limitations. 63 /// 64 /// The bucket heap is a very simple structure. It can store only 65 /// \c int priorities and it maintains a list of items for each priority 66 /// in the range <tt>[0..C)</tt>. So it should only be used when the 67 /// priorities are small. It is not intended to use as a Dijkstra heap. 68 /// 69 /// \tparam IM A read-writable item map with \c int values, used 70 /// internally to handle the cross references. 71 /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap. 72 /// The default is \e min-heap. If this parameter is set to \c false, 73 /// then the comparison is reversed, so the top(), prio() and pop() 74 /// functions deal with the item having maximum priority instead of the 75 /// minimum. 76 /// 77 /// \sa SimpleBucketHeap 73 78 template <typename IM, bool MIN = true> 74 79 class BucketHeap { 75 80 76 81 public: 77 /// \e 78 typedef typename IM::Key Item; 79 /// \e 82 83 /// Type of the item-int map. 84 typedef IM ItemIntMap; 85 /// Type of the priorities. 80 86 typedef int Prio; 81 /// \e82 typedef std::pair<Item, Prio> Pair;83 /// \e84 typedef IM ItemIntMap;87 /// Type of the items stored in the heap. 88 typedef typename ItemIntMap::Key Item; 89 /// Type of the item-priority pairs. 90 typedef std::pair<Item,Prio> Pair; 85 91 86 92 private: … … 90 96 public: 91 97 92 /// \brief Type to represent the items states.93 /// 94 /// Each Item element have a state associated to it. It maybe "in heap",95 /// "pre heap" or "postheap". The latter two are indifferent from the98 /// \brief Type to represent the states of the items. 99 /// 100 /// Each item has a state associated to it. It can be "in heap", 101 /// "pre-heap" or "post-heap". The latter two are indifferent from the 96 102 /// heap's point of view, but may be useful to the user. 97 103 /// … … 105 111 106 112 public: 107 /// \brief The constructor. 108 /// 109 /// The constructor. 110 /// \param map should be given to the constructor, since it is used 111 /// internally to handle the cross references. The value of the map 112 /// should be PRE_HEAP (-1) for each element. 113 114 /// \brief Constructor. 115 /// 116 /// Constructor. 117 /// \param map A map that assigns \c int values to the items. 118 /// It is used internally to handle the cross references. 119 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 113 120 explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {} 114 121 115 /// The number of items stored in the heap.116 /// 117 /// \brief Returns the number of items stored in the heap.122 /// \brief The number of items stored in the heap. 123 /// 124 /// This function returns the number of items stored in the heap. 118 125 int size() const { return _data.size(); } 119 126 120 /// \brief Check s if the heap stores no items.121 /// 122 /// Returns \c true if and only if the heap stores no items.127 /// \brief Check if the heap is empty. 128 /// 129 /// This function returns \c true if the heap is empty. 123 130 bool empty() const { return _data.empty(); } 124 131 125 /// \brief Make empty this heap. 126 /// 127 /// Make empty this heap. It does not change the cross reference 128 /// map. If you want to reuse a heap what is not surely empty you 129 /// should first clear the heap and after that you should set the 130 /// cross reference map for each item to \c PRE_HEAP. 132 /// \brief Make the heap empty. 133 /// 134 /// This functon makes the heap empty. 135 /// It does not change the cross reference map. If you want to reuse 136 /// a heap that is not surely empty, you should first clear it and 137 /// then you should set the cross reference map to \c PRE_HEAP 138 /// for each item. 131 139 void clear() { 132 140 _data.clear(); _first.clear(); _minimum = 0; … … 135 143 private: 136 144 137 void relocate _last(int idx) {145 void relocateLast(int idx) { 138 146 if (idx + 1 < int(_data.size())) { 139 147 _data[idx] = _data.back(); … … 175 183 176 184 public: 185 177 186 /// \brief Insert a pair of item and priority into the heap. 178 187 /// 179 /// Adds \c p.first to the heap with priority \c p.second. 188 /// This function inserts \c p.first to the heap with priority 189 /// \c p.second. 180 190 /// \param p The pair to insert. 191 /// \pre \c p.first must not be stored in the heap. 181 192 void push(const Pair& p) { 182 193 push(p.first, p.second); … … 185 196 /// \brief Insert an item into the heap with the given priority. 186 197 /// 187 /// Adds \c i to the heap with priority \c p. 198 /// This function inserts the given item into the heap with the 199 /// given priority. 188 200 /// \param i The item to insert. 189 201 /// \param p The priority of the item. 202 /// \pre \e i must not be stored in the heap. 190 203 void push(const Item &i, const Prio &p) { 191 204 int idx = _data.size(); … … 198 211 } 199 212 200 /// \brief Return s the item withminimum priority.201 /// 202 /// This method returns the item withminimum priority.203 /// \pre The heap must be non empty.213 /// \brief Return the item having minimum priority. 214 /// 215 /// This function returns the item having minimum priority. 216 /// \pre The heap must be non-empty. 204 217 Item top() const { 205 218 while (_first[_minimum] == -1) { … … 209 222 } 210 223 211 /// \brief Returns the minimum priority.212 /// 213 /// Itreturns the minimum priority.214 /// \pre The heap must be non empty.224 /// \brief The minimum priority. 225 /// 226 /// This function returns the minimum priority. 227 /// \pre The heap must be non-empty. 215 228 Prio prio() const { 216 229 while (_first[_minimum] == -1) { … … 220 233 } 221 234 222 /// \brief Deletes the item withminimum priority.223 /// 224 /// This method deletes the item with minimum priority from the heap.235 /// \brief Remove the item having minimum priority. 236 /// 237 /// This function removes the item having minimum priority. 225 238 /// \pre The heap must be non-empty. 226 239 void pop() { … … 231 244 _iim[_data[idx].item] = -2; 232 245 unlace(idx); 233 relocate_last(idx); 234 } 235 236 /// \brief Deletes \c i from the heap. 237 /// 238 /// This method deletes item \c i from the heap, if \c i was 239 /// already stored in the heap. 240 /// \param i The item to erase. 246 relocateLast(idx); 247 } 248 249 /// \brief Remove the given item from the heap. 250 /// 251 /// This function removes the given item from the heap if it is 252 /// already stored. 253 /// \param i The item to delete. 254 /// \pre \e i must be in the heap. 241 255 void erase(const Item &i) { 242 256 int idx = _iim[i]; 243 257 _iim[_data[idx].item] = -2; 244 258 unlace(idx); 245 relocate_last(idx); 246 } 247 248 249 /// \brief Returns the priority of \c i. 250 /// 251 /// This function returns the priority of item \c i. 252 /// \pre \c i must be in the heap. 253 /// \param i The item. 259 relocateLast(idx); 260 } 261 262 /// \brief The priority of the given item. 263 /// 264 /// This function returns the priority of the given item. 265 /// \param i The item. 266 /// \pre \e i must be in the heap. 254 267 Prio operator[](const Item &i) const { 255 268 int idx = _iim[i]; … … 257 270 } 258 271 259 /// \brief \c i gets to the heap with priority \c p independently 260 /// if \c i was already there. 261 /// 262 /// This method calls \ref push(\c i, \c p) if \c i is not stored 263 /// in the heap and sets the priority of \c i to \c p otherwise. 272 /// \brief Set the priority of an item or insert it, if it is 273 /// not stored in the heap. 274 /// 275 /// This method sets the priority of the given item if it is 276 /// already stored in the heap. Otherwise it inserts the given 277 /// item into the heap with the given priority. 264 278 /// \param i The item. 265 279 /// \param p The priority. … … 275 289 } 276 290 277 /// \brief Decreases the priority of \c i to \c p. 278 /// 279 /// This method decreases the priority of item \c i to \c p. 280 /// \pre \c i must be stored in the heap with priority at least \c 281 /// p relative to \c Compare. 291 /// \brief Decrease the priority of an item to the given value. 292 /// 293 /// This function decreases the priority of an item to the given value. 282 294 /// \param i The item. 283 295 /// \param p The priority. 296 /// \pre \e i must be stored in the heap with priority at least \e p. 284 297 void decrease(const Item &i, const Prio &p) { 285 298 int idx = _iim[i]; … … 292 305 } 293 306 294 /// \brief Increases the priority of \c i to \c p. 295 /// 296 /// This method sets the priority of item \c i to \c p. 297 /// \pre \c i must be stored in the heap with priority at most \c 298 /// p relative to \c Compare. 307 /// \brief Increase the priority of an item to the given value. 308 /// 309 /// This function increases the priority of an item to the given value. 299 310 /// \param i The item. 300 311 /// \param p The priority. 312 /// \pre \e i must be stored in the heap with priority at most \e p. 301 313 void increase(const Item &i, const Prio &p) { 302 314 int idx = _iim[i]; … … 306 318 } 307 319 308 /// \brief Return s if \c item is in, has already been in, or has309 /// never been in the heap.310 /// 311 /// This method returns PRE_HEAP if \c item has never been in the312 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP313 /// otherwise. In the latter case it is possible that \c item will314 /// get backto the heap again.320 /// \brief Return the state of an item. 321 /// 322 /// This method returns \c PRE_HEAP if the given item has never 323 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 324 /// and \c POST_HEAP otherwise. 325 /// In the latter case it is possible that the item will get back 326 /// to the heap again. 315 327 /// \param i The item. 316 328 State state(const Item &i) const { … … 320 332 } 321 333 322 /// \brief Set s the state of the \citem in the heap.323 /// 324 /// Sets the state of the \c item in the heap. It can be used to325 /// manually clear the heap when it is important to achive the326 /// better time complexity.334 /// \brief Set the state of an item in the heap. 335 /// 336 /// This function sets the state of the given item in the heap. 337 /// It can be used to manually clear the heap when it is important 338 /// to achive better time complexity. 327 339 /// \param i The item. 328 340 /// \param st The state. It should not be \c IN_HEAP. … … 360 372 }; // class BucketHeap 361 373 362 /// \ingroup auxdat363 /// 364 /// \brief A Simplified Bucket Heap implementation.374 /// \ingroup heaps 375 /// 376 /// \brief Simplified bucket heap data structure. 365 377 /// 366 378 /// This class implements a simplified \e bucket \e heap data 367 /// structure. It does not provide some functionality but it faster 368 /// and simplier data structure than the BucketHeap. The main 369 /// difference is that the BucketHeap stores for every key a double 370 /// linked list while this class stores just simple lists. In the 371 /// other way it does not support erasing each elements just the 372 /// minimal and it does not supports key increasing, decreasing. 373 /// 374 /// \param IM A read and write Item int map, used internally 375 /// to handle the cross references. 376 /// \param MIN If the given parameter is false then instead of the 377 /// minimum value the maximum can be retrivied with the top() and 378 /// prio() member functions. 379 /// structure. It does not provide some functionality, but it is 380 /// faster and simpler than BucketHeap. The main difference is 381 /// that BucketHeap stores a doubly-linked list for each key while 382 /// this class stores only simply-linked lists. It supports erasing 383 /// only for the item having minimum priority and it does not support 384 /// key increasing and decreasing. 385 /// 386 /// Note that this implementation does not conform to the 387 /// \ref concepts::Heap "heap concept" due to the lack of some 388 /// functionality. 389 /// 390 /// \tparam IM A read-writable item map with \c int values, used 391 /// internally to handle the cross references. 392 /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap. 393 /// The default is \e min-heap. If this parameter is set to \c false, 394 /// then the comparison is reversed, so the top(), prio() and pop() 395 /// functions deal with the item having maximum priority instead of the 396 /// minimum. 379 397 /// 380 398 /// \sa BucketHeap … … 383 401 384 402 public: 385 typedef typename IM::Key Item; 403 404 /// Type of the item-int map. 405 typedef IM ItemIntMap; 406 /// Type of the priorities. 386 407 typedef int Prio; 387 typedef std::pair<Item, Prio> Pair; 388 typedef IM ItemIntMap; 408 /// Type of the items stored in the heap. 409 typedef typename ItemIntMap::Key Item; 410 /// Type of the item-priority pairs. 411 typedef std::pair<Item,Prio> Pair; 389 412 390 413 private: … … 394 417 public: 395 418 396 /// \brief Type to represent the items states.397 /// 398 /// Each Item element have a state associated to it. It maybe "in heap",399 /// "pre heap" or "postheap". The latter two are indifferent from the419 /// \brief Type to represent the states of the items. 420 /// 421 /// Each item has a state associated to it. It can be "in heap", 422 /// "pre-heap" or "post-heap". The latter two are indifferent from the 400 423 /// heap's point of view, but may be useful to the user. 401 424 /// … … 410 433 public: 411 434 412 /// \brief The constructor.413 /// 414 /// The constructor.415 /// \param map should be given to the constructor, since it is used416 /// internally to handle the cross references. The value of the map417 /// should be PRE_HEAP (-1) for each element.435 /// \brief Constructor. 436 /// 437 /// Constructor. 438 /// \param map A map that assigns \c int values to the items. 439 /// It is used internally to handle the cross references. 440 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 418 441 explicit SimpleBucketHeap(ItemIntMap &map) 419 442 : _iim(map), _free(-1), _num(0), _minimum(0) {} 420 443 421 /// \brief Returns the number of items stored in the heap.422 /// 423 /// Th e number of items stored in the heap.444 /// \brief The number of items stored in the heap. 445 /// 446 /// This function returns the number of items stored in the heap. 424 447 int size() const { return _num; } 425 448 426 /// \brief Check s if the heap stores no items.427 /// 428 /// Returns \c true if and only if the heap stores no items.449 /// \brief Check if the heap is empty. 450 /// 451 /// This function returns \c true if the heap is empty. 429 452 bool empty() const { return _num == 0; } 430 453 431 /// \brief Make empty this heap. 432 /// 433 /// Make empty this heap. It does not change the cross reference 434 /// map. If you want to reuse a heap what is not surely empty you 435 /// should first clear the heap and after that you should set the 436 /// cross reference map for each item to \c PRE_HEAP. 454 /// \brief Make the heap empty. 455 /// 456 /// This functon makes the heap empty. 457 /// It does not change the cross reference map. If you want to reuse 458 /// a heap that is not surely empty, you should first clear it and 459 /// then you should set the cross reference map to \c PRE_HEAP 460 /// for each item. 437 461 void clear() { 438 462 _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0; … … 441 465 /// \brief Insert a pair of item and priority into the heap. 442 466 /// 443 /// Adds \c p.first to the heap with priority \c p.second. 467 /// This function inserts \c p.first to the heap with priority 468 /// \c p.second. 444 469 /// \param p The pair to insert. 470 /// \pre \c p.first must not be stored in the heap. 445 471 void push(const Pair& p) { 446 472 push(p.first, p.second); … … 449 475 /// \brief Insert an item into the heap with the given priority. 450 476 /// 451 /// Adds \c i to the heap with priority \c p. 477 /// This function inserts the given item into the heap with the 478 /// given priority. 452 479 /// \param i The item to insert. 453 480 /// \param p The priority of the item. 481 /// \pre \e i must not be stored in the heap. 454 482 void push(const Item &i, const Prio &p) { 455 483 int idx; … … 472 500 } 473 501 474 /// \brief Return s the item withminimum priority.475 /// 476 /// This method returns the item withminimum priority.477 /// \pre The heap must be non empty.502 /// \brief Return the item having minimum priority. 503 /// 504 /// This function returns the item having minimum priority. 505 /// \pre The heap must be non-empty. 478 506 Item top() const { 479 507 while (_first[_minimum] == -1) { … … 483 511 } 484 512 485 /// \brief Returns the minimum priority.486 /// 487 /// Itreturns the minimum priority.488 /// \pre The heap must be non empty.513 /// \brief The minimum priority. 514 /// 515 /// This function returns the minimum priority. 516 /// \pre The heap must be non-empty. 489 517 Prio prio() const { 490 518 while (_first[_minimum] == -1) { … … 494 522 } 495 523 496 /// \brief Deletes the item withminimum priority.497 /// 498 /// This method deletes the item with minimum priority from the heap.524 /// \brief Remove the item having minimum priority. 525 /// 526 /// This function removes the item having minimum priority. 499 527 /// \pre The heap must be non-empty. 500 528 void pop() { … … 510 538 } 511 539 512 /// \brief Returns the priority of \c i. 513 /// 514 /// This function returns the priority of item \c i. 515 /// \warning This operator is not a constant time function 516 /// because it scans the whole data structure to find the proper 517 /// value. 518 /// \pre \c i must be in the heap. 519 /// \param i The item. 540 /// \brief The priority of the given item. 541 /// 542 /// This function returns the priority of the given item. 543 /// \param i The item. 544 /// \pre \e i must be in the heap. 545 /// \warning This operator is not a constant time function because 546 /// it scans the whole data structure to find the proper value. 520 547 Prio operator[](const Item &i) const { 521 for (int k = 0; k < _first.size(); ++k) {548 for (int k = 0; k < int(_first.size()); ++k) { 522 549 int idx = _first[k]; 523 550 while (idx != -1) { … … 531 558 } 532 559 533 /// \brief Return s if \c item is in, has already been in, or has534 /// never been in the heap.535 /// 536 /// This method returns PRE_HEAP if \c item has never been in the537 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP538 /// otherwise. In the latter case it is possible that \c item will539 /// get backto the heap again.560 /// \brief Return the state of an item. 561 /// 562 /// This method returns \c PRE_HEAP if the given item has never 563 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 564 /// and \c POST_HEAP otherwise. 565 /// In the latter case it is possible that the item will get back 566 /// to the heap again. 540 567 /// \param i The item. 541 568 State state(const Item &i) const { -
lemon/concepts/heap.h
r584 r710 17 17 */ 18 18 19 #ifndef LEMON_CONCEPTS_HEAP_H 20 #define LEMON_CONCEPTS_HEAP_H 21 19 22 ///\ingroup concept 20 23 ///\file 21 24 ///\brief The concept of heaps. 22 25 23 #ifndef LEMON_CONCEPTS_HEAP_H24 #define LEMON_CONCEPTS_HEAP_H25 26 26 #include <lemon/core.h> 27 27 #include <lemon/concept_check.h> … … 36 36 /// \brief The heap concept. 37 37 /// 38 /// Concept class describing the main interface of heaps. A \e heap 39 /// is a data structure for storing items with specified values called 40 /// \e priorities in such a way that finding the item with minimum 41 /// priority is efficient. In a heap one can change the priority of an 42 /// item, add or erase an item, etc. 38 /// This concept class describes the main interface of heaps. 39 /// The various \ref heaps "heap structures" are efficient 40 /// implementations of the abstract data type \e priority \e queue. 41 /// They store items with specified values called \e priorities 42 /// in such a way that finding and removing the item with minimum 43 /// priority are efficient. The basic operations are adding and 44 /// erasing items, changing the priority of an item, etc. 43 45 /// 44 /// \tparam PR Type of the priority of the items. 45 /// \tparam IM A read and writable item map with int values, used 46 /// Heaps are crucial in several algorithms, such as Dijkstra and Prim. 47 /// Any class that conforms to this concept can be used easily in such 48 /// algorithms. 49 /// 50 /// \tparam PR Type of the priorities of the items. 51 /// \tparam IM A read-writable item map with \c int values, used 46 52 /// internally to handle the cross references. 47 /// \tparam C omp A functor class for the ordering ofthe priorities.53 /// \tparam CMP A functor class for comparing the priorities. 48 54 /// The default is \c std::less<PR>. 49 55 #ifdef DOXYGEN 50 template <typename PR, typename IM, typename C omp = std::less<PR>>56 template <typename PR, typename IM, typename CMP> 51 57 #else 52 template <typename PR, typename IM >58 template <typename PR, typename IM, typename CMP = std::less<PR> > 53 59 #endif 54 60 class Heap { … … 65 71 /// 66 72 /// Each item has a state associated to it. It can be "in heap", 67 /// "pre heap" or "post heap". The later two are indifferent 68 /// from the point of view of the heap, but may be useful for 69 /// the user. 73 /// "pre-heap" or "post-heap". The latter two are indifferent from the 74 /// heap's point of view, but may be useful to the user. 70 75 /// 71 76 /// The item-int map must be initialized in such way that it assigns … … 73 78 enum State { 74 79 IN_HEAP = 0, ///< = 0. The "in heap" state constant. 75 PRE_HEAP = -1, ///< = -1. The "pre 76 POST_HEAP = -2 ///< = -2. The "post 80 PRE_HEAP = -1, ///< = -1. The "pre-heap" state constant. 81 POST_HEAP = -2 ///< = -2. The "post-heap" state constant. 77 82 }; 78 83 79 /// \brief The constructor.80 /// 81 /// The constructor.84 /// \brief Constructor. 85 /// 86 /// Constructor. 82 87 /// \param map A map that assigns \c int values to keys of type 83 88 /// \c Item. It is used internally by the heap implementations to 84 89 /// handle the cross references. The assigned value must be 85 /// \c PRE_HEAP (<tt>-1</tt>) for e veryitem.90 /// \c PRE_HEAP (<tt>-1</tt>) for each item. 86 91 explicit Heap(ItemIntMap &map) {} 87 92 93 /// \brief Constructor. 94 /// 95 /// Constructor. 96 /// \param map A map that assigns \c int values to keys of type 97 /// \c Item. It is used internally by the heap implementations to 98 /// handle the cross references. The assigned value must be 99 /// \c PRE_HEAP (<tt>-1</tt>) for each item. 100 /// \param comp The function object used for comparing the priorities. 101 explicit Heap(ItemIntMap &map, const CMP &comp) {} 102 88 103 /// \brief The number of items stored in the heap. 89 104 /// 90 /// Returns the number of items stored in the heap.105 /// This function returns the number of items stored in the heap. 91 106 int size() const { return 0; } 92 107 93 /// \brief Check sif the heap is empty.94 /// 95 /// Returns \c true if the heap is empty.108 /// \brief Check if the heap is empty. 109 /// 110 /// This function returns \c true if the heap is empty. 96 111 bool empty() const { return false; } 97 112 98 /// \brief Makes the heap empty. 99 /// 100 /// Makes the heap empty. 101 void clear(); 102 103 /// \brief Inserts an item into the heap with the given priority. 104 /// 105 /// Inserts the given item into the heap with the given priority. 113 /// \brief Make the heap empty. 114 /// 115 /// This functon makes the heap empty. 116 /// It does not change the cross reference map. If you want to reuse 117 /// a heap that is not surely empty, you should first clear it and 118 /// then you should set the cross reference map to \c PRE_HEAP 119 /// for each item. 120 void clear() {} 121 122 /// \brief Insert an item into the heap with the given priority. 123 /// 124 /// This function inserts the given item into the heap with the 125 /// given priority. 106 126 /// \param i The item to insert. 107 127 /// \param p The priority of the item. 128 /// \pre \e i must not be stored in the heap. 108 129 void push(const Item &i, const Prio &p) {} 109 130 110 /// \brief Return sthe item having minimum priority.111 /// 112 /// Returns the item having minimum priority.131 /// \brief Return the item having minimum priority. 132 /// 133 /// This function returns the item having minimum priority. 113 134 /// \pre The heap must be non-empty. 114 135 Item top() const {} … … 116 137 /// \brief The minimum priority. 117 138 /// 118 /// Returns the minimum priority.139 /// This function returns the minimum priority. 119 140 /// \pre The heap must be non-empty. 120 141 Prio prio() const {} 121 142 122 /// \brief Remove sthe item having minimum priority.123 /// 124 /// Removes the item having minimum priority.143 /// \brief Remove the item having minimum priority. 144 /// 145 /// This function removes the item having minimum priority. 125 146 /// \pre The heap must be non-empty. 126 147 void pop() {} 127 148 128 /// \brief Removes an item from the heap. 129 /// 130 /// Removes the given item from the heap if it is already stored. 149 /// \brief Remove the given item from the heap. 150 /// 151 /// This function removes the given item from the heap if it is 152 /// already stored. 131 153 /// \param i The item to delete. 154 /// \pre \e i must be in the heap. 132 155 void erase(const Item &i) {} 133 156 134 /// \brief The priority of an item.135 /// 136 /// Returns the priority of the given item.137 /// \param i The item. 138 /// \pre \ ci must be in the heap.157 /// \brief The priority of the given item. 158 /// 159 /// This function returns the priority of the given item. 160 /// \param i The item. 161 /// \pre \e i must be in the heap. 139 162 Prio operator[](const Item &i) const {} 140 163 141 /// \brief Set s the priority of an item or insertsit, if it is164 /// \brief Set the priority of an item or insert it, if it is 142 165 /// not stored in the heap. 143 166 /// 144 167 /// This method sets the priority of the given item if it is 145 /// already stored in the heap. 146 /// Otherwise it inserts the given itemwith the given priority.168 /// already stored in the heap. Otherwise it inserts the given 169 /// item into the heap with the given priority. 147 170 /// 148 171 /// \param i The item. … … 150 173 void set(const Item &i, const Prio &p) {} 151 174 152 /// \brief Decrease sthe priority of an item to the given value.153 /// 154 /// Decreases the priority of an item to the given value.175 /// \brief Decrease the priority of an item to the given value. 176 /// 177 /// This function decreases the priority of an item to the given value. 155 178 /// \param i The item. 156 179 /// \param p The priority. 157 /// \pre \ c i must be stored in the heap with priority at least \cp.180 /// \pre \e i must be stored in the heap with priority at least \e p. 158 181 void decrease(const Item &i, const Prio &p) {} 159 182 160 /// \brief Increase sthe priority of an item to the given value.161 /// 162 /// Increases the priority of an item to the given value.183 /// \brief Increase the priority of an item to the given value. 184 /// 185 /// This function increases the priority of an item to the given value. 163 186 /// \param i The item. 164 187 /// \param p The priority. 165 /// \pre \ c i must be stored in the heap with priority at most \cp.188 /// \pre \e i must be stored in the heap with priority at most \e p. 166 189 void increase(const Item &i, const Prio &p) {} 167 190 168 /// \brief Returns if an item is in, has already been in, or has 169 /// never been in the heap. 191 /// \brief Return the state of an item. 170 192 /// 171 193 /// This method returns \c PRE_HEAP if the given item has never … … 177 199 State state(const Item &i) const {} 178 200 179 /// \brief Set sthe state of an item in the heap.180 /// 181 /// Sets the state of the given item in the heap. It can be used182 /// to manually clear the heap when it is important to achive the183 /// better time complexity.201 /// \brief Set the state of an item in the heap. 202 /// 203 /// This function sets the state of the given item in the heap. 204 /// It can be used to manually clear the heap when it is important 205 /// to achive better time complexity. 184 206 /// \param i The item. 185 207 /// \param st The state. It should not be \c IN_HEAP. -
lemon/fib_heap.h
r683 r711 21 21 22 22 ///\file 23 ///\ingroup auxdat24 ///\brief Fibonacci Heap implementation.23 ///\ingroup heaps 24 ///\brief Fibonacci heap implementation. 25 25 26 26 #include <vector> 27 #include <utility> 27 28 #include <functional> 28 29 #include <lemon/math.h> … … 30 31 namespace lemon { 31 32 32 /// \ingroup auxdat33 /// \ingroup heaps 33 34 /// 34 /// \brief Fibonacci Heap.35 /// \brief Fibonacci heap data structure. 35 36 /// 36 ///This class implements the \e Fibonacci \e heap data structure. A \e heap 37 ///is a data structure for storing items with specified values called \e 38 ///priorities in such a way that finding the item with minimum priority is 39 ///efficient. \c CMP specifies the ordering of the priorities. In a heap 40 ///one can change the priority of an item, add or erase an item, etc. 37 /// This class implements the \e Fibonacci \e heap data structure. 38 /// It fully conforms to the \ref concepts::Heap "heap concept". 41 39 /// 42 /// The methods \ref increase and \ref erase are not efficient in a Fibonacci43 /// heap. In case of many calls to these operations, it is better to use a44 /// \ref BinHeap "binary heap".40 /// The methods \ref increase() and \ref erase() are not efficient in a 41 /// Fibonacci heap. In case of many calls of these operations, it is 42 /// better to use other heap structure, e.g. \ref BinHeap "binary heap". 45 43 /// 46 ///\param PRIO Type of the priority of the items. 47 ///\param IM A read and writable Item int map, used internally 48 ///to handle the cross references. 49 ///\param CMP A class for the ordering of the priorities. The 50 ///default is \c std::less<PRIO>. 51 /// 52 ///\sa BinHeap 53 ///\sa Dijkstra 44 /// \tparam PR Type of the priorities of the items. 45 /// \tparam IM A read-writable item map with \c int values, used 46 /// internally to handle the cross references. 47 /// \tparam CMP A functor class for comparing the priorities. 48 /// The default is \c std::less<PR>. 54 49 #ifdef DOXYGEN 55 template <typename PR IO, typename IM, typename CMP>50 template <typename PR, typename IM, typename CMP> 56 51 #else 57 template <typename PR IO, typename IM, typename CMP = std::less<PRIO> >52 template <typename PR, typename IM, typename CMP = std::less<PR> > 58 53 #endif 59 54 class FibHeap { 60 55 public: 61 ///\e 56 57 /// Type of the item-int map. 62 58 typedef IM ItemIntMap; 63 /// \e64 typedef PR IOPrio;65 /// \e59 /// Type of the priorities. 60 typedef PR Prio; 61 /// Type of the items stored in the heap. 66 62 typedef typename ItemIntMap::Key Item; 67 /// \e63 /// Type of the item-priority pairs. 68 64 typedef std::pair<Item,Prio> Pair; 69 /// \e65 /// Functor type for comparing the priorities. 70 66 typedef CMP Compare; 71 67 … … 81 77 public: 82 78 83 /// \brief Type to represent the items states.84 /// 85 /// Each Item element have a state associated to it. It maybe "in heap",86 /// "pre heap" or "postheap". The latter two are indifferent from the79 /// \brief Type to represent the states of the items. 80 /// 81 /// Each item has a state associated to it. It can be "in heap", 82 /// "pre-heap" or "post-heap". The latter two are indifferent from the 87 83 /// heap's point of view, but may be useful to the user. 88 84 /// … … 95 91 }; 96 92 97 /// \brief The constructor 98 /// 99 /// \c map should be given to the constructor, since it is 100 /// used internally to handle the cross references. 93 /// \brief Constructor. 94 /// 95 /// Constructor. 96 /// \param map A map that assigns \c int values to the items. 97 /// It is used internally to handle the cross references. 98 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 101 99 explicit FibHeap(ItemIntMap &map) 102 100 : _minimum(0), _iim(map), _num() {} 103 101 104 /// \brief The constructor 105 /// 106 /// \c map should be given to the constructor, since it is used 107 /// internally to handle the cross references. \c comp is an 108 /// object for ordering of the priorities. 102 /// \brief Constructor. 103 /// 104 /// Constructor. 105 /// \param map A map that assigns \c int values to the items. 106 /// It is used internally to handle the cross references. 107 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 108 /// \param comp The function object used for comparing the priorities. 109 109 FibHeap(ItemIntMap &map, const Compare &comp) 110 110 : _minimum(0), _iim(map), _comp(comp), _num() {} … … 112 112 /// \brief The number of items stored in the heap. 113 113 /// 114 /// Returns the number of items stored in the heap.114 /// This function returns the number of items stored in the heap. 115 115 int size() const { return _num; } 116 116 117 /// \brief Check s if the heap stores no items.118 /// 119 /// Returns \c true if and only if the heap stores no items.117 /// \brief Check if the heap is empty. 118 /// 119 /// This function returns \c true if the heap is empty. 120 120 bool empty() const { return _num==0; } 121 121 122 /// \brief Make empty this heap. 123 /// 124 /// Make empty this heap. It does not change the cross reference 125 /// map. If you want to reuse a heap what is not surely empty you 126 /// should first clear the heap and after that you should set the 127 /// cross reference map for each item to \c PRE_HEAP. 122 /// \brief Make the heap empty. 123 /// 124 /// This functon makes the heap empty. 125 /// It does not change the cross reference map. If you want to reuse 126 /// a heap that is not surely empty, you should first clear it and 127 /// then you should set the cross reference map to \c PRE_HEAP 128 /// for each item. 128 129 void clear() { 129 130 _data.clear(); _minimum = 0; _num = 0; 130 131 } 131 132 132 /// \brief \c item gets to the heap with priority \c value independently 133 /// if \c item was already there. 134 /// 135 /// This method calls \ref push(\c item, \c value) if \c item is not 136 /// stored in the heap and it calls \ref decrease(\c item, \c value) or 137 /// \ref increase(\c item, \c value) otherwise. 138 void set (const Item& item, const Prio& value) { 139 int i=_iim[item]; 140 if ( i >= 0 && _data[i].in ) { 141 if ( _comp(value, _data[i].prio) ) decrease(item, value); 142 if ( _comp(_data[i].prio, value) ) increase(item, value); 143 } else push(item, value); 144 } 145 146 /// \brief Adds \c item to the heap with priority \c value. 147 /// 148 /// Adds \c item to the heap with priority \c value. 149 /// \pre \c item must not be stored in the heap. 150 void push (const Item& item, const Prio& value) { 133 /// \brief Insert an item into the heap with the given priority. 134 /// 135 /// This function inserts the given item into the heap with the 136 /// given priority. 137 /// \param item The item to insert. 138 /// \param prio The priority of the item. 139 /// \pre \e item must not be stored in the heap. 140 void push (const Item& item, const Prio& prio) { 151 141 int i=_iim[item]; 152 142 if ( i < 0 ) { … … 169 159 _data[_minimum].right_neighbor=i; 170 160 _data[i].left_neighbor=_minimum; 171 if ( _comp( value, _data[_minimum].prio) ) _minimum=i;161 if ( _comp( prio, _data[_minimum].prio) ) _minimum=i; 172 162 } else { 173 163 _data[i].right_neighbor=_data[i].left_neighbor=i; 174 164 _minimum=i; 175 165 } 176 _data[i].prio= value;166 _data[i].prio=prio; 177 167 ++_num; 178 168 } 179 169 180 /// \brief Returns the item with minimum priority relative to \c Compare. 181 /// 182 /// This method returns the item with minimum priority relative to \c 183 /// Compare. 184 /// \pre The heap must be nonempty. 170 /// \brief Return the item having minimum priority. 171 /// 172 /// This function returns the item having minimum priority. 173 /// \pre The heap must be non-empty. 185 174 Item top() const { return _data[_minimum].name; } 186 175 187 /// \brief Returns the minimum priority relative to \c Compare. 188 /// 189 /// It returns the minimum priority relative to \c Compare. 190 /// \pre The heap must be nonempty. 191 const Prio& prio() const { return _data[_minimum].prio; } 192 193 /// \brief Returns the priority of \c item. 194 /// 195 /// It returns the priority of \c item. 196 /// \pre \c item must be in the heap. 197 const Prio& operator[](const Item& item) const { 198 return _data[_iim[item]].prio; 199 } 200 201 /// \brief Deletes the item with minimum priority relative to \c Compare. 202 /// 203 /// This method deletes the item with minimum priority relative to \c 204 /// Compare from the heap. 176 /// \brief The minimum priority. 177 /// 178 /// This function returns the minimum priority. 179 /// \pre The heap must be non-empty. 180 Prio prio() const { return _data[_minimum].prio; } 181 182 /// \brief Remove the item having minimum priority. 183 /// 184 /// This function removes the item having minimum priority. 205 185 /// \pre The heap must be non-empty. 206 186 void pop() { … … 209 189 _data[_minimum].in=false; 210 190 if ( _data[_minimum].degree!=0 ) { 211 make root(_data[_minimum].child);191 makeRoot(_data[_minimum].child); 212 192 _minimum=_data[_minimum].child; 213 193 balance(); … … 222 202 int last_child=_data[child].left_neighbor; 223 203 224 make root(child);204 makeRoot(child); 225 205 226 206 _data[left].right_neighbor=child; … … 235 215 } 236 216 237 /// \brief Deletes \c item from the heap. 238 /// 239 /// This method deletes \c item from the heap, if \c item was already 240 /// stored in the heap. It is quite inefficient in Fibonacci heaps. 217 /// \brief Remove the given item from the heap. 218 /// 219 /// This function removes the given item from the heap if it is 220 /// already stored. 221 /// \param item The item to delete. 222 /// \pre \e item must be in the heap. 241 223 void erase (const Item& item) { 242 224 int i=_iim[item]; … … 253 235 } 254 236 255 /// \brief Decreases the priority of \c item to \c value. 256 /// 257 /// This method decreases the priority of \c item to \c value. 258 /// \pre \c item must be stored in the heap with priority at least \c 259 /// value relative to \c Compare. 260 void decrease (Item item, const Prio& value) { 237 /// \brief The priority of the given item. 238 /// 239 /// This function returns the priority of the given item. 240 /// \param item The item. 241 /// \pre \e item must be in the heap. 242 Prio operator[](const Item& item) const { 243 return _data[_iim[item]].prio; 244 } 245 246 /// \brief Set the priority of an item or insert it, if it is 247 /// not stored in the heap. 248 /// 249 /// This method sets the priority of the given item if it is 250 /// already stored in the heap. Otherwise it inserts the given 251 /// item into the heap with the given priority. 252 /// \param item The item. 253 /// \param prio The priority. 254 void set (const Item& item, const Prio& prio) { 261 255 int i=_iim[item]; 262 _data[i].prio=value; 256 if ( i >= 0 && _data[i].in ) { 257 if ( _comp(prio, _data[i].prio) ) decrease(item, prio); 258 if ( _comp(_data[i].prio, prio) ) increase(item, prio); 259 } else push(item, prio); 260 } 261 262 /// \brief Decrease the priority of an item to the given value. 263 /// 264 /// This function decreases the priority of an item to the given value. 265 /// \param item The item. 266 /// \param prio The priority. 267 /// \pre \e item must be stored in the heap with priority at least \e prio. 268 void decrease (const Item& item, const Prio& prio) { 269 int i=_iim[item]; 270 _data[i].prio=prio; 263 271 int p=_data[i].parent; 264 272 265 if ( p!=-1 && _comp( value, _data[p].prio) ) {273 if ( p!=-1 && _comp(prio, _data[p].prio) ) { 266 274 cut(i,p); 267 275 cascade(p); 268 276 } 269 if ( _comp(value, _data[_minimum].prio) ) _minimum=i; 270 } 271 272 /// \brief Increases the priority of \c item to \c value. 273 /// 274 /// This method sets the priority of \c item to \c value. Though 275 /// there is no precondition on the priority of \c item, this 276 /// method should be used only if it is indeed necessary to increase 277 /// (relative to \c Compare) the priority of \c item, because this 278 /// method is inefficient. 279 void increase (Item item, const Prio& value) { 277 if ( _comp(prio, _data[_minimum].prio) ) _minimum=i; 278 } 279 280 /// \brief Increase the priority of an item to the given value. 281 /// 282 /// This function increases the priority of an item to the given value. 283 /// \param item The item. 284 /// \param prio The priority. 285 /// \pre \e item must be stored in the heap with priority at most \e prio. 286 void increase (const Item& item, const Prio& prio) { 280 287 erase(item); 281 push(item, value);282 } 283 284 285 /// \brief Returns if \c item is in, has already been in, or has never286 /// been in the heap.287 /// 288 /// This method returns PRE_HEAP if \c item has never been in the289 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP290 /// otherwise. In the latter case it is possible that \c item will291 /// get back to the heap again.288 push(item, prio); 289 } 290 291 /// \brief Return the state of an item. 292 /// 293 /// This method returns \c PRE_HEAP if the given item has never 294 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 295 /// and \c POST_HEAP otherwise. 296 /// In the latter case it is possible that the item will get back 297 /// to the heap again. 298 /// \param item The item. 292 299 State state(const Item &item) const { 293 300 int i=_iim[item]; … … 299 306 } 300 307 301 /// \brief Set s the state of the \citem in the heap.302 /// 303 /// Sets the state of the \c item in the heap. It can be used to304 /// manually clear the heap when it is important to achive the305 /// better time _complexity.308 /// \brief Set the state of an item in the heap. 309 /// 310 /// This function sets the state of the given item in the heap. 311 /// It can be used to manually clear the heap when it is important 312 /// to achive better time complexity. 306 313 /// \param i The item. 307 314 /// \param st The state. It should not be \c IN_HEAP. … … 366 373 } 367 374 368 void make root(int c) {375 void makeRoot(int c) { 369 376 int s=c; 370 377 do { -
lemon/radix_heap.h
r683 r711 20 20 #define LEMON_RADIX_HEAP_H 21 21 22 ///\ingroup auxdat22 ///\ingroup heaps 23 23 ///\file 24 ///\brief Radix Heap implementation.24 ///\brief Radix heap implementation. 25 25 26 26 #include <vector> … … 30 30 31 31 32 /// \ingroup auxdata32 /// \ingroup heaps 33 33 /// 34 /// \brief A Radix Heap implementation.34 /// \brief Radix heap data structure. 35 35 /// 36 /// This class implements the \e radix \e heap data structure. A \e heap 37 /// is a data structure for storing items with specified values called \e 38 /// priorities in such a way that finding the item with minimum priority is 39 /// efficient. This heap type can store only items with \e int priority. 40 /// In a heap one can change the priority of an item, add or erase an 41 /// item, but the priority cannot be decreased under the last removed 42 /// item's priority. 36 /// This class implements the \e radix \e heap data structure. 37 /// It practically conforms to the \ref concepts::Heap "heap concept", 38 /// but it has some limitations due its special implementation. 39 /// The type of the priorities must be \c int and the priority of an 40 /// item cannot be decreased under the priority of the last removed item. 43 41 /// 44 /// \param IM A read and writable Item int map, used internally 45 /// to handle the cross references. 46 /// 47 /// \see BinHeap 48 /// \see Dijkstra 42 /// \tparam IM A read-writable item map with \c int values, used 43 /// internally to handle the cross references. 49 44 template <typename IM> 50 45 class RadixHeap { 51 46 52 47 public: 53 typedef typename IM::Key Item; 48 49 /// Type of the item-int map. 50 typedef IM ItemIntMap; 51 /// Type of the priorities. 54 52 typedef int Prio; 55 typedef IM ItemIntMap; 53 /// Type of the items stored in the heap. 54 typedef typename ItemIntMap::Key Item; 56 55 57 56 /// \brief Exception thrown by RadixHeap. 58 57 /// 59 /// This Exception is thrown when a smaller priority60 /// is inserted into the \e RadixHeap then the last time erased.58 /// This exception is thrown when an item is inserted into a 59 /// RadixHeap with a priority smaller than the last erased one. 61 60 /// \see RadixHeap 62 63 class UnderFlowPriorityError : public Exception { 61 class PriorityUnderflowError : public Exception { 64 62 public: 65 63 virtual const char* what() const throw() { 66 return "lemon::RadixHeap:: UnderFlowPriorityError";64 return "lemon::RadixHeap::PriorityUnderflowError"; 67 65 } 68 66 }; 69 67 70 /// \brief Type to represent the items states.71 /// 72 /// Each Item element have a state associated to it. It maybe "in heap",73 /// "pre heap" or "postheap". The latter two are indifferent from the68 /// \brief Type to represent the states of the items. 69 /// 70 /// Each item has a state associated to it. It can be "in heap", 71 /// "pre-heap" or "post-heap". The latter two are indifferent from the 74 72 /// heap's point of view, but may be useful to the user. 75 73 /// 76 /// The ItemIntMap \e should be initialized in such way that it maps77 /// PRE_HEAP (-1) to any element to be put in the heap...74 /// The item-int map must be initialized in such way that it assigns 75 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. 78 76 enum State { 79 IN_HEAP = 0, 80 PRE_HEAP = -1, 81 POST_HEAP = -2 77 IN_HEAP = 0, ///< = 0. 78 PRE_HEAP = -1, ///< = -1. 79 POST_HEAP = -2 ///< = -2. 82 80 }; 83 81 … … 97 95 }; 98 96 99 std::vector<RadixItem> data;100 std::vector<RadixBox> boxes;97 std::vector<RadixItem> _data; 98 std::vector<RadixBox> _boxes; 101 99 102 100 ItemIntMap &_iim; 103 101 104 105 102 public: 106 /// \brief The constructor. 107 /// 108 /// The constructor.109 /// 110 /// \param map It should be given to the constructor, since it is used111 /// internally to handle the cross references. The value of the map112 /// should be PRE_HEAP (-1) for each element.113 /// 114 /// \param minimal The initial minimal valueof the heap.115 /// \param capacity It determines the initial capacity of the heap.116 RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)117 : _iim(map){118 boxes.push_back(RadixBox(minimal, 1));119 boxes.push_back(RadixBox(minimal+ 1, 1));120 while (lower( boxes.size() - 1, capacity + minimal- 1)) {103 104 /// \brief Constructor. 105 /// 106 /// Constructor. 107 /// \param map A map that assigns \c int values to the items. 108 /// It is used internally to handle the cross references. 109 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 110 /// \param minimum The initial minimum value of the heap. 111 /// \param capacity The initial capacity of the heap. 112 RadixHeap(ItemIntMap &map, int minimum = 0, int capacity = 0) 113 : _iim(map) 114 { 115 _boxes.push_back(RadixBox(minimum, 1)); 116 _boxes.push_back(RadixBox(minimum + 1, 1)); 117 while (lower(_boxes.size() - 1, capacity + minimum - 1)) { 121 118 extend(); 122 119 } 123 120 } 124 121 125 /// The number of items stored in the heap. 126 /// 127 /// \brief Returns the number of items stored in the heap. 128 int size() const { return data.size(); } 129 /// \brief Checks if the heap stores no items. 130 /// 131 /// Returns \c true if and only if the heap stores no items. 132 bool empty() const { return data.empty(); } 133 134 /// \brief Make empty this heap. 135 /// 136 /// Make empty this heap. It does not change the cross reference 137 /// map. If you want to reuse a heap what is not surely empty you 138 /// should first clear the heap and after that you should set the 139 /// cross reference map for each item to \c PRE_HEAP. 140 void clear(int minimal = 0, int capacity = 0) { 141 data.clear(); boxes.clear(); 142 boxes.push_back(RadixBox(minimal, 1)); 143 boxes.push_back(RadixBox(minimal + 1, 1)); 144 while (lower(boxes.size() - 1, capacity + minimal - 1)) { 122 /// \brief The number of items stored in the heap. 123 /// 124 /// This function returns the number of items stored in the heap. 125 int size() const { return _data.size(); } 126 127 /// \brief Check if the heap is empty. 128 /// 129 /// This function returns \c true if the heap is empty. 130 bool empty() const { return _data.empty(); } 131 132 /// \brief Make the heap empty. 133 /// 134 /// This functon makes the heap empty. 135 /// It does not change the cross reference map. If you want to reuse 136 /// a heap that is not surely empty, you should first clear it and 137 /// then you should set the cross reference map to \c PRE_HEAP 138 /// for each item. 139 /// \param minimum The minimum value of the heap. 140 /// \param capacity The capacity of the heap. 141 void clear(int minimum = 0, int capacity = 0) { 142 _data.clear(); _boxes.clear(); 143 _boxes.push_back(RadixBox(minimum, 1)); 144 _boxes.push_back(RadixBox(minimum + 1, 1)); 145 while (lower(_boxes.size() - 1, capacity + minimum - 1)) { 145 146 extend(); 146 147 } … … 150 151 151 152 bool upper(int box, Prio pr) { 152 return pr < boxes[box].min;153 return pr < _boxes[box].min; 153 154 } 154 155 155 156 bool lower(int box, Prio pr) { 156 return pr >= boxes[box].min +boxes[box].size;157 } 158 159 // / \brief Remove item from the box list.157 return pr >= _boxes[box].min + _boxes[box].size; 158 } 159 160 // Remove item from the box list 160 161 void remove(int index) { 161 if ( data[index].prev >= 0) {162 data[data[index].prev].next =data[index].next;162 if (_data[index].prev >= 0) { 163 _data[_data[index].prev].next = _data[index].next; 163 164 } else { 164 boxes[data[index].box].first =data[index].next;165 } 166 if ( data[index].next >= 0) {167 data[data[index].next].prev =data[index].prev;168 } 169 } 170 171 // / \brief Insert item into the box list.165 _boxes[_data[index].box].first = _data[index].next; 166 } 167 if (_data[index].next >= 0) { 168 _data[_data[index].next].prev = _data[index].prev; 169 } 170 } 171 172 // Insert item into the box list 172 173 void insert(int box, int index) { 173 if ( boxes[box].first == -1) {174 boxes[box].first = index;175 data[index].next =data[index].prev = -1;174 if (_boxes[box].first == -1) { 175 _boxes[box].first = index; 176 _data[index].next = _data[index].prev = -1; 176 177 } else { 177 data[index].next =boxes[box].first;178 data[boxes[box].first].prev = index;179 data[index].prev = -1;180 boxes[box].first = index;181 } 182 data[index].box = box;183 } 184 185 // / \brief Add a new box to the box list.178 _data[index].next = _boxes[box].first; 179 _data[_boxes[box].first].prev = index; 180 _data[index].prev = -1; 181 _boxes[box].first = index; 182 } 183 _data[index].box = box; 184 } 185 186 // Add a new box to the box list 186 187 void extend() { 187 int min = boxes.back().min +boxes.back().size;188 int bs = 2 * boxes.back().size;189 boxes.push_back(RadixBox(min, bs));190 } 191 192 // / \briefMove an item up into the proper box.193 void bubble _up(int index) {194 if (!lower( data[index].box,data[index].prio)) return;188 int min = _boxes.back().min + _boxes.back().size; 189 int bs = 2 * _boxes.back().size; 190 _boxes.push_back(RadixBox(min, bs)); 191 } 192 193 // Move an item up into the proper box. 194 void bubbleUp(int index) { 195 if (!lower(_data[index].box, _data[index].prio)) return; 195 196 remove(index); 196 int box = findUp( data[index].box,data[index].prio);197 int box = findUp(_data[index].box, _data[index].prio); 197 198 insert(box, index); 198 199 } 199 200 200 // / \brief Find up the proper box for the item with the given prio.201 // Find up the proper box for the item with the given priority 201 202 int findUp(int start, int pr) { 202 203 while (lower(start, pr)) { 203 if (++start == int( boxes.size())) {204 if (++start == int(_boxes.size())) { 204 205 extend(); 205 206 } … … 208 209 } 209 210 210 // / \brief Move an item down into the proper box.211 void bubble _down(int index) {212 if (!upper( data[index].box,data[index].prio)) return;211 // Move an item down into the proper box 212 void bubbleDown(int index) { 213 if (!upper(_data[index].box, _data[index].prio)) return; 213 214 remove(index); 214 int box = findDown( data[index].box,data[index].prio);215 int box = findDown(_data[index].box, _data[index].prio); 215 216 insert(box, index); 216 217 } 217 218 218 // / \brief Find up the proper box for the item with the given prio.219 // Find down the proper box for the item with the given priority 219 220 int findDown(int start, int pr) { 220 221 while (upper(start, pr)) { 221 if (--start < 0) throw UnderFlowPriorityError();222 if (--start < 0) throw PriorityUnderflowError(); 222 223 } 223 224 return start; 224 225 } 225 226 226 // / \brief Find the first not empty box.227 // Find the first non-empty box 227 228 int findFirst() { 228 229 int first = 0; 229 while ( boxes[first].first == -1) ++first;230 while (_boxes[first].first == -1) ++first; 230 231 return first; 231 232 } 232 233 233 // / \brief Gives back the minimal prio of the box.234 // Gives back the minimum priority of the given box 234 235 int minValue(int box) { 235 int min = data[boxes[box].first].prio;236 for (int k = boxes[box].first; k != -1; k =data[k].next) {237 if ( data[k].prio < min) min =data[k].prio;236 int min = _data[_boxes[box].first].prio; 237 for (int k = _boxes[box].first; k != -1; k = _data[k].next) { 238 if (_data[k].prio < min) min = _data[k].prio; 238 239 } 239 240 return min; 240 241 } 241 242 242 /// \brief Rearrange the items of the heap and makes the 243 /// first box not empty. 243 // Rearrange the items of the heap and make the first box non-empty 244 244 void moveDown() { 245 245 int box = findFirst(); … … 247 247 int min = minValue(box); 248 248 for (int i = 0; i <= box; ++i) { 249 boxes[i].min = min;250 min += boxes[i].size;251 } 252 int curr = boxes[box].first, next;249 _boxes[i].min = min; 250 min += _boxes[i].size; 251 } 252 int curr = _boxes[box].first, next; 253 253 while (curr != -1) { 254 next = data[curr].next;255 bubble _down(curr);254 next = _data[curr].next; 255 bubbleDown(curr); 256 256 curr = next; 257 257 } 258 258 } 259 259 260 void relocate _last(int index) {261 if (index != int( data.size()) - 1) {262 data[index] =data.back();263 if ( data[index].prev != -1) {264 data[data[index].prev].next = index;260 void relocateLast(int index) { 261 if (index != int(_data.size()) - 1) { 262 _data[index] = _data.back(); 263 if (_data[index].prev != -1) { 264 _data[_data[index].prev].next = index; 265 265 } else { 266 boxes[data[index].box].first = index;266 _boxes[_data[index].box].first = index; 267 267 } 268 if ( data[index].next != -1) {269 data[data[index].next].prev = index;268 if (_data[index].next != -1) { 269 _data[_data[index].next].prev = index; 270 270 } 271 _iim[ data[index].item] = index;272 } 273 data.pop_back();271 _iim[_data[index].item] = index; 272 } 273 _data.pop_back(); 274 274 } 275 275 … … 278 278 /// \brief Insert an item into the heap with the given priority. 279 279 /// 280 /// Adds \c i to the heap with priority \c p. 280 /// This function inserts the given item into the heap with the 281 /// given priority. 281 282 /// \param i The item to insert. 282 283 /// \param p The priority of the item. 284 /// \pre \e i must not be stored in the heap. 285 /// \warning This method may throw an \c UnderFlowPriorityException. 283 286 void push(const Item &i, const Prio &p) { 284 int n = data.size();287 int n = _data.size(); 285 288 _iim.set(i, n); 286 data.push_back(RadixItem(i, p));287 while (lower( boxes.size() - 1, p)) {289 _data.push_back(RadixItem(i, p)); 290 while (lower(_boxes.size() - 1, p)) { 288 291 extend(); 289 292 } 290 int box = findDown( boxes.size() - 1, p);293 int box = findDown(_boxes.size() - 1, p); 291 294 insert(box, n); 292 295 } 293 296 294 /// \brief Return s the item withminimum priority.295 /// 296 /// This method returns the item withminimum priority.297 /// \pre The heap must be non empty.297 /// \brief Return the item having minimum priority. 298 /// 299 /// This function returns the item having minimum priority. 300 /// \pre The heap must be non-empty. 298 301 Item top() const { 299 302 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown(); 300 return data[boxes[0].first].item;301 } 302 303 /// \brief Returns the minimum priority.304 /// 305 /// Itreturns the minimum priority.306 /// \pre The heap must be non empty.303 return _data[_boxes[0].first].item; 304 } 305 306 /// \brief The minimum priority. 307 /// 308 /// This function returns the minimum priority. 309 /// \pre The heap must be non-empty. 307 310 Prio prio() const { 308 311 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown(); 309 return data[boxes[0].first].prio;312 return _data[_boxes[0].first].prio; 310 313 } 311 314 312 /// \brief Deletes the item withminimum priority.313 /// 314 /// This method deletes the item withminimum priority.315 /// \brief Remove the item having minimum priority. 316 /// 317 /// This function removes the item having minimum priority. 315 318 /// \pre The heap must be non-empty. 316 319 void pop() { 317 320 moveDown(); 318 int index = boxes[0].first;319 _iim[ data[index].item] = POST_HEAP;321 int index = _boxes[0].first; 322 _iim[_data[index].item] = POST_HEAP; 320 323 remove(index); 321 relocate_last(index); 322 } 323 324 /// \brief Deletes \c i from the heap. 325 /// 326 /// This method deletes item \c i from the heap, if \c i was 327 /// already stored in the heap. 328 /// \param i The item to erase. 324 relocateLast(index); 325 } 326 327 /// \brief Remove the given item from the heap. 328 /// 329 /// This function removes the given item from the heap if it is 330 /// already stored. 331 /// \param i The item to delete. 332 /// \pre \e i must be in the heap. 329 333 void erase(const Item &i) { 330 334 int index = _iim[i]; 331 335 _iim[i] = POST_HEAP; 332 336 remove(index); 333 relocate _last(index);337 relocateLast(index); 334 338 } 335 339 336 /// \brief Returns the priority of \c i.337 /// 338 /// This function returns the priority of item \c i.339 /// \p re \c i must be in the heap.340 /// \p aram i The item.340 /// \brief The priority of the given item. 341 /// 342 /// This function returns the priority of the given item. 343 /// \param i The item. 344 /// \pre \e i must be in the heap. 341 345 Prio operator[](const Item &i) const { 342 346 int idx = _iim[i]; 343 return data[idx].prio;344 } 345 346 /// \brief \c i gets to the heap with priority \c p independently347 /// if \c i was already there.348 /// 349 /// This method calls \ref push(\c i, \c p) if \c i is not stored350 /// in the heap and sets the priority of \c i to \c p otherwise.351 /// It may throw an \e UnderFlowPriorityException.347 return _data[idx].prio; 348 } 349 350 /// \brief Set the priority of an item or insert it, if it is 351 /// not stored in the heap. 352 /// 353 /// This method sets the priority of the given item if it is 354 /// already stored in the heap. Otherwise it inserts the given 355 /// item into the heap with the given priority. 352 356 /// \param i The item. 353 357 /// \param p The priority. 358 /// \pre \e i must be in the heap. 359 /// \warning This method may throw an \c UnderFlowPriorityException. 354 360 void set(const Item &i, const Prio &p) { 355 361 int idx = _iim[i]; … … 357 363 push(i, p); 358 364 } 359 else if( p >= data[idx].prio ) {360 data[idx].prio = p;361 bubble _up(idx);365 else if( p >= _data[idx].prio ) { 366 _data[idx].prio = p; 367 bubbleUp(idx); 362 368 } else { 363 data[idx].prio = p; 364 bubble_down(idx); 365 } 366 } 367 368 369 /// \brief Decreases the priority of \c i to \c p. 370 /// 371 /// This method decreases the priority of item \c i to \c p. 372 /// \pre \c i must be stored in the heap with priority at least \c p, and 373 /// \c should be greater or equal to the last removed item's priority. 369 _data[idx].prio = p; 370 bubbleDown(idx); 371 } 372 } 373 374 /// \brief Decrease the priority of an item to the given value. 375 /// 376 /// This function decreases the priority of an item to the given value. 374 377 /// \param i The item. 375 378 /// \param p The priority. 379 /// \pre \e i must be stored in the heap with priority at least \e p. 380 /// \warning This method may throw an \c UnderFlowPriorityException. 376 381 void decrease(const Item &i, const Prio &p) { 377 382 int idx = _iim[i]; 378 data[idx].prio = p; 379 bubble_down(idx); 380 } 381 382 /// \brief Increases the priority of \c i to \c p. 383 /// 384 /// This method sets the priority of item \c i to \c p. 385 /// \pre \c i must be stored in the heap with priority at most \c p 383 _data[idx].prio = p; 384 bubbleDown(idx); 385 } 386 387 /// \brief Increase the priority of an item to the given value. 388 /// 389 /// This function increases the priority of an item to the given value. 386 390 /// \param i The item. 387 391 /// \param p The priority. 392 /// \pre \e i must be stored in the heap with priority at most \e p. 388 393 void increase(const Item &i, const Prio &p) { 389 394 int idx = _iim[i]; 390 data[idx].prio = p;391 bubble _up(idx);392 } 393 394 /// \brief Return s if \c item is in, has already been in, or has395 /// never been in the heap.396 /// 397 /// This method returns PRE_HEAP if \c item has never been in the398 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP399 /// otherwise. In the latter case it is possible that \c item will400 /// get backto the heap again.395 _data[idx].prio = p; 396 bubbleUp(idx); 397 } 398 399 /// \brief Return the state of an item. 400 /// 401 /// This method returns \c PRE_HEAP if the given item has never 402 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 403 /// and \c POST_HEAP otherwise. 404 /// In the latter case it is possible that the item will get back 405 /// to the heap again. 401 406 /// \param i The item. 402 407 State state(const Item &i) const { … … 406 411 } 407 412 408 /// \brief Set s the state of the \citem in the heap.409 /// 410 /// Sets the state of the \c item in the heap. It can be used to411 /// manually clear the heap when it is important to achive the412 /// better time complexity.413 /// \brief Set the state of an item in the heap. 414 /// 415 /// This function sets the state of the given item in the heap. 416 /// It can be used to manually clear the heap when it is important 417 /// to achive better time complexity. 413 418 /// \param i The item. 414 419 /// \param st The state. It should not be \c IN_HEAP.
Note: See TracChangeset
for help on using the changeset viewer.
