Changeset 730:9f529abcaebf in lemon
- Timestamp:
- 06/11/09 23:13:24 (16 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
- Location:
- lemon
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bin_heap.h
r631 r730 34 34 ///\brief A Binary Heap implementation. 35 35 /// 36 ///This class implements the \e binary \e heap data structure. 37 /// 36 ///This class implements the \e binary \e heap data structure. 37 /// 38 38 ///A \e heap is a data structure for storing items with specified values 39 39 ///called \e priorities in such a way that finding the item with minimum 40 ///priority is efficient. \c C ompspecifies the ordering of the priorities.40 ///priority is efficient. \c CMP specifies the ordering of the priorities. 41 41 ///In a heap one can change the priority of an item, add or erase an 42 42 ///item, etc. … … 45 45 ///\tparam IM A read and writable item map with int values, used internally 46 46 ///to handle the cross references. 47 ///\tparam C ompA functor class for the ordering of the priorities.47 ///\tparam CMP A functor class for the ordering of the priorities. 48 48 ///The default is \c std::less<PR>. 49 49 /// 50 50 ///\sa FibHeap 51 51 ///\sa Dijkstra 52 template <typename PR, typename IM, typename C omp= std::less<PR> >52 template <typename PR, typename IM, typename CMP = std::less<PR> > 53 53 class BinHeap { 54 54 … … 63 63 typedef std::pair<Item,Prio> Pair; 64 64 ///\e 65 typedef C ompCompare;65 typedef CMP Compare; 66 66 67 67 /// \brief Type to represent the items states. -
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 item-int 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 non-empty. 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 item-int 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 non-empty. 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 -
lemon/fib_heap.h
r728 r730 37 37 ///is a data structure for storing items with specified values called \e 38 38 ///priorities in such a way that finding the item with minimum priority is 39 ///efficient. \c C omparespecifies the ordering of the priorities. In a heap39 ///efficient. \c CMP specifies the ordering of the priorities. In a heap 40 40 ///one can change the priority of an item, add or erase an item, etc. 41 41 /// … … 44 44 ///\ref BinHeap "binary heap". 45 45 /// 46 ///\param _PrioType of the priority of the items.47 ///\param _ItemIntMapA read and writable Item int map, used internally46 ///\param PRIO Type of the priority of the items. 47 ///\param IM A read and writable Item int map, used internally 48 48 ///to handle the cross references. 49 ///\param _CompareA class for the ordering of the priorities. The50 ///default is \c std::less< _Prio>.49 ///\param CMP A class for the ordering of the priorities. The 50 ///default is \c std::less<PRIO>. 51 51 /// 52 52 ///\sa BinHeap 53 53 ///\sa Dijkstra 54 54 #ifdef DOXYGEN 55 template <typename _Prio, 56 typename _ItemIntMap, 57 typename _Compare> 55 template <typename PRIO, typename IM, typename CMP> 58 56 #else 59 template <typename _Prio, 60 typename _ItemIntMap, 61 typename _Compare = std::less<_Prio> > 57 template <typename PRIO, typename IM, typename CMP = std::less<PRIO> > 62 58 #endif 63 59 class FibHeap { 64 60 public: 65 61 ///\e 66 typedef _ItemIntMapItemIntMap;62 typedef IM ItemIntMap; 67 63 ///\e 68 typedef _PrioPrio;64 typedef PRIO Prio; 69 65 ///\e 70 66 typedef typename ItemIntMap::Key Item; … … 72 68 typedef std::pair<Item,Prio> Pair; 73 69 ///\e 74 typedef _CompareCompare;70 typedef CMP Compare; 75 71 76 72 private: 77 class store;78 79 std::vector< store> container;80 int minimum;81 ItemIntMap & iimap;82 Compare comp;83 int num_items;73 class Store; 74 75 std::vector<Store> _data; 76 int _minimum; 77 ItemIntMap &_iim; 78 Compare _comp; 79 int _num; 84 80 85 81 public: 86 ///Status of the nodes 82 83 /// \brief Type to represent the items states. 84 /// 85 /// Each Item element have a state associated to it. It may be "in heap", 86 /// "pre heap" or "post heap". The latter two are indifferent from the 87 /// heap's point of view, but may be useful to the user. 88 /// 89 /// The item-int map must be initialized in such way that it assigns 90 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. 87 91 enum State { 88 ///The node is in the heap 89 IN_HEAP = 0, 90 ///The node has never been in the heap 91 PRE_HEAP = -1, 92 ///The node was in the heap but it got out of it 93 POST_HEAP = -2 92 IN_HEAP = 0, ///< = 0. 93 PRE_HEAP = -1, ///< = -1. 94 POST_HEAP = -2 ///< = -2. 94 95 }; 95 96 96 97 /// \brief The constructor 97 98 /// 98 /// \c _iimap should be given to the constructor, since it is99 /// \c map should be given to the constructor, since it is 99 100 /// used internally to handle the cross references. 100 explicit FibHeap(ItemIntMap & _iimap)101 : minimum(0), iimap(_iimap), num_items() {}101 explicit FibHeap(ItemIntMap &map) 102 : _minimum(0), _iim(map), _num() {} 102 103 103 104 /// \brief The constructor 104 105 /// 105 /// \c _iimap should be given to the constructor, since it is used106 /// internally to handle the cross references. \c _comp is an106 /// \c map should be given to the constructor, since it is used 107 /// internally to handle the cross references. \c comp is an 107 108 /// object for ordering of the priorities. 108 FibHeap(ItemIntMap & _iimap, const Compare &_comp)109 : minimum(0), iimap(_iimap), comp(_comp), num_items() {}109 FibHeap(ItemIntMap &map, const Compare &comp) 110 : _minimum(0), _iim(map), _comp(comp), _num() {} 110 111 111 112 /// \brief The number of items stored in the heap. 112 113 /// 113 114 /// Returns the number of items stored in the heap. 114 int size() const { return num_items; }115 int size() const { return _num; } 115 116 116 117 /// \brief Checks if the heap stores no items. 117 118 /// 118 119 /// Returns \c true if and only if the heap stores no items. 119 bool empty() const { return num_items==0; }120 bool empty() const { return _num==0; } 120 121 121 122 /// \brief Make empty this heap. … … 126 127 /// cross reference map for each item to \c PRE_HEAP. 127 128 void clear() { 128 container.clear(); minimum = 0; num_items= 0;129 _data.clear(); _minimum = 0; _num = 0; 129 130 } 130 131 … … 136 137 /// \ref increase(\c item, \c value) otherwise. 137 138 void set (const Item& item, const Prio& value) { 138 int i= iimap[item];139 if ( i >= 0 && container[i].in ) {140 if ( comp(value, container[i].prio) ) decrease(item, value);141 if ( comp(container[i].prio, value) ) increase(item, 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); 142 143 } else push(item, value); 143 144 } … … 148 149 /// \pre \c item must not be stored in the heap. 149 150 void push (const Item& item, const Prio& value) { 150 int i= iimap[item];151 int i=_iim[item]; 151 152 if ( i < 0 ) { 152 int s= container.size();153 iimap.set( item, s );154 store st;153 int s=_data.size(); 154 _iim.set( item, s ); 155 Store st; 155 156 st.name=item; 156 container.push_back(st);157 _data.push_back(st); 157 158 i=s; 158 159 } else { 159 container[i].parent=container[i].child=-1;160 container[i].degree=0;161 container[i].in=true;162 container[i].marked=false;163 } 164 165 if ( num_items) {166 container[container[minimum].right_neighbor].left_neighbor=i;167 container[i].right_neighbor=container[minimum].right_neighbor;168 container[minimum].right_neighbor=i;169 container[i].left_neighbor=minimum;170 if ( comp( value, container[minimum].prio) )minimum=i;160 _data[i].parent=_data[i].child=-1; 161 _data[i].degree=0; 162 _data[i].in=true; 163 _data[i].marked=false; 164 } 165 166 if ( _num ) { 167 _data[_data[_minimum].right_neighbor].left_neighbor=i; 168 _data[i].right_neighbor=_data[_minimum].right_neighbor; 169 _data[_minimum].right_neighbor=i; 170 _data[i].left_neighbor=_minimum; 171 if ( _comp( value, _data[_minimum].prio) ) _minimum=i; 171 172 } else { 172 container[i].right_neighbor=container[i].left_neighbor=i;173 minimum=i;174 } 175 container[i].prio=value;176 ++ num_items;173 _data[i].right_neighbor=_data[i].left_neighbor=i; 174 _minimum=i; 175 } 176 _data[i].prio=value; 177 ++_num; 177 178 } 178 179 … … 182 183 /// Compare. 183 184 /// \pre The heap must be nonempty. 184 Item top() const { return container[minimum].name; }185 Item top() const { return _data[_minimum].name; } 185 186 186 187 /// \brief Returns the minimum priority relative to \c Compare. … … 188 189 /// It returns the minimum priority relative to \c Compare. 189 190 /// \pre The heap must be nonempty. 190 const Prio& prio() const { return container[minimum].prio; }191 const Prio& prio() const { return _data[_minimum].prio; } 191 192 192 193 /// \brief Returns the priority of \c item. … … 195 196 /// \pre \c item must be in the heap. 196 197 const Prio& operator[](const Item& item) const { 197 return container[iimap[item]].prio;198 return _data[_iim[item]].prio; 198 199 } 199 200 … … 205 206 void pop() { 206 207 /*The first case is that there are only one root.*/ 207 if ( container[minimum].left_neighbor==minimum ) {208 container[minimum].in=false;209 if ( container[minimum].degree!=0 ) {210 makeroot( container[minimum].child);211 minimum=container[minimum].child;208 if ( _data[_minimum].left_neighbor==_minimum ) { 209 _data[_minimum].in=false; 210 if ( _data[_minimum].degree!=0 ) { 211 makeroot(_data[_minimum].child); 212 _minimum=_data[_minimum].child; 212 213 balance(); 213 214 } 214 215 } else { 215 int right= container[minimum].right_neighbor;216 unlace( minimum);217 container[minimum].in=false;218 if ( container[minimum].degree > 0 ) {219 int left= container[minimum].left_neighbor;220 int child= container[minimum].child;221 int last_child= container[child].left_neighbor;216 int right=_data[_minimum].right_neighbor; 217 unlace(_minimum); 218 _data[_minimum].in=false; 219 if ( _data[_minimum].degree > 0 ) { 220 int left=_data[_minimum].left_neighbor; 221 int child=_data[_minimum].child; 222 int last_child=_data[child].left_neighbor; 222 223 223 224 makeroot(child); 224 225 225 container[left].right_neighbor=child;226 container[child].left_neighbor=left;227 container[right].left_neighbor=last_child;228 container[last_child].right_neighbor=right;229 } 230 minimum=right;226 _data[left].right_neighbor=child; 227 _data[child].left_neighbor=left; 228 _data[right].left_neighbor=last_child; 229 _data[last_child].right_neighbor=right; 230 } 231 _minimum=right; 231 232 balance(); 232 233 } // the case where there are more roots 233 -- num_items;234 --_num; 234 235 } 235 236 … … 239 240 /// stored in the heap. It is quite inefficient in Fibonacci heaps. 240 241 void erase (const Item& item) { 241 int i= iimap[item];242 243 if ( i >= 0 && container[i].in ) {244 if ( container[i].parent!=-1 ) {245 int p= container[i].parent;242 int i=_iim[item]; 243 244 if ( i >= 0 && _data[i].in ) { 245 if ( _data[i].parent!=-1 ) { 246 int p=_data[i].parent; 246 247 cut(i,p); 247 248 cascade(p); 248 249 } 249 minimum=i; //As if its prio would be -infinity250 _minimum=i; //As if its prio would be -infinity 250 251 pop(); 251 252 } … … 258 259 /// value relative to \c Compare. 259 260 void decrease (Item item, const Prio& value) { 260 int i= iimap[item];261 container[i].prio=value;262 int p= container[i].parent;263 264 if ( p!=-1 && comp(value, container[p].prio) ) {261 int i=_iim[item]; 262 _data[i].prio=value; 263 int p=_data[i].parent; 264 265 if ( p!=-1 && _comp(value, _data[p].prio) ) { 265 266 cut(i,p); 266 267 cascade(p); 267 268 } 268 if ( comp(value, container[minimum].prio) )minimum=i;269 if ( _comp(value, _data[_minimum].prio) ) _minimum=i; 269 270 } 270 271 … … 290 291 /// get back to the heap again. 291 292 State state(const Item &item) const { 292 int i= iimap[item];293 int i=_iim[item]; 293 294 if( i>=0 ) { 294 if ( container[i].in ) i=0;295 if ( _data[i].in ) i=0; 295 296 else i=-2; 296 297 } … … 302 303 /// Sets the state of the \c item in the heap. It can be used to 303 304 /// manually clear the heap when it is important to achive the 304 /// better time complexity.305 /// better time _complexity. 305 306 /// \param i The item. 306 307 /// \param st The state. It should not be \c IN_HEAP. … … 312 313 erase(i); 313 314 } 314 iimap[i] = st;315 _iim[i] = st; 315 316 break; 316 317 case IN_HEAP: … … 323 324 void balance() { 324 325 325 int maxdeg=int( std::floor( 2.08*log(double( container.size()))))+1;326 int maxdeg=int( std::floor( 2.08*log(double(_data.size()))))+1; 326 327 327 328 std::vector<int> A(maxdeg,-1); … … 331 332 *We set minimum to this during balance(). 332 333 */ 333 int anchor= container[minimum].left_neighbor;334 int next= minimum;334 int anchor=_data[_minimum].left_neighbor; 335 int next=_minimum; 335 336 bool end=false; 336 337 … … 338 339 int active=next; 339 340 if ( anchor==active ) end=true; 340 int d= container[active].degree;341 next= container[active].right_neighbor;341 int d=_data[active].degree; 342 next=_data[active].right_neighbor; 342 343 343 344 while (A[d]!=-1) { 344 if( comp(container[active].prio, container[A[d]].prio) ) {345 if( _comp(_data[active].prio, _data[A[d]].prio) ) { 345 346 fuse(active,A[d]); 346 347 } else { … … 355 356 356 357 357 while ( container[minimum].parent >=0 )358 minimum=container[minimum].parent;359 int s= minimum;360 int m= minimum;358 while ( _data[_minimum].parent >=0 ) 359 _minimum=_data[_minimum].parent; 360 int s=_minimum; 361 int m=_minimum; 361 362 do { 362 if ( comp(container[s].prio, container[minimum].prio) )minimum=s;363 s= container[s].right_neighbor;363 if ( _comp(_data[s].prio, _data[_minimum].prio) ) _minimum=s; 364 s=_data[s].right_neighbor; 364 365 } while ( s != m ); 365 366 } … … 368 369 int s=c; 369 370 do { 370 container[s].parent=-1;371 s= container[s].right_neighbor;371 _data[s].parent=-1; 372 s=_data[s].right_neighbor; 372 373 } while ( s != c ); 373 374 } … … 377 378 *Replacing a from the children of b. 378 379 */ 379 -- container[b].degree;380 381 if ( container[b].degree !=0 ) {382 int child= container[b].child;380 --_data[b].degree; 381 382 if ( _data[b].degree !=0 ) { 383 int child=_data[b].child; 383 384 if ( child==a ) 384 container[b].child=container[child].right_neighbor;385 _data[b].child=_data[child].right_neighbor; 385 386 unlace(a); 386 387 } … … 388 389 389 390 /*Lacing a to the roots.*/ 390 int right= container[minimum].right_neighbor;391 container[minimum].right_neighbor=a;392 container[a].left_neighbor=minimum;393 container[a].right_neighbor=right;394 container[right].left_neighbor=a;395 396 container[a].parent=-1;397 container[a].marked=false;391 int right=_data[_minimum].right_neighbor; 392 _data[_minimum].right_neighbor=a; 393 _data[a].left_neighbor=_minimum; 394 _data[a].right_neighbor=right; 395 _data[right].left_neighbor=a; 396 397 _data[a].parent=-1; 398 _data[a].marked=false; 398 399 } 399 400 400 401 void cascade(int a) { 401 if ( container[a].parent!=-1 ) {402 int p= container[a].parent;403 404 if ( container[a].marked==false ) container[a].marked=true;402 if ( _data[a].parent!=-1 ) { 403 int p=_data[a].parent; 404 405 if ( _data[a].marked==false ) _data[a].marked=true; 405 406 else { 406 407 cut(a,p); … … 414 415 415 416 /*Lacing b under a.*/ 416 container[b].parent=a;417 418 if ( container[a].degree==0) {419 container[b].left_neighbor=b;420 container[b].right_neighbor=b;421 container[a].child=b;417 _data[b].parent=a; 418 419 if (_data[a].degree==0) { 420 _data[b].left_neighbor=b; 421 _data[b].right_neighbor=b; 422 _data[a].child=b; 422 423 } else { 423 int child= container[a].child;424 int last_child= container[child].left_neighbor;425 container[child].left_neighbor=b;426 container[b].right_neighbor=child;427 container[last_child].right_neighbor=b;428 container[b].left_neighbor=last_child;429 } 430 431 ++ container[a].degree;432 433 container[b].marked=false;424 int child=_data[a].child; 425 int last_child=_data[child].left_neighbor; 426 _data[child].left_neighbor=b; 427 _data[b].right_neighbor=child; 428 _data[last_child].right_neighbor=b; 429 _data[b].left_neighbor=last_child; 430 } 431 432 ++_data[a].degree; 433 434 _data[b].marked=false; 434 435 } 435 436 … … 438 439 */ 439 440 void unlace(int a) { 440 int leftn= container[a].left_neighbor;441 int rightn= container[a].right_neighbor;442 container[leftn].right_neighbor=rightn;443 container[rightn].left_neighbor=leftn;444 } 445 446 447 class store {441 int leftn=_data[a].left_neighbor; 442 int rightn=_data[a].right_neighbor; 443 _data[leftn].right_neighbor=rightn; 444 _data[rightn].left_neighbor=leftn; 445 } 446 447 448 class Store { 448 449 friend class FibHeap; 449 450 … … 458 459 Prio prio; 459 460 460 store() : parent(-1), child(-1), degree(), marked(false), in(true) {}461 Store() : parent(-1), child(-1), degree(), marked(false), in(true) {} 461 462 }; 462 463 }; -
lemon/radix_heap.h
r728 r730 42 42 /// item's priority. 43 43 /// 44 /// \param _ItemIntMapA read and writable Item int map, used internally44 /// \param IM A read and writable Item int map, used internally 45 45 /// to handle the cross references. 46 46 /// 47 47 /// \see BinHeap 48 48 /// \see Dijkstra 49 template <typename _ItemIntMap>49 template <typename IM> 50 50 class RadixHeap { 51 51 52 52 public: 53 typedef typename _ItemIntMap::Key Item;53 typedef typename IM::Key Item; 54 54 typedef int Prio; 55 typedef _ItemIntMapItemIntMap;55 typedef IM ItemIntMap; 56 56 57 57 /// \brief Exception thrown by RadixHeap. … … 100 100 std::vector<RadixBox> boxes; 101 101 102 ItemIntMap & iim;102 ItemIntMap &_iim; 103 103 104 104 … … 108 108 /// The constructor. 109 109 /// 110 /// \param _iimIt should be given to the constructor, since it is used110 /// \param map It should be given to the constructor, since it is used 111 111 /// internally to handle the cross references. The value of the map 112 112 /// should be PRE_HEAP (-1) for each element. … … 114 114 /// \param minimal The initial minimal value of the heap. 115 115 /// \param capacity It determines the initial capacity of the heap. 116 RadixHeap(ItemIntMap & _iim, int minimal = 0, int capacity = 0)117 : iim(_iim) {116 RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0) 117 : _iim(map) { 118 118 boxes.push_back(RadixBox(minimal, 1)); 119 119 boxes.push_back(RadixBox(minimal + 1, 1)); … … 269 269 data[data[index].next].prev = index; 270 270 } 271 iim[data[index].item] = index;271 _iim[data[index].item] = index; 272 272 } 273 273 data.pop_back(); … … 283 283 void push(const Item &i, const Prio &p) { 284 284 int n = data.size(); 285 iim.set(i, n);285 _iim.set(i, n); 286 286 data.push_back(RadixItem(i, p)); 287 287 while (lower(boxes.size() - 1, p)) { … … 317 317 moveDown(); 318 318 int index = boxes[0].first; 319 iim[data[index].item] = POST_HEAP;319 _iim[data[index].item] = POST_HEAP; 320 320 remove(index); 321 321 relocate_last(index); … … 328 328 /// \param i The item to erase. 329 329 void erase(const Item &i) { 330 int index = iim[i];331 iim[i] = POST_HEAP;330 int index = _iim[i]; 331 _iim[i] = POST_HEAP; 332 332 remove(index); 333 333 relocate_last(index); … … 340 340 /// \param i The item. 341 341 Prio operator[](const Item &i) const { 342 int idx = iim[i];342 int idx = _iim[i]; 343 343 return data[idx].prio; 344 344 } … … 353 353 /// \param p The priority. 354 354 void set(const Item &i, const Prio &p) { 355 int idx = iim[i];355 int idx = _iim[i]; 356 356 if( idx < 0 ) { 357 357 push(i, p); … … 375 375 /// \param p The priority. 376 376 void decrease(const Item &i, const Prio &p) { 377 int idx = iim[i];377 int idx = _iim[i]; 378 378 data[idx].prio = p; 379 379 bubble_down(idx); … … 387 387 /// \param p The priority. 388 388 void increase(const Item &i, const Prio &p) { 389 int idx = iim[i];389 int idx = _iim[i]; 390 390 data[idx].prio = p; 391 391 bubble_up(idx); … … 401 401 /// \param i The item. 402 402 State state(const Item &i) const { 403 int s = iim[i];403 int s = _iim[i]; 404 404 if( s >= 0 ) s = 0; 405 405 return State(s); … … 420 420 erase(i); 421 421 } 422 iim[i] = st;422 _iim[i] = st; 423 423 break; 424 424 case IN_HEAP:
Note: See TracChangeset
for help on using the changeset viewer.