1.1 --- a/lemon/radix_heap.h Wed Jul 08 17:22:36 2009 +0200
1.2 +++ b/lemon/radix_heap.h Wed Jul 08 17:47:01 2009 +0200
1.3 @@ -58,10 +58,10 @@
1.4 /// This exception is thrown when an item is inserted into a
1.5 /// RadixHeap with a priority smaller than the last erased one.
1.6 /// \see RadixHeap
1.7 - class UnderFlowPriorityError : public Exception {
1.8 + class PriorityUnderflowError : public Exception {
1.9 public:
1.10 virtual const char* what() const throw() {
1.11 - return "lemon::RadixHeap::UnderFlowPriorityError";
1.12 + return "lemon::RadixHeap::PriorityUnderflowError";
1.13 }
1.14 };
1.15
1.16 @@ -94,8 +94,8 @@
1.17 RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
1.18 };
1.19
1.20 - std::vector<RadixItem> data;
1.21 - std::vector<RadixBox> boxes;
1.22 + std::vector<RadixItem> _data;
1.23 + std::vector<RadixBox> _boxes;
1.24
1.25 ItemIntMap &_iim;
1.26
1.27 @@ -112,9 +112,9 @@
1.28 RadixHeap(ItemIntMap &map, int minimum = 0, int capacity = 0)
1.29 : _iim(map)
1.30 {
1.31 - boxes.push_back(RadixBox(minimum, 1));
1.32 - boxes.push_back(RadixBox(minimum + 1, 1));
1.33 - while (lower(boxes.size() - 1, capacity + minimum - 1)) {
1.34 + _boxes.push_back(RadixBox(minimum, 1));
1.35 + _boxes.push_back(RadixBox(minimum + 1, 1));
1.36 + while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
1.37 extend();
1.38 }
1.39 }
1.40 @@ -122,12 +122,12 @@
1.41 /// \brief The number of items stored in the heap.
1.42 ///
1.43 /// This function returns the number of items stored in the heap.
1.44 - int size() const { return data.size(); }
1.45 + int size() const { return _data.size(); }
1.46
1.47 /// \brief Check if the heap is empty.
1.48 ///
1.49 /// This function returns \c true if the heap is empty.
1.50 - bool empty() const { return data.empty(); }
1.51 + bool empty() const { return _data.empty(); }
1.52
1.53 /// \brief Make the heap empty.
1.54 ///
1.55 @@ -139,10 +139,10 @@
1.56 /// \param minimum The minimum value of the heap.
1.57 /// \param capacity The capacity of the heap.
1.58 void clear(int minimum = 0, int capacity = 0) {
1.59 - data.clear(); boxes.clear();
1.60 - boxes.push_back(RadixBox(minimum, 1));
1.61 - boxes.push_back(RadixBox(minimum + 1, 1));
1.62 - while (lower(boxes.size() - 1, capacity + minimum - 1)) {
1.63 + _data.clear(); _boxes.clear();
1.64 + _boxes.push_back(RadixBox(minimum, 1));
1.65 + _boxes.push_back(RadixBox(minimum + 1, 1));
1.66 + while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
1.67 extend();
1.68 }
1.69 }
1.70 @@ -150,58 +150,58 @@
1.71 private:
1.72
1.73 bool upper(int box, Prio pr) {
1.74 - return pr < boxes[box].min;
1.75 + return pr < _boxes[box].min;
1.76 }
1.77
1.78 bool lower(int box, Prio pr) {
1.79 - return pr >= boxes[box].min + boxes[box].size;
1.80 + return pr >= _boxes[box].min + _boxes[box].size;
1.81 }
1.82
1.83 // Remove item from the box list
1.84 void remove(int index) {
1.85 - if (data[index].prev >= 0) {
1.86 - data[data[index].prev].next = data[index].next;
1.87 + if (_data[index].prev >= 0) {
1.88 + _data[_data[index].prev].next = _data[index].next;
1.89 } else {
1.90 - boxes[data[index].box].first = data[index].next;
1.91 + _boxes[_data[index].box].first = _data[index].next;
1.92 }
1.93 - if (data[index].next >= 0) {
1.94 - data[data[index].next].prev = data[index].prev;
1.95 + if (_data[index].next >= 0) {
1.96 + _data[_data[index].next].prev = _data[index].prev;
1.97 }
1.98 }
1.99
1.100 // Insert item into the box list
1.101 void insert(int box, int index) {
1.102 - if (boxes[box].first == -1) {
1.103 - boxes[box].first = index;
1.104 - data[index].next = data[index].prev = -1;
1.105 + if (_boxes[box].first == -1) {
1.106 + _boxes[box].first = index;
1.107 + _data[index].next = _data[index].prev = -1;
1.108 } else {
1.109 - data[index].next = boxes[box].first;
1.110 - data[boxes[box].first].prev = index;
1.111 - data[index].prev = -1;
1.112 - boxes[box].first = index;
1.113 + _data[index].next = _boxes[box].first;
1.114 + _data[_boxes[box].first].prev = index;
1.115 + _data[index].prev = -1;
1.116 + _boxes[box].first = index;
1.117 }
1.118 - data[index].box = box;
1.119 + _data[index].box = box;
1.120 }
1.121
1.122 // Add a new box to the box list
1.123 void extend() {
1.124 - int min = boxes.back().min + boxes.back().size;
1.125 - int bs = 2 * boxes.back().size;
1.126 - boxes.push_back(RadixBox(min, bs));
1.127 + int min = _boxes.back().min + _boxes.back().size;
1.128 + int bs = 2 * _boxes.back().size;
1.129 + _boxes.push_back(RadixBox(min, bs));
1.130 }
1.131
1.132 // Move an item up into the proper box.
1.133 - void bubble_up(int index) {
1.134 - if (!lower(data[index].box, data[index].prio)) return;
1.135 + void bubbleUp(int index) {
1.136 + if (!lower(_data[index].box, _data[index].prio)) return;
1.137 remove(index);
1.138 - int box = findUp(data[index].box, data[index].prio);
1.139 + int box = findUp(_data[index].box, _data[index].prio);
1.140 insert(box, index);
1.141 }
1.142
1.143 // Find up the proper box for the item with the given priority
1.144 int findUp(int start, int pr) {
1.145 while (lower(start, pr)) {
1.146 - if (++start == int(boxes.size())) {
1.147 + if (++start == int(_boxes.size())) {
1.148 extend();
1.149 }
1.150 }
1.151 @@ -209,17 +209,17 @@
1.152 }
1.153
1.154 // Move an item down into the proper box
1.155 - void bubble_down(int index) {
1.156 - if (!upper(data[index].box, data[index].prio)) return;
1.157 + void bubbleDown(int index) {
1.158 + if (!upper(_data[index].box, _data[index].prio)) return;
1.159 remove(index);
1.160 - int box = findDown(data[index].box, data[index].prio);
1.161 + int box = findDown(_data[index].box, _data[index].prio);
1.162 insert(box, index);
1.163 }
1.164
1.165 // Find down the proper box for the item with the given priority
1.166 int findDown(int start, int pr) {
1.167 while (upper(start, pr)) {
1.168 - if (--start < 0) throw UnderFlowPriorityError();
1.169 + if (--start < 0) throw PriorityUnderflowError();
1.170 }
1.171 return start;
1.172 }
1.173 @@ -227,15 +227,15 @@
1.174 // Find the first non-empty box
1.175 int findFirst() {
1.176 int first = 0;
1.177 - while (boxes[first].first == -1) ++first;
1.178 + while (_boxes[first].first == -1) ++first;
1.179 return first;
1.180 }
1.181
1.182 // Gives back the minimum priority of the given box
1.183 int minValue(int box) {
1.184 - int min = data[boxes[box].first].prio;
1.185 - for (int k = boxes[box].first; k != -1; k = data[k].next) {
1.186 - if (data[k].prio < min) min = data[k].prio;
1.187 + int min = _data[_boxes[box].first].prio;
1.188 + for (int k = _boxes[box].first; k != -1; k = _data[k].next) {
1.189 + if (_data[k].prio < min) min = _data[k].prio;
1.190 }
1.191 return min;
1.192 }
1.193 @@ -246,31 +246,31 @@
1.194 if (box == 0) return;
1.195 int min = minValue(box);
1.196 for (int i = 0; i <= box; ++i) {
1.197 - boxes[i].min = min;
1.198 - min += boxes[i].size;
1.199 + _boxes[i].min = min;
1.200 + min += _boxes[i].size;
1.201 }
1.202 - int curr = boxes[box].first, next;
1.203 + int curr = _boxes[box].first, next;
1.204 while (curr != -1) {
1.205 - next = data[curr].next;
1.206 - bubble_down(curr);
1.207 + next = _data[curr].next;
1.208 + bubbleDown(curr);
1.209 curr = next;
1.210 }
1.211 }
1.212
1.213 - void relocate_last(int index) {
1.214 - if (index != int(data.size()) - 1) {
1.215 - data[index] = data.back();
1.216 - if (data[index].prev != -1) {
1.217 - data[data[index].prev].next = index;
1.218 + void relocateLast(int index) {
1.219 + if (index != int(_data.size()) - 1) {
1.220 + _data[index] = _data.back();
1.221 + if (_data[index].prev != -1) {
1.222 + _data[_data[index].prev].next = index;
1.223 } else {
1.224 - boxes[data[index].box].first = index;
1.225 + _boxes[_data[index].box].first = index;
1.226 }
1.227 - if (data[index].next != -1) {
1.228 - data[data[index].next].prev = index;
1.229 + if (_data[index].next != -1) {
1.230 + _data[_data[index].next].prev = index;
1.231 }
1.232 - _iim[data[index].item] = index;
1.233 + _iim[_data[index].item] = index;
1.234 }
1.235 - data.pop_back();
1.236 + _data.pop_back();
1.237 }
1.238
1.239 public:
1.240 @@ -284,13 +284,13 @@
1.241 /// \pre \e i must not be stored in the heap.
1.242 /// \warning This method may throw an \c UnderFlowPriorityException.
1.243 void push(const Item &i, const Prio &p) {
1.244 - int n = data.size();
1.245 + int n = _data.size();
1.246 _iim.set(i, n);
1.247 - data.push_back(RadixItem(i, p));
1.248 - while (lower(boxes.size() - 1, p)) {
1.249 + _data.push_back(RadixItem(i, p));
1.250 + while (lower(_boxes.size() - 1, p)) {
1.251 extend();
1.252 }
1.253 - int box = findDown(boxes.size() - 1, p);
1.254 + int box = findDown(_boxes.size() - 1, p);
1.255 insert(box, n);
1.256 }
1.257
1.258 @@ -300,7 +300,7 @@
1.259 /// \pre The heap must be non-empty.
1.260 Item top() const {
1.261 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
1.262 - return data[boxes[0].first].item;
1.263 + return _data[_boxes[0].first].item;
1.264 }
1.265
1.266 /// \brief The minimum priority.
1.267 @@ -309,7 +309,7 @@
1.268 /// \pre The heap must be non-empty.
1.269 Prio prio() const {
1.270 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
1.271 - return data[boxes[0].first].prio;
1.272 + return _data[_boxes[0].first].prio;
1.273 }
1.274
1.275 /// \brief Remove the item having minimum priority.
1.276 @@ -318,10 +318,10 @@
1.277 /// \pre The heap must be non-empty.
1.278 void pop() {
1.279 moveDown();
1.280 - int index = boxes[0].first;
1.281 - _iim[data[index].item] = POST_HEAP;
1.282 + int index = _boxes[0].first;
1.283 + _iim[_data[index].item] = POST_HEAP;
1.284 remove(index);
1.285 - relocate_last(index);
1.286 + relocateLast(index);
1.287 }
1.288
1.289 /// \brief Remove the given item from the heap.
1.290 @@ -334,7 +334,7 @@
1.291 int index = _iim[i];
1.292 _iim[i] = POST_HEAP;
1.293 remove(index);
1.294 - relocate_last(index);
1.295 + relocateLast(index);
1.296 }
1.297
1.298 /// \brief The priority of the given item.
1.299 @@ -344,7 +344,7 @@
1.300 /// \pre \e i must be in the heap.
1.301 Prio operator[](const Item &i) const {
1.302 int idx = _iim[i];
1.303 - return data[idx].prio;
1.304 + return _data[idx].prio;
1.305 }
1.306
1.307 /// \brief Set the priority of an item or insert it, if it is
1.308 @@ -362,12 +362,12 @@
1.309 if( idx < 0 ) {
1.310 push(i, p);
1.311 }
1.312 - else if( p >= data[idx].prio ) {
1.313 - data[idx].prio = p;
1.314 - bubble_up(idx);
1.315 + else if( p >= _data[idx].prio ) {
1.316 + _data[idx].prio = p;
1.317 + bubbleUp(idx);
1.318 } else {
1.319 - data[idx].prio = p;
1.320 - bubble_down(idx);
1.321 + _data[idx].prio = p;
1.322 + bubbleDown(idx);
1.323 }
1.324 }
1.325
1.326 @@ -380,8 +380,8 @@
1.327 /// \warning This method may throw an \c UnderFlowPriorityException.
1.328 void decrease(const Item &i, const Prio &p) {
1.329 int idx = _iim[i];
1.330 - data[idx].prio = p;
1.331 - bubble_down(idx);
1.332 + _data[idx].prio = p;
1.333 + bubbleDown(idx);
1.334 }
1.335
1.336 /// \brief Increase the priority of an item to the given value.
1.337 @@ -392,8 +392,8 @@
1.338 /// \pre \e i must be stored in the heap with priority at most \e p.
1.339 void increase(const Item &i, const Prio &p) {
1.340 int idx = _iim[i];
1.341 - data[idx].prio = p;
1.342 - bubble_up(idx);
1.343 + _data[idx].prio = p;
1.344 + bubbleUp(idx);
1.345 }
1.346
1.347 /// \brief Return the state of an item.