Changeset 711:28cfac049a6a in lemon-1.2 for lemon/radix_heap.h
- Timestamp:
- 07/08/09 17:47:01 (15 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/radix_heap.h
r710 r711 59 59 /// RadixHeap with a priority smaller than the last erased one. 60 60 /// \see RadixHeap 61 class UnderFlowPriorityError : public Exception {61 class PriorityUnderflowError : public Exception { 62 62 public: 63 63 virtual const char* what() const throw() { 64 return "lemon::RadixHeap:: UnderFlowPriorityError";64 return "lemon::RadixHeap::PriorityUnderflowError"; 65 65 } 66 66 }; … … 95 95 }; 96 96 97 std::vector<RadixItem> data;98 std::vector<RadixBox> boxes;97 std::vector<RadixItem> _data; 98 std::vector<RadixBox> _boxes; 99 99 100 100 ItemIntMap &_iim; … … 113 113 : _iim(map) 114 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)) {115 _boxes.push_back(RadixBox(minimum, 1)); 116 _boxes.push_back(RadixBox(minimum + 1, 1)); 117 while (lower(_boxes.size() - 1, capacity + minimum - 1)) { 118 118 extend(); 119 119 } … … 123 123 /// 124 124 /// This function returns the number of items stored in the heap. 125 int size() const { return data.size(); }125 int size() const { return _data.size(); } 126 126 127 127 /// \brief Check if the heap is empty. 128 128 /// 129 129 /// This function returns \c true if the heap is empty. 130 bool empty() const { return data.empty(); }130 bool empty() const { return _data.empty(); } 131 131 132 132 /// \brief Make the heap empty. … … 140 140 /// \param capacity The capacity of the heap. 141 141 void clear(int minimum = 0, int capacity = 0) { 142 data.clear();boxes.clear();143 boxes.push_back(RadixBox(minimum, 1));144 boxes.push_back(RadixBox(minimum + 1, 1));145 while (lower( boxes.size() - 1, capacity + minimum - 1)) {142 _data.clear(); _boxes.clear(); 143 _boxes.push_back(RadixBox(minimum, 1)); 144 _boxes.push_back(RadixBox(minimum + 1, 1)); 145 while (lower(_boxes.size() - 1, capacity + minimum - 1)) { 146 146 extend(); 147 147 } … … 151 151 152 152 bool upper(int box, Prio pr) { 153 return pr < boxes[box].min;153 return pr < _boxes[box].min; 154 154 } 155 155 156 156 bool lower(int box, Prio pr) { 157 return pr >= boxes[box].min +boxes[box].size;157 return pr >= _boxes[box].min + _boxes[box].size; 158 158 } 159 159 160 160 // Remove item from the box list 161 161 void remove(int index) { 162 if ( data[index].prev >= 0) {163 data[data[index].prev].next =data[index].next;162 if (_data[index].prev >= 0) { 163 _data[_data[index].prev].next = _data[index].next; 164 164 } else { 165 boxes[data[index].box].first =data[index].next;166 } 167 if ( data[index].next >= 0) {168 data[data[index].next].prev =data[index].prev;165 _boxes[_data[index].box].first = _data[index].next; 166 } 167 if (_data[index].next >= 0) { 168 _data[_data[index].next].prev = _data[index].prev; 169 169 } 170 170 } … … 172 172 // Insert item into the box list 173 173 void insert(int box, int index) { 174 if ( boxes[box].first == -1) {175 boxes[box].first = index;176 data[index].next =data[index].prev = -1;174 if (_boxes[box].first == -1) { 175 _boxes[box].first = index; 176 _data[index].next = _data[index].prev = -1; 177 177 } else { 178 data[index].next =boxes[box].first;179 data[boxes[box].first].prev = index;180 data[index].prev = -1;181 boxes[box].first = index;182 } 183 data[index].box = box;178 _data[index].next = _boxes[box].first; 179 _data[_boxes[box].first].prev = index; 180 _data[index].prev = -1; 181 _boxes[box].first = index; 182 } 183 _data[index].box = box; 184 184 } 185 185 186 186 // Add a new box to the box list 187 187 void extend() { 188 int min = boxes.back().min +boxes.back().size;189 int bs = 2 * boxes.back().size;190 boxes.push_back(RadixBox(min, bs));188 int min = _boxes.back().min + _boxes.back().size; 189 int bs = 2 * _boxes.back().size; 190 _boxes.push_back(RadixBox(min, bs)); 191 191 } 192 192 193 193 // Move an item up into the proper box. 194 void bubble _up(int index) {195 if (!lower( data[index].box,data[index].prio)) return;194 void bubbleUp(int index) { 195 if (!lower(_data[index].box, _data[index].prio)) return; 196 196 remove(index); 197 int box = findUp( data[index].box,data[index].prio);197 int box = findUp(_data[index].box, _data[index].prio); 198 198 insert(box, index); 199 199 } … … 202 202 int findUp(int start, int pr) { 203 203 while (lower(start, pr)) { 204 if (++start == int( boxes.size())) {204 if (++start == int(_boxes.size())) { 205 205 extend(); 206 206 } … … 210 210 211 211 // Move an item down into the proper box 212 void bubble _down(int index) {213 if (!upper( data[index].box,data[index].prio)) return;212 void bubbleDown(int index) { 213 if (!upper(_data[index].box, _data[index].prio)) return; 214 214 remove(index); 215 int box = findDown( data[index].box,data[index].prio);215 int box = findDown(_data[index].box, _data[index].prio); 216 216 insert(box, index); 217 217 } … … 220 220 int findDown(int start, int pr) { 221 221 while (upper(start, pr)) { 222 if (--start < 0) throw UnderFlowPriorityError();222 if (--start < 0) throw PriorityUnderflowError(); 223 223 } 224 224 return start; … … 228 228 int findFirst() { 229 229 int first = 0; 230 while ( boxes[first].first == -1) ++first;230 while (_boxes[first].first == -1) ++first; 231 231 return first; 232 232 } … … 234 234 // Gives back the minimum priority of the given box 235 235 int minValue(int box) { 236 int min = data[boxes[box].first].prio;237 for (int k = boxes[box].first; k != -1; k =data[k].next) {238 if ( data[k].prio < min) min =data[k].prio;236 int min = _data[_boxes[box].first].prio; 237 for (int k = _boxes[box].first; k != -1; k = _data[k].next) { 238 if (_data[k].prio < min) min = _data[k].prio; 239 239 } 240 240 return min; … … 247 247 int min = minValue(box); 248 248 for (int i = 0; i <= box; ++i) { 249 boxes[i].min = min;250 min += boxes[i].size;251 } 252 int curr = boxes[box].first, next;249 _boxes[i].min = min; 250 min += _boxes[i].size; 251 } 252 int curr = _boxes[box].first, next; 253 253 while (curr != -1) { 254 next = data[curr].next;255 bubble _down(curr);254 next = _data[curr].next; 255 bubbleDown(curr); 256 256 curr = next; 257 257 } 258 258 } 259 259 260 void relocate _last(int index) {261 if (index != int( data.size()) - 1) {262 data[index] =data.back();263 if ( data[index].prev != -1) {264 data[data[index].prev].next = index;260 void relocateLast(int index) { 261 if (index != int(_data.size()) - 1) { 262 _data[index] = _data.back(); 263 if (_data[index].prev != -1) { 264 _data[_data[index].prev].next = index; 265 265 } else { 266 boxes[data[index].box].first = index;266 _boxes[_data[index].box].first = index; 267 267 } 268 if ( data[index].next != -1) {269 data[data[index].next].prev = index;268 if (_data[index].next != -1) { 269 _data[_data[index].next].prev = index; 270 270 } 271 _iim[ data[index].item] = index;272 } 273 data.pop_back();271 _iim[_data[index].item] = index; 272 } 273 _data.pop_back(); 274 274 } 275 275 … … 285 285 /// \warning This method may throw an \c UnderFlowPriorityException. 286 286 void push(const Item &i, const Prio &p) { 287 int n = data.size();287 int n = _data.size(); 288 288 _iim.set(i, n); 289 data.push_back(RadixItem(i, p));290 while (lower( boxes.size() - 1, p)) {289 _data.push_back(RadixItem(i, p)); 290 while (lower(_boxes.size() - 1, p)) { 291 291 extend(); 292 292 } 293 int box = findDown( boxes.size() - 1, p);293 int box = findDown(_boxes.size() - 1, p); 294 294 insert(box, n); 295 295 } … … 301 301 Item top() const { 302 302 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown(); 303 return data[boxes[0].first].item;303 return _data[_boxes[0].first].item; 304 304 } 305 305 … … 310 310 Prio prio() const { 311 311 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown(); 312 return data[boxes[0].first].prio;312 return _data[_boxes[0].first].prio; 313 313 } 314 314 … … 319 319 void pop() { 320 320 moveDown(); 321 int index = boxes[0].first;322 _iim[ data[index].item] = POST_HEAP;321 int index = _boxes[0].first; 322 _iim[_data[index].item] = POST_HEAP; 323 323 remove(index); 324 relocate _last(index);324 relocateLast(index); 325 325 } 326 326 … … 335 335 _iim[i] = POST_HEAP; 336 336 remove(index); 337 relocate _last(index);337 relocateLast(index); 338 338 } 339 339 … … 345 345 Prio operator[](const Item &i) const { 346 346 int idx = _iim[i]; 347 return data[idx].prio;347 return _data[idx].prio; 348 348 } 349 349 … … 363 363 push(i, p); 364 364 } 365 else if( p >= data[idx].prio ) {366 data[idx].prio = p;367 bubble _up(idx);365 else if( p >= _data[idx].prio ) { 366 _data[idx].prio = p; 367 bubbleUp(idx); 368 368 } else { 369 data[idx].prio = p;370 bubble _down(idx);369 _data[idx].prio = p; 370 bubbleDown(idx); 371 371 } 372 372 } … … 381 381 void decrease(const Item &i, const Prio &p) { 382 382 int idx = _iim[i]; 383 data[idx].prio = p;384 bubble _down(idx);383 _data[idx].prio = p; 384 bubbleDown(idx); 385 385 } 386 386 … … 393 393 void increase(const Item &i, const Prio &p) { 394 394 int idx = _iim[i]; 395 data[idx].prio = p;396 bubble _up(idx);395 _data[idx].prio = p; 396 bubbleUp(idx); 397 397 } 398 398
Note: See TracChangeset
for help on using the changeset viewer.