00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_RADIX_HEAP_H
00020 #define LEMON_RADIX_HEAP_H
00021
00025
00026 #include <vector>
00027 #include <lemon/error.h>
00028
00029 namespace lemon {
00030
00037
00038 class UnderFlowPriorityError : public RuntimeError {
00039 public:
00040 virtual const char* exceptionName() const {
00041 return "lemon::UnderFlowPriorityError";
00042 }
00043 };
00044
00064
00065 template <typename _Item, typename _ItemIntMap>
00066 class RadixHeap {
00067
00068 public:
00069 typedef _Item Item;
00070 typedef int Prio;
00071 typedef _ItemIntMap ItemIntMap;
00072
00081 enum state_enum {
00082 IN_HEAP = 0,
00083 PRE_HEAP = -1,
00084 POST_HEAP = -2
00085 };
00086
00087 private:
00088
00089 struct RadixItem {
00090 int prev, next, box;
00091 Item item;
00092 int prio;
00093 RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
00094 };
00095
00096 struct RadixBox {
00097 int first;
00098 int min, size;
00099 RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
00100 };
00101
00102 std::vector<RadixItem> data;
00103 std::vector<RadixBox> boxes;
00104
00105 ItemIntMap &iim;
00106
00107
00108 public:
00119 RadixHeap(ItemIntMap &_iim, int minimal = 0, int capacity = 0)
00120 : iim(_iim) {
00121 boxes.push_back(RadixBox(minimal, 1));
00122 boxes.push_back(RadixBox(minimal + 1, 1));
00123 while (lower(boxes.size() - 1, capacity + minimal - 1)) {
00124 extend();
00125 }
00126 }
00127
00131 int size() const { return data.size(); }
00135 bool empty() const { return data.empty(); }
00136
00140 void clear(int minimal = 0, int capacity = 0) {
00141 for (int i = 0; i < (int)data.size(); ++i) {
00142 iim[data[i].item] = -2;
00143 }
00144 data.clear(); boxes.clear();
00145 boxes.push_back(RadixBox(minimal, 1));
00146 boxes.push_back(RadixBox(minimal + 1, 1));
00147 while (lower(boxes.size() - 1, capacity + minimal - 1)) {
00148 extend();
00149 }
00150 }
00151
00152 private:
00153
00154 bool upper(int box, Prio prio) {
00155 return prio < boxes[box].min;
00156 }
00157
00158 bool lower(int box, Prio prio) {
00159 return prio >= boxes[box].min + boxes[box].size;
00160 }
00161
00163 void remove(int index) {
00164 if (data[index].prev >= 0) {
00165 data[data[index].prev].next = data[index].next;
00166 } else {
00167 boxes[data[index].box].first = data[index].next;
00168 }
00169 if (data[index].next >= 0) {
00170 data[data[index].next].prev = data[index].prev;
00171 }
00172 }
00173
00175 void insert(int box, int index) {
00176 if (boxes[box].first == -1) {
00177 boxes[box].first = index;
00178 data[index].next = data[index].prev = -1;
00179 } else {
00180 data[index].next = boxes[box].first;
00181 data[boxes[box].first].prev = index;
00182 data[index].prev = -1;
00183 boxes[box].first = index;
00184 }
00185 data[index].box = box;
00186 }
00187
00189 void extend() {
00190 int min = boxes.back().min + boxes.back().size;
00191 int size = 2 * boxes.back().size;
00192 boxes.push_back(RadixBox(min, size));
00193 }
00194
00196 void bubble_up(int index) {
00197 if (!lower(data[index].box, data[index].prio)) return;
00198 remove(index);
00199 int box = findUp(data[index].box, data[index].prio);
00200 insert(box, index);
00201 }
00202
00204 int findUp(int start, int prio) {
00205 while (lower(start, prio)) {
00206 if (++start == (int)boxes.size()) {
00207 extend();
00208 }
00209 }
00210 return start;
00211 }
00212
00214 void bubble_down(int index) {
00215 if (!upper(data[index].box, data[index].prio)) return;
00216 remove(index);
00217 int box = findDown(data[index].box, data[index].prio);
00218 insert(box, index);
00219 }
00220
00222 int findDown(int start, int prio) {
00223 while (upper(start, prio)) {
00224 if (--start < 0) throw UnderFlowPriorityError();
00225 }
00226 return start;
00227 }
00228
00230 int findFirst() {
00231 int first = 0;
00232 while (boxes[first].first == -1) ++first;
00233 return first;
00234 }
00235
00237 int minValue(int box) {
00238 int min = data[boxes[box].first].prio;
00239 for (int k = boxes[box].first; k != -1; k = data[k].next) {
00240 if (data[k].prio < min) min = data[k].prio;
00241 }
00242 return min;
00243 }
00244
00247 void moveDown() {
00248 int box = findFirst();
00249 if (box == 0) return;
00250 int min = minValue(box);
00251 for (int i = 0; i <= box; ++i) {
00252 boxes[i].min = min;
00253 min += boxes[i].size;
00254 }
00255 int curr = boxes[box].first, next;
00256 while (curr != -1) {
00257 next = data[curr].next;
00258 bubble_down(curr);
00259 curr = next;
00260 }
00261 }
00262
00263 void relocate_last(int index) {
00264 if (index != (int)data.size() - 1) {
00265 data[index] = data.back();
00266 if (data[index].prev != -1) {
00267 data[data[index].prev].next = index;
00268 } else {
00269 boxes[data[index].box].first = index;
00270 }
00271 if (data[index].next != -1) {
00272 data[data[index].next].prev = index;
00273 }
00274 iim[data[index].item] = index;
00275 }
00276 data.pop_back();
00277 }
00278
00279 public:
00280
00286 void push(const Item &i, const Prio &p) {
00287 int n = data.size();
00288 iim.set(i, n);
00289 data.push_back(RadixItem(i, p));
00290 while (lower(boxes.size() - 1, p)) {
00291 extend();
00292 }
00293 int box = findDown(boxes.size() - 1, p);
00294 insert(box, n);
00295 }
00296
00301 Item top() const {
00302 const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
00303 return data[boxes[0].first].item;
00304 }
00305
00310 Prio prio() const {
00311 const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
00312 return data[boxes[0].first].prio;
00313 }
00314
00319 void pop() {
00320 moveDown();
00321 int index = boxes[0].first;
00322 iim[data[index].item] = POST_HEAP;
00323 remove(index);
00324 relocate_last(index);
00325 }
00326
00332 void erase(const Item &i) {
00333 int index = iim[i];
00334 iim[i] = POST_HEAP;
00335 remove(index);
00336 relocate_last(index);
00337 }
00338
00344 Prio operator[](const Item &i) const {
00345 int idx = iim[i];
00346 return data[idx].prio;
00347 }
00348
00357 void set(const Item &i, const Prio &p) {
00358 int idx = iim[i];
00359 if( idx < 0 ) {
00360 push(i, p);
00361 }
00362 else if( p >= data[idx].prio ) {
00363 data[idx].prio = p;
00364 bubble_up(idx);
00365 } else {
00366 data[idx].prio = p;
00367 bubble_down(idx);
00368 }
00369 }
00370
00371
00379 void decrease(const Item &i, const Prio &p) {
00380 int idx = iim[i];
00381 data[idx].prio = p;
00382 bubble_down(idx);
00383 }
00384
00391 void increase(const Item &i, const Prio &p) {
00392 int idx = iim[i];
00393 data[idx].prio = p;
00394 bubble_up(idx);
00395 }
00396
00405 state_enum state(const Item &i) const {
00406 int s = iim[i];
00407 if( s >= 0 ) s = 0;
00408 return state_enum(s);
00409 }
00410
00418 void state(const Item& i, state_enum st) {
00419 switch (st) {
00420 case POST_HEAP:
00421 case PRE_HEAP:
00422 if (state(i) == IN_HEAP) {
00423 erase(i);
00424 }
00425 iim[i] = st;
00426 break;
00427 case IN_HEAP:
00428 break;
00429 }
00430 }
00431
00432 };
00433
00434 }
00435
00436 #endif // LEMON_RADIX_HEAP_H