1.1 --- a/lemon/bucket_heap.h Thu Jun 11 22:11:29 2009 +0200
1.2 +++ b/lemon/bucket_heap.h Thu Jun 11 22:16:11 2009 +0200
1.3 @@ -29,6 +29,30 @@
1.4
1.5 namespace lemon {
1.6
1.7 + namespace _bucket_heap_bits {
1.8 +
1.9 + template <bool minimize>
1.10 + struct DirectionTraits {
1.11 + static bool less(int left, int right) {
1.12 + return left < right;
1.13 + }
1.14 + static void increase(int& value) {
1.15 + ++value;
1.16 + }
1.17 + };
1.18 +
1.19 + template <>
1.20 + struct DirectionTraits<false> {
1.21 + static bool less(int left, int right) {
1.22 + return left > right;
1.23 + }
1.24 + static void increase(int& value) {
1.25 + --value;
1.26 + }
1.27 + };
1.28 +
1.29 + }
1.30 +
1.31 /// \ingroup auxdat
1.32 ///
1.33 /// \brief A Bucket Heap implementation.
1.34 @@ -45,7 +69,7 @@
1.35 /// to handle the cross references.
1.36 /// \param minimize If the given parameter is true then the heap gives back
1.37 /// the lowest priority.
1.38 - template <typename _ItemIntMap, bool minimize = true >
1.39 + template <typename _ItemIntMap, bool minimize = true>
1.40 class BucketHeap {
1.41
1.42 public:
1.43 @@ -58,6 +82,12 @@
1.44 /// \e
1.45 typedef _ItemIntMap ItemIntMap;
1.46
1.47 + private:
1.48 +
1.49 + typedef _bucket_heap_bits::DirectionTraits<minimize> Direction;
1.50 +
1.51 + public:
1.52 +
1.53 /// \brief Type to represent the items states.
1.54 ///
1.55 /// Each Item element have a state associated to it. It may be "in heap",
1.56 @@ -161,7 +191,7 @@
1.57 index[i] = idx;
1.58 data.push_back(BucketItem(i, p));
1.59 lace(idx);
1.60 - if (p < minimal) {
1.61 + if (Direction::less(p, minimal)) {
1.62 minimal = p;
1.63 }
1.64 }
1.65 @@ -172,7 +202,7 @@
1.66 /// \pre The heap must be nonempty.
1.67 Item top() const {
1.68 while (first[minimal] == -1) {
1.69 - ++minimal;
1.70 + Direction::increase(minimal);
1.71 }
1.72 return data[first[minimal]].item;
1.73 }
1.74 @@ -183,7 +213,7 @@
1.75 /// \pre The heap must be nonempty.
1.76 Prio prio() const {
1.77 while (first[minimal] == -1) {
1.78 - ++minimal;
1.79 + Direction::increase(minimal);
1.80 }
1.81 return minimal;
1.82 }
1.83 @@ -194,7 +224,7 @@
1.84 /// \pre The heap must be non-empty.
1.85 void pop() {
1.86 while (first[minimal] == -1) {
1.87 - ++minimal;
1.88 + Direction::increase(minimal);
1.89 }
1.90 int idx = first[minimal];
1.91 index[data[idx].item] = -2;
1.92 @@ -235,11 +265,11 @@
1.93 void set(const Item &i, const Prio &p) {
1.94 int idx = index[i];
1.95 if (idx < 0) {
1.96 - push(i,p);
1.97 - } else if (p > data[idx].value) {
1.98 + push(i, p);
1.99 + } else if (Direction::less(p, data[idx].value)) {
1.100 + decrease(i, p);
1.101 + } else {
1.102 increase(i, p);
1.103 - } else {
1.104 - decrease(i, p);
1.105 }
1.106 }
1.107
1.108 @@ -254,7 +284,7 @@
1.109 int idx = index[i];
1.110 unlace(idx);
1.111 data[idx].value = p;
1.112 - if (p < minimal) {
1.113 + if (Direction::less(p, minimal)) {
1.114 minimal = p;
1.115 }
1.116 lace(idx);
1.117 @@ -328,193 +358,6 @@
1.118
1.119 }; // class BucketHeap
1.120
1.121 -
1.122 - template <typename _ItemIntMap>
1.123 - class BucketHeap<_ItemIntMap, false> {
1.124 -
1.125 - public:
1.126 - typedef typename _ItemIntMap::Key Item;
1.127 - typedef int Prio;
1.128 - typedef std::pair<Item, Prio> Pair;
1.129 - typedef _ItemIntMap ItemIntMap;
1.130 -
1.131 - enum State {
1.132 - IN_HEAP = 0,
1.133 - PRE_HEAP = -1,
1.134 - POST_HEAP = -2
1.135 - };
1.136 -
1.137 - public:
1.138 -
1.139 - explicit BucketHeap(ItemIntMap &_index) : index(_index), maximal(-1) {}
1.140 -
1.141 - int size() const { return data.size(); }
1.142 - bool empty() const { return data.empty(); }
1.143 -
1.144 - void clear() {
1.145 - data.clear(); first.clear(); maximal = -1;
1.146 - }
1.147 -
1.148 - private:
1.149 -
1.150 - void relocate_last(int idx) {
1.151 - if (idx + 1 != int(data.size())) {
1.152 - data[idx] = data.back();
1.153 - if (data[idx].prev != -1) {
1.154 - data[data[idx].prev].next = idx;
1.155 - } else {
1.156 - first[data[idx].value] = idx;
1.157 - }
1.158 - if (data[idx].next != -1) {
1.159 - data[data[idx].next].prev = idx;
1.160 - }
1.161 - index[data[idx].item] = idx;
1.162 - }
1.163 - data.pop_back();
1.164 - }
1.165 -
1.166 - void unlace(int idx) {
1.167 - if (data[idx].prev != -1) {
1.168 - data[data[idx].prev].next = data[idx].next;
1.169 - } else {
1.170 - first[data[idx].value] = data[idx].next;
1.171 - }
1.172 - if (data[idx].next != -1) {
1.173 - data[data[idx].next].prev = data[idx].prev;
1.174 - }
1.175 - }
1.176 -
1.177 - void lace(int idx) {
1.178 - if (int(first.size()) <= data[idx].value) {
1.179 - first.resize(data[idx].value + 1, -1);
1.180 - }
1.181 - data[idx].next = first[data[idx].value];
1.182 - if (data[idx].next != -1) {
1.183 - data[data[idx].next].prev = idx;
1.184 - }
1.185 - first[data[idx].value] = idx;
1.186 - data[idx].prev = -1;
1.187 - }
1.188 -
1.189 - public:
1.190 -
1.191 - void push(const Pair& p) {
1.192 - push(p.first, p.second);
1.193 - }
1.194 -
1.195 - void push(const Item &i, const Prio &p) {
1.196 - int idx = data.size();
1.197 - index[i] = idx;
1.198 - data.push_back(BucketItem(i, p));
1.199 - lace(idx);
1.200 - if (data[idx].value > maximal) {
1.201 - maximal = data[idx].value;
1.202 - }
1.203 - }
1.204 -
1.205 - Item top() const {
1.206 - while (first[maximal] == -1) {
1.207 - --maximal;
1.208 - }
1.209 - return data[first[maximal]].item;
1.210 - }
1.211 -
1.212 - Prio prio() const {
1.213 - while (first[maximal] == -1) {
1.214 - --maximal;
1.215 - }
1.216 - return maximal;
1.217 - }
1.218 -
1.219 - void pop() {
1.220 - while (first[maximal] == -1) {
1.221 - --maximal;
1.222 - }
1.223 - int idx = first[maximal];
1.224 - index[data[idx].item] = -2;
1.225 - unlace(idx);
1.226 - relocate_last(idx);
1.227 - }
1.228 -
1.229 - void erase(const Item &i) {
1.230 - int idx = index[i];
1.231 - index[data[idx].item] = -2;
1.232 - unlace(idx);
1.233 - relocate_last(idx);
1.234 - }
1.235 -
1.236 - Prio operator[](const Item &i) const {
1.237 - int idx = index[i];
1.238 - return data[idx].value;
1.239 - }
1.240 -
1.241 - void set(const Item &i, const Prio &p) {
1.242 - int idx = index[i];
1.243 - if (idx < 0) {
1.244 - push(i,p);
1.245 - } else if (p > data[idx].value) {
1.246 - decrease(i, p);
1.247 - } else {
1.248 - increase(i, p);
1.249 - }
1.250 - }
1.251 -
1.252 - void decrease(const Item &i, const Prio &p) {
1.253 - int idx = index[i];
1.254 - unlace(idx);
1.255 - data[idx].value = p;
1.256 - if (p > maximal) {
1.257 - maximal = p;
1.258 - }
1.259 - lace(idx);
1.260 - }
1.261 -
1.262 - void increase(const Item &i, const Prio &p) {
1.263 - int idx = index[i];
1.264 - unlace(idx);
1.265 - data[idx].value = p;
1.266 - lace(idx);
1.267 - }
1.268 -
1.269 - State state(const Item &i) const {
1.270 - int idx = index[i];
1.271 - if (idx >= 0) idx = 0;
1.272 - return State(idx);
1.273 - }
1.274 -
1.275 - void state(const Item& i, State st) {
1.276 - switch (st) {
1.277 - case POST_HEAP:
1.278 - case PRE_HEAP:
1.279 - if (state(i) == IN_HEAP) {
1.280 - erase(i);
1.281 - }
1.282 - index[i] = st;
1.283 - break;
1.284 - case IN_HEAP:
1.285 - break;
1.286 - }
1.287 - }
1.288 -
1.289 - private:
1.290 -
1.291 - struct BucketItem {
1.292 - BucketItem(const Item& _item, int _value)
1.293 - : item(_item), value(_value) {}
1.294 -
1.295 - Item item;
1.296 - int value;
1.297 -
1.298 - int prev, next;
1.299 - };
1.300 -
1.301 - ItemIntMap& index;
1.302 - std::vector<int> first;
1.303 - std::vector<BucketItem> data;
1.304 - mutable int maximal;
1.305 -
1.306 - }; // class BucketHeap
1.307 -
1.308 /// \ingroup auxdat
1.309 ///
1.310 /// \brief A Simplified Bucket Heap implementation.
1.311 @@ -524,7 +367,7 @@
1.312 /// and simplier data structure than the BucketHeap. The main
1.313 /// difference is that the BucketHeap stores for every key a double
1.314 /// linked list while this class stores just simple lists. In the
1.315 - /// other way it does not supports erasing each elements just the
1.316 + /// other way it does not support erasing each elements just the
1.317 /// minimal and it does not supports key increasing, decreasing.
1.318 ///
1.319 /// \param _ItemIntMap A read and writable Item int map, used internally
1.320 @@ -542,6 +385,12 @@
1.321 typedef std::pair<Item, Prio> Pair;
1.322 typedef _ItemIntMap ItemIntMap;
1.323
1.324 + private:
1.325 +
1.326 + typedef _bucket_heap_bits::DirectionTraits<minimize> Direction;
1.327 +
1.328 + public:
1.329 +
1.330 /// \brief Type to represent the items states.
1.331 ///
1.332 /// Each Item element have a state associated to it. It may be "in heap",
1.333 @@ -614,7 +463,7 @@
1.334 if (p >= int(first.size())) first.resize(p + 1, -1);
1.335 data[idx].next = first[p];
1.336 first[p] = idx;
1.337 - if (p < minimal) {
1.338 + if (Direction::less(p, minimal)) {
1.339 minimal = p;
1.340 }
1.341 ++num;
1.342 @@ -626,7 +475,7 @@
1.343 /// \pre The heap must be nonempty.
1.344 Item top() const {
1.345 while (first[minimal] == -1) {
1.346 - ++minimal;
1.347 + Direction::increase(minimal);
1.348 }
1.349 return data[first[minimal]].item;
1.350 }
1.351 @@ -637,7 +486,7 @@
1.352 /// \pre The heap must be nonempty.
1.353 Prio prio() const {
1.354 while (first[minimal] == -1) {
1.355 - ++minimal;
1.356 + Direction::increase(minimal);
1.357 }
1.358 return minimal;
1.359 }
1.360 @@ -648,7 +497,7 @@
1.361 /// \pre The heap must be non-empty.
1.362 void pop() {
1.363 while (first[minimal] == -1) {
1.364 - ++minimal;
1.365 + Direction::increase(minimal);
1.366 }
1.367 int idx = first[minimal];
1.368 index[data[idx].item] = -2;
1.369 @@ -711,121 +560,6 @@
1.370
1.371 }; // class SimpleBucketHeap
1.372
1.373 - template <typename _ItemIntMap>
1.374 - class SimpleBucketHeap<_ItemIntMap, false> {
1.375 -
1.376 - public:
1.377 - typedef typename _ItemIntMap::Key Item;
1.378 - typedef int Prio;
1.379 - typedef std::pair<Item, Prio> Pair;
1.380 - typedef _ItemIntMap ItemIntMap;
1.381 -
1.382 - enum State {
1.383 - IN_HEAP = 0,
1.384 - PRE_HEAP = -1,
1.385 - POST_HEAP = -2
1.386 - };
1.387 -
1.388 - public:
1.389 -
1.390 - explicit SimpleBucketHeap(ItemIntMap &_index)
1.391 - : index(_index), free(-1), num(0), maximal(0) {}
1.392 -
1.393 - int size() const { return num; }
1.394 -
1.395 - bool empty() const { return num == 0; }
1.396 -
1.397 - void clear() {
1.398 - data.clear(); first.clear(); free = -1; num = 0; maximal = 0;
1.399 - }
1.400 -
1.401 - void push(const Pair& p) {
1.402 - push(p.first, p.second);
1.403 - }
1.404 -
1.405 - void push(const Item &i, const Prio &p) {
1.406 - int idx;
1.407 - if (free == -1) {
1.408 - idx = data.size();
1.409 - data.push_back(BucketItem(i));
1.410 - } else {
1.411 - idx = free;
1.412 - free = data[idx].next;
1.413 - data[idx].item = i;
1.414 - }
1.415 - index[i] = idx;
1.416 - if (p >= int(first.size())) first.resize(p + 1, -1);
1.417 - data[idx].next = first[p];
1.418 - first[p] = idx;
1.419 - if (p > maximal) {
1.420 - maximal = p;
1.421 - }
1.422 - ++num;
1.423 - }
1.424 -
1.425 - Item top() const {
1.426 - while (first[maximal] == -1) {
1.427 - --maximal;
1.428 - }
1.429 - return data[first[maximal]].item;
1.430 - }
1.431 -
1.432 - Prio prio() const {
1.433 - while (first[maximal] == -1) {
1.434 - --maximal;
1.435 - }
1.436 - return maximal;
1.437 - }
1.438 -
1.439 - void pop() {
1.440 - while (first[maximal] == -1) {
1.441 - --maximal;
1.442 - }
1.443 - int idx = first[maximal];
1.444 - index[data[idx].item] = -2;
1.445 - first[maximal] = data[idx].next;
1.446 - data[idx].next = free;
1.447 - free = idx;
1.448 - --num;
1.449 - }
1.450 -
1.451 - Prio operator[](const Item &i) const {
1.452 - for (int k = 0; k < first.size(); ++k) {
1.453 - int idx = first[k];
1.454 - while (idx != -1) {
1.455 - if (data[idx].item == i) {
1.456 - return k;
1.457 - }
1.458 - idx = data[idx].next;
1.459 - }
1.460 - }
1.461 - return -1;
1.462 - }
1.463 -
1.464 - State state(const Item &i) const {
1.465 - int idx = index[i];
1.466 - if (idx >= 0) idx = 0;
1.467 - return State(idx);
1.468 - }
1.469 -
1.470 - private:
1.471 -
1.472 - struct BucketItem {
1.473 - BucketItem(const Item& _item) : item(_item) {}
1.474 -
1.475 - Item item;
1.476 -
1.477 - int next;
1.478 - };
1.479 -
1.480 - ItemIntMap& index;
1.481 - std::vector<int> first;
1.482 - std::vector<BucketItem> data;
1.483 - int free, num;
1.484 - mutable int maximal;
1.485 -
1.486 - };
1.487 -
1.488 }
1.489
1.490 #endif