Changeset 1717:75fe24093ded in lemon0.x for lemon/radix_heap.h
 Timestamp:
 10/14/05 12:40:00 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2244
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/radix_heap.h
r1435 r1717 27 27 namespace lemon { 28 28 29 /// \addtogroup auxdat30 /// @{31 32 29 /// \brief Exception thrown by RadixHeap. 33 30 /// … … 44 41 }; 45 42 43 /// \ingroup auxdata 44 /// 46 45 /// \brief A Radix Heap implementation. 47 46 /// … … 109 108 /// 110 109 /// The constructor. 111 /// \param _iim should be given to the constructor, since it is used112 /// internally to handle the cross references. The value of the map113 /// should be PRE_HEAP (1) for each element.114 explicit RadixHeap(ItemIntMap &_iim) : iim(_iim) {115 boxes.push_back(RadixBox(0, 1));116 boxes.push_back(RadixBox(1, 1));117 }118 119 /// \brief The constructor.120 ///121 /// The constructor.122 110 /// 123 111 /// \param _iim It should be given to the constructor, since it is used … … 125 113 /// should be PRE_HEAP (1) for each element. 126 114 /// 115 /// \param minimal The initial minimal value of the heap. 127 116 /// \param capacity It determines the initial capacity of the heap. 128 RadixHeap(ItemIntMap &_iim, int capacity) : iim(_iim) { 129 boxes.push_back(RadixBox(0, 1)); 130 boxes.push_back(RadixBox(1, 1)); 131 while (upper(boxes.back(), capacity)) { 117 RadixHeap(ItemIntMap &_iim, int minimal = 0, int capacity = 0) 118 : iim(_iim) { 119 boxes.push_back(RadixBox(minimal, 1)); 120 boxes.push_back(RadixBox(minimal + 1, 1)); 121 while (lower(boxes.size()  1, capacity + minimal  1)) { 132 122 extend(); 133 123 } … … 142 132 /// Returns \c true if and only if the heap stores no items. 143 133 bool empty() const { return data.empty(); } 134 135 /// \brief Make empty this heap. 136 /// 137 /// Make empty this heap. 138 void clear(int minimal = 0, int capacity = 0) { 139 for (int i = 0; i < (int)data.size(); ++i) { 140 iim[data[i].item] = 2; 141 } 142 data.clear(); boxes.clear(); 143 boxes.push_back(RadixBox(minimal, 1)); 144 boxes.push_back(RadixBox(minimal + 1, 1)); 145 while (lower(boxes.size()  1, capacity + minimal  1)) { 146 extend(); 147 } 148 } 144 149 145 150 private: … … 272 277 public: 273 278 274 /// \brief Insert an item into the heap with the given heap.279 /// \brief Insert an item into the heap with the given priority. 275 280 /// 276 281 /// Adds \c i to the heap with priority \c p. … … 293 298 /// \pre The heap must be nonempty. 294 299 Item top() const { 295 const_cast<RadixHeap<Item, ItemIntMap> *>(this)>moveDown();300 const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown(); 296 301 return data[boxes[0].first].item; 297 302 } … … 302 307 /// \pre The heap must be nonempty. 303 308 Prio prio() const { 304 const_cast<RadixHeap<Item, ItemIntMap> *>(this)>moveDown();309 const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown(); 305 310 return data[boxes[0].first].prio; 306 311 }
Note: See TracChangeset
for help on using the changeset viewer.