Changeset 730:9f529abcaebf in lemon for lemon/bucket_heap.h
 Timestamp:
 06/11/09 23:13:24 (10 years ago)
 Branch:
 default
 Children:
 733:7439dc5fe1b9, 738:9e54e3b27db0, 740:7bda7860e0a8, 743:c9b9da1a90a0, 748:d1a9224f1e30, 756:0747f332c478, 760:4ac30454f1c1, 765:703ebf476a1d, 805:b31e130db13d
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/bucket_heap.h
r729 r730 32 32 namespace _bucket_heap_bits { 33 33 34 template <bool minimize>34 template <bool MIN> 35 35 struct DirectionTraits { 36 36 static bool less(int left, int right) { … … 66 66 /// the priorities are small. It is not intended to use as dijkstra heap. 67 67 /// 68 /// \param _ItemIntMap A read and writable Item int map, used internally68 /// \param IM A read and write Item int map, used internally 69 69 /// to handle the cross references. 70 /// \param minimize If the given parameter is true then the heap gives back 71 /// the lowest priority. 72 template <typename _ItemIntMap, bool minimize = true> 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. 73 template <typename IM, bool MIN = true> 73 74 class BucketHeap { 74 75 75 76 public: 76 77 /// \e 77 typedef typename _ItemIntMap::Key Item;78 typedef typename IM::Key Item; 78 79 /// \e 79 80 typedef int Prio; … … 81 82 typedef std::pair<Item, Prio> Pair; 82 83 /// \e 83 typedef _ItemIntMapItemIntMap;84 typedef IM ItemIntMap; 84 85 85 86 private: 86 87 87 typedef _bucket_heap_bits::DirectionTraits< minimize> Direction;88 typedef _bucket_heap_bits::DirectionTraits<MIN> Direction; 88 89 89 90 public: … … 95 96 /// heap's point of view, but may be useful to the user. 96 97 /// 97 /// The ItemIntMap \e should be initialized in such way that it maps98 /// PRE_HEAP (1) to any element to be put in the heap...98 /// The itemint map must be initialized in such way that it assigns 99 /// \c PRE_HEAP (<tt>1</tt>) to any element to be put in the heap. 99 100 enum State { 100 IN_HEAP = 0, 101 PRE_HEAP = 1, 102 POST_HEAP = 2 101 IN_HEAP = 0, ///< = 0. 102 PRE_HEAP = 1, ///< = 1. 103 POST_HEAP = 2 ///< = 2. 103 104 }; 104 105 … … 107 108 /// 108 109 /// The constructor. 109 /// \param _indexshould be given to the constructor, since it is used110 /// \param map should be given to the constructor, since it is used 110 111 /// internally to handle the cross references. The value of the map 111 112 /// should be PRE_HEAP (1) for each element. 112 explicit BucketHeap(ItemIntMap & _index) : index(_index), minimal(0) {}113 explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {} 113 114 114 115 /// The number of items stored in the heap. 115 116 /// 116 117 /// \brief Returns the number of items stored in the heap. 117 int size() const { return data.size(); }118 int size() const { return _data.size(); } 118 119 119 120 /// \brief Checks if the heap stores no items. 120 121 /// 121 122 /// Returns \c true if and only if the heap stores no items. 122 bool empty() const { return data.empty(); }123 bool empty() const { return _data.empty(); } 123 124 124 125 /// \brief Make empty this heap. … … 129 130 /// cross reference map for each item to \c PRE_HEAP. 130 131 void clear() { 131 data.clear(); first.clear(); minimal= 0;132 _data.clear(); _first.clear(); _minimum = 0; 132 133 } 133 134 … … 135 136 136 137 void relocate_last(int idx) { 137 if (idx + 1 < int( data.size())) {138 data[idx] =data.back();139 if ( data[idx].prev != 1) {140 data[data[idx].prev].next = idx;138 if (idx + 1 < int(_data.size())) { 139 _data[idx] = _data.back(); 140 if (_data[idx].prev != 1) { 141 _data[_data[idx].prev].next = idx; 141 142 } else { 142 first[data[idx].value] = idx;143 _first[_data[idx].value] = idx; 143 144 } 144 if ( data[idx].next != 1) {145 data[data[idx].next].prev = idx;145 if (_data[idx].next != 1) { 146 _data[_data[idx].next].prev = idx; 146 147 } 147 index[data[idx].item] = idx;148 } 149 data.pop_back();148 _iim[_data[idx].item] = idx; 149 } 150 _data.pop_back(); 150 151 } 151 152 152 153 void unlace(int idx) { 153 if ( data[idx].prev != 1) {154 data[data[idx].prev].next =data[idx].next;154 if (_data[idx].prev != 1) { 155 _data[_data[idx].prev].next = _data[idx].next; 155 156 } else { 156 first[data[idx].value] =data[idx].next;157 } 158 if ( data[idx].next != 1) {159 data[data[idx].next].prev =data[idx].prev;157 _first[_data[idx].value] = _data[idx].next; 158 } 159 if (_data[idx].next != 1) { 160 _data[_data[idx].next].prev = _data[idx].prev; 160 161 } 161 162 } 162 163 163 164 void lace(int idx) { 164 if (int( first.size()) <=data[idx].value) {165 first.resize(data[idx].value + 1, 1);166 } 167 data[idx].next = first[data[idx].value];168 if ( data[idx].next != 1) {169 data[data[idx].next].prev = idx;170 } 171 first[data[idx].value] = idx;172 data[idx].prev = 1;165 if (int(_first.size()) <= _data[idx].value) { 166 _first.resize(_data[idx].value + 1, 1); 167 } 168 _data[idx].next = _first[_data[idx].value]; 169 if (_data[idx].next != 1) { 170 _data[_data[idx].next].prev = idx; 171 } 172 _first[_data[idx].value] = idx; 173 _data[idx].prev = 1; 173 174 } 174 175 … … 188 189 /// \param p The priority of the item. 189 190 void push(const Item &i, const Prio &p) { 190 int idx = data.size();191 index[i] = idx;192 data.push_back(BucketItem(i, p));191 int idx = _data.size(); 192 _iim[i] = idx; 193 _data.push_back(BucketItem(i, p)); 193 194 lace(idx); 194 if (Direction::less(p, minimal)) {195 minimal= p;195 if (Direction::less(p, _minimum)) { 196 _minimum = p; 196 197 } 197 198 } … … 202 203 /// \pre The heap must be nonempty. 203 204 Item top() const { 204 while ( first[minimal] == 1) {205 Direction::increase( minimal);206 } 207 return data[first[minimal]].item;205 while (_first[_minimum] == 1) { 206 Direction::increase(_minimum); 207 } 208 return _data[_first[_minimum]].item; 208 209 } 209 210 … … 213 214 /// \pre The heap must be nonempty. 214 215 Prio prio() const { 215 while ( first[minimal] == 1) {216 Direction::increase( minimal);217 } 218 return minimal;216 while (_first[_minimum] == 1) { 217 Direction::increase(_minimum); 218 } 219 return _minimum; 219 220 } 220 221 … … 224 225 /// \pre The heap must be nonempty. 225 226 void pop() { 226 while ( first[minimal] == 1) {227 Direction::increase( minimal);228 } 229 int idx = first[minimal];230 index[data[idx].item] = 2;227 while (_first[_minimum] == 1) { 228 Direction::increase(_minimum); 229 } 230 int idx = _first[_minimum]; 231 _iim[_data[idx].item] = 2; 231 232 unlace(idx); 232 233 relocate_last(idx); … … 239 240 /// \param i The item to erase. 240 241 void erase(const Item &i) { 241 int idx = index[i];242 index[data[idx].item] = 2;242 int idx = _iim[i]; 243 _iim[_data[idx].item] = 2; 243 244 unlace(idx); 244 245 relocate_last(idx); … … 252 253 /// \param i The item. 253 254 Prio operator[](const Item &i) const { 254 int idx = index[i];255 return data[idx].value;255 int idx = _iim[i]; 256 return _data[idx].value; 256 257 } 257 258 … … 264 265 /// \param p The priority. 265 266 void set(const Item &i, const Prio &p) { 266 int idx = index[i];267 int idx = _iim[i]; 267 268 if (idx < 0) { 268 269 push(i, p); 269 } else if (Direction::less(p, data[idx].value)) {270 } else if (Direction::less(p, _data[idx].value)) { 270 271 decrease(i, p); 271 272 } else { … … 282 283 /// \param p The priority. 283 284 void decrease(const Item &i, const Prio &p) { 284 int idx = index[i];285 int idx = _iim[i]; 285 286 unlace(idx); 286 data[idx].value = p;287 if (Direction::less(p, minimal)) {288 minimal= p;287 _data[idx].value = p; 288 if (Direction::less(p, _minimum)) { 289 _minimum = p; 289 290 } 290 291 lace(idx); … … 299 300 /// \param p The priority. 300 301 void increase(const Item &i, const Prio &p) { 301 int idx = index[i];302 int idx = _iim[i]; 302 303 unlace(idx); 303 data[idx].value = p;304 _data[idx].value = p; 304 305 lace(idx); 305 306 } … … 314 315 /// \param i The item. 315 316 State state(const Item &i) const { 316 int idx = index[i];317 int idx = _iim[i]; 317 318 if (idx >= 0) idx = 0; 318 319 return State(idx); … … 333 334 erase(i); 334 335 } 335 index[i] = st;336 _iim[i] = st; 336 337 break; 337 338 case IN_HEAP: … … 352 353 }; 353 354 354 ItemIntMap& index;355 std::vector<int> first;356 std::vector<BucketItem> data;357 mutable int minimal;355 ItemIntMap& _iim; 356 std::vector<int> _first; 357 std::vector<BucketItem> _data; 358 mutable int _minimum; 358 359 359 360 }; // class BucketHeap … … 371 372 /// minimal and it does not supports key increasing, decreasing. 372 373 /// 373 /// \param _ItemIntMap A read and writable Item int map, used internally374 /// \param IM A read and write Item int map, used internally 374 375 /// to handle the cross references. 375 /// \param minimize If the given parameter is true then the heap gives back 376 /// the lowest priority. 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. 377 379 /// 378 380 /// \sa BucketHeap 379 template <typename _ItemIntMap, bool minimize= true >381 template <typename IM, bool MIN = true > 380 382 class SimpleBucketHeap { 381 383 382 384 public: 383 typedef typename _ItemIntMap::Key Item;385 typedef typename IM::Key Item; 384 386 typedef int Prio; 385 387 typedef std::pair<Item, Prio> Pair; 386 typedef _ItemIntMapItemIntMap;388 typedef IM ItemIntMap; 387 389 388 390 private: 389 391 390 typedef _bucket_heap_bits::DirectionTraits< minimize> Direction;392 typedef _bucket_heap_bits::DirectionTraits<MIN> Direction; 391 393 392 394 public: … … 398 400 /// heap's point of view, but may be useful to the user. 399 401 /// 400 /// The ItemIntMap \e should be initialized in such way that it maps401 /// PRE_HEAP (1) to any element to be put in the heap...402 /// The itemint map must be initialized in such way that it assigns 403 /// \c PRE_HEAP (<tt>1</tt>) to any element to be put in the heap. 402 404 enum State { 403 IN_HEAP = 0, 404 PRE_HEAP = 1, 405 POST_HEAP = 2 405 IN_HEAP = 0, ///< = 0. 406 PRE_HEAP = 1, ///< = 1. 407 POST_HEAP = 2 ///< = 2. 406 408 }; 407 409 … … 411 413 /// 412 414 /// The constructor. 413 /// \param _indexshould be given to the constructor, since it is used415 /// \param map should be given to the constructor, since it is used 414 416 /// internally to handle the cross references. The value of the map 415 417 /// should be PRE_HEAP (1) for each element. 416 explicit SimpleBucketHeap(ItemIntMap & _index)417 : index(_index), free(1), num(0), minimal(0) {}418 explicit SimpleBucketHeap(ItemIntMap &map) 419 : _iim(map), _free(1), _num(0), _minimum(0) {} 418 420 419 421 /// \brief Returns the number of items stored in the heap. 420 422 /// 421 423 /// The number of items stored in the heap. 422 int size() const { return num; }424 int size() const { return _num; } 423 425 424 426 /// \brief Checks if the heap stores no items. 425 427 /// 426 428 /// Returns \c true if and only if the heap stores no items. 427 bool empty() const { return num == 0; }429 bool empty() const { return _num == 0; } 428 430 429 431 /// \brief Make empty this heap. … … 434 436 /// cross reference map for each item to \c PRE_HEAP. 435 437 void clear() { 436 data.clear(); first.clear(); free = 1; num = 0; minimal= 0;438 _data.clear(); _first.clear(); _free = 1; _num = 0; _minimum = 0; 437 439 } 438 440 … … 452 454 void push(const Item &i, const Prio &p) { 453 455 int idx; 454 if ( free == 1) {455 idx = data.size();456 data.push_back(BucketItem(i));456 if (_free == 1) { 457 idx = _data.size(); 458 _data.push_back(BucketItem(i)); 457 459 } else { 458 idx = free;459 free =data[idx].next;460 data[idx].item = i;461 } 462 index[i] = idx;463 if (p >= int( first.size()))first.resize(p + 1, 1);464 data[idx].next =first[p];465 first[p] = idx;466 if (Direction::less(p, minimal)) {467 minimal= p;468 } 469 ++ num;460 idx = _free; 461 _free = _data[idx].next; 462 _data[idx].item = i; 463 } 464 _iim[i] = idx; 465 if (p >= int(_first.size())) _first.resize(p + 1, 1); 466 _data[idx].next = _first[p]; 467 _first[p] = idx; 468 if (Direction::less(p, _minimum)) { 469 _minimum = p; 470 } 471 ++_num; 470 472 } 471 473 … … 475 477 /// \pre The heap must be nonempty. 476 478 Item top() const { 477 while ( first[minimal] == 1) {478 Direction::increase( minimal);479 } 480 return data[first[minimal]].item;479 while (_first[_minimum] == 1) { 480 Direction::increase(_minimum); 481 } 482 return _data[_first[_minimum]].item; 481 483 } 482 484 … … 486 488 /// \pre The heap must be nonempty. 487 489 Prio prio() const { 488 while ( first[minimal] == 1) {489 Direction::increase( minimal);490 } 491 return minimal;490 while (_first[_minimum] == 1) { 491 Direction::increase(_minimum); 492 } 493 return _minimum; 492 494 } 493 495 … … 497 499 /// \pre The heap must be nonempty. 498 500 void pop() { 499 while ( first[minimal] == 1) {500 Direction::increase( minimal);501 } 502 int idx = first[minimal];503 index[data[idx].item] = 2;504 first[minimal] =data[idx].next;505 data[idx].next =free;506 free = idx;507  num;501 while (_first[_minimum] == 1) { 502 Direction::increase(_minimum); 503 } 504 int idx = _first[_minimum]; 505 _iim[_data[idx].item] = 2; 506 _first[_minimum] = _data[idx].next; 507 _data[idx].next = _free; 508 _free = idx; 509 _num; 508 510 } 509 511 … … 517 519 /// \param i The item. 518 520 Prio operator[](const Item &i) const { 519 for (int k = 0; k < first.size(); ++k) {520 int idx = first[k];521 for (int k = 0; k < _first.size(); ++k) { 522 int idx = _first[k]; 521 523 while (idx != 1) { 522 if ( data[idx].item == i) {524 if (_data[idx].item == i) { 523 525 return k; 524 526 } 525 idx = data[idx].next;527 idx = _data[idx].next; 526 528 } 527 529 } … … 538 540 /// \param i The item. 539 541 State state(const Item &i) const { 540 int idx = index[i];542 int idx = _iim[i]; 541 543 if (idx >= 0) idx = 0; 542 544 return State(idx); … … 553 555 }; 554 556 555 ItemIntMap& index;556 std::vector<int> first;557 std::vector<BucketItem> data;558 int free,num;559 mutable int minimal;557 ItemIntMap& _iim; 558 std::vector<int> _first; 559 std::vector<BucketItem> _data; 560 int _free, _num; 561 mutable int _minimum; 560 562 561 563 }; // class SimpleBucketHeap
Note: See TracChangeset
for help on using the changeset viewer.