00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_LINEAR_HEAP_H
00020 #define LEMON_LINEAR_HEAP_H
00021
00025
00026 #include <vector>
00027 #include <utility>
00028 #include <functional>
00029
00030 namespace lemon {
00031
00033
00049 template <typename _Item, typename _ItemIntMap, bool minimize = true >
00050 class LinearHeap {
00051
00052 public:
00053 typedef _Item Item;
00054 typedef int Prio;
00055 typedef std::pair<Item, Prio> Pair;
00056 typedef _ItemIntMap ItemIntMap;
00057
00066 enum state_enum {
00067 IN_HEAP = 0,
00068 PRE_HEAP = -1,
00069 POST_HEAP = -2
00070 };
00071
00072 public:
00079 explicit LinearHeap(ItemIntMap &_index) : index(_index), minimal(0) {}
00080
00084 int size() const { return data.size(); }
00085
00089 bool empty() const { return data.empty(); }
00090
00094 void clear() {
00095 for (int i = 0; i < (int)data.size(); ++i) {
00096 index[data[i].item] = -2;
00097 }
00098 data.clear(); first.clear(); minimal = 0;
00099 }
00100
00101 private:
00102
00103 void relocate_last(int idx) {
00104 if (idx + 1 < (int)data.size()) {
00105 data[idx] = data.back();
00106 if (data[idx].prev != -1) {
00107 data[data[idx].prev].next = idx;
00108 } else {
00109 first[data[idx].value] = idx;
00110 }
00111 if (data[idx].next != -1) {
00112 data[data[idx].next].prev = idx;
00113 }
00114 index[data[idx].item] = idx;
00115 }
00116 data.pop_back();
00117 }
00118
00119 void unlace(int idx) {
00120 if (data[idx].prev != -1) {
00121 data[data[idx].prev].next = data[idx].next;
00122 } else {
00123 first[data[idx].value] = data[idx].next;
00124 }
00125 if (data[idx].next != -1) {
00126 data[data[idx].next].prev = data[idx].prev;
00127 }
00128 }
00129
00130 void lace(int idx) {
00131 if ((int)first.size() <= data[idx].value) {
00132 first.resize(data[idx].value + 1, -1);
00133 }
00134 data[idx].next = first[data[idx].value];
00135 if (data[idx].next != -1) {
00136 data[data[idx].next].prev = idx;
00137 }
00138 first[data[idx].value] = idx;
00139 data[idx].prev = -1;
00140 }
00141
00142 public:
00147 void push(const Pair& p) {
00148 push(p.first, p.second);
00149 }
00150
00156 void push(const Item &i, const Prio &p) {
00157 int idx = data.size();
00158 index[i] = idx;
00159 data.push_back(LinearItem(i, p));
00160 lace(idx);
00161 if (p < minimal) {
00162 minimal = p;
00163 }
00164 }
00165
00170 Item top() const {
00171 while (first[minimal] == -1) {
00172 ++minimal;
00173 }
00174 return data[first[minimal]].item;
00175 }
00176
00181 Prio prio() const {
00182 while (first[minimal] == -1) {
00183 ++minimal;
00184 }
00185 return minimal;
00186 }
00187
00192 void pop() {
00193 while (first[minimal] == -1) {
00194 ++minimal;
00195 }
00196 int idx = first[minimal];
00197 index[data[idx].item] = -2;
00198 unlace(idx);
00199 relocate_last(idx);
00200 }
00201
00207 void erase(const Item &i) {
00208 int idx = index[i];
00209 index[data[idx].item] = -2;
00210 unlace(idx);
00211 relocate_last(idx);
00212 }
00213
00214
00220 Prio operator[](const Item &i) const {
00221 int idx = index[i];
00222 return data[idx].value;
00223 }
00224
00232 void set(const Item &i, const Prio &p) {
00233 int idx = index[i];
00234 if (idx < 0) {
00235 push(i,p);
00236 } else if (p > data[idx].value) {
00237 increase(i, p);
00238 } else {
00239 decrease(i, p);
00240 }
00241 }
00242
00244
00250 void decrease(const Item &i, const Prio &p) {
00251 int idx = index[i];
00252 unlace(idx);
00253 data[idx].value = p;
00254 if (p < minimal) {
00255 minimal = p;
00256 }
00257 lace(idx);
00258 }
00259
00267 void increase(const Item &i, const Prio &p) {
00268 int idx = index[i];
00269 unlace(idx);
00270 data[idx].value = p;
00271 lace(idx);
00272 }
00273
00282 state_enum state(const Item &i) const {
00283 int idx = index[i];
00284 if (idx >= 0) idx = 0;
00285 return state_enum(idx);
00286 }
00287
00295 void state(const Item& i, state_enum st) {
00296 switch (st) {
00297 case POST_HEAP:
00298 case PRE_HEAP:
00299 if (state(i) == IN_HEAP) {
00300 erase(i);
00301 }
00302 index[i] = st;
00303 break;
00304 case IN_HEAP:
00305 break;
00306 }
00307 }
00308
00309 private:
00310
00311 struct LinearItem {
00312 LinearItem(const Item& _item, int _value)
00313 : item(_item), value(_value) {}
00314
00315 Item item;
00316 int value;
00317
00318 int prev, next;
00319 };
00320
00321 ItemIntMap& index;
00322 std::vector<int> first;
00323 std::vector<LinearItem> data;
00324 mutable int minimal;
00325
00326 };
00327
00328
00329 template <typename _Item, typename _ItemIntMap>
00330 class LinearHeap<_Item, _ItemIntMap, false> {
00331
00332 public:
00333 typedef _Item Item;
00334 typedef int Prio;
00335 typedef std::pair<Item, Prio> Pair;
00336 typedef _ItemIntMap ItemIntMap;
00337
00338 enum state_enum {
00339 IN_HEAP = 0,
00340 PRE_HEAP = -1,
00341 POST_HEAP = -2
00342 };
00343
00344 public:
00345
00346 explicit LinearHeap(ItemIntMap &_index) : index(_index), maximal(-1) {}
00347
00348 int size() const { return data.size(); }
00349 bool empty() const { return data.empty(); }
00350
00351 void clear() {
00352 for (int i = 0; i < (int)data.size(); ++i) {
00353 index[data[i].item] = -2;
00354 }
00355 data.clear(); first.clear(); maximal = -1;
00356 }
00357
00358 private:
00359
00360 void relocate_last(int idx) {
00361 if (idx + 1 != (int)data.size()) {
00362 data[idx] = data.back();
00363 if (data[idx].prev != -1) {
00364 data[data[idx].prev].next = idx;
00365 } else {
00366 first[data[idx].value] = idx;
00367 }
00368 if (data[idx].next != -1) {
00369 data[data[idx].next].prev = idx;
00370 }
00371 index[data[idx].item] = idx;
00372 }
00373 data.pop_back();
00374 }
00375
00376 void unlace(int idx) {
00377 if (data[idx].prev != -1) {
00378 data[data[idx].prev].next = data[idx].next;
00379 } else {
00380 first[data[idx].value] = data[idx].next;
00381 }
00382 if (data[idx].next != -1) {
00383 data[data[idx].next].prev = data[idx].prev;
00384 }
00385 }
00386
00387 void lace(int idx) {
00388 if ((int)first.size() <= data[idx].value) {
00389 first.resize(data[idx].value + 1, -1);
00390 }
00391 data[idx].next = first[data[idx].value];
00392 if (data[idx].next != -1) {
00393 data[data[idx].next].prev = idx;
00394 }
00395 first[data[idx].value] = idx;
00396 data[idx].prev = -1;
00397 }
00398
00399 public:
00400
00401 void push(const Pair& p) {
00402 push(p.first, p.second);
00403 }
00404
00405 void push(const Item &i, const Prio &p) {
00406 int idx = data.size();
00407 index[i] = idx;
00408 data.push_back(LinearItem(i, p));
00409 lace(idx);
00410 if (data[idx].value > maximal) {
00411 maximal = data[idx].value;
00412 }
00413 }
00414
00415 Item top() const {
00416 while (first[maximal] == -1) {
00417 --maximal;
00418 }
00419 return data[first[maximal]].item;
00420 }
00421
00422 Prio prio() const {
00423 while (first[maximal] == -1) {
00424 --maximal;
00425 }
00426 return maximal;
00427 }
00428
00429 void pop() {
00430 while (first[maximal] == -1) {
00431 --maximal;
00432 }
00433 int idx = first[maximal];
00434 index[data[idx].item] = -2;
00435 unlace(idx);
00436 relocate_last(idx);
00437 }
00438
00439 void erase(const Item &i) {
00440 int idx = index[i];
00441 index[data[idx].item] = -2;
00442 unlace(idx);
00443 relocate_last(idx);
00444 }
00445
00446 Prio operator[](const Item &i) const {
00447 int idx = index[i];
00448 return data[idx].value;
00449 }
00450
00451 void set(const Item &i, const Prio &p) {
00452 int idx = index[i];
00453 if (idx < 0) {
00454 push(i,p);
00455 } else if (p > data[idx].value) {
00456 decrease(i, p);
00457 } else {
00458 increase(i, p);
00459 }
00460 }
00461
00462 void decrease(const Item &i, const Prio &p) {
00463 int idx = index[i];
00464 unlace(idx);
00465 data[idx].value = p;
00466 if (p > maximal) {
00467 maximal = p;
00468 }
00469 lace(idx);
00470 }
00471
00472 void increase(const Item &i, const Prio &p) {
00473 int idx = index[i];
00474 unlace(idx);
00475 data[idx].value = p;
00476 lace(idx);
00477 }
00478
00479 state_enum state(const Item &i) const {
00480 int idx = index[i];
00481 if (idx >= 0) idx = 0;
00482 return state_enum(idx);
00483 }
00484
00485 void state(const Item& i, state_enum st) {
00486 switch (st) {
00487 case POST_HEAP:
00488 case PRE_HEAP:
00489 if (state(i) == IN_HEAP) {
00490 erase(i);
00491 }
00492 index[i] = st;
00493 break;
00494 case IN_HEAP:
00495 break;
00496 }
00497 }
00498
00499 private:
00500
00501 struct LinearItem {
00502 LinearItem(const Item& _item, int _value)
00503 : item(_item), value(_value) {}
00504
00505 Item item;
00506 int value;
00507
00508 int prev, next;
00509 };
00510
00511 ItemIntMap& index;
00512 std::vector<int> first;
00513 std::vector<LinearItem> data;
00514 mutable int maximal;
00515
00516 };
00517
00518 }
00519
00520 #endif