Changeset 756:0747f332c478 in lemon
- Timestamp:
- 07/08/09 17:21:30 (15 years ago)
- Branch:
- default
- Phase:
- public
- Location:
- lemon
- Files:
-
- 5 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bin_heap.h
r730 r756 22 22 ///\ingroup auxdat 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 auxdat 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(); … … 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(); … … 182 182 } 183 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. 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() { … … 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]; … … 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. … … 268 269 } 269 270 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.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]; … … 280 280 } 281 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.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]; … … 292 291 } 293 292 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.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
r730 r756 22 22 ///\ingroup auxdat 23 23 ///\file 24 ///\brief Bucket Heap implementation.24 ///\brief Bucket heap implementation. 25 25 26 26 #include <vector> … … 56 56 /// \ingroup auxdat 57 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. 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; … … 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() { … … 234 247 } 235 248 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. 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]; … … 246 260 } 247 261 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. 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. … … 362 374 /// \ingroup auxdat 363 375 /// 364 /// \brief A Simplified Bucket Heap implementation.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
r631 r756 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 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
r730 r756 22 22 ///\file 23 23 ///\ingroup auxdat 24 ///\brief Fibonacci Heap implementation.24 ///\brief Fibonacci heap implementation. 25 25 26 26 #include <vector> 27 #include <utility> 27 28 #include <functional> 28 29 #include <lemon/math.h> … … 32 33 /// \ingroup auxdat 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() { … … 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. -
lemon/radix_heap.h
r730 r756 22 22 ///\ingroup auxdat 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 auxdat a32 /// \ingroup auxdat 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 61 class UnderFlowPriorityError : public Exception { 64 62 public: … … 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 … … 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(minim al, 1));119 boxes.push_back(RadixBox(minim al+ 1, 1));120 while (lower(boxes.size() - 1, capacity + minim al- 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.122 /// \brief The number of items stored in the heap. 123 /// 124 /// This function returns the number of items stored in the heap. 128 125 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. 126 127 /// \brief Check if the heap is empty. 128 /// 129 /// This function returns \c true if the heap is empty. 132 130 bool empty() const { return data.empty(); } 133 131 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) { 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) { 141 142 data.clear(); boxes.clear(); 142 boxes.push_back(RadixBox(minim al, 1));143 boxes.push_back(RadixBox(minim al+ 1, 1));144 while (lower(boxes.size() - 1, capacity + minim al- 1)) {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 } … … 157 158 } 158 159 159 // / \brief Remove item from the box list.160 // Remove item from the box list 160 161 void remove(int index) { 161 162 if (data[index].prev >= 0) { … … 169 170 } 170 171 171 // / \brief Insert item into the box list.172 // Insert item into the box list 172 173 void insert(int box, int index) { 173 174 if (boxes[box].first == -1) { … … 183 184 } 184 185 185 // / \brief Add a new box to the box list.186 // Add a new box to the box list 186 187 void extend() { 187 188 int min = boxes.back().min + boxes.back().size; … … 190 191 } 191 192 192 // / \briefMove an item up into the proper box.193 // Move an item up into the proper box. 193 194 void bubble_up(int index) { 194 195 if (!lower(data[index].box, data[index].prio)) return; … … 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)) { … … 208 209 } 209 210 210 // / \brief Move an item down into the proper box.211 // Move an item down into the proper box 211 212 void bubble_down(int index) { 212 213 if (!upper(data[index].box, data[index].prio)) return; … … 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)) { … … 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; … … 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 236 int min = data[boxes[box].first].prio; … … 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(); … … 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 287 int n = data.size(); … … 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(); … … 301 304 } 302 305 303 /// \brief Returns the minimum priority.304 /// 305 /// Itreturns the minimum priority.306 /// \pre The heap must be non empty.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(); … … 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() { … … 322 325 } 323 326 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. 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]; … … 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]; … … 344 348 } 345 349 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.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]; … … 366 372 } 367 373 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. 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]; … … 380 385 } 381 386 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 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]; … … 392 397 } 393 398 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.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.