1.1 --- a/demo/coloring.cc Tue Apr 04 17:43:23 2006 +0000
1.2 +++ b/demo/coloring.cc Tue Apr 04 17:45:35 2006 +0000
1.3 @@ -30,7 +30,7 @@
1.4 #include <iostream>
1.5
1.6 #include <lemon/smart_graph.h>
1.7 -#include <lemon/linear_heap.h>
1.8 +#include <lemon/bucket_heap.h>
1.9 #include <lemon/graph_reader.h>
1.10 #include <lemon/graph_to_eps.h>
1.11
1.12 @@ -63,7 +63,7 @@
1.13 Graph::NodeMap<int> color(graph, -2);
1.14
1.15 Graph::NodeMap<int> heapMap(graph, -1);
1.16 - LinearHeap<Node, Graph::NodeMap<int> > heap(heapMap);
1.17 + BucketHeap<Node, Graph::NodeMap<int> > heap(heapMap);
1.18
1.19 for (NodeIt it(graph); it != INVALID; ++it) {
1.20 heap.push(it, countOutEdges(graph, it));
2.1 --- a/lemon/Makefile.am Tue Apr 04 17:43:23 2006 +0000
2.2 +++ b/lemon/Makefile.am Tue Apr 04 17:45:35 2006 +0000
2.3 @@ -53,7 +53,7 @@
2.4 iterable_maps.h \
2.5 johnson.h \
2.6 kruskal.h \
2.7 - linear_heap.h \
2.8 + bucket_heap.h \
2.9 list_graph.h \
2.10 lp.h \
2.11 lp_base.h \
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/bucket_heap.h Tue Apr 04 17:45:35 2006 +0000
3.3 @@ -0,0 +1,520 @@
3.4 +/* -*- C++ -*-
3.5 + *
3.6 + * This file is a part of LEMON, a generic C++ optimization library
3.7 + *
3.8 + * Copyright (C) 2003-2006
3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 + *
3.12 + * Permission to use, modify and distribute this software is granted
3.13 + * provided that this copyright notice appears in all copies. For
3.14 + * precise terms see the accompanying LICENSE file.
3.15 + *
3.16 + * This software is provided "AS IS" with no warranty of any kind,
3.17 + * express or implied, and with no claim as to its suitability for any
3.18 + * purpose.
3.19 + *
3.20 + */
3.21 +
3.22 +#ifndef LEMON_BUCKET_HEAP_H
3.23 +#define LEMON_BUCKET_HEAP_H
3.24 +
3.25 +///\ingroup auxdat
3.26 +///\file
3.27 +///\brief Bucket Heap implementation.
3.28 +
3.29 +#include <vector>
3.30 +#include <utility>
3.31 +#include <functional>
3.32 +
3.33 +namespace lemon {
3.34 +
3.35 + /// \ingroup auxdat
3.36 +
3.37 + /// \brief A Bucket Heap implementation.
3.38 + ///
3.39 + /// This class implements the \e bucket \e heap data structure. A \e heap
3.40 + /// is a data structure for storing items with specified values called \e
3.41 + /// priorities in such a way that finding the item with minimum priority is
3.42 + /// efficient. The bucket heap is very simple implementation, it can store
3.43 + /// only integer priorities and it stores for each priority in the [0..C]
3.44 + /// range a list of items. So it should be used only when the priorities
3.45 + /// are small. It is not intended to use as dijkstra heap.
3.46 + ///
3.47 + /// \param _Item Type of the items to be stored.
3.48 + /// \param _ItemIntMap A read and writable Item int map, used internally
3.49 + /// to handle the cross references.
3.50 + /// \param minimize If the given parameter is true then the heap gives back
3.51 + /// the lowest priority.
3.52 + template <typename _Item, typename _ItemIntMap, bool minimize = true >
3.53 + class BucketHeap {
3.54 +
3.55 + public:
3.56 + typedef _Item Item;
3.57 + typedef int Prio;
3.58 + typedef std::pair<Item, Prio> Pair;
3.59 + typedef _ItemIntMap ItemIntMap;
3.60 +
3.61 + /// \brief Type to represent the items states.
3.62 + ///
3.63 + /// Each Item element have a state associated to it. It may be "in heap",
3.64 + /// "pre heap" or "post heap". The latter two are indifferent from the
3.65 + /// heap's point of view, but may be useful to the user.
3.66 + ///
3.67 + /// The ItemIntMap \e should be initialized in such way that it maps
3.68 + /// PRE_HEAP (-1) to any element to be put in the heap...
3.69 + enum state_enum {
3.70 + IN_HEAP = 0,
3.71 + PRE_HEAP = -1,
3.72 + POST_HEAP = -2
3.73 + };
3.74 +
3.75 + public:
3.76 + /// \brief The constructor.
3.77 + ///
3.78 + /// The constructor.
3.79 + /// \param _index should be given to the constructor, since it is used
3.80 + /// internally to handle the cross references. The value of the map
3.81 + /// should be PRE_HEAP (-1) for each element.
3.82 + explicit BucketHeap(ItemIntMap &_index) : index(_index), minimal(0) {}
3.83 +
3.84 + /// The number of items stored in the heap.
3.85 + ///
3.86 + /// \brief Returns the number of items stored in the heap.
3.87 + int size() const { return data.size(); }
3.88 +
3.89 + /// \brief Checks if the heap stores no items.
3.90 + ///
3.91 + /// Returns \c true if and only if the heap stores no items.
3.92 + bool empty() const { return data.empty(); }
3.93 +
3.94 + /// \brief Make empty this heap.
3.95 + ///
3.96 + /// Make empty this heap.
3.97 + void clear() {
3.98 + for (int i = 0; i < (int)data.size(); ++i) {
3.99 + index[data[i].item] = -2;
3.100 + }
3.101 + data.clear(); first.clear(); minimal = 0;
3.102 + }
3.103 +
3.104 + private:
3.105 +
3.106 + void relocate_last(int idx) {
3.107 + if (idx + 1 < (int)data.size()) {
3.108 + data[idx] = data.back();
3.109 + if (data[idx].prev != -1) {
3.110 + data[data[idx].prev].next = idx;
3.111 + } else {
3.112 + first[data[idx].value] = idx;
3.113 + }
3.114 + if (data[idx].next != -1) {
3.115 + data[data[idx].next].prev = idx;
3.116 + }
3.117 + index[data[idx].item] = idx;
3.118 + }
3.119 + data.pop_back();
3.120 + }
3.121 +
3.122 + void unlace(int idx) {
3.123 + if (data[idx].prev != -1) {
3.124 + data[data[idx].prev].next = data[idx].next;
3.125 + } else {
3.126 + first[data[idx].value] = data[idx].next;
3.127 + }
3.128 + if (data[idx].next != -1) {
3.129 + data[data[idx].next].prev = data[idx].prev;
3.130 + }
3.131 + }
3.132 +
3.133 + void lace(int idx) {
3.134 + if ((int)first.size() <= data[idx].value) {
3.135 + first.resize(data[idx].value + 1, -1);
3.136 + }
3.137 + data[idx].next = first[data[idx].value];
3.138 + if (data[idx].next != -1) {
3.139 + data[data[idx].next].prev = idx;
3.140 + }
3.141 + first[data[idx].value] = idx;
3.142 + data[idx].prev = -1;
3.143 + }
3.144 +
3.145 + public:
3.146 + /// \brief Insert a pair of item and priority into the heap.
3.147 + ///
3.148 + /// Adds \c p.first to the heap with priority \c p.second.
3.149 + /// \param p The pair to insert.
3.150 + void push(const Pair& p) {
3.151 + push(p.first, p.second);
3.152 + }
3.153 +
3.154 + /// \brief Insert an item into the heap with the given priority.
3.155 + ///
3.156 + /// Adds \c i to the heap with priority \c p.
3.157 + /// \param i The item to insert.
3.158 + /// \param p The priority of the item.
3.159 + void push(const Item &i, const Prio &p) {
3.160 + int idx = data.size();
3.161 + index[i] = idx;
3.162 + data.push_back(BucketItem(i, p));
3.163 + lace(idx);
3.164 + if (p < minimal) {
3.165 + minimal = p;
3.166 + }
3.167 + }
3.168 +
3.169 + /// \brief Returns the item with minimum priority.
3.170 + ///
3.171 + /// This method returns the item with minimum priority.
3.172 + /// \pre The heap must be nonempty.
3.173 + Item top() const {
3.174 + while (first[minimal] == -1) {
3.175 + ++minimal;
3.176 + }
3.177 + return data[first[minimal]].item;
3.178 + }
3.179 +
3.180 + /// \brief Returns the minimum priority.
3.181 + ///
3.182 + /// It returns the minimum priority.
3.183 + /// \pre The heap must be nonempty.
3.184 + Prio prio() const {
3.185 + while (first[minimal] == -1) {
3.186 + ++minimal;
3.187 + }
3.188 + return minimal;
3.189 + }
3.190 +
3.191 + /// \brief Deletes the item with minimum priority.
3.192 + ///
3.193 + /// This method deletes the item with minimum priority from the heap.
3.194 + /// \pre The heap must be non-empty.
3.195 + void pop() {
3.196 + while (first[minimal] == -1) {
3.197 + ++minimal;
3.198 + }
3.199 + int idx = first[minimal];
3.200 + index[data[idx].item] = -2;
3.201 + unlace(idx);
3.202 + relocate_last(idx);
3.203 + }
3.204 +
3.205 + /// \brief Deletes \c i from the heap.
3.206 + ///
3.207 + /// This method deletes item \c i from the heap, if \c i was
3.208 + /// already stored in the heap.
3.209 + /// \param i The item to erase.
3.210 + void erase(const Item &i) {
3.211 + int idx = index[i];
3.212 + index[data[idx].item] = -2;
3.213 + unlace(idx);
3.214 + relocate_last(idx);
3.215 + }
3.216 +
3.217 +
3.218 + /// \brief Returns the priority of \c i.
3.219 + ///
3.220 + /// This function returns the priority of item \c i.
3.221 + /// \pre \c i must be in the heap.
3.222 + /// \param i The item.
3.223 + Prio operator[](const Item &i) const {
3.224 + int idx = index[i];
3.225 + return data[idx].value;
3.226 + }
3.227 +
3.228 + /// \brief \c i gets to the heap with priority \c p independently
3.229 + /// if \c i was already there.
3.230 + ///
3.231 + /// This method calls \ref push(\c i, \c p) if \c i is not stored
3.232 + /// in the heap and sets the priority of \c i to \c p otherwise.
3.233 + /// \param i The item.
3.234 + /// \param p The priority.
3.235 + void set(const Item &i, const Prio &p) {
3.236 + int idx = index[i];
3.237 + if (idx < 0) {
3.238 + push(i,p);
3.239 + } else if (p > data[idx].value) {
3.240 + increase(i, p);
3.241 + } else {
3.242 + decrease(i, p);
3.243 + }
3.244 + }
3.245 +
3.246 + /// \brief Decreases the priority of \c i to \c p.
3.247 +
3.248 + /// This method decreases the priority of item \c i to \c p.
3.249 + /// \pre \c i must be stored in the heap with priority at least \c
3.250 + /// p relative to \c Compare.
3.251 + /// \param i The item.
3.252 + /// \param p The priority.
3.253 + void decrease(const Item &i, const Prio &p) {
3.254 + int idx = index[i];
3.255 + unlace(idx);
3.256 + data[idx].value = p;
3.257 + if (p < minimal) {
3.258 + minimal = p;
3.259 + }
3.260 + lace(idx);
3.261 + }
3.262 +
3.263 + /// \brief Increases the priority of \c i to \c p.
3.264 + ///
3.265 + /// This method sets the priority of item \c i to \c p.
3.266 + /// \pre \c i must be stored in the heap with priority at most \c
3.267 + /// p relative to \c Compare.
3.268 + /// \param i The item.
3.269 + /// \param p The priority.
3.270 + void increase(const Item &i, const Prio &p) {
3.271 + int idx = index[i];
3.272 + unlace(idx);
3.273 + data[idx].value = p;
3.274 + lace(idx);
3.275 + }
3.276 +
3.277 + /// \brief Returns if \c item is in, has already been in, or has
3.278 + /// never been in the heap.
3.279 + ///
3.280 + /// This method returns PRE_HEAP if \c item has never been in the
3.281 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
3.282 + /// otherwise. In the latter case it is possible that \c item will
3.283 + /// get back to the heap again.
3.284 + /// \param i The item.
3.285 + state_enum state(const Item &i) const {
3.286 + int idx = index[i];
3.287 + if (idx >= 0) idx = 0;
3.288 + return state_enum(idx);
3.289 + }
3.290 +
3.291 + /// \brief Sets the state of the \c item in the heap.
3.292 + ///
3.293 + /// Sets the state of the \c item in the heap. It can be used to
3.294 + /// manually clear the heap when it is important to achive the
3.295 + /// better time complexity.
3.296 + /// \param i The item.
3.297 + /// \param st The state. It should not be \c IN_HEAP.
3.298 + void state(const Item& i, state_enum st) {
3.299 + switch (st) {
3.300 + case POST_HEAP:
3.301 + case PRE_HEAP:
3.302 + if (state(i) == IN_HEAP) {
3.303 + erase(i);
3.304 + }
3.305 + index[i] = st;
3.306 + break;
3.307 + case IN_HEAP:
3.308 + break;
3.309 + }
3.310 + }
3.311 +
3.312 + private:
3.313 +
3.314 + struct BucketItem {
3.315 + BucketItem(const Item& _item, int _value)
3.316 + : item(_item), value(_value) {}
3.317 +
3.318 + Item item;
3.319 + int value;
3.320 +
3.321 + int prev, next;
3.322 + };
3.323 +
3.324 + ItemIntMap& index;
3.325 + std::vector<int> first;
3.326 + std::vector<BucketItem> data;
3.327 + mutable int minimal;
3.328 +
3.329 + }; // class BucketHeap
3.330 +
3.331 +
3.332 + template <typename _Item, typename _ItemIntMap>
3.333 + class BucketHeap<_Item, _ItemIntMap, false> {
3.334 +
3.335 + public:
3.336 + typedef _Item Item;
3.337 + typedef int Prio;
3.338 + typedef std::pair<Item, Prio> Pair;
3.339 + typedef _ItemIntMap ItemIntMap;
3.340 +
3.341 + enum state_enum {
3.342 + IN_HEAP = 0,
3.343 + PRE_HEAP = -1,
3.344 + POST_HEAP = -2
3.345 + };
3.346 +
3.347 + public:
3.348 +
3.349 + explicit BucketHeap(ItemIntMap &_index) : index(_index), maximal(-1) {}
3.350 +
3.351 + int size() const { return data.size(); }
3.352 + bool empty() const { return data.empty(); }
3.353 +
3.354 + void clear() {
3.355 + for (int i = 0; i < (int)data.size(); ++i) {
3.356 + index[data[i].item] = -2;
3.357 + }
3.358 + data.clear(); first.clear(); maximal = -1;
3.359 + }
3.360 +
3.361 + private:
3.362 +
3.363 + void relocate_last(int idx) {
3.364 + if (idx + 1 != (int)data.size()) {
3.365 + data[idx] = data.back();
3.366 + if (data[idx].prev != -1) {
3.367 + data[data[idx].prev].next = idx;
3.368 + } else {
3.369 + first[data[idx].value] = idx;
3.370 + }
3.371 + if (data[idx].next != -1) {
3.372 + data[data[idx].next].prev = idx;
3.373 + }
3.374 + index[data[idx].item] = idx;
3.375 + }
3.376 + data.pop_back();
3.377 + }
3.378 +
3.379 + void unlace(int idx) {
3.380 + if (data[idx].prev != -1) {
3.381 + data[data[idx].prev].next = data[idx].next;
3.382 + } else {
3.383 + first[data[idx].value] = data[idx].next;
3.384 + }
3.385 + if (data[idx].next != -1) {
3.386 + data[data[idx].next].prev = data[idx].prev;
3.387 + }
3.388 + }
3.389 +
3.390 + void lace(int idx) {
3.391 + if ((int)first.size() <= data[idx].value) {
3.392 + first.resize(data[idx].value + 1, -1);
3.393 + }
3.394 + data[idx].next = first[data[idx].value];
3.395 + if (data[idx].next != -1) {
3.396 + data[data[idx].next].prev = idx;
3.397 + }
3.398 + first[data[idx].value] = idx;
3.399 + data[idx].prev = -1;
3.400 + }
3.401 +
3.402 + public:
3.403 +
3.404 + void push(const Pair& p) {
3.405 + push(p.first, p.second);
3.406 + }
3.407 +
3.408 + void push(const Item &i, const Prio &p) {
3.409 + int idx = data.size();
3.410 + index[i] = idx;
3.411 + data.push_back(BucketItem(i, p));
3.412 + lace(idx);
3.413 + if (data[idx].value > maximal) {
3.414 + maximal = data[idx].value;
3.415 + }
3.416 + }
3.417 +
3.418 + Item top() const {
3.419 + while (first[maximal] == -1) {
3.420 + --maximal;
3.421 + }
3.422 + return data[first[maximal]].item;
3.423 + }
3.424 +
3.425 + Prio prio() const {
3.426 + while (first[maximal] == -1) {
3.427 + --maximal;
3.428 + }
3.429 + return maximal;
3.430 + }
3.431 +
3.432 + void pop() {
3.433 + while (first[maximal] == -1) {
3.434 + --maximal;
3.435 + }
3.436 + int idx = first[maximal];
3.437 + index[data[idx].item] = -2;
3.438 + unlace(idx);
3.439 + relocate_last(idx);
3.440 + }
3.441 +
3.442 + void erase(const Item &i) {
3.443 + int idx = index[i];
3.444 + index[data[idx].item] = -2;
3.445 + unlace(idx);
3.446 + relocate_last(idx);
3.447 + }
3.448 +
3.449 + Prio operator[](const Item &i) const {
3.450 + int idx = index[i];
3.451 + return data[idx].value;
3.452 + }
3.453 +
3.454 + void set(const Item &i, const Prio &p) {
3.455 + int idx = index[i];
3.456 + if (idx < 0) {
3.457 + push(i,p);
3.458 + } else if (p > data[idx].value) {
3.459 + decrease(i, p);
3.460 + } else {
3.461 + increase(i, p);
3.462 + }
3.463 + }
3.464 +
3.465 + void decrease(const Item &i, const Prio &p) {
3.466 + int idx = index[i];
3.467 + unlace(idx);
3.468 + data[idx].value = p;
3.469 + if (p > maximal) {
3.470 + maximal = p;
3.471 + }
3.472 + lace(idx);
3.473 + }
3.474 +
3.475 + void increase(const Item &i, const Prio &p) {
3.476 + int idx = index[i];
3.477 + unlace(idx);
3.478 + data[idx].value = p;
3.479 + lace(idx);
3.480 + }
3.481 +
3.482 + state_enum state(const Item &i) const {
3.483 + int idx = index[i];
3.484 + if (idx >= 0) idx = 0;
3.485 + return state_enum(idx);
3.486 + }
3.487 +
3.488 + void state(const Item& i, state_enum st) {
3.489 + switch (st) {
3.490 + case POST_HEAP:
3.491 + case PRE_HEAP:
3.492 + if (state(i) == IN_HEAP) {
3.493 + erase(i);
3.494 + }
3.495 + index[i] = st;
3.496 + break;
3.497 + case IN_HEAP:
3.498 + break;
3.499 + }
3.500 + }
3.501 +
3.502 + private:
3.503 +
3.504 + struct BucketItem {
3.505 + BucketItem(const Item& _item, int _value)
3.506 + : item(_item), value(_value) {}
3.507 +
3.508 + Item item;
3.509 + int value;
3.510 +
3.511 + int prev, next;
3.512 + };
3.513 +
3.514 + ItemIntMap& index;
3.515 + std::vector<int> first;
3.516 + std::vector<BucketItem> data;
3.517 + mutable int maximal;
3.518 +
3.519 + }; // class BucketHeap
3.520 +
3.521 +}
3.522 +
3.523 +#endif
4.1 --- a/lemon/linear_heap.h Tue Apr 04 17:43:23 2006 +0000
4.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
4.3 @@ -1,520 +0,0 @@
4.4 -/* -*- C++ -*-
4.5 - *
4.6 - * This file is a part of LEMON, a generic C++ optimization library
4.7 - *
4.8 - * Copyright (C) 2003-2006
4.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 - *
4.12 - * Permission to use, modify and distribute this software is granted
4.13 - * provided that this copyright notice appears in all copies. For
4.14 - * precise terms see the accompanying LICENSE file.
4.15 - *
4.16 - * This software is provided "AS IS" with no warranty of any kind,
4.17 - * express or implied, and with no claim as to its suitability for any
4.18 - * purpose.
4.19 - *
4.20 - */
4.21 -
4.22 -#ifndef LEMON_LINEAR_HEAP_H
4.23 -#define LEMON_LINEAR_HEAP_H
4.24 -
4.25 -///\ingroup auxdat
4.26 -///\file
4.27 -///\brief Binary Heap implementation.
4.28 -
4.29 -#include <vector>
4.30 -#include <utility>
4.31 -#include <functional>
4.32 -
4.33 -namespace lemon {
4.34 -
4.35 - /// \ingroup auxdat
4.36 -
4.37 - /// \brief A Linear Heap implementation.
4.38 - ///
4.39 - /// This class implements the \e linear \e heap data structure. A \e heap
4.40 - /// is a data structure for storing items with specified values called \e
4.41 - /// priorities in such a way that finding the item with minimum priority is
4.42 - /// efficient. The linear heap is very simple implementation, it can store
4.43 - /// only integer priorities and it stores for each priority in the [0..C]
4.44 - /// range a list of items. So it should be used only when the priorities
4.45 - /// are small. It is not intended to use as dijkstra heap.
4.46 - ///
4.47 - /// \param _Item Type of the items to be stored.
4.48 - /// \param _ItemIntMap A read and writable Item int map, used internally
4.49 - /// to handle the cross references.
4.50 - /// \param minimize If the given parameter is true then the heap gives back
4.51 - /// the lowest priority.
4.52 - template <typename _Item, typename _ItemIntMap, bool minimize = true >
4.53 - class LinearHeap {
4.54 -
4.55 - public:
4.56 - typedef _Item Item;
4.57 - typedef int Prio;
4.58 - typedef std::pair<Item, Prio> Pair;
4.59 - typedef _ItemIntMap ItemIntMap;
4.60 -
4.61 - /// \brief Type to represent the items states.
4.62 - ///
4.63 - /// Each Item element have a state associated to it. It may be "in heap",
4.64 - /// "pre heap" or "post heap". The latter two are indifferent from the
4.65 - /// heap's point of view, but may be useful to the user.
4.66 - ///
4.67 - /// The ItemIntMap \e should be initialized in such way that it maps
4.68 - /// PRE_HEAP (-1) to any element to be put in the heap...
4.69 - enum state_enum {
4.70 - IN_HEAP = 0,
4.71 - PRE_HEAP = -1,
4.72 - POST_HEAP = -2
4.73 - };
4.74 -
4.75 - public:
4.76 - /// \brief The constructor.
4.77 - ///
4.78 - /// The constructor.
4.79 - /// \param _index should be given to the constructor, since it is used
4.80 - /// internally to handle the cross references. The value of the map
4.81 - /// should be PRE_HEAP (-1) for each element.
4.82 - explicit LinearHeap(ItemIntMap &_index) : index(_index), minimal(0) {}
4.83 -
4.84 - /// The number of items stored in the heap.
4.85 - ///
4.86 - /// \brief Returns the number of items stored in the heap.
4.87 - int size() const { return data.size(); }
4.88 -
4.89 - /// \brief Checks if the heap stores no items.
4.90 - ///
4.91 - /// Returns \c true if and only if the heap stores no items.
4.92 - bool empty() const { return data.empty(); }
4.93 -
4.94 - /// \brief Make empty this heap.
4.95 - ///
4.96 - /// Make empty this heap.
4.97 - void clear() {
4.98 - for (int i = 0; i < (int)data.size(); ++i) {
4.99 - index[data[i].item] = -2;
4.100 - }
4.101 - data.clear(); first.clear(); minimal = 0;
4.102 - }
4.103 -
4.104 - private:
4.105 -
4.106 - void relocate_last(int idx) {
4.107 - if (idx + 1 < (int)data.size()) {
4.108 - data[idx] = data.back();
4.109 - if (data[idx].prev != -1) {
4.110 - data[data[idx].prev].next = idx;
4.111 - } else {
4.112 - first[data[idx].value] = idx;
4.113 - }
4.114 - if (data[idx].next != -1) {
4.115 - data[data[idx].next].prev = idx;
4.116 - }
4.117 - index[data[idx].item] = idx;
4.118 - }
4.119 - data.pop_back();
4.120 - }
4.121 -
4.122 - void unlace(int idx) {
4.123 - if (data[idx].prev != -1) {
4.124 - data[data[idx].prev].next = data[idx].next;
4.125 - } else {
4.126 - first[data[idx].value] = data[idx].next;
4.127 - }
4.128 - if (data[idx].next != -1) {
4.129 - data[data[idx].next].prev = data[idx].prev;
4.130 - }
4.131 - }
4.132 -
4.133 - void lace(int idx) {
4.134 - if ((int)first.size() <= data[idx].value) {
4.135 - first.resize(data[idx].value + 1, -1);
4.136 - }
4.137 - data[idx].next = first[data[idx].value];
4.138 - if (data[idx].next != -1) {
4.139 - data[data[idx].next].prev = idx;
4.140 - }
4.141 - first[data[idx].value] = idx;
4.142 - data[idx].prev = -1;
4.143 - }
4.144 -
4.145 - public:
4.146 - /// \brief Insert a pair of item and priority into the heap.
4.147 - ///
4.148 - /// Adds \c p.first to the heap with priority \c p.second.
4.149 - /// \param p The pair to insert.
4.150 - void push(const Pair& p) {
4.151 - push(p.first, p.second);
4.152 - }
4.153 -
4.154 - /// \brief Insert an item into the heap with the given priority.
4.155 - ///
4.156 - /// Adds \c i to the heap with priority \c p.
4.157 - /// \param i The item to insert.
4.158 - /// \param p The priority of the item.
4.159 - void push(const Item &i, const Prio &p) {
4.160 - int idx = data.size();
4.161 - index[i] = idx;
4.162 - data.push_back(LinearItem(i, p));
4.163 - lace(idx);
4.164 - if (p < minimal) {
4.165 - minimal = p;
4.166 - }
4.167 - }
4.168 -
4.169 - /// \brief Returns the item with minimum priority.
4.170 - ///
4.171 - /// This method returns the item with minimum priority.
4.172 - /// \pre The heap must be nonempty.
4.173 - Item top() const {
4.174 - while (first[minimal] == -1) {
4.175 - ++minimal;
4.176 - }
4.177 - return data[first[minimal]].item;
4.178 - }
4.179 -
4.180 - /// \brief Returns the minimum priority.
4.181 - ///
4.182 - /// It returns the minimum priority.
4.183 - /// \pre The heap must be nonempty.
4.184 - Prio prio() const {
4.185 - while (first[minimal] == -1) {
4.186 - ++minimal;
4.187 - }
4.188 - return minimal;
4.189 - }
4.190 -
4.191 - /// \brief Deletes the item with minimum priority.
4.192 - ///
4.193 - /// This method deletes the item with minimum priority from the heap.
4.194 - /// \pre The heap must be non-empty.
4.195 - void pop() {
4.196 - while (first[minimal] == -1) {
4.197 - ++minimal;
4.198 - }
4.199 - int idx = first[minimal];
4.200 - index[data[idx].item] = -2;
4.201 - unlace(idx);
4.202 - relocate_last(idx);
4.203 - }
4.204 -
4.205 - /// \brief Deletes \c i from the heap.
4.206 - ///
4.207 - /// This method deletes item \c i from the heap, if \c i was
4.208 - /// already stored in the heap.
4.209 - /// \param i The item to erase.
4.210 - void erase(const Item &i) {
4.211 - int idx = index[i];
4.212 - index[data[idx].item] = -2;
4.213 - unlace(idx);
4.214 - relocate_last(idx);
4.215 - }
4.216 -
4.217 -
4.218 - /// \brief Returns the priority of \c i.
4.219 - ///
4.220 - /// This function returns the priority of item \c i.
4.221 - /// \pre \c i must be in the heap.
4.222 - /// \param i The item.
4.223 - Prio operator[](const Item &i) const {
4.224 - int idx = index[i];
4.225 - return data[idx].value;
4.226 - }
4.227 -
4.228 - /// \brief \c i gets to the heap with priority \c p independently
4.229 - /// if \c i was already there.
4.230 - ///
4.231 - /// This method calls \ref push(\c i, \c p) if \c i is not stored
4.232 - /// in the heap and sets the priority of \c i to \c p otherwise.
4.233 - /// \param i The item.
4.234 - /// \param p The priority.
4.235 - void set(const Item &i, const Prio &p) {
4.236 - int idx = index[i];
4.237 - if (idx < 0) {
4.238 - push(i,p);
4.239 - } else if (p > data[idx].value) {
4.240 - increase(i, p);
4.241 - } else {
4.242 - decrease(i, p);
4.243 - }
4.244 - }
4.245 -
4.246 - /// \brief Decreases the priority of \c i to \c p.
4.247 -
4.248 - /// This method decreases the priority of item \c i to \c p.
4.249 - /// \pre \c i must be stored in the heap with priority at least \c
4.250 - /// p relative to \c Compare.
4.251 - /// \param i The item.
4.252 - /// \param p The priority.
4.253 - void decrease(const Item &i, const Prio &p) {
4.254 - int idx = index[i];
4.255 - unlace(idx);
4.256 - data[idx].value = p;
4.257 - if (p < minimal) {
4.258 - minimal = p;
4.259 - }
4.260 - lace(idx);
4.261 - }
4.262 -
4.263 - /// \brief Increases the priority of \c i to \c p.
4.264 - ///
4.265 - /// This method sets the priority of item \c i to \c p.
4.266 - /// \pre \c i must be stored in the heap with priority at most \c
4.267 - /// p relative to \c Compare.
4.268 - /// \param i The item.
4.269 - /// \param p The priority.
4.270 - void increase(const Item &i, const Prio &p) {
4.271 - int idx = index[i];
4.272 - unlace(idx);
4.273 - data[idx].value = p;
4.274 - lace(idx);
4.275 - }
4.276 -
4.277 - /// \brief Returns if \c item is in, has already been in, or has
4.278 - /// never been in the heap.
4.279 - ///
4.280 - /// This method returns PRE_HEAP if \c item has never been in the
4.281 - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
4.282 - /// otherwise. In the latter case it is possible that \c item will
4.283 - /// get back to the heap again.
4.284 - /// \param i The item.
4.285 - state_enum state(const Item &i) const {
4.286 - int idx = index[i];
4.287 - if (idx >= 0) idx = 0;
4.288 - return state_enum(idx);
4.289 - }
4.290 -
4.291 - /// \brief Sets the state of the \c item in the heap.
4.292 - ///
4.293 - /// Sets the state of the \c item in the heap. It can be used to
4.294 - /// manually clear the heap when it is important to achive the
4.295 - /// better time complexity.
4.296 - /// \param i The item.
4.297 - /// \param st The state. It should not be \c IN_HEAP.
4.298 - void state(const Item& i, state_enum st) {
4.299 - switch (st) {
4.300 - case POST_HEAP:
4.301 - case PRE_HEAP:
4.302 - if (state(i) == IN_HEAP) {
4.303 - erase(i);
4.304 - }
4.305 - index[i] = st;
4.306 - break;
4.307 - case IN_HEAP:
4.308 - break;
4.309 - }
4.310 - }
4.311 -
4.312 - private:
4.313 -
4.314 - struct LinearItem {
4.315 - LinearItem(const Item& _item, int _value)
4.316 - : item(_item), value(_value) {}
4.317 -
4.318 - Item item;
4.319 - int value;
4.320 -
4.321 - int prev, next;
4.322 - };
4.323 -
4.324 - ItemIntMap& index;
4.325 - std::vector<int> first;
4.326 - std::vector<LinearItem> data;
4.327 - mutable int minimal;
4.328 -
4.329 - }; // class LinearHeap
4.330 -
4.331 -
4.332 - template <typename _Item, typename _ItemIntMap>
4.333 - class LinearHeap<_Item, _ItemIntMap, false> {
4.334 -
4.335 - public:
4.336 - typedef _Item Item;
4.337 - typedef int Prio;
4.338 - typedef std::pair<Item, Prio> Pair;
4.339 - typedef _ItemIntMap ItemIntMap;
4.340 -
4.341 - enum state_enum {
4.342 - IN_HEAP = 0,
4.343 - PRE_HEAP = -1,
4.344 - POST_HEAP = -2
4.345 - };
4.346 -
4.347 - public:
4.348 -
4.349 - explicit LinearHeap(ItemIntMap &_index) : index(_index), maximal(-1) {}
4.350 -
4.351 - int size() const { return data.size(); }
4.352 - bool empty() const { return data.empty(); }
4.353 -
4.354 - void clear() {
4.355 - for (int i = 0; i < (int)data.size(); ++i) {
4.356 - index[data[i].item] = -2;
4.357 - }
4.358 - data.clear(); first.clear(); maximal = -1;
4.359 - }
4.360 -
4.361 - private:
4.362 -
4.363 - void relocate_last(int idx) {
4.364 - if (idx + 1 != (int)data.size()) {
4.365 - data[idx] = data.back();
4.366 - if (data[idx].prev != -1) {
4.367 - data[data[idx].prev].next = idx;
4.368 - } else {
4.369 - first[data[idx].value] = idx;
4.370 - }
4.371 - if (data[idx].next != -1) {
4.372 - data[data[idx].next].prev = idx;
4.373 - }
4.374 - index[data[idx].item] = idx;
4.375 - }
4.376 - data.pop_back();
4.377 - }
4.378 -
4.379 - void unlace(int idx) {
4.380 - if (data[idx].prev != -1) {
4.381 - data[data[idx].prev].next = data[idx].next;
4.382 - } else {
4.383 - first[data[idx].value] = data[idx].next;
4.384 - }
4.385 - if (data[idx].next != -1) {
4.386 - data[data[idx].next].prev = data[idx].prev;
4.387 - }
4.388 - }
4.389 -
4.390 - void lace(int idx) {
4.391 - if ((int)first.size() <= data[idx].value) {
4.392 - first.resize(data[idx].value + 1, -1);
4.393 - }
4.394 - data[idx].next = first[data[idx].value];
4.395 - if (data[idx].next != -1) {
4.396 - data[data[idx].next].prev = idx;
4.397 - }
4.398 - first[data[idx].value] = idx;
4.399 - data[idx].prev = -1;
4.400 - }
4.401 -
4.402 - public:
4.403 -
4.404 - void push(const Pair& p) {
4.405 - push(p.first, p.second);
4.406 - }
4.407 -
4.408 - void push(const Item &i, const Prio &p) {
4.409 - int idx = data.size();
4.410 - index[i] = idx;
4.411 - data.push_back(LinearItem(i, p));
4.412 - lace(idx);
4.413 - if (data[idx].value > maximal) {
4.414 - maximal = data[idx].value;
4.415 - }
4.416 - }
4.417 -
4.418 - Item top() const {
4.419 - while (first[maximal] == -1) {
4.420 - --maximal;
4.421 - }
4.422 - return data[first[maximal]].item;
4.423 - }
4.424 -
4.425 - Prio prio() const {
4.426 - while (first[maximal] == -1) {
4.427 - --maximal;
4.428 - }
4.429 - return maximal;
4.430 - }
4.431 -
4.432 - void pop() {
4.433 - while (first[maximal] == -1) {
4.434 - --maximal;
4.435 - }
4.436 - int idx = first[maximal];
4.437 - index[data[idx].item] = -2;
4.438 - unlace(idx);
4.439 - relocate_last(idx);
4.440 - }
4.441 -
4.442 - void erase(const Item &i) {
4.443 - int idx = index[i];
4.444 - index[data[idx].item] = -2;
4.445 - unlace(idx);
4.446 - relocate_last(idx);
4.447 - }
4.448 -
4.449 - Prio operator[](const Item &i) const {
4.450 - int idx = index[i];
4.451 - return data[idx].value;
4.452 - }
4.453 -
4.454 - void set(const Item &i, const Prio &p) {
4.455 - int idx = index[i];
4.456 - if (idx < 0) {
4.457 - push(i,p);
4.458 - } else if (p > data[idx].value) {
4.459 - decrease(i, p);
4.460 - } else {
4.461 - increase(i, p);
4.462 - }
4.463 - }
4.464 -
4.465 - void decrease(const Item &i, const Prio &p) {
4.466 - int idx = index[i];
4.467 - unlace(idx);
4.468 - data[idx].value = p;
4.469 - if (p > maximal) {
4.470 - maximal = p;
4.471 - }
4.472 - lace(idx);
4.473 - }
4.474 -
4.475 - void increase(const Item &i, const Prio &p) {
4.476 - int idx = index[i];
4.477 - unlace(idx);
4.478 - data[idx].value = p;
4.479 - lace(idx);
4.480 - }
4.481 -
4.482 - state_enum state(const Item &i) const {
4.483 - int idx = index[i];
4.484 - if (idx >= 0) idx = 0;
4.485 - return state_enum(idx);
4.486 - }
4.487 -
4.488 - void state(const Item& i, state_enum st) {
4.489 - switch (st) {
4.490 - case POST_HEAP:
4.491 - case PRE_HEAP:
4.492 - if (state(i) == IN_HEAP) {
4.493 - erase(i);
4.494 - }
4.495 - index[i] = st;
4.496 - break;
4.497 - case IN_HEAP:
4.498 - break;
4.499 - }
4.500 - }
4.501 -
4.502 - private:
4.503 -
4.504 - struct LinearItem {
4.505 - LinearItem(const Item& _item, int _value)
4.506 - : item(_item), value(_value) {}
4.507 -
4.508 - Item item;
4.509 - int value;
4.510 -
4.511 - int prev, next;
4.512 - };
4.513 -
4.514 - ItemIntMap& index;
4.515 - std::vector<int> first;
4.516 - std::vector<LinearItem> data;
4.517 - mutable int maximal;
4.518 -
4.519 - }; // class LinearHeap
4.520 -
4.521 -}
4.522 -
4.523 -#endif
5.1 --- a/lemon/min_cut.h Tue Apr 04 17:43:23 2006 +0000
5.2 +++ b/lemon/min_cut.h Tue Apr 04 17:45:35 2006 +0000
5.3 @@ -24,7 +24,7 @@
5.4
5.5 #include <lemon/list_graph.h>
5.6 #include <lemon/bin_heap.h>
5.7 -#include <lemon/linear_heap.h>
5.8 +#include <lemon/bucket_heap.h>
5.9
5.10 #include <lemon/bits/invalid.h>
5.11 #include <lemon/error.h>
5.12 @@ -48,7 +48,7 @@
5.13 struct HeapSelector<ConstMap<CapacityKey, Const<int, 1> > > {
5.14 template <typename Key, typename Value, typename Ref>
5.15 struct Selector {
5.16 - typedef LinearHeap<Key, Ref, false > Heap;
5.17 + typedef BucketHeap<Key, Ref, false > Heap;
5.18 };
5.19 };
5.20
5.21 @@ -94,7 +94,7 @@
5.22 /// maximalize the priorities. The default heap type is
5.23 /// the \ref BinHeap, but it is specialized when the
5.24 /// CapacityMap is ConstMap<Graph::Node, Const<int, 1> >
5.25 - /// to LinearHeap.
5.26 + /// to BucketHeap.
5.27 ///
5.28 /// \sa MaxCardinalitySearch
5.29 typedef typename _min_cut_bits
5.30 @@ -841,7 +841,7 @@
5.31 ///
5.32 /// The complexity of the algorithm is O(n*e*log(n)) but with Fibonacci
5.33 /// heap it can be decreased to O(n*e+n^2*log(n)). When the neutral capacity
5.34 - /// map is used then it uses LinearHeap which results O(n*e) time complexity.
5.35 + /// map is used then it uses BucketHeap which results O(n*e) time complexity.
5.36 #ifdef DOXYGEN
5.37 template <typename _Graph, typename _CapacityMap, typename _Traits>
5.38 #else
6.1 --- a/lemon/topology.h Tue Apr 04 17:43:23 2006 +0000
6.2 +++ b/lemon/topology.h Tue Apr 04 17:45:35 2006 +0000
6.3 @@ -30,7 +30,7 @@
6.4 #include <lemon/concept_check.h>
6.5
6.6 #include <lemon/bin_heap.h>
6.7 -#include <lemon/linear_heap.h>
6.8 +#include <lemon/bucket_heap.h>
6.9
6.10 #include <stack>
6.11 #include <functional>
7.1 --- a/test/heap_test.cc Tue Apr 04 17:43:23 2006 +0000
7.2 +++ b/test/heap_test.cc Tue Apr 04 17:45:35 2006 +0000
7.3 @@ -31,7 +31,7 @@
7.4 #include <lemon/bin_heap.h>
7.5 #include <lemon/fib_heap.h>
7.6 #include <lemon/radix_heap.h>
7.7 -#include <lemon/linear_heap.h>
7.8 +#include <lemon/bucket_heap.h>
7.9
7.10 #include "test_tools.h"
7.11
7.12 @@ -120,14 +120,14 @@
7.13 }
7.14
7.15 {
7.16 - std::cerr << "Checking Linear Heap" << std::endl;
7.17 + std::cerr << "Checking Bucket Heap" << std::endl;
7.18
7.19 - typedef LinearHeap<Item, ItemIntMap> IntHeap;
7.20 + typedef BucketHeap<Item, ItemIntMap> IntHeap;
7.21 checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
7.22 heapSortTest<IntHeap>(100);
7.23 heapIncreaseTest<IntHeap>(100);
7.24
7.25 - typedef LinearHeap<Node, Graph::NodeMap<int> > NodeHeap;
7.26 + typedef BucketHeap<Node, Graph::NodeMap<int> > NodeHeap;
7.27 checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
7.28 Timer timer;
7.29 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);