1.1 --- a/lemon/Makefile.am Fri Oct 14 10:53:51 2005 +0000
1.2 +++ b/lemon/Makefile.am Fri Oct 14 10:58:54 2005 +0000
1.3 @@ -41,6 +41,7 @@
1.4 iterable_maps.h \
1.5 johnson.h \
1.6 kruskal.h \
1.7 + linear_heap.h \
1.8 list_graph.h \
1.9 lp.h \
1.10 lp_base.h \
1.11 @@ -48,6 +49,7 @@
1.12 lp_glpk.h \
1.13 lp_skeleton.h \
1.14 maps.h \
1.15 + matrix_maps.h \
1.16 max_matching.h \
1.17 min_cost_flow.h \
1.18 suurballe.h \
1.19 @@ -57,6 +59,7 @@
1.20 smart_graph.h \
1.21 time_measure.h \
1.22 topology.h \
1.23 + traits.h \
1.24 unionfind.h \
1.25 xy.h \
1.26 concept_check.h \
1.27 @@ -82,6 +85,7 @@
1.28 concept/graph.h \
1.29 concept/graph_component.h \
1.30 concept/undir_graph.h \
1.31 + concept/matrix_maps.h \
1.32 concept/maps.h \
1.33 concept/heap.h \
1.34 concept/path.h
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/linear_heap.h Fri Oct 14 10:58:54 2005 +0000
2.3 @@ -0,0 +1,486 @@
2.4 +/* -*- C++ -*-
2.5 + * lemon/linear_heap.h - Part of LEMON, a generic C++ optimization library
2.6 + *
2.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.9 + *
2.10 + * Permission to use, modify and distribute this software is granted
2.11 + * provided that this copyright notice appears in all copies. For
2.12 + * precise terms see the accompanying LICENSE file.
2.13 + *
2.14 + * This software is provided "AS IS" with no warranty of any kind,
2.15 + * express or implied, and with no claim as to its suitability for any
2.16 + * purpose.
2.17 + *
2.18 + */
2.19 +
2.20 +#ifndef LEMON_LINEAR_HEAP_H
2.21 +#define LEMON_LINEAR_HEAP_H
2.22 +
2.23 +///\ingroup auxdat
2.24 +///\file
2.25 +///\brief Binary Heap implementation.
2.26 +
2.27 +#include <vector>
2.28 +#include <utility>
2.29 +#include <functional>
2.30 +
2.31 +namespace lemon {
2.32 +
2.33 + /// \addtogroup auxdat
2.34 + /// @{
2.35 +
2.36 + /// \brief A Linear Heap implementation.
2.37 + ///
2.38 + /// This class implements the \e linear \e heap data structure. A \e heap
2.39 + /// is a data structure for storing items with specified values called \e
2.40 + /// priorities in such a way that finding the item with minimum priority is
2.41 + /// efficient. The linear heap is very simple implementation, it can store
2.42 + /// only integer priorities and it stores for each priority in the [0..C]
2.43 + /// range a list of items. So it should be used only when the priorities
2.44 + /// are small. It is not intended to use as dijkstra heap.
2.45 + ///
2.46 + /// \param _Item Type of the items to be stored.
2.47 + /// \param _ItemIntMap A read and writable Item int map, used internally
2.48 + /// to handle the cross references.
2.49 + /// \param minimize If the given parameter is true then the heap gives back
2.50 + /// the lowest priority.
2.51 + template <typename _Item, typename _ItemIntMap, bool minimize = true >
2.52 + class LinearHeap {
2.53 +
2.54 + public:
2.55 + typedef _Item Item;
2.56 + typedef int Prio;
2.57 + typedef std::pair<Item, Prio> Pair;
2.58 + typedef _ItemIntMap ItemIntMap;
2.59 +
2.60 + /// \brief Type to represent the items states.
2.61 + ///
2.62 + /// Each Item element have a state associated to it. It may be "in heap",
2.63 + /// "pre heap" or "post heap". The latter two are indifferent from the
2.64 + /// heap's point of view, but may be useful to the user.
2.65 + ///
2.66 + /// The ItemIntMap \e should be initialized in such way that it maps
2.67 + /// PRE_HEAP (-1) to any element to be put in the heap...
2.68 + enum state_enum {
2.69 + IN_HEAP = 0,
2.70 + PRE_HEAP = -1,
2.71 + POST_HEAP = -2
2.72 + };
2.73 +
2.74 + public:
2.75 + /// \brief The constructor.
2.76 + ///
2.77 + /// The constructor.
2.78 + /// \param _index should be given to the constructor, since it is used
2.79 + /// internally to handle the cross references. The value of the map
2.80 + /// should be PRE_HEAP (-1) for each element.
2.81 + explicit LinearHeap(ItemIntMap &_index) : index(_index), minimal(0) {}
2.82 +
2.83 + /// The number of items stored in the heap.
2.84 + ///
2.85 + /// \brief Returns the number of items stored in the heap.
2.86 + int size() const { return data.size(); }
2.87 +
2.88 + /// \brief Checks if the heap stores no items.
2.89 + ///
2.90 + /// Returns \c true if and only if the heap stores no items.
2.91 + bool empty() const { return data.empty(); }
2.92 +
2.93 + /// \brief Make empty this heap.
2.94 + ///
2.95 + /// Make empty this heap.
2.96 + void clear() {
2.97 + for (int i = 0; i < (int)data.size(); ++i) {
2.98 + index[data[i].item] = -2;
2.99 + }
2.100 + data.clear(); first.clear(); minimal = 0;
2.101 + }
2.102 +
2.103 + private:
2.104 +
2.105 + void relocate_last(int idx) {
2.106 + if (idx + 1 < (int)data.size()) {
2.107 + data[idx] = data.back();
2.108 + if (data[idx].prev != -1) {
2.109 + data[data[idx].prev].next = idx;
2.110 + } else {
2.111 + first[data[idx].value] = idx;
2.112 + }
2.113 + if (data[idx].next != -1) {
2.114 + data[data[idx].next].prev = idx;
2.115 + }
2.116 + index[data[idx].item] = idx;
2.117 + }
2.118 + data.pop_back();
2.119 + }
2.120 +
2.121 + void unlace(int idx) {
2.122 + if (data[idx].prev != -1) {
2.123 + data[data[idx].prev].next = data[idx].next;
2.124 + } else {
2.125 + first[data[idx].value] = data[idx].next;
2.126 + }
2.127 + if (data[idx].next != -1) {
2.128 + data[data[idx].next].prev = data[idx].prev;
2.129 + }
2.130 + }
2.131 +
2.132 + void lace(int idx) {
2.133 + if ((int)first.size() <= data[idx].value) {
2.134 + first.resize(data[idx].value + 1, -1);
2.135 + }
2.136 + data[idx].next = first[data[idx].value];
2.137 + if (data[idx].next != -1) {
2.138 + data[data[idx].next].prev = idx;
2.139 + }
2.140 + first[data[idx].value] = idx;
2.141 + data[idx].prev = -1;
2.142 + }
2.143 +
2.144 + public:
2.145 + /// \brief Insert a pair of item and priority into the heap.
2.146 + ///
2.147 + /// Adds \c p.first to the heap with priority \c p.second.
2.148 + /// \param p The pair to insert.
2.149 + void push(const Pair& p) {
2.150 + push(p.first, p.second);
2.151 + }
2.152 +
2.153 + /// \brief Insert an item into the heap with the given priority.
2.154 + ///
2.155 + /// Adds \c i to the heap with priority \c p.
2.156 + /// \param i The item to insert.
2.157 + /// \param p The priority of the item.
2.158 + void push(const Item &i, const Prio &p) {
2.159 + int idx = data.size();
2.160 + index[i] = idx;
2.161 + data.push_back(LinearItem(i, p));
2.162 + lace(idx);
2.163 + if (p < minimal) {
2.164 + minimal = p;
2.165 + }
2.166 + }
2.167 +
2.168 + /// \brief Returns the item with minimum priority relative to \c Compare.
2.169 + ///
2.170 + /// This method returns the item with minimum priority relative to \c
2.171 + /// Compare.
2.172 + /// \pre The heap must be nonempty.
2.173 + Item top() const {
2.174 + while (first[minimal] == -1) {
2.175 + ++minimal;
2.176 + }
2.177 + return data[first[minimal]].item;
2.178 + }
2.179 +
2.180 + /// \brief Returns the minimum priority relative to \c Compare.
2.181 + ///
2.182 + /// It returns the minimum priority relative to \c Compare.
2.183 + /// \pre The heap must be nonempty.
2.184 + Prio prio() const {
2.185 + while (first[minimal] == -1) {
2.186 + ++minimal;
2.187 + }
2.188 + return minimal;
2.189 + }
2.190 +
2.191 + /// \brief Deletes the item with minimum priority relative to \c Compare.
2.192 + ///
2.193 + /// This method deletes the item with minimum priority relative to \c
2.194 + /// Compare from the heap.
2.195 + /// \pre The heap must be non-empty.
2.196 + void pop() {
2.197 + while (first[minimal] == -1) {
2.198 + ++minimal;
2.199 + }
2.200 + int idx = first[minimal];
2.201 + index[data[idx].item] = -2;
2.202 + unlace(idx);
2.203 + relocate_last(idx);
2.204 + }
2.205 +
2.206 + /// \brief Deletes \c i from the heap.
2.207 + ///
2.208 + /// This method deletes item \c i from the heap, if \c i was
2.209 + /// already stored in the heap.
2.210 + /// \param i The item to erase.
2.211 + void erase(const Item &i) {
2.212 + int idx = index[i];
2.213 + index[data[idx].item] = -2;
2.214 + unlace(idx);
2.215 + relocate_last(idx);
2.216 + }
2.217 +
2.218 +
2.219 + /// \brief Returns the priority of \c i.
2.220 + ///
2.221 + /// This function returns the priority of item \c i.
2.222 + /// \pre \c i must be in the heap.
2.223 + /// \param i The item.
2.224 + Prio operator[](const Item &i) const {
2.225 + int idx = index[i];
2.226 + return data[idx].value;
2.227 + }
2.228 +
2.229 + /// \brief \c i gets to the heap with priority \c p independently
2.230 + /// if \c i was already there.
2.231 + ///
2.232 + /// This method calls \ref push(\c i, \c p) if \c i is not stored
2.233 + /// in the heap and sets the priority of \c i to \c p otherwise.
2.234 + /// \param i The item.
2.235 + /// \param p The priority.
2.236 + void set(const Item &i, const Prio &p) {
2.237 + int idx = index[i];
2.238 + if (idx < 0) {
2.239 + push(i,p);
2.240 + } else if (p > data[idx].value) {
2.241 + increase(i, p);
2.242 + } else {
2.243 + decrease(i, p);
2.244 + }
2.245 + }
2.246 +
2.247 + /// \brief Decreases the priority of \c i to \c p.
2.248 +
2.249 + /// This method decreases the priority of item \c i to \c p.
2.250 + /// \pre \c i must be stored in the heap with priority at least \c
2.251 + /// p relative to \c Compare.
2.252 + /// \param i The item.
2.253 + /// \param p The priority.
2.254 + void decrease(const Item &i, const Prio &p) {
2.255 + int idx = index[i];
2.256 + unlace(idx);
2.257 + data[idx].value = p;
2.258 + if (p < minimal) {
2.259 + minimal = p;
2.260 + }
2.261 + lace(idx);
2.262 + }
2.263 +
2.264 + /// \brief Increases the priority of \c i to \c p.
2.265 + ///
2.266 + /// This method sets the priority of item \c i to \c p.
2.267 + /// \pre \c i must be stored in the heap with priority at most \c
2.268 + /// p relative to \c Compare.
2.269 + /// \param i The item.
2.270 + /// \param p The priority.
2.271 + void increase(const Item &i, const Prio &p) {
2.272 + int idx = index[i];
2.273 + unlace(idx);
2.274 + data[idx].value = p;
2.275 + lace(idx);
2.276 + }
2.277 +
2.278 + /// \brief Returns if \c item is in, has already been in, or has
2.279 + /// never been in the heap.
2.280 + ///
2.281 + /// This method returns PRE_HEAP if \c item has never been in the
2.282 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
2.283 + /// otherwise. In the latter case it is possible that \c item will
2.284 + /// get back to the heap again.
2.285 + /// \param i The item.
2.286 + state_enum state(const Item &i) const {
2.287 + int idx = index[i];
2.288 + if (idx >= 0) idx = 0;
2.289 + return state_enum(idx);
2.290 + }
2.291 +
2.292 + private:
2.293 +
2.294 + struct LinearItem {
2.295 + LinearItem(const Item& _item, int _value)
2.296 + : item(_item), value(_value) {}
2.297 +
2.298 + Item item;
2.299 + int value;
2.300 +
2.301 + int prev, next;
2.302 + };
2.303 +
2.304 + ItemIntMap& index;
2.305 + std::vector<int> first;
2.306 + std::vector<LinearItem> data;
2.307 + mutable int minimal;
2.308 +
2.309 + }; // class LinearHeap
2.310 +
2.311 +
2.312 + template <typename _Item, typename _ItemIntMap>
2.313 + class LinearHeap<_Item, _ItemIntMap, false> {
2.314 +
2.315 + public:
2.316 + typedef _Item Item;
2.317 + typedef int Prio;
2.318 + typedef std::pair<Item, Prio> Pair;
2.319 + typedef _ItemIntMap ItemIntMap;
2.320 +
2.321 + enum state_enum {
2.322 + IN_HEAP = 0,
2.323 + PRE_HEAP = -1,
2.324 + POST_HEAP = -2
2.325 + };
2.326 +
2.327 + public:
2.328 +
2.329 + explicit LinearHeap(ItemIntMap &_index) : index(_index), maximal(-1) {}
2.330 +
2.331 + int size() const { return data.size(); }
2.332 + bool empty() const { return data.empty(); }
2.333 +
2.334 + void clear() {
2.335 + for (int i = 0; i < (int)data.size(); ++i) {
2.336 + index[data[i].item] = -2;
2.337 + }
2.338 + data.clear(); first.clear(); maximal = -1;
2.339 + }
2.340 +
2.341 + private:
2.342 +
2.343 + void relocate_last(int idx) {
2.344 + if (idx + 1 != (int)data.size()) {
2.345 + data[idx] = data.back();
2.346 + if (data[idx].prev != -1) {
2.347 + data[data[idx].prev].next = idx;
2.348 + } else {
2.349 + first[data[idx].value] = idx;
2.350 + }
2.351 + if (data[idx].next != -1) {
2.352 + data[data[idx].next].prev = idx;
2.353 + }
2.354 + index[data[idx].item] = idx;
2.355 + }
2.356 + data.pop_back();
2.357 + }
2.358 +
2.359 + void unlace(int idx) {
2.360 + if (data[idx].prev != -1) {
2.361 + data[data[idx].prev].next = data[idx].next;
2.362 + } else {
2.363 + first[data[idx].value] = data[idx].next;
2.364 + }
2.365 + if (data[idx].next != -1) {
2.366 + data[data[idx].next].prev = data[idx].prev;
2.367 + }
2.368 + }
2.369 +
2.370 + void lace(int idx) {
2.371 + if ((int)first.size() <= data[idx].value) {
2.372 + first.resize(data[idx].value + 1, -1);
2.373 + }
2.374 + data[idx].next = first[data[idx].value];
2.375 + if (data[idx].next != -1) {
2.376 + data[data[idx].next].prev = idx;
2.377 + }
2.378 + first[data[idx].value] = idx;
2.379 + data[idx].prev = -1;
2.380 + }
2.381 +
2.382 + public:
2.383 +
2.384 + void push(const Pair& p) {
2.385 + push(p.first, p.second);
2.386 + }
2.387 +
2.388 + void push(const Item &i, const Prio &p) {
2.389 + int idx = data.size();
2.390 + index[i] = idx;
2.391 + data.push_back(LinearItem(i, p));
2.392 + lace(idx);
2.393 + if (data[idx].value > maximal) {
2.394 + maximal = data[idx].value;
2.395 + }
2.396 + }
2.397 +
2.398 + Item top() const {
2.399 + while (first[maximal] == -1) {
2.400 + --maximal;
2.401 + }
2.402 + return data[first[maximal]].item;
2.403 + }
2.404 +
2.405 + Prio prio() const {
2.406 + while (first[maximal] == -1) {
2.407 + --maximal;
2.408 + }
2.409 + return maximal;
2.410 + }
2.411 +
2.412 + void pop() {
2.413 + while (first[maximal] == -1) {
2.414 + --maximal;
2.415 + }
2.416 + int idx = first[maximal];
2.417 + index[data[idx].item] = -2;
2.418 + unlace(idx);
2.419 + relocate_last(idx);
2.420 + }
2.421 +
2.422 + void erase(const Item &i) {
2.423 + int idx = index[i];
2.424 + index[data[idx].item] = -2;
2.425 + unlace(idx);
2.426 + relocate_last(idx);
2.427 + }
2.428 +
2.429 + Prio operator[](const Item &i) const {
2.430 + int idx = index[i];
2.431 + return data[idx].value;
2.432 + }
2.433 +
2.434 + void set(const Item &i, const Prio &p) {
2.435 + int idx = index[i];
2.436 + if (idx < 0) {
2.437 + push(i,p);
2.438 + } else if (p > data[idx].value) {
2.439 + decrease(i, p);
2.440 + } else {
2.441 + increase(i, p);
2.442 + }
2.443 + }
2.444 +
2.445 + void decrease(const Item &i, const Prio &p) {
2.446 + int idx = index[i];
2.447 + unlace(idx);
2.448 + data[idx].value = p;
2.449 + if (p > maximal) {
2.450 + maximal = p;
2.451 + }
2.452 + lace(idx);
2.453 + }
2.454 +
2.455 + void increase(const Item &i, const Prio &p) {
2.456 + int idx = index[i];
2.457 + unlace(idx);
2.458 + data[idx].value = p;
2.459 + lace(idx);
2.460 + }
2.461 +
2.462 + state_enum state(const Item &i) const {
2.463 + int idx = index[i];
2.464 + if (idx >= 0) idx = 0;
2.465 + return state_enum(idx);
2.466 + }
2.467 +
2.468 + private:
2.469 +
2.470 + struct LinearItem {
2.471 + LinearItem(const Item& _item, int _value)
2.472 + : item(_item), value(_value) {}
2.473 +
2.474 + Item item;
2.475 + int value;
2.476 +
2.477 + int prev, next;
2.478 + };
2.479 +
2.480 + ItemIntMap& index;
2.481 + std::vector<int> first;
2.482 + std::vector<LinearItem> data;
2.483 + mutable int maximal;
2.484 +
2.485 + }; // class LinearHeap
2.486 +
2.487 +}
2.488 +
2.489 +#endif