1.1 --- a/lemon/bin_heap.h Wed Jul 08 17:22:36 2009 +0200
1.2 +++ b/lemon/bin_heap.h Wed Jul 08 17:47:01 2009 +0200
1.3 @@ -124,12 +124,12 @@
1.4 private:
1.5 static int parent(int i) { return (i-1)/2; }
1.6
1.7 - static int second_child(int i) { return 2*i+2; }
1.8 + static int secondChild(int i) { return 2*i+2; }
1.9 bool less(const Pair &p1, const Pair &p2) const {
1.10 return _comp(p1.second, p2.second);
1.11 }
1.12
1.13 - int bubble_up(int hole, Pair p) {
1.14 + int bubbleUp(int hole, Pair p) {
1.15 int par = parent(hole);
1.16 while( hole>0 && less(p,_data[par]) ) {
1.17 move(_data[par],hole);
1.18 @@ -140,8 +140,8 @@
1.19 return hole;
1.20 }
1.21
1.22 - int bubble_down(int hole, Pair p, int length) {
1.23 - int child = second_child(hole);
1.24 + int bubbleDown(int hole, Pair p, int length) {
1.25 + int child = secondChild(hole);
1.26 while(child < length) {
1.27 if( less(_data[child-1], _data[child]) ) {
1.28 --child;
1.29 @@ -150,7 +150,7 @@
1.30 goto ok;
1.31 move(_data[child], hole);
1.32 hole = child;
1.33 - child = second_child(hole);
1.34 + child = secondChild(hole);
1.35 }
1.36 child--;
1.37 if( child<length && less(_data[child], p) ) {
1.38 @@ -178,7 +178,7 @@
1.39 void push(const Pair &p) {
1.40 int n = _data.size();
1.41 _data.resize(n+1);
1.42 - bubble_up(n, p);
1.43 + bubbleUp(n, p);
1.44 }
1.45
1.46 /// \brief Insert an item into the heap with the given priority.
1.47 @@ -214,7 +214,7 @@
1.48 int n = _data.size()-1;
1.49 _iim.set(_data[0].first, POST_HEAP);
1.50 if (n > 0) {
1.51 - bubble_down(0, _data[n], n);
1.52 + bubbleDown(0, _data[n], n);
1.53 }
1.54 _data.pop_back();
1.55 }
1.56 @@ -230,8 +230,8 @@
1.57 int n = _data.size()-1;
1.58 _iim.set(_data[h].first, POST_HEAP);
1.59 if( h < n ) {
1.60 - if ( bubble_up(h, _data[n]) == h) {
1.61 - bubble_down(h, _data[n], n);
1.62 + if ( bubbleUp(h, _data[n]) == h) {
1.63 + bubbleDown(h, _data[n], n);
1.64 }
1.65 }
1.66 _data.pop_back();
1.67 @@ -261,10 +261,10 @@
1.68 push(i,p);
1.69 }
1.70 else if( _comp(p, _data[idx].second) ) {
1.71 - bubble_up(idx, Pair(i,p));
1.72 + bubbleUp(idx, Pair(i,p));
1.73 }
1.74 else {
1.75 - bubble_down(idx, Pair(i,p), _data.size());
1.76 + bubbleDown(idx, Pair(i,p), _data.size());
1.77 }
1.78 }
1.79
1.80 @@ -276,7 +276,7 @@
1.81 /// \pre \e i must be stored in the heap with priority at least \e p.
1.82 void decrease(const Item &i, const Prio &p) {
1.83 int idx = _iim[i];
1.84 - bubble_up(idx, Pair(i,p));
1.85 + bubbleUp(idx, Pair(i,p));
1.86 }
1.87
1.88 /// \brief Increase the priority of an item to the given value.
1.89 @@ -287,7 +287,7 @@
1.90 /// \pre \e i must be stored in the heap with priority at most \e p.
1.91 void increase(const Item &i, const Prio &p) {
1.92 int idx = _iim[i];
1.93 - bubble_down(idx, Pair(i,p), _data.size());
1.94 + bubbleDown(idx, Pair(i,p), _data.size());
1.95 }
1.96
1.97 /// \brief Return the state of an item.
2.1 --- a/lemon/bucket_heap.h Wed Jul 08 17:22:36 2009 +0200
2.2 +++ b/lemon/bucket_heap.h Wed Jul 08 17:47:01 2009 +0200
2.3 @@ -142,7 +142,7 @@
2.4
2.5 private:
2.6
2.7 - void relocate_last(int idx) {
2.8 + void relocateLast(int idx) {
2.9 if (idx + 1 < int(_data.size())) {
2.10 _data[idx] = _data.back();
2.11 if (_data[idx].prev != -1) {
2.12 @@ -243,7 +243,7 @@
2.13 int idx = _first[_minimum];
2.14 _iim[_data[idx].item] = -2;
2.15 unlace(idx);
2.16 - relocate_last(idx);
2.17 + relocateLast(idx);
2.18 }
2.19
2.20 /// \brief Remove the given item from the heap.
2.21 @@ -256,7 +256,7 @@
2.22 int idx = _iim[i];
2.23 _iim[_data[idx].item] = -2;
2.24 unlace(idx);
2.25 - relocate_last(idx);
2.26 + relocateLast(idx);
2.27 }
2.28
2.29 /// \brief The priority of the given item.
3.1 --- a/lemon/fib_heap.h Wed Jul 08 17:22:36 2009 +0200
3.2 +++ b/lemon/fib_heap.h Wed Jul 08 17:47:01 2009 +0200
3.3 @@ -188,7 +188,7 @@
3.4 if ( _data[_minimum].left_neighbor==_minimum ) {
3.5 _data[_minimum].in=false;
3.6 if ( _data[_minimum].degree!=0 ) {
3.7 - makeroot(_data[_minimum].child);
3.8 + makeRoot(_data[_minimum].child);
3.9 _minimum=_data[_minimum].child;
3.10 balance();
3.11 }
3.12 @@ -201,7 +201,7 @@
3.13 int child=_data[_minimum].child;
3.14 int last_child=_data[child].left_neighbor;
3.15
3.16 - makeroot(child);
3.17 + makeRoot(child);
3.18
3.19 _data[left].right_neighbor=child;
3.20 _data[child].left_neighbor=left;
3.21 @@ -372,7 +372,7 @@
3.22 } while ( s != m );
3.23 }
3.24
3.25 - void makeroot(int c) {
3.26 + void makeRoot(int c) {
3.27 int s=c;
3.28 do {
3.29 _data[s].parent=-1;
4.1 --- a/lemon/radix_heap.h Wed Jul 08 17:22:36 2009 +0200
4.2 +++ b/lemon/radix_heap.h Wed Jul 08 17:47:01 2009 +0200
4.3 @@ -58,10 +58,10 @@
4.4 /// This exception is thrown when an item is inserted into a
4.5 /// RadixHeap with a priority smaller than the last erased one.
4.6 /// \see RadixHeap
4.7 - class UnderFlowPriorityError : public Exception {
4.8 + class PriorityUnderflowError : public Exception {
4.9 public:
4.10 virtual const char* what() const throw() {
4.11 - return "lemon::RadixHeap::UnderFlowPriorityError";
4.12 + return "lemon::RadixHeap::PriorityUnderflowError";
4.13 }
4.14 };
4.15
4.16 @@ -94,8 +94,8 @@
4.17 RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
4.18 };
4.19
4.20 - std::vector<RadixItem> data;
4.21 - std::vector<RadixBox> boxes;
4.22 + std::vector<RadixItem> _data;
4.23 + std::vector<RadixBox> _boxes;
4.24
4.25 ItemIntMap &_iim;
4.26
4.27 @@ -112,9 +112,9 @@
4.28 RadixHeap(ItemIntMap &map, int minimum = 0, int capacity = 0)
4.29 : _iim(map)
4.30 {
4.31 - boxes.push_back(RadixBox(minimum, 1));
4.32 - boxes.push_back(RadixBox(minimum + 1, 1));
4.33 - while (lower(boxes.size() - 1, capacity + minimum - 1)) {
4.34 + _boxes.push_back(RadixBox(minimum, 1));
4.35 + _boxes.push_back(RadixBox(minimum + 1, 1));
4.36 + while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
4.37 extend();
4.38 }
4.39 }
4.40 @@ -122,12 +122,12 @@
4.41 /// \brief The number of items stored in the heap.
4.42 ///
4.43 /// This function returns the number of items stored in the heap.
4.44 - int size() const { return data.size(); }
4.45 + int size() const { return _data.size(); }
4.46
4.47 /// \brief Check if the heap is empty.
4.48 ///
4.49 /// This function returns \c true if the heap is empty.
4.50 - bool empty() const { return data.empty(); }
4.51 + bool empty() const { return _data.empty(); }
4.52
4.53 /// \brief Make the heap empty.
4.54 ///
4.55 @@ -139,10 +139,10 @@
4.56 /// \param minimum The minimum value of the heap.
4.57 /// \param capacity The capacity of the heap.
4.58 void clear(int minimum = 0, int capacity = 0) {
4.59 - data.clear(); boxes.clear();
4.60 - boxes.push_back(RadixBox(minimum, 1));
4.61 - boxes.push_back(RadixBox(minimum + 1, 1));
4.62 - while (lower(boxes.size() - 1, capacity + minimum - 1)) {
4.63 + _data.clear(); _boxes.clear();
4.64 + _boxes.push_back(RadixBox(minimum, 1));
4.65 + _boxes.push_back(RadixBox(minimum + 1, 1));
4.66 + while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
4.67 extend();
4.68 }
4.69 }
4.70 @@ -150,58 +150,58 @@
4.71 private:
4.72
4.73 bool upper(int box, Prio pr) {
4.74 - return pr < boxes[box].min;
4.75 + return pr < _boxes[box].min;
4.76 }
4.77
4.78 bool lower(int box, Prio pr) {
4.79 - return pr >= boxes[box].min + boxes[box].size;
4.80 + return pr >= _boxes[box].min + _boxes[box].size;
4.81 }
4.82
4.83 // Remove item from the box list
4.84 void remove(int index) {
4.85 - if (data[index].prev >= 0) {
4.86 - data[data[index].prev].next = data[index].next;
4.87 + if (_data[index].prev >= 0) {
4.88 + _data[_data[index].prev].next = _data[index].next;
4.89 } else {
4.90 - boxes[data[index].box].first = data[index].next;
4.91 + _boxes[_data[index].box].first = _data[index].next;
4.92 }
4.93 - if (data[index].next >= 0) {
4.94 - data[data[index].next].prev = data[index].prev;
4.95 + if (_data[index].next >= 0) {
4.96 + _data[_data[index].next].prev = _data[index].prev;
4.97 }
4.98 }
4.99
4.100 // Insert item into the box list
4.101 void insert(int box, int index) {
4.102 - if (boxes[box].first == -1) {
4.103 - boxes[box].first = index;
4.104 - data[index].next = data[index].prev = -1;
4.105 + if (_boxes[box].first == -1) {
4.106 + _boxes[box].first = index;
4.107 + _data[index].next = _data[index].prev = -1;
4.108 } else {
4.109 - data[index].next = boxes[box].first;
4.110 - data[boxes[box].first].prev = index;
4.111 - data[index].prev = -1;
4.112 - boxes[box].first = index;
4.113 + _data[index].next = _boxes[box].first;
4.114 + _data[_boxes[box].first].prev = index;
4.115 + _data[index].prev = -1;
4.116 + _boxes[box].first = index;
4.117 }
4.118 - data[index].box = box;
4.119 + _data[index].box = box;
4.120 }
4.121
4.122 // Add a new box to the box list
4.123 void extend() {
4.124 - int min = boxes.back().min + boxes.back().size;
4.125 - int bs = 2 * boxes.back().size;
4.126 - boxes.push_back(RadixBox(min, bs));
4.127 + int min = _boxes.back().min + _boxes.back().size;
4.128 + int bs = 2 * _boxes.back().size;
4.129 + _boxes.push_back(RadixBox(min, bs));
4.130 }
4.131
4.132 // Move an item up into the proper box.
4.133 - void bubble_up(int index) {
4.134 - if (!lower(data[index].box, data[index].prio)) return;
4.135 + void bubbleUp(int index) {
4.136 + if (!lower(_data[index].box, _data[index].prio)) return;
4.137 remove(index);
4.138 - int box = findUp(data[index].box, data[index].prio);
4.139 + int box = findUp(_data[index].box, _data[index].prio);
4.140 insert(box, index);
4.141 }
4.142
4.143 // Find up the proper box for the item with the given priority
4.144 int findUp(int start, int pr) {
4.145 while (lower(start, pr)) {
4.146 - if (++start == int(boxes.size())) {
4.147 + if (++start == int(_boxes.size())) {
4.148 extend();
4.149 }
4.150 }
4.151 @@ -209,17 +209,17 @@
4.152 }
4.153
4.154 // Move an item down into the proper box
4.155 - void bubble_down(int index) {
4.156 - if (!upper(data[index].box, data[index].prio)) return;
4.157 + void bubbleDown(int index) {
4.158 + if (!upper(_data[index].box, _data[index].prio)) return;
4.159 remove(index);
4.160 - int box = findDown(data[index].box, data[index].prio);
4.161 + int box = findDown(_data[index].box, _data[index].prio);
4.162 insert(box, index);
4.163 }
4.164
4.165 // Find down the proper box for the item with the given priority
4.166 int findDown(int start, int pr) {
4.167 while (upper(start, pr)) {
4.168 - if (--start < 0) throw UnderFlowPriorityError();
4.169 + if (--start < 0) throw PriorityUnderflowError();
4.170 }
4.171 return start;
4.172 }
4.173 @@ -227,15 +227,15 @@
4.174 // Find the first non-empty box
4.175 int findFirst() {
4.176 int first = 0;
4.177 - while (boxes[first].first == -1) ++first;
4.178 + while (_boxes[first].first == -1) ++first;
4.179 return first;
4.180 }
4.181
4.182 // Gives back the minimum priority of the given box
4.183 int minValue(int box) {
4.184 - int min = data[boxes[box].first].prio;
4.185 - for (int k = boxes[box].first; k != -1; k = data[k].next) {
4.186 - if (data[k].prio < min) min = data[k].prio;
4.187 + int min = _data[_boxes[box].first].prio;
4.188 + for (int k = _boxes[box].first; k != -1; k = _data[k].next) {
4.189 + if (_data[k].prio < min) min = _data[k].prio;
4.190 }
4.191 return min;
4.192 }
4.193 @@ -246,31 +246,31 @@
4.194 if (box == 0) return;
4.195 int min = minValue(box);
4.196 for (int i = 0; i <= box; ++i) {
4.197 - boxes[i].min = min;
4.198 - min += boxes[i].size;
4.199 + _boxes[i].min = min;
4.200 + min += _boxes[i].size;
4.201 }
4.202 - int curr = boxes[box].first, next;
4.203 + int curr = _boxes[box].first, next;
4.204 while (curr != -1) {
4.205 - next = data[curr].next;
4.206 - bubble_down(curr);
4.207 + next = _data[curr].next;
4.208 + bubbleDown(curr);
4.209 curr = next;
4.210 }
4.211 }
4.212
4.213 - void relocate_last(int index) {
4.214 - if (index != int(data.size()) - 1) {
4.215 - data[index] = data.back();
4.216 - if (data[index].prev != -1) {
4.217 - data[data[index].prev].next = index;
4.218 + void relocateLast(int index) {
4.219 + if (index != int(_data.size()) - 1) {
4.220 + _data[index] = _data.back();
4.221 + if (_data[index].prev != -1) {
4.222 + _data[_data[index].prev].next = index;
4.223 } else {
4.224 - boxes[data[index].box].first = index;
4.225 + _boxes[_data[index].box].first = index;
4.226 }
4.227 - if (data[index].next != -1) {
4.228 - data[data[index].next].prev = index;
4.229 + if (_data[index].next != -1) {
4.230 + _data[_data[index].next].prev = index;
4.231 }
4.232 - _iim[data[index].item] = index;
4.233 + _iim[_data[index].item] = index;
4.234 }
4.235 - data.pop_back();
4.236 + _data.pop_back();
4.237 }
4.238
4.239 public:
4.240 @@ -284,13 +284,13 @@
4.241 /// \pre \e i must not be stored in the heap.
4.242 /// \warning This method may throw an \c UnderFlowPriorityException.
4.243 void push(const Item &i, const Prio &p) {
4.244 - int n = data.size();
4.245 + int n = _data.size();
4.246 _iim.set(i, n);
4.247 - data.push_back(RadixItem(i, p));
4.248 - while (lower(boxes.size() - 1, p)) {
4.249 + _data.push_back(RadixItem(i, p));
4.250 + while (lower(_boxes.size() - 1, p)) {
4.251 extend();
4.252 }
4.253 - int box = findDown(boxes.size() - 1, p);
4.254 + int box = findDown(_boxes.size() - 1, p);
4.255 insert(box, n);
4.256 }
4.257
4.258 @@ -300,7 +300,7 @@
4.259 /// \pre The heap must be non-empty.
4.260 Item top() const {
4.261 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
4.262 - return data[boxes[0].first].item;
4.263 + return _data[_boxes[0].first].item;
4.264 }
4.265
4.266 /// \brief The minimum priority.
4.267 @@ -309,7 +309,7 @@
4.268 /// \pre The heap must be non-empty.
4.269 Prio prio() const {
4.270 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
4.271 - return data[boxes[0].first].prio;
4.272 + return _data[_boxes[0].first].prio;
4.273 }
4.274
4.275 /// \brief Remove the item having minimum priority.
4.276 @@ -318,10 +318,10 @@
4.277 /// \pre The heap must be non-empty.
4.278 void pop() {
4.279 moveDown();
4.280 - int index = boxes[0].first;
4.281 - _iim[data[index].item] = POST_HEAP;
4.282 + int index = _boxes[0].first;
4.283 + _iim[_data[index].item] = POST_HEAP;
4.284 remove(index);
4.285 - relocate_last(index);
4.286 + relocateLast(index);
4.287 }
4.288
4.289 /// \brief Remove the given item from the heap.
4.290 @@ -334,7 +334,7 @@
4.291 int index = _iim[i];
4.292 _iim[i] = POST_HEAP;
4.293 remove(index);
4.294 - relocate_last(index);
4.295 + relocateLast(index);
4.296 }
4.297
4.298 /// \brief The priority of the given item.
4.299 @@ -344,7 +344,7 @@
4.300 /// \pre \e i must be in the heap.
4.301 Prio operator[](const Item &i) const {
4.302 int idx = _iim[i];
4.303 - return data[idx].prio;
4.304 + return _data[idx].prio;
4.305 }
4.306
4.307 /// \brief Set the priority of an item or insert it, if it is
4.308 @@ -362,12 +362,12 @@
4.309 if( idx < 0 ) {
4.310 push(i, p);
4.311 }
4.312 - else if( p >= data[idx].prio ) {
4.313 - data[idx].prio = p;
4.314 - bubble_up(idx);
4.315 + else if( p >= _data[idx].prio ) {
4.316 + _data[idx].prio = p;
4.317 + bubbleUp(idx);
4.318 } else {
4.319 - data[idx].prio = p;
4.320 - bubble_down(idx);
4.321 + _data[idx].prio = p;
4.322 + bubbleDown(idx);
4.323 }
4.324 }
4.325
4.326 @@ -380,8 +380,8 @@
4.327 /// \warning This method may throw an \c UnderFlowPriorityException.
4.328 void decrease(const Item &i, const Prio &p) {
4.329 int idx = _iim[i];
4.330 - data[idx].prio = p;
4.331 - bubble_down(idx);
4.332 + _data[idx].prio = p;
4.333 + bubbleDown(idx);
4.334 }
4.335
4.336 /// \brief Increase the priority of an item to the given value.
4.337 @@ -392,8 +392,8 @@
4.338 /// \pre \e i must be stored in the heap with priority at most \e p.
4.339 void increase(const Item &i, const Prio &p) {
4.340 int idx = _iim[i];
4.341 - data[idx].prio = p;
4.342 - bubble_up(idx);
4.343 + _data[idx].prio = p;
4.344 + bubbleUp(idx);
4.345 }
4.346
4.347 /// \brief Return the state of an item.