Changeset 758:28cfac049a6a in lemon
 Timestamp:
 07/08/09 17:47:01 (10 years ago)
 Branch:
 default
 Phase:
 public
 Location:
 lemon
 Files:

 4 edited
Legend:
 Unmodified
 Added
 Removed

lemon/bin_heap.h
r757 r758 125 125 static int parent(int i) { return (i1)/2; } 126 126 127 static int second _child(int i) { return 2*i+2; }127 static int secondChild(int i) { return 2*i+2; } 128 128 bool less(const Pair &p1, const Pair &p2) const { 129 129 return _comp(p1.second, p2.second); 130 130 } 131 131 132 int bubble _up(int hole, Pair p) {132 int bubbleUp(int hole, Pair p) { 133 133 int par = parent(hole); 134 134 while( hole>0 && less(p,_data[par]) ) { … … 141 141 } 142 142 143 int bubble _down(int hole, Pair p, int length) {144 int child = second _child(hole);143 int bubbleDown(int hole, Pair p, int length) { 144 int child = secondChild(hole); 145 145 while(child < length) { 146 146 if( less(_data[child1], _data[child]) ) { … … 151 151 move(_data[child], hole); 152 152 hole = child; 153 child = second _child(hole);153 child = secondChild(hole); 154 154 } 155 155 child; … … 179 179 int n = _data.size(); 180 180 _data.resize(n+1); 181 bubble _up(n, p);181 bubbleUp(n, p); 182 182 } 183 183 … … 215 215 _iim.set(_data[0].first, POST_HEAP); 216 216 if (n > 0) { 217 bubble _down(0, _data[n], n);217 bubbleDown(0, _data[n], n); 218 218 } 219 219 _data.pop_back(); … … 231 231 _iim.set(_data[h].first, POST_HEAP); 232 232 if( h < n ) { 233 if ( bubble _up(h, _data[n]) == h) {234 bubble _down(h, _data[n], n);233 if ( bubbleUp(h, _data[n]) == h) { 234 bubbleDown(h, _data[n], n); 235 235 } 236 236 } … … 262 262 } 263 263 else if( _comp(p, _data[idx].second) ) { 264 bubble _up(idx, Pair(i,p));264 bubbleUp(idx, Pair(i,p)); 265 265 } 266 266 else { 267 bubble _down(idx, Pair(i,p), _data.size());267 bubbleDown(idx, Pair(i,p), _data.size()); 268 268 } 269 269 } … … 277 277 void decrease(const Item &i, const Prio &p) { 278 278 int idx = _iim[i]; 279 bubble _up(idx, Pair(i,p));279 bubbleUp(idx, Pair(i,p)); 280 280 } 281 281 … … 288 288 void increase(const Item &i, const Prio &p) { 289 289 int idx = _iim[i]; 290 bubble _down(idx, Pair(i,p), _data.size());290 bubbleDown(idx, Pair(i,p), _data.size()); 291 291 } 292 292 
lemon/bucket_heap.h
r757 r758 143 143 private: 144 144 145 void relocate _last(int idx) {145 void relocateLast(int idx) { 146 146 if (idx + 1 < int(_data.size())) { 147 147 _data[idx] = _data.back(); … … 244 244 _iim[_data[idx].item] = 2; 245 245 unlace(idx); 246 relocate _last(idx);246 relocateLast(idx); 247 247 } 248 248 … … 257 257 _iim[_data[idx].item] = 2; 258 258 unlace(idx); 259 relocate _last(idx);259 relocateLast(idx); 260 260 } 261 261 
lemon/fib_heap.h
r757 r758 189 189 _data[_minimum].in=false; 190 190 if ( _data[_minimum].degree!=0 ) { 191 make root(_data[_minimum].child);191 makeRoot(_data[_minimum].child); 192 192 _minimum=_data[_minimum].child; 193 193 balance(); … … 202 202 int last_child=_data[child].left_neighbor; 203 203 204 make root(child);204 makeRoot(child); 205 205 206 206 _data[left].right_neighbor=child; … … 373 373 } 374 374 375 void make root(int c) {375 void makeRoot(int c) { 376 376 int s=c; 377 377 do { 
lemon/radix_heap.h
r757 r758 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.