Changes in lemon/bucket_heap.h [683:9f529abcaebf:877:141f9c0db4a3] in lemon-1.2
- File:
-
- 1 edited
-
lemon/bucket_heap.h (modified) (28 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/bucket_heap.h
r683 r877 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 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 {
Note: See TracChangeset
for help on using the changeset viewer.
