1.1 --- a/lemon/Makefile.am Sun Feb 21 18:55:01 2010 +0100
1.2 +++ b/lemon/Makefile.am Fri Feb 26 17:08:30 2010 +0100
1.3 @@ -59,7 +59,6 @@
1.4 lemon/assert.h \
1.5 lemon/bfs.h \
1.6 lemon/bin_heap.h \
1.7 - lemon/bucket_heap.h \
1.8 lemon/cbc.h \
1.9 lemon/circulation.h \
1.10 lemon/clp.h \
1.11 @@ -77,7 +76,6 @@
1.12 lemon/elevator.h \
1.13 lemon/error.h \
1.14 lemon/euler.h \
1.15 - lemon/fib_heap.h \
1.16 lemon/full_graph.h \
1.17 lemon/glpk.h \
1.18 lemon/gomory_hu.h \
1.19 @@ -100,7 +98,6 @@
1.20 lemon/network_simplex.h \
1.21 lemon/path.h \
1.22 lemon/preflow.h \
1.23 - lemon/radix_heap.h \
1.24 lemon/radix_sort.h \
1.25 lemon/random.h \
1.26 lemon/smart_graph.h \
2.1 --- a/lemon/bin_heap.h Sun Feb 21 18:55:01 2010 +0100
2.2 +++ b/lemon/bin_heap.h Fri Feb 26 17:08:30 2010 +0100
2.3 @@ -33,23 +33,23 @@
2.4 ///
2.5 ///\brief A Binary Heap implementation.
2.6 ///
2.7 - ///This class implements the \e binary \e heap data structure.
2.8 - ///
2.9 + ///This class implements the \e binary \e heap data structure.
2.10 + ///
2.11 ///A \e heap is a data structure for storing items with specified values
2.12 ///called \e priorities in such a way that finding the item with minimum
2.13 - ///priority is efficient. \c CMP specifies the ordering of the priorities.
2.14 + ///priority is efficient. \c Comp specifies the ordering of the priorities.
2.15 ///In a heap one can change the priority of an item, add or erase an
2.16 ///item, etc.
2.17 ///
2.18 ///\tparam PR Type of the priority of the items.
2.19 ///\tparam IM A read and writable item map with int values, used internally
2.20 ///to handle the cross references.
2.21 - ///\tparam CMP A functor class for the ordering of the priorities.
2.22 + ///\tparam Comp A functor class for the ordering of the priorities.
2.23 ///The default is \c std::less<PR>.
2.24 ///
2.25 ///\sa FibHeap
2.26 ///\sa Dijkstra
2.27 - template <typename PR, typename IM, typename CMP = std::less<PR> >
2.28 + template <typename PR, typename IM, typename Comp = std::less<PR> >
2.29 class BinHeap {
2.30
2.31 public:
2.32 @@ -62,7 +62,7 @@
2.33 ///\e
2.34 typedef std::pair<Item,Prio> Pair;
2.35 ///\e
2.36 - typedef CMP Compare;
2.37 + typedef Comp Compare;
2.38
2.39 /// \brief Type to represent the items states.
2.40 ///
3.1 --- a/lemon/bits/map_extender.h Sun Feb 21 18:55:01 2010 +0100
3.2 +++ b/lemon/bits/map_extender.h Fri Feb 26 17:08:30 2010 +0100
3.3 @@ -49,8 +49,6 @@
3.4 typedef typename Parent::Reference Reference;
3.5 typedef typename Parent::ConstReference ConstReference;
3.6
3.7 - typedef typename Parent::ReferenceMapTag ReferenceMapTag;
3.8 -
3.9 class MapIt;
3.10 class ConstMapIt;
3.11
3.12 @@ -193,8 +191,6 @@
3.13 typedef typename Parent::Reference Reference;
3.14 typedef typename Parent::ConstReference ConstReference;
3.15
3.16 - typedef typename Parent::ReferenceMapTag ReferenceMapTag;
3.17 -
3.18 class MapIt;
3.19 class ConstMapIt;
3.20
4.1 --- a/lemon/bucket_heap.h Sun Feb 21 18:55:01 2010 +0100
4.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
4.3 @@ -1,567 +0,0 @@
4.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
4.5 - *
4.6 - * This file is a part of LEMON, a generic C++ optimization library.
4.7 - *
4.8 - * Copyright (C) 2003-2009
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_BUCKET_HEAP_H
4.23 -#define LEMON_BUCKET_HEAP_H
4.24 -
4.25 -///\ingroup auxdat
4.26 -///\file
4.27 -///\brief Bucket 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 - namespace _bucket_heap_bits {
4.36 -
4.37 - template <bool MIN>
4.38 - struct DirectionTraits {
4.39 - static bool less(int left, int right) {
4.40 - return left < right;
4.41 - }
4.42 - static void increase(int& value) {
4.43 - ++value;
4.44 - }
4.45 - };
4.46 -
4.47 - template <>
4.48 - struct DirectionTraits<false> {
4.49 - static bool less(int left, int right) {
4.50 - return left > right;
4.51 - }
4.52 - static void increase(int& value) {
4.53 - --value;
4.54 - }
4.55 - };
4.56 -
4.57 - }
4.58 -
4.59 - /// \ingroup auxdat
4.60 - ///
4.61 - /// \brief A Bucket Heap implementation.
4.62 - ///
4.63 - /// This class implements the \e bucket \e heap data structure. A \e heap
4.64 - /// is a data structure for storing items with specified values called \e
4.65 - /// priorities in such a way that finding the item with minimum priority is
4.66 - /// efficient. The bucket heap is very simple implementation, it can store
4.67 - /// only integer priorities and it stores for each priority in the
4.68 - /// \f$ [0..C) \f$ range a list of items. So it should be used only when
4.69 - /// the priorities are small. It is not intended to use as dijkstra heap.
4.70 - ///
4.71 - /// \param IM A read and write Item int map, used internally
4.72 - /// to handle the cross references.
4.73 - /// \param MIN If the given parameter is false then instead of the
4.74 - /// minimum value the maximum can be retrivied with the top() and
4.75 - /// prio() member functions.
4.76 - template <typename IM, bool MIN = true>
4.77 - class BucketHeap {
4.78 -
4.79 - public:
4.80 - /// \e
4.81 - typedef typename IM::Key Item;
4.82 - /// \e
4.83 - typedef int Prio;
4.84 - /// \e
4.85 - typedef std::pair<Item, Prio> Pair;
4.86 - /// \e
4.87 - typedef IM ItemIntMap;
4.88 -
4.89 - private:
4.90 -
4.91 - typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
4.92 -
4.93 - public:
4.94 -
4.95 - /// \brief Type to represent the items states.
4.96 - ///
4.97 - /// Each Item element have a state associated to it. It may be "in heap",
4.98 - /// "pre heap" or "post heap". The latter two are indifferent from the
4.99 - /// heap's point of view, but may be useful to the user.
4.100 - ///
4.101 - /// The item-int map must be initialized in such way that it assigns
4.102 - /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
4.103 - enum State {
4.104 - IN_HEAP = 0, ///< = 0.
4.105 - PRE_HEAP = -1, ///< = -1.
4.106 - POST_HEAP = -2 ///< = -2.
4.107 - };
4.108 -
4.109 - public:
4.110 - /// \brief The constructor.
4.111 - ///
4.112 - /// The constructor.
4.113 - /// \param map should be given to the constructor, since it is used
4.114 - /// internally to handle the cross references. The value of the map
4.115 - /// should be PRE_HEAP (-1) for each element.
4.116 - explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
4.117 -
4.118 - /// The number of items stored in the heap.
4.119 - ///
4.120 - /// \brief Returns the number of items stored in the heap.
4.121 - int size() const { return _data.size(); }
4.122 -
4.123 - /// \brief Checks if the heap stores no items.
4.124 - ///
4.125 - /// Returns \c true if and only if the heap stores no items.
4.126 - bool empty() const { return _data.empty(); }
4.127 -
4.128 - /// \brief Make empty this heap.
4.129 - ///
4.130 - /// Make empty this heap. It does not change the cross reference
4.131 - /// map. If you want to reuse a heap what is not surely empty you
4.132 - /// should first clear the heap and after that you should set the
4.133 - /// cross reference map for each item to \c PRE_HEAP.
4.134 - void clear() {
4.135 - _data.clear(); _first.clear(); _minimum = 0;
4.136 - }
4.137 -
4.138 - private:
4.139 -
4.140 - void relocate_last(int idx) {
4.141 - if (idx + 1 < int(_data.size())) {
4.142 - _data[idx] = _data.back();
4.143 - if (_data[idx].prev != -1) {
4.144 - _data[_data[idx].prev].next = idx;
4.145 - } else {
4.146 - _first[_data[idx].value] = idx;
4.147 - }
4.148 - if (_data[idx].next != -1) {
4.149 - _data[_data[idx].next].prev = idx;
4.150 - }
4.151 - _iim[_data[idx].item] = idx;
4.152 - }
4.153 - _data.pop_back();
4.154 - }
4.155 -
4.156 - void unlace(int idx) {
4.157 - if (_data[idx].prev != -1) {
4.158 - _data[_data[idx].prev].next = _data[idx].next;
4.159 - } else {
4.160 - _first[_data[idx].value] = _data[idx].next;
4.161 - }
4.162 - if (_data[idx].next != -1) {
4.163 - _data[_data[idx].next].prev = _data[idx].prev;
4.164 - }
4.165 - }
4.166 -
4.167 - void lace(int idx) {
4.168 - if (int(_first.size()) <= _data[idx].value) {
4.169 - _first.resize(_data[idx].value + 1, -1);
4.170 - }
4.171 - _data[idx].next = _first[_data[idx].value];
4.172 - if (_data[idx].next != -1) {
4.173 - _data[_data[idx].next].prev = idx;
4.174 - }
4.175 - _first[_data[idx].value] = idx;
4.176 - _data[idx].prev = -1;
4.177 - }
4.178 -
4.179 - public:
4.180 - /// \brief Insert a pair of item and priority into the heap.
4.181 - ///
4.182 - /// Adds \c p.first to the heap with priority \c p.second.
4.183 - /// \param p The pair to insert.
4.184 - void push(const Pair& p) {
4.185 - push(p.first, p.second);
4.186 - }
4.187 -
4.188 - /// \brief Insert an item into the heap with the given priority.
4.189 - ///
4.190 - /// Adds \c i to the heap with priority \c p.
4.191 - /// \param i The item to insert.
4.192 - /// \param p The priority of the item.
4.193 - void push(const Item &i, const Prio &p) {
4.194 - int idx = _data.size();
4.195 - _iim[i] = idx;
4.196 - _data.push_back(BucketItem(i, p));
4.197 - lace(idx);
4.198 - if (Direction::less(p, _minimum)) {
4.199 - _minimum = p;
4.200 - }
4.201 - }
4.202 -
4.203 - /// \brief Returns the item with minimum priority.
4.204 - ///
4.205 - /// This method returns the item with minimum priority.
4.206 - /// \pre The heap must be nonempty.
4.207 - Item top() const {
4.208 - while (_first[_minimum] == -1) {
4.209 - Direction::increase(_minimum);
4.210 - }
4.211 - return _data[_first[_minimum]].item;
4.212 - }
4.213 -
4.214 - /// \brief Returns the minimum priority.
4.215 - ///
4.216 - /// It returns the minimum priority.
4.217 - /// \pre The heap must be nonempty.
4.218 - Prio prio() const {
4.219 - while (_first[_minimum] == -1) {
4.220 - Direction::increase(_minimum);
4.221 - }
4.222 - return _minimum;
4.223 - }
4.224 -
4.225 - /// \brief Deletes the item with minimum priority.
4.226 - ///
4.227 - /// This method deletes the item with minimum priority from the heap.
4.228 - /// \pre The heap must be non-empty.
4.229 - void pop() {
4.230 - while (_first[_minimum] == -1) {
4.231 - Direction::increase(_minimum);
4.232 - }
4.233 - int idx = _first[_minimum];
4.234 - _iim[_data[idx].item] = -2;
4.235 - unlace(idx);
4.236 - relocate_last(idx);
4.237 - }
4.238 -
4.239 - /// \brief Deletes \c i from the heap.
4.240 - ///
4.241 - /// This method deletes item \c i from the heap, if \c i was
4.242 - /// already stored in the heap.
4.243 - /// \param i The item to erase.
4.244 - void erase(const Item &i) {
4.245 - int idx = _iim[i];
4.246 - _iim[_data[idx].item] = -2;
4.247 - unlace(idx);
4.248 - relocate_last(idx);
4.249 - }
4.250 -
4.251 -
4.252 - /// \brief Returns the priority of \c i.
4.253 - ///
4.254 - /// This function returns the priority of item \c i.
4.255 - /// \pre \c i must be in the heap.
4.256 - /// \param i The item.
4.257 - Prio operator[](const Item &i) const {
4.258 - int idx = _iim[i];
4.259 - return _data[idx].value;
4.260 - }
4.261 -
4.262 - /// \brief \c i gets to the heap with priority \c p independently
4.263 - /// if \c i was already there.
4.264 - ///
4.265 - /// This method calls \ref push(\c i, \c p) if \c i is not stored
4.266 - /// in the heap and sets the priority of \c i to \c p otherwise.
4.267 - /// \param i The item.
4.268 - /// \param p The priority.
4.269 - void set(const Item &i, const Prio &p) {
4.270 - int idx = _iim[i];
4.271 - if (idx < 0) {
4.272 - push(i, p);
4.273 - } else if (Direction::less(p, _data[idx].value)) {
4.274 - decrease(i, p);
4.275 - } else {
4.276 - increase(i, p);
4.277 - }
4.278 - }
4.279 -
4.280 - /// \brief Decreases the priority of \c i to \c p.
4.281 - ///
4.282 - /// This method decreases the priority of item \c i to \c p.
4.283 - /// \pre \c i must be stored in the heap with priority at least \c
4.284 - /// p relative to \c Compare.
4.285 - /// \param i The item.
4.286 - /// \param p The priority.
4.287 - void decrease(const Item &i, const Prio &p) {
4.288 - int idx = _iim[i];
4.289 - unlace(idx);
4.290 - _data[idx].value = p;
4.291 - if (Direction::less(p, _minimum)) {
4.292 - _minimum = p;
4.293 - }
4.294 - lace(idx);
4.295 - }
4.296 -
4.297 - /// \brief Increases the priority of \c i to \c p.
4.298 - ///
4.299 - /// This method sets the priority of item \c i to \c p.
4.300 - /// \pre \c i must be stored in the heap with priority at most \c
4.301 - /// p relative to \c Compare.
4.302 - /// \param i The item.
4.303 - /// \param p The priority.
4.304 - void increase(const Item &i, const Prio &p) {
4.305 - int idx = _iim[i];
4.306 - unlace(idx);
4.307 - _data[idx].value = p;
4.308 - lace(idx);
4.309 - }
4.310 -
4.311 - /// \brief Returns if \c item is in, has already been in, or has
4.312 - /// never been in the heap.
4.313 - ///
4.314 - /// This method returns PRE_HEAP if \c item has never been in the
4.315 - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
4.316 - /// otherwise. In the latter case it is possible that \c item will
4.317 - /// get back to the heap again.
4.318 - /// \param i The item.
4.319 - State state(const Item &i) const {
4.320 - int idx = _iim[i];
4.321 - if (idx >= 0) idx = 0;
4.322 - return State(idx);
4.323 - }
4.324 -
4.325 - /// \brief Sets the state of the \c item in the heap.
4.326 - ///
4.327 - /// Sets the state of the \c item in the heap. It can be used to
4.328 - /// manually clear the heap when it is important to achive the
4.329 - /// better time complexity.
4.330 - /// \param i The item.
4.331 - /// \param st The state. It should not be \c IN_HEAP.
4.332 - void state(const Item& i, State st) {
4.333 - switch (st) {
4.334 - case POST_HEAP:
4.335 - case PRE_HEAP:
4.336 - if (state(i) == IN_HEAP) {
4.337 - erase(i);
4.338 - }
4.339 - _iim[i] = st;
4.340 - break;
4.341 - case IN_HEAP:
4.342 - break;
4.343 - }
4.344 - }
4.345 -
4.346 - private:
4.347 -
4.348 - struct BucketItem {
4.349 - BucketItem(const Item& _item, int _value)
4.350 - : item(_item), value(_value) {}
4.351 -
4.352 - Item item;
4.353 - int value;
4.354 -
4.355 - int prev, next;
4.356 - };
4.357 -
4.358 - ItemIntMap& _iim;
4.359 - std::vector<int> _first;
4.360 - std::vector<BucketItem> _data;
4.361 - mutable int _minimum;
4.362 -
4.363 - }; // class BucketHeap
4.364 -
4.365 - /// \ingroup auxdat
4.366 - ///
4.367 - /// \brief A Simplified Bucket Heap implementation.
4.368 - ///
4.369 - /// This class implements a simplified \e bucket \e heap data
4.370 - /// structure. It does not provide some functionality but it faster
4.371 - /// and simplier data structure than the BucketHeap. The main
4.372 - /// difference is that the BucketHeap stores for every key a double
4.373 - /// linked list while this class stores just simple lists. In the
4.374 - /// other way it does not support erasing each elements just the
4.375 - /// minimal and it does not supports key increasing, decreasing.
4.376 - ///
4.377 - /// \param IM A read and write Item int map, used internally
4.378 - /// to handle the cross references.
4.379 - /// \param MIN If the given parameter is false then instead of the
4.380 - /// minimum value the maximum can be retrivied with the top() and
4.381 - /// prio() member functions.
4.382 - ///
4.383 - /// \sa BucketHeap
4.384 - template <typename IM, bool MIN = true >
4.385 - class SimpleBucketHeap {
4.386 -
4.387 - public:
4.388 - typedef typename IM::Key Item;
4.389 - typedef int Prio;
4.390 - typedef std::pair<Item, Prio> Pair;
4.391 - typedef IM ItemIntMap;
4.392 -
4.393 - private:
4.394 -
4.395 - typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
4.396 -
4.397 - public:
4.398 -
4.399 - /// \brief Type to represent the items states.
4.400 - ///
4.401 - /// Each Item element have a state associated to it. It may be "in heap",
4.402 - /// "pre heap" or "post heap". The latter two are indifferent from the
4.403 - /// heap's point of view, but may be useful to the user.
4.404 - ///
4.405 - /// The item-int map must be initialized in such way that it assigns
4.406 - /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
4.407 - enum State {
4.408 - IN_HEAP = 0, ///< = 0.
4.409 - PRE_HEAP = -1, ///< = -1.
4.410 - POST_HEAP = -2 ///< = -2.
4.411 - };
4.412 -
4.413 - public:
4.414 -
4.415 - /// \brief The constructor.
4.416 - ///
4.417 - /// The constructor.
4.418 - /// \param map should be given to the constructor, since it is used
4.419 - /// internally to handle the cross references. The value of the map
4.420 - /// should be PRE_HEAP (-1) for each element.
4.421 - explicit SimpleBucketHeap(ItemIntMap &map)
4.422 - : _iim(map), _free(-1), _num(0), _minimum(0) {}
4.423 -
4.424 - /// \brief Returns the number of items stored in the heap.
4.425 - ///
4.426 - /// The number of items stored in the heap.
4.427 - int size() const { return _num; }
4.428 -
4.429 - /// \brief Checks if the heap stores no items.
4.430 - ///
4.431 - /// Returns \c true if and only if the heap stores no items.
4.432 - bool empty() const { return _num == 0; }
4.433 -
4.434 - /// \brief Make empty this heap.
4.435 - ///
4.436 - /// Make empty this heap. It does not change the cross reference
4.437 - /// map. If you want to reuse a heap what is not surely empty you
4.438 - /// should first clear the heap and after that you should set the
4.439 - /// cross reference map for each item to \c PRE_HEAP.
4.440 - void clear() {
4.441 - _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
4.442 - }
4.443 -
4.444 - /// \brief Insert a pair of item and priority into the heap.
4.445 - ///
4.446 - /// Adds \c p.first to the heap with priority \c p.second.
4.447 - /// \param p The pair to insert.
4.448 - void push(const Pair& p) {
4.449 - push(p.first, p.second);
4.450 - }
4.451 -
4.452 - /// \brief Insert an item into the heap with the given priority.
4.453 - ///
4.454 - /// Adds \c i to the heap with priority \c p.
4.455 - /// \param i The item to insert.
4.456 - /// \param p The priority of the item.
4.457 - void push(const Item &i, const Prio &p) {
4.458 - int idx;
4.459 - if (_free == -1) {
4.460 - idx = _data.size();
4.461 - _data.push_back(BucketItem(i));
4.462 - } else {
4.463 - idx = _free;
4.464 - _free = _data[idx].next;
4.465 - _data[idx].item = i;
4.466 - }
4.467 - _iim[i] = idx;
4.468 - if (p >= int(_first.size())) _first.resize(p + 1, -1);
4.469 - _data[idx].next = _first[p];
4.470 - _first[p] = idx;
4.471 - if (Direction::less(p, _minimum)) {
4.472 - _minimum = p;
4.473 - }
4.474 - ++_num;
4.475 - }
4.476 -
4.477 - /// \brief Returns the item with minimum priority.
4.478 - ///
4.479 - /// This method returns the item with minimum priority.
4.480 - /// \pre The heap must be nonempty.
4.481 - Item top() const {
4.482 - while (_first[_minimum] == -1) {
4.483 - Direction::increase(_minimum);
4.484 - }
4.485 - return _data[_first[_minimum]].item;
4.486 - }
4.487 -
4.488 - /// \brief Returns the minimum priority.
4.489 - ///
4.490 - /// It returns the minimum priority.
4.491 - /// \pre The heap must be nonempty.
4.492 - Prio prio() const {
4.493 - while (_first[_minimum] == -1) {
4.494 - Direction::increase(_minimum);
4.495 - }
4.496 - return _minimum;
4.497 - }
4.498 -
4.499 - /// \brief Deletes the item with minimum priority.
4.500 - ///
4.501 - /// This method deletes the item with minimum priority from the heap.
4.502 - /// \pre The heap must be non-empty.
4.503 - void pop() {
4.504 - while (_first[_minimum] == -1) {
4.505 - Direction::increase(_minimum);
4.506 - }
4.507 - int idx = _first[_minimum];
4.508 - _iim[_data[idx].item] = -2;
4.509 - _first[_minimum] = _data[idx].next;
4.510 - _data[idx].next = _free;
4.511 - _free = idx;
4.512 - --_num;
4.513 - }
4.514 -
4.515 - /// \brief Returns the priority of \c i.
4.516 - ///
4.517 - /// This function returns the priority of item \c i.
4.518 - /// \warning This operator is not a constant time function
4.519 - /// because it scans the whole data structure to find the proper
4.520 - /// value.
4.521 - /// \pre \c i must be in the heap.
4.522 - /// \param i The item.
4.523 - Prio operator[](const Item &i) const {
4.524 - for (int k = 0; k < _first.size(); ++k) {
4.525 - int idx = _first[k];
4.526 - while (idx != -1) {
4.527 - if (_data[idx].item == i) {
4.528 - return k;
4.529 - }
4.530 - idx = _data[idx].next;
4.531 - }
4.532 - }
4.533 - return -1;
4.534 - }
4.535 -
4.536 - /// \brief Returns if \c item is in, has already been in, or has
4.537 - /// never been in the heap.
4.538 - ///
4.539 - /// This method returns PRE_HEAP if \c item has never been in the
4.540 - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
4.541 - /// otherwise. In the latter case it is possible that \c item will
4.542 - /// get back to the heap again.
4.543 - /// \param i The item.
4.544 - State state(const Item &i) const {
4.545 - int idx = _iim[i];
4.546 - if (idx >= 0) idx = 0;
4.547 - return State(idx);
4.548 - }
4.549 -
4.550 - private:
4.551 -
4.552 - struct BucketItem {
4.553 - BucketItem(const Item& _item)
4.554 - : item(_item) {}
4.555 -
4.556 - Item item;
4.557 - int next;
4.558 - };
4.559 -
4.560 - ItemIntMap& _iim;
4.561 - std::vector<int> _first;
4.562 - std::vector<BucketItem> _data;
4.563 - int _free, _num;
4.564 - mutable int _minimum;
4.565 -
4.566 - }; // class SimpleBucketHeap
4.567 -
4.568 -}
4.569 -
4.570 -#endif
5.1 --- a/lemon/concepts/maps.h Sun Feb 21 18:55:01 2010 +0100
5.2 +++ b/lemon/concepts/maps.h Fri Feb 26 17:08:30 2010 +0100
5.3 @@ -182,8 +182,7 @@
5.4
5.5 template<typename _ReferenceMap>
5.6 struct Constraints {
5.7 - typename enable_if<typename _ReferenceMap::ReferenceMapTag, void>::type
5.8 - constraints() {
5.9 + void constraints() {
5.10 checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
5.11 ref = m[key];
5.12 m[key] = val;
6.1 --- a/lemon/fib_heap.h Sun Feb 21 18:55:01 2010 +0100
6.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
6.3 @@ -1,468 +0,0 @@
6.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
6.5 - *
6.6 - * This file is a part of LEMON, a generic C++ optimization library.
6.7 - *
6.8 - * Copyright (C) 2003-2009
6.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
6.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
6.11 - *
6.12 - * Permission to use, modify and distribute this software is granted
6.13 - * provided that this copyright notice appears in all copies. For
6.14 - * precise terms see the accompanying LICENSE file.
6.15 - *
6.16 - * This software is provided "AS IS" with no warranty of any kind,
6.17 - * express or implied, and with no claim as to its suitability for any
6.18 - * purpose.
6.19 - *
6.20 - */
6.21 -
6.22 -#ifndef LEMON_FIB_HEAP_H
6.23 -#define LEMON_FIB_HEAP_H
6.24 -
6.25 -///\file
6.26 -///\ingroup auxdat
6.27 -///\brief Fibonacci Heap implementation.
6.28 -
6.29 -#include <vector>
6.30 -#include <functional>
6.31 -#include <lemon/math.h>
6.32 -
6.33 -namespace lemon {
6.34 -
6.35 - /// \ingroup auxdat
6.36 - ///
6.37 - ///\brief Fibonacci Heap.
6.38 - ///
6.39 - ///This class implements the \e Fibonacci \e heap data structure. A \e heap
6.40 - ///is a data structure for storing items with specified values called \e
6.41 - ///priorities in such a way that finding the item with minimum priority is
6.42 - ///efficient. \c CMP specifies the ordering of the priorities. In a heap
6.43 - ///one can change the priority of an item, add or erase an item, etc.
6.44 - ///
6.45 - ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
6.46 - ///heap. In case of many calls to these operations, it is better to use a
6.47 - ///\ref BinHeap "binary heap".
6.48 - ///
6.49 - ///\param PRIO Type of the priority of the items.
6.50 - ///\param IM A read and writable Item int map, used internally
6.51 - ///to handle the cross references.
6.52 - ///\param CMP A class for the ordering of the priorities. The
6.53 - ///default is \c std::less<PRIO>.
6.54 - ///
6.55 - ///\sa BinHeap
6.56 - ///\sa Dijkstra
6.57 -#ifdef DOXYGEN
6.58 - template <typename PRIO, typename IM, typename CMP>
6.59 -#else
6.60 - template <typename PRIO, typename IM, typename CMP = std::less<PRIO> >
6.61 -#endif
6.62 - class FibHeap {
6.63 - public:
6.64 - ///\e
6.65 - typedef IM ItemIntMap;
6.66 - ///\e
6.67 - typedef PRIO Prio;
6.68 - ///\e
6.69 - typedef typename ItemIntMap::Key Item;
6.70 - ///\e
6.71 - typedef std::pair<Item,Prio> Pair;
6.72 - ///\e
6.73 - typedef CMP Compare;
6.74 -
6.75 - private:
6.76 - class Store;
6.77 -
6.78 - std::vector<Store> _data;
6.79 - int _minimum;
6.80 - ItemIntMap &_iim;
6.81 - Compare _comp;
6.82 - int _num;
6.83 -
6.84 - public:
6.85 -
6.86 - /// \brief Type to represent the items states.
6.87 - ///
6.88 - /// Each Item element have a state associated to it. It may be "in heap",
6.89 - /// "pre heap" or "post heap". The latter two are indifferent from the
6.90 - /// heap's point of view, but may be useful to the user.
6.91 - ///
6.92 - /// The item-int map must be initialized in such way that it assigns
6.93 - /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
6.94 - enum State {
6.95 - IN_HEAP = 0, ///< = 0.
6.96 - PRE_HEAP = -1, ///< = -1.
6.97 - POST_HEAP = -2 ///< = -2.
6.98 - };
6.99 -
6.100 - /// \brief The constructor
6.101 - ///
6.102 - /// \c map should be given to the constructor, since it is
6.103 - /// used internally to handle the cross references.
6.104 - explicit FibHeap(ItemIntMap &map)
6.105 - : _minimum(0), _iim(map), _num() {}
6.106 -
6.107 - /// \brief The constructor
6.108 - ///
6.109 - /// \c map should be given to the constructor, since it is used
6.110 - /// internally to handle the cross references. \c comp is an
6.111 - /// object for ordering of the priorities.
6.112 - FibHeap(ItemIntMap &map, const Compare &comp)
6.113 - : _minimum(0), _iim(map), _comp(comp), _num() {}
6.114 -
6.115 - /// \brief The number of items stored in the heap.
6.116 - ///
6.117 - /// Returns the number of items stored in the heap.
6.118 - int size() const { return _num; }
6.119 -
6.120 - /// \brief Checks if the heap stores no items.
6.121 - ///
6.122 - /// Returns \c true if and only if the heap stores no items.
6.123 - bool empty() const { return _num==0; }
6.124 -
6.125 - /// \brief Make empty this heap.
6.126 - ///
6.127 - /// Make empty this heap. It does not change the cross reference
6.128 - /// map. If you want to reuse a heap what is not surely empty you
6.129 - /// should first clear the heap and after that you should set the
6.130 - /// cross reference map for each item to \c PRE_HEAP.
6.131 - void clear() {
6.132 - _data.clear(); _minimum = 0; _num = 0;
6.133 - }
6.134 -
6.135 - /// \brief \c item gets to the heap with priority \c value independently
6.136 - /// if \c item was already there.
6.137 - ///
6.138 - /// This method calls \ref push(\c item, \c value) if \c item is not
6.139 - /// stored in the heap and it calls \ref decrease(\c item, \c value) or
6.140 - /// \ref increase(\c item, \c value) otherwise.
6.141 - void set (const Item& item, const Prio& value) {
6.142 - int i=_iim[item];
6.143 - if ( i >= 0 && _data[i].in ) {
6.144 - if ( _comp(value, _data[i].prio) ) decrease(item, value);
6.145 - if ( _comp(_data[i].prio, value) ) increase(item, value);
6.146 - } else push(item, value);
6.147 - }
6.148 -
6.149 - /// \brief Adds \c item to the heap with priority \c value.
6.150 - ///
6.151 - /// Adds \c item to the heap with priority \c value.
6.152 - /// \pre \c item must not be stored in the heap.
6.153 - void push (const Item& item, const Prio& value) {
6.154 - int i=_iim[item];
6.155 - if ( i < 0 ) {
6.156 - int s=_data.size();
6.157 - _iim.set( item, s );
6.158 - Store st;
6.159 - st.name=item;
6.160 - _data.push_back(st);
6.161 - i=s;
6.162 - } else {
6.163 - _data[i].parent=_data[i].child=-1;
6.164 - _data[i].degree=0;
6.165 - _data[i].in=true;
6.166 - _data[i].marked=false;
6.167 - }
6.168 -
6.169 - if ( _num ) {
6.170 - _data[_data[_minimum].right_neighbor].left_neighbor=i;
6.171 - _data[i].right_neighbor=_data[_minimum].right_neighbor;
6.172 - _data[_minimum].right_neighbor=i;
6.173 - _data[i].left_neighbor=_minimum;
6.174 - if ( _comp( value, _data[_minimum].prio) ) _minimum=i;
6.175 - } else {
6.176 - _data[i].right_neighbor=_data[i].left_neighbor=i;
6.177 - _minimum=i;
6.178 - }
6.179 - _data[i].prio=value;
6.180 - ++_num;
6.181 - }
6.182 -
6.183 - /// \brief Returns the item with minimum priority relative to \c Compare.
6.184 - ///
6.185 - /// This method returns the item with minimum priority relative to \c
6.186 - /// Compare.
6.187 - /// \pre The heap must be nonempty.
6.188 - Item top() const { return _data[_minimum].name; }
6.189 -
6.190 - /// \brief Returns the minimum priority relative to \c Compare.
6.191 - ///
6.192 - /// It returns the minimum priority relative to \c Compare.
6.193 - /// \pre The heap must be nonempty.
6.194 - const Prio& prio() const { return _data[_minimum].prio; }
6.195 -
6.196 - /// \brief Returns the priority of \c item.
6.197 - ///
6.198 - /// It returns the priority of \c item.
6.199 - /// \pre \c item must be in the heap.
6.200 - const Prio& operator[](const Item& item) const {
6.201 - return _data[_iim[item]].prio;
6.202 - }
6.203 -
6.204 - /// \brief Deletes the item with minimum priority relative to \c Compare.
6.205 - ///
6.206 - /// This method deletes the item with minimum priority relative to \c
6.207 - /// Compare from the heap.
6.208 - /// \pre The heap must be non-empty.
6.209 - void pop() {
6.210 - /*The first case is that there are only one root.*/
6.211 - if ( _data[_minimum].left_neighbor==_minimum ) {
6.212 - _data[_minimum].in=false;
6.213 - if ( _data[_minimum].degree!=0 ) {
6.214 - makeroot(_data[_minimum].child);
6.215 - _minimum=_data[_minimum].child;
6.216 - balance();
6.217 - }
6.218 - } else {
6.219 - int right=_data[_minimum].right_neighbor;
6.220 - unlace(_minimum);
6.221 - _data[_minimum].in=false;
6.222 - if ( _data[_minimum].degree > 0 ) {
6.223 - int left=_data[_minimum].left_neighbor;
6.224 - int child=_data[_minimum].child;
6.225 - int last_child=_data[child].left_neighbor;
6.226 -
6.227 - makeroot(child);
6.228 -
6.229 - _data[left].right_neighbor=child;
6.230 - _data[child].left_neighbor=left;
6.231 - _data[right].left_neighbor=last_child;
6.232 - _data[last_child].right_neighbor=right;
6.233 - }
6.234 - _minimum=right;
6.235 - balance();
6.236 - } // the case where there are more roots
6.237 - --_num;
6.238 - }
6.239 -
6.240 - /// \brief Deletes \c item from the heap.
6.241 - ///
6.242 - /// This method deletes \c item from the heap, if \c item was already
6.243 - /// stored in the heap. It is quite inefficient in Fibonacci heaps.
6.244 - void erase (const Item& item) {
6.245 - int i=_iim[item];
6.246 -
6.247 - if ( i >= 0 && _data[i].in ) {
6.248 - if ( _data[i].parent!=-1 ) {
6.249 - int p=_data[i].parent;
6.250 - cut(i,p);
6.251 - cascade(p);
6.252 - }
6.253 - _minimum=i; //As if its prio would be -infinity
6.254 - pop();
6.255 - }
6.256 - }
6.257 -
6.258 - /// \brief Decreases the priority of \c item to \c value.
6.259 - ///
6.260 - /// This method decreases the priority of \c item to \c value.
6.261 - /// \pre \c item must be stored in the heap with priority at least \c
6.262 - /// value relative to \c Compare.
6.263 - void decrease (Item item, const Prio& value) {
6.264 - int i=_iim[item];
6.265 - _data[i].prio=value;
6.266 - int p=_data[i].parent;
6.267 -
6.268 - if ( p!=-1 && _comp(value, _data[p].prio) ) {
6.269 - cut(i,p);
6.270 - cascade(p);
6.271 - }
6.272 - if ( _comp(value, _data[_minimum].prio) ) _minimum=i;
6.273 - }
6.274 -
6.275 - /// \brief Increases the priority of \c item to \c value.
6.276 - ///
6.277 - /// This method sets the priority of \c item to \c value. Though
6.278 - /// there is no precondition on the priority of \c item, this
6.279 - /// method should be used only if it is indeed necessary to increase
6.280 - /// (relative to \c Compare) the priority of \c item, because this
6.281 - /// method is inefficient.
6.282 - void increase (Item item, const Prio& value) {
6.283 - erase(item);
6.284 - push(item, value);
6.285 - }
6.286 -
6.287 -
6.288 - /// \brief Returns if \c item is in, has already been in, or has never
6.289 - /// been in the heap.
6.290 - ///
6.291 - /// This method returns PRE_HEAP if \c item has never been in the
6.292 - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
6.293 - /// otherwise. In the latter case it is possible that \c item will
6.294 - /// get back to the heap again.
6.295 - State state(const Item &item) const {
6.296 - int i=_iim[item];
6.297 - if( i>=0 ) {
6.298 - if ( _data[i].in ) i=0;
6.299 - else i=-2;
6.300 - }
6.301 - return State(i);
6.302 - }
6.303 -
6.304 - /// \brief Sets the state of the \c item in the heap.
6.305 - ///
6.306 - /// Sets the state of the \c item in the heap. It can be used to
6.307 - /// manually clear the heap when it is important to achive the
6.308 - /// better time _complexity.
6.309 - /// \param i The item.
6.310 - /// \param st The state. It should not be \c IN_HEAP.
6.311 - void state(const Item& i, State st) {
6.312 - switch (st) {
6.313 - case POST_HEAP:
6.314 - case PRE_HEAP:
6.315 - if (state(i) == IN_HEAP) {
6.316 - erase(i);
6.317 - }
6.318 - _iim[i] = st;
6.319 - break;
6.320 - case IN_HEAP:
6.321 - break;
6.322 - }
6.323 - }
6.324 -
6.325 - private:
6.326 -
6.327 - void balance() {
6.328 -
6.329 - int maxdeg=int( std::floor( 2.08*log(double(_data.size()))))+1;
6.330 -
6.331 - std::vector<int> A(maxdeg,-1);
6.332 -
6.333 - /*
6.334 - *Recall that now minimum does not point to the minimum prio element.
6.335 - *We set minimum to this during balance().
6.336 - */
6.337 - int anchor=_data[_minimum].left_neighbor;
6.338 - int next=_minimum;
6.339 - bool end=false;
6.340 -
6.341 - do {
6.342 - int active=next;
6.343 - if ( anchor==active ) end=true;
6.344 - int d=_data[active].degree;
6.345 - next=_data[active].right_neighbor;
6.346 -
6.347 - while (A[d]!=-1) {
6.348 - if( _comp(_data[active].prio, _data[A[d]].prio) ) {
6.349 - fuse(active,A[d]);
6.350 - } else {
6.351 - fuse(A[d],active);
6.352 - active=A[d];
6.353 - }
6.354 - A[d]=-1;
6.355 - ++d;
6.356 - }
6.357 - A[d]=active;
6.358 - } while ( !end );
6.359 -
6.360 -
6.361 - while ( _data[_minimum].parent >=0 )
6.362 - _minimum=_data[_minimum].parent;
6.363 - int s=_minimum;
6.364 - int m=_minimum;
6.365 - do {
6.366 - if ( _comp(_data[s].prio, _data[_minimum].prio) ) _minimum=s;
6.367 - s=_data[s].right_neighbor;
6.368 - } while ( s != m );
6.369 - }
6.370 -
6.371 - void makeroot(int c) {
6.372 - int s=c;
6.373 - do {
6.374 - _data[s].parent=-1;
6.375 - s=_data[s].right_neighbor;
6.376 - } while ( s != c );
6.377 - }
6.378 -
6.379 - void cut(int a, int b) {
6.380 - /*
6.381 - *Replacing a from the children of b.
6.382 - */
6.383 - --_data[b].degree;
6.384 -
6.385 - if ( _data[b].degree !=0 ) {
6.386 - int child=_data[b].child;
6.387 - if ( child==a )
6.388 - _data[b].child=_data[child].right_neighbor;
6.389 - unlace(a);
6.390 - }
6.391 -
6.392 -
6.393 - /*Lacing a to the roots.*/
6.394 - int right=_data[_minimum].right_neighbor;
6.395 - _data[_minimum].right_neighbor=a;
6.396 - _data[a].left_neighbor=_minimum;
6.397 - _data[a].right_neighbor=right;
6.398 - _data[right].left_neighbor=a;
6.399 -
6.400 - _data[a].parent=-1;
6.401 - _data[a].marked=false;
6.402 - }
6.403 -
6.404 - void cascade(int a) {
6.405 - if ( _data[a].parent!=-1 ) {
6.406 - int p=_data[a].parent;
6.407 -
6.408 - if ( _data[a].marked==false ) _data[a].marked=true;
6.409 - else {
6.410 - cut(a,p);
6.411 - cascade(p);
6.412 - }
6.413 - }
6.414 - }
6.415 -
6.416 - void fuse(int a, int b) {
6.417 - unlace(b);
6.418 -
6.419 - /*Lacing b under a.*/
6.420 - _data[b].parent=a;
6.421 -
6.422 - if (_data[a].degree==0) {
6.423 - _data[b].left_neighbor=b;
6.424 - _data[b].right_neighbor=b;
6.425 - _data[a].child=b;
6.426 - } else {
6.427 - int child=_data[a].child;
6.428 - int last_child=_data[child].left_neighbor;
6.429 - _data[child].left_neighbor=b;
6.430 - _data[b].right_neighbor=child;
6.431 - _data[last_child].right_neighbor=b;
6.432 - _data[b].left_neighbor=last_child;
6.433 - }
6.434 -
6.435 - ++_data[a].degree;
6.436 -
6.437 - _data[b].marked=false;
6.438 - }
6.439 -
6.440 - /*
6.441 - *It is invoked only if a has siblings.
6.442 - */
6.443 - void unlace(int a) {
6.444 - int leftn=_data[a].left_neighbor;
6.445 - int rightn=_data[a].right_neighbor;
6.446 - _data[leftn].right_neighbor=rightn;
6.447 - _data[rightn].left_neighbor=leftn;
6.448 - }
6.449 -
6.450 -
6.451 - class Store {
6.452 - friend class FibHeap;
6.453 -
6.454 - Item name;
6.455 - int parent;
6.456 - int left_neighbor;
6.457 - int right_neighbor;
6.458 - int child;
6.459 - int degree;
6.460 - bool marked;
6.461 - bool in;
6.462 - Prio prio;
6.463 -
6.464 - Store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
6.465 - };
6.466 - };
6.467 -
6.468 -} //namespace lemon
6.469 -
6.470 -#endif //LEMON_FIB_HEAP_H
6.471 -
7.1 --- a/lemon/radix_heap.h Sun Feb 21 18:55:01 2010 +0100
7.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
7.3 @@ -1,433 +0,0 @@
7.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
7.5 - *
7.6 - * This file is a part of LEMON, a generic C++ optimization library.
7.7 - *
7.8 - * Copyright (C) 2003-2009
7.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
7.11 - *
7.12 - * Permission to use, modify and distribute this software is granted
7.13 - * provided that this copyright notice appears in all copies. For
7.14 - * precise terms see the accompanying LICENSE file.
7.15 - *
7.16 - * This software is provided "AS IS" with no warranty of any kind,
7.17 - * express or implied, and with no claim as to its suitability for any
7.18 - * purpose.
7.19 - *
7.20 - */
7.21 -
7.22 -#ifndef LEMON_RADIX_HEAP_H
7.23 -#define LEMON_RADIX_HEAP_H
7.24 -
7.25 -///\ingroup auxdat
7.26 -///\file
7.27 -///\brief Radix Heap implementation.
7.28 -
7.29 -#include <vector>
7.30 -#include <lemon/error.h>
7.31 -
7.32 -namespace lemon {
7.33 -
7.34 -
7.35 - /// \ingroup auxdata
7.36 - ///
7.37 - /// \brief A Radix Heap implementation.
7.38 - ///
7.39 - /// This class implements the \e radix \e heap data structure. A \e heap
7.40 - /// is a data structure for storing items with specified values called \e
7.41 - /// priorities in such a way that finding the item with minimum priority is
7.42 - /// efficient. This heap type can store only items with \e int priority.
7.43 - /// In a heap one can change the priority of an item, add or erase an
7.44 - /// item, but the priority cannot be decreased under the last removed
7.45 - /// item's priority.
7.46 - ///
7.47 - /// \param IM A read and writable Item int map, used internally
7.48 - /// to handle the cross references.
7.49 - ///
7.50 - /// \see BinHeap
7.51 - /// \see Dijkstra
7.52 - template <typename IM>
7.53 - class RadixHeap {
7.54 -
7.55 - public:
7.56 - typedef typename IM::Key Item;
7.57 - typedef int Prio;
7.58 - typedef IM ItemIntMap;
7.59 -
7.60 - /// \brief Exception thrown by RadixHeap.
7.61 - ///
7.62 - /// This Exception is thrown when a smaller priority
7.63 - /// is inserted into the \e RadixHeap then the last time erased.
7.64 - /// \see RadixHeap
7.65 -
7.66 - class UnderFlowPriorityError : public Exception {
7.67 - public:
7.68 - virtual const char* what() const throw() {
7.69 - return "lemon::RadixHeap::UnderFlowPriorityError";
7.70 - }
7.71 - };
7.72 -
7.73 - /// \brief Type to represent the items states.
7.74 - ///
7.75 - /// Each Item element have a state associated to it. It may be "in heap",
7.76 - /// "pre heap" or "post heap". The latter two are indifferent from the
7.77 - /// heap's point of view, but may be useful to the user.
7.78 - ///
7.79 - /// The ItemIntMap \e should be initialized in such way that it maps
7.80 - /// PRE_HEAP (-1) to any element to be put in the heap...
7.81 - enum State {
7.82 - IN_HEAP = 0,
7.83 - PRE_HEAP = -1,
7.84 - POST_HEAP = -2
7.85 - };
7.86 -
7.87 - private:
7.88 -
7.89 - struct RadixItem {
7.90 - int prev, next, box;
7.91 - Item item;
7.92 - int prio;
7.93 - RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
7.94 - };
7.95 -
7.96 - struct RadixBox {
7.97 - int first;
7.98 - int min, size;
7.99 - RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
7.100 - };
7.101 -
7.102 - std::vector<RadixItem> data;
7.103 - std::vector<RadixBox> boxes;
7.104 -
7.105 - ItemIntMap &_iim;
7.106 -
7.107 -
7.108 - public:
7.109 - /// \brief The constructor.
7.110 - ///
7.111 - /// The constructor.
7.112 - ///
7.113 - /// \param map It should be given to the constructor, since it is used
7.114 - /// internally to handle the cross references. The value of the map
7.115 - /// should be PRE_HEAP (-1) for each element.
7.116 - ///
7.117 - /// \param minimal The initial minimal value of the heap.
7.118 - /// \param capacity It determines the initial capacity of the heap.
7.119 - RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)
7.120 - : _iim(map) {
7.121 - boxes.push_back(RadixBox(minimal, 1));
7.122 - boxes.push_back(RadixBox(minimal + 1, 1));
7.123 - while (lower(boxes.size() - 1, capacity + minimal - 1)) {
7.124 - extend();
7.125 - }
7.126 - }
7.127 -
7.128 - /// The number of items stored in the heap.
7.129 - ///
7.130 - /// \brief Returns the number of items stored in the heap.
7.131 - int size() const { return data.size(); }
7.132 - /// \brief Checks if the heap stores no items.
7.133 - ///
7.134 - /// Returns \c true if and only if the heap stores no items.
7.135 - bool empty() const { return data.empty(); }
7.136 -
7.137 - /// \brief Make empty this heap.
7.138 - ///
7.139 - /// Make empty this heap. It does not change the cross reference
7.140 - /// map. If you want to reuse a heap what is not surely empty you
7.141 - /// should first clear the heap and after that you should set the
7.142 - /// cross reference map for each item to \c PRE_HEAP.
7.143 - void clear(int minimal = 0, int capacity = 0) {
7.144 - data.clear(); boxes.clear();
7.145 - boxes.push_back(RadixBox(minimal, 1));
7.146 - boxes.push_back(RadixBox(minimal + 1, 1));
7.147 - while (lower(boxes.size() - 1, capacity + minimal - 1)) {
7.148 - extend();
7.149 - }
7.150 - }
7.151 -
7.152 - private:
7.153 -
7.154 - bool upper(int box, Prio pr) {
7.155 - return pr < boxes[box].min;
7.156 - }
7.157 -
7.158 - bool lower(int box, Prio pr) {
7.159 - return pr >= boxes[box].min + boxes[box].size;
7.160 - }
7.161 -
7.162 - /// \brief Remove item from the box list.
7.163 - void remove(int index) {
7.164 - if (data[index].prev >= 0) {
7.165 - data[data[index].prev].next = data[index].next;
7.166 - } else {
7.167 - boxes[data[index].box].first = data[index].next;
7.168 - }
7.169 - if (data[index].next >= 0) {
7.170 - data[data[index].next].prev = data[index].prev;
7.171 - }
7.172 - }
7.173 -
7.174 - /// \brief Insert item into the box list.
7.175 - void insert(int box, int index) {
7.176 - if (boxes[box].first == -1) {
7.177 - boxes[box].first = index;
7.178 - data[index].next = data[index].prev = -1;
7.179 - } else {
7.180 - data[index].next = boxes[box].first;
7.181 - data[boxes[box].first].prev = index;
7.182 - data[index].prev = -1;
7.183 - boxes[box].first = index;
7.184 - }
7.185 - data[index].box = box;
7.186 - }
7.187 -
7.188 - /// \brief Add a new box to the box list.
7.189 - void extend() {
7.190 - int min = boxes.back().min + boxes.back().size;
7.191 - int bs = 2 * boxes.back().size;
7.192 - boxes.push_back(RadixBox(min, bs));
7.193 - }
7.194 -
7.195 - /// \brief Move an item up into the proper box.
7.196 - void bubble_up(int index) {
7.197 - if (!lower(data[index].box, data[index].prio)) return;
7.198 - remove(index);
7.199 - int box = findUp(data[index].box, data[index].prio);
7.200 - insert(box, index);
7.201 - }
7.202 -
7.203 - /// \brief Find up the proper box for the item with the given prio.
7.204 - int findUp(int start, int pr) {
7.205 - while (lower(start, pr)) {
7.206 - if (++start == int(boxes.size())) {
7.207 - extend();
7.208 - }
7.209 - }
7.210 - return start;
7.211 - }
7.212 -
7.213 - /// \brief Move an item down into the proper box.
7.214 - void bubble_down(int index) {
7.215 - if (!upper(data[index].box, data[index].prio)) return;
7.216 - remove(index);
7.217 - int box = findDown(data[index].box, data[index].prio);
7.218 - insert(box, index);
7.219 - }
7.220 -
7.221 - /// \brief Find up the proper box for the item with the given prio.
7.222 - int findDown(int start, int pr) {
7.223 - while (upper(start, pr)) {
7.224 - if (--start < 0) throw UnderFlowPriorityError();
7.225 - }
7.226 - return start;
7.227 - }
7.228 -
7.229 - /// \brief Find the first not empty box.
7.230 - int findFirst() {
7.231 - int first = 0;
7.232 - while (boxes[first].first == -1) ++first;
7.233 - return first;
7.234 - }
7.235 -
7.236 - /// \brief Gives back the minimal prio of the box.
7.237 - int minValue(int box) {
7.238 - int min = data[boxes[box].first].prio;
7.239 - for (int k = boxes[box].first; k != -1; k = data[k].next) {
7.240 - if (data[k].prio < min) min = data[k].prio;
7.241 - }
7.242 - return min;
7.243 - }
7.244 -
7.245 - /// \brief Rearrange the items of the heap and makes the
7.246 - /// first box not empty.
7.247 - void moveDown() {
7.248 - int box = findFirst();
7.249 - if (box == 0) return;
7.250 - int min = minValue(box);
7.251 - for (int i = 0; i <= box; ++i) {
7.252 - boxes[i].min = min;
7.253 - min += boxes[i].size;
7.254 - }
7.255 - int curr = boxes[box].first, next;
7.256 - while (curr != -1) {
7.257 - next = data[curr].next;
7.258 - bubble_down(curr);
7.259 - curr = next;
7.260 - }
7.261 - }
7.262 -
7.263 - void relocate_last(int index) {
7.264 - if (index != int(data.size()) - 1) {
7.265 - data[index] = data.back();
7.266 - if (data[index].prev != -1) {
7.267 - data[data[index].prev].next = index;
7.268 - } else {
7.269 - boxes[data[index].box].first = index;
7.270 - }
7.271 - if (data[index].next != -1) {
7.272 - data[data[index].next].prev = index;
7.273 - }
7.274 - _iim[data[index].item] = index;
7.275 - }
7.276 - data.pop_back();
7.277 - }
7.278 -
7.279 - public:
7.280 -
7.281 - /// \brief Insert an item into the heap with the given priority.
7.282 - ///
7.283 - /// Adds \c i to the heap with priority \c p.
7.284 - /// \param i The item to insert.
7.285 - /// \param p The priority of the item.
7.286 - void push(const Item &i, const Prio &p) {
7.287 - int n = data.size();
7.288 - _iim.set(i, n);
7.289 - data.push_back(RadixItem(i, p));
7.290 - while (lower(boxes.size() - 1, p)) {
7.291 - extend();
7.292 - }
7.293 - int box = findDown(boxes.size() - 1, p);
7.294 - insert(box, n);
7.295 - }
7.296 -
7.297 - /// \brief Returns the item with minimum priority.
7.298 - ///
7.299 - /// This method returns the item with minimum priority.
7.300 - /// \pre The heap must be nonempty.
7.301 - Item top() const {
7.302 - const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
7.303 - return data[boxes[0].first].item;
7.304 - }
7.305 -
7.306 - /// \brief Returns the minimum priority.
7.307 - ///
7.308 - /// It returns the minimum priority.
7.309 - /// \pre The heap must be nonempty.
7.310 - Prio prio() const {
7.311 - const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
7.312 - return data[boxes[0].first].prio;
7.313 - }
7.314 -
7.315 - /// \brief Deletes the item with minimum priority.
7.316 - ///
7.317 - /// This method deletes the item with minimum priority.
7.318 - /// \pre The heap must be non-empty.
7.319 - void pop() {
7.320 - moveDown();
7.321 - int index = boxes[0].first;
7.322 - _iim[data[index].item] = POST_HEAP;
7.323 - remove(index);
7.324 - relocate_last(index);
7.325 - }
7.326 -
7.327 - /// \brief Deletes \c i from the heap.
7.328 - ///
7.329 - /// This method deletes item \c i from the heap, if \c i was
7.330 - /// already stored in the heap.
7.331 - /// \param i The item to erase.
7.332 - void erase(const Item &i) {
7.333 - int index = _iim[i];
7.334 - _iim[i] = POST_HEAP;
7.335 - remove(index);
7.336 - relocate_last(index);
7.337 - }
7.338 -
7.339 - /// \brief Returns the priority of \c i.
7.340 - ///
7.341 - /// This function returns the priority of item \c i.
7.342 - /// \pre \c i must be in the heap.
7.343 - /// \param i The item.
7.344 - Prio operator[](const Item &i) const {
7.345 - int idx = _iim[i];
7.346 - return data[idx].prio;
7.347 - }
7.348 -
7.349 - /// \brief \c i gets to the heap with priority \c p independently
7.350 - /// if \c i was already there.
7.351 - ///
7.352 - /// This method calls \ref push(\c i, \c p) if \c i is not stored
7.353 - /// in the heap and sets the priority of \c i to \c p otherwise.
7.354 - /// It may throw an \e UnderFlowPriorityException.
7.355 - /// \param i The item.
7.356 - /// \param p The priority.
7.357 - void set(const Item &i, const Prio &p) {
7.358 - int idx = _iim[i];
7.359 - if( idx < 0 ) {
7.360 - push(i, p);
7.361 - }
7.362 - else if( p >= data[idx].prio ) {
7.363 - data[idx].prio = p;
7.364 - bubble_up(idx);
7.365 - } else {
7.366 - data[idx].prio = p;
7.367 - bubble_down(idx);
7.368 - }
7.369 - }
7.370 -
7.371 -
7.372 - /// \brief Decreases the priority of \c i to \c p.
7.373 - ///
7.374 - /// This method decreases the priority of item \c i to \c p.
7.375 - /// \pre \c i must be stored in the heap with priority at least \c p, and
7.376 - /// \c should be greater or equal to the last removed item's priority.
7.377 - /// \param i The item.
7.378 - /// \param p The priority.
7.379 - void decrease(const Item &i, const Prio &p) {
7.380 - int idx = _iim[i];
7.381 - data[idx].prio = p;
7.382 - bubble_down(idx);
7.383 - }
7.384 -
7.385 - /// \brief Increases the priority of \c i to \c p.
7.386 - ///
7.387 - /// This method sets the priority of item \c i to \c p.
7.388 - /// \pre \c i must be stored in the heap with priority at most \c p
7.389 - /// \param i The item.
7.390 - /// \param p The priority.
7.391 - void increase(const Item &i, const Prio &p) {
7.392 - int idx = _iim[i];
7.393 - data[idx].prio = p;
7.394 - bubble_up(idx);
7.395 - }
7.396 -
7.397 - /// \brief Returns if \c item is in, has already been in, or has
7.398 - /// never been in the heap.
7.399 - ///
7.400 - /// This method returns PRE_HEAP if \c item has never been in the
7.401 - /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
7.402 - /// otherwise. In the latter case it is possible that \c item will
7.403 - /// get back to the heap again.
7.404 - /// \param i The item.
7.405 - State state(const Item &i) const {
7.406 - int s = _iim[i];
7.407 - if( s >= 0 ) s = 0;
7.408 - return State(s);
7.409 - }
7.410 -
7.411 - /// \brief Sets the state of the \c item in the heap.
7.412 - ///
7.413 - /// Sets the state of the \c item in the heap. It can be used to
7.414 - /// manually clear the heap when it is important to achive the
7.415 - /// better time complexity.
7.416 - /// \param i The item.
7.417 - /// \param st The state. It should not be \c IN_HEAP.
7.418 - void state(const Item& i, State st) {
7.419 - switch (st) {
7.420 - case POST_HEAP:
7.421 - case PRE_HEAP:
7.422 - if (state(i) == IN_HEAP) {
7.423 - erase(i);
7.424 - }
7.425 - _iim[i] = st;
7.426 - break;
7.427 - case IN_HEAP:
7.428 - break;
7.429 - }
7.430 - }
7.431 -
7.432 - }; // class RadixHeap
7.433 -
7.434 -} // namespace lemon
7.435 -
7.436 -#endif // LEMON_RADIX_HEAP_H
8.1 --- a/test/heap_test.cc Sun Feb 21 18:55:01 2010 +0100
8.2 +++ b/test/heap_test.cc Fri Feb 26 17:08:30 2010 +0100
8.3 @@ -31,9 +31,6 @@
8.4 #include <lemon/maps.h>
8.5
8.6 #include <lemon/bin_heap.h>
8.7 -#include <lemon/fib_heap.h>
8.8 -#include <lemon/radix_heap.h>
8.9 -#include <lemon/bucket_heap.h>
8.10
8.11 #include "test_tools.h"
8.12
8.13 @@ -186,39 +183,5 @@
8.14 dijkstraHeapTest<NodeHeap>(digraph, length, source);
8.15 }
8.16
8.17 - {
8.18 - typedef FibHeap<Prio, ItemIntMap> IntHeap;
8.19 - checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
8.20 - heapSortTest<IntHeap>();
8.21 - heapIncreaseTest<IntHeap>();
8.22 -
8.23 - typedef FibHeap<Prio, IntNodeMap > NodeHeap;
8.24 - checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
8.25 - dijkstraHeapTest<NodeHeap>(digraph, length, source);
8.26 - }
8.27 -
8.28 - {
8.29 - typedef RadixHeap<ItemIntMap> IntHeap;
8.30 - checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
8.31 - heapSortTest<IntHeap>();
8.32 - heapIncreaseTest<IntHeap>();
8.33 -
8.34 - typedef RadixHeap<IntNodeMap > NodeHeap;
8.35 - checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
8.36 - dijkstraHeapTest<NodeHeap>(digraph, length, source);
8.37 - }
8.38 -
8.39 - {
8.40 - typedef BucketHeap<ItemIntMap> IntHeap;
8.41 - checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
8.42 - heapSortTest<IntHeap>();
8.43 - heapIncreaseTest<IntHeap>();
8.44 -
8.45 - typedef BucketHeap<IntNodeMap > NodeHeap;
8.46 - checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
8.47 - dijkstraHeapTest<NodeHeap>(digraph, length, source);
8.48 - }
8.49 -
8.50 -
8.51 return 0;
8.52 }