1.1 --- a/lemon/Makefile.am Thu Jul 23 18:13:59 2009 +0200
1.2 +++ b/lemon/Makefile.am Sun Aug 02 13:44:45 2009 +0200
1.3 @@ -59,6 +59,7 @@
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 @@ -76,6 +77,7 @@
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 @@ -99,6 +101,7 @@
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 Thu Jul 23 18:13:59 2009 +0200
2.2 +++ b/lemon/bin_heap.h Sun Aug 02 13:44:45 2009 +0200
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 Comp specifies the ordering of the priorities.
2.14 + ///priority is efficient. \c CMP 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 Comp A functor class for the ordering of the priorities.
2.22 + ///\tparam CMP 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 Comp = std::less<PR> >
2.28 + template <typename PR, typename IM, typename CMP = 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 Comp Compare;
2.37 + typedef CMP Compare;
2.38
2.39 /// \brief Type to represent the items states.
2.40 ///
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/bucket_heap.h Sun Aug 02 13:44:45 2009 +0200
3.3 @@ -0,0 +1,567 @@
3.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
3.5 + *
3.6 + * This file is a part of LEMON, a generic C++ optimization library.
3.7 + *
3.8 + * Copyright (C) 2003-2009
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 + namespace _bucket_heap_bits {
3.36 +
3.37 + template <bool MIN>
3.38 + struct DirectionTraits {
3.39 + static bool less(int left, int right) {
3.40 + return left < right;
3.41 + }
3.42 + static void increase(int& value) {
3.43 + ++value;
3.44 + }
3.45 + };
3.46 +
3.47 + template <>
3.48 + struct DirectionTraits<false> {
3.49 + static bool less(int left, int right) {
3.50 + return left > right;
3.51 + }
3.52 + static void increase(int& value) {
3.53 + --value;
3.54 + }
3.55 + };
3.56 +
3.57 + }
3.58 +
3.59 + /// \ingroup auxdat
3.60 + ///
3.61 + /// \brief A Bucket Heap implementation.
3.62 + ///
3.63 + /// This class implements the \e bucket \e heap data structure. A \e heap
3.64 + /// is a data structure for storing items with specified values called \e
3.65 + /// priorities in such a way that finding the item with minimum priority is
3.66 + /// efficient. The bucket heap is very simple implementation, it can store
3.67 + /// only integer priorities and it stores for each priority in the
3.68 + /// \f$ [0..C) \f$ range a list of items. So it should be used only when
3.69 + /// the priorities are small. It is not intended to use as dijkstra heap.
3.70 + ///
3.71 + /// \param IM A read and write Item int map, used internally
3.72 + /// to handle the cross references.
3.73 + /// \param MIN If the given parameter is false then instead of the
3.74 + /// minimum value the maximum can be retrivied with the top() and
3.75 + /// prio() member functions.
3.76 + template <typename IM, bool MIN = true>
3.77 + class BucketHeap {
3.78 +
3.79 + public:
3.80 + /// \e
3.81 + typedef typename IM::Key Item;
3.82 + /// \e
3.83 + typedef int Prio;
3.84 + /// \e
3.85 + typedef std::pair<Item, Prio> Pair;
3.86 + /// \e
3.87 + typedef IM ItemIntMap;
3.88 +
3.89 + private:
3.90 +
3.91 + typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
3.92 +
3.93 + public:
3.94 +
3.95 + /// \brief Type to represent the items states.
3.96 + ///
3.97 + /// Each Item element have a state associated to it. It may be "in heap",
3.98 + /// "pre heap" or "post heap". The latter two are indifferent from the
3.99 + /// heap's point of view, but may be useful to the user.
3.100 + ///
3.101 + /// The item-int map must be initialized in such way that it assigns
3.102 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
3.103 + enum State {
3.104 + IN_HEAP = 0, ///< = 0.
3.105 + PRE_HEAP = -1, ///< = -1.
3.106 + POST_HEAP = -2 ///< = -2.
3.107 + };
3.108 +
3.109 + public:
3.110 + /// \brief The constructor.
3.111 + ///
3.112 + /// The constructor.
3.113 + /// \param map should be given to the constructor, since it is used
3.114 + /// internally to handle the cross references. The value of the map
3.115 + /// should be PRE_HEAP (-1) for each element.
3.116 + explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
3.117 +
3.118 + /// The number of items stored in the heap.
3.119 + ///
3.120 + /// \brief Returns the number of items stored in the heap.
3.121 + int size() const { return _data.size(); }
3.122 +
3.123 + /// \brief Checks if the heap stores no items.
3.124 + ///
3.125 + /// Returns \c true if and only if the heap stores no items.
3.126 + bool empty() const { return _data.empty(); }
3.127 +
3.128 + /// \brief Make empty this heap.
3.129 + ///
3.130 + /// Make empty this heap. It does not change the cross reference
3.131 + /// map. If you want to reuse a heap what is not surely empty you
3.132 + /// should first clear the heap and after that you should set the
3.133 + /// cross reference map for each item to \c PRE_HEAP.
3.134 + void clear() {
3.135 + _data.clear(); _first.clear(); _minimum = 0;
3.136 + }
3.137 +
3.138 + private:
3.139 +
3.140 + void relocate_last(int idx) {
3.141 + if (idx + 1 < int(_data.size())) {
3.142 + _data[idx] = _data.back();
3.143 + if (_data[idx].prev != -1) {
3.144 + _data[_data[idx].prev].next = idx;
3.145 + } else {
3.146 + _first[_data[idx].value] = idx;
3.147 + }
3.148 + if (_data[idx].next != -1) {
3.149 + _data[_data[idx].next].prev = idx;
3.150 + }
3.151 + _iim[_data[idx].item] = idx;
3.152 + }
3.153 + _data.pop_back();
3.154 + }
3.155 +
3.156 + void unlace(int idx) {
3.157 + if (_data[idx].prev != -1) {
3.158 + _data[_data[idx].prev].next = _data[idx].next;
3.159 + } else {
3.160 + _first[_data[idx].value] = _data[idx].next;
3.161 + }
3.162 + if (_data[idx].next != -1) {
3.163 + _data[_data[idx].next].prev = _data[idx].prev;
3.164 + }
3.165 + }
3.166 +
3.167 + void lace(int idx) {
3.168 + if (int(_first.size()) <= _data[idx].value) {
3.169 + _first.resize(_data[idx].value + 1, -1);
3.170 + }
3.171 + _data[idx].next = _first[_data[idx].value];
3.172 + if (_data[idx].next != -1) {
3.173 + _data[_data[idx].next].prev = idx;
3.174 + }
3.175 + _first[_data[idx].value] = idx;
3.176 + _data[idx].prev = -1;
3.177 + }
3.178 +
3.179 + public:
3.180 + /// \brief Insert a pair of item and priority into the heap.
3.181 + ///
3.182 + /// Adds \c p.first to the heap with priority \c p.second.
3.183 + /// \param p The pair to insert.
3.184 + void push(const Pair& p) {
3.185 + push(p.first, p.second);
3.186 + }
3.187 +
3.188 + /// \brief Insert an item into the heap with the given priority.
3.189 + ///
3.190 + /// Adds \c i to the heap with priority \c p.
3.191 + /// \param i The item to insert.
3.192 + /// \param p The priority of the item.
3.193 + void push(const Item &i, const Prio &p) {
3.194 + int idx = _data.size();
3.195 + _iim[i] = idx;
3.196 + _data.push_back(BucketItem(i, p));
3.197 + lace(idx);
3.198 + if (Direction::less(p, _minimum)) {
3.199 + _minimum = p;
3.200 + }
3.201 + }
3.202 +
3.203 + /// \brief Returns the item with minimum priority.
3.204 + ///
3.205 + /// This method returns the item with minimum priority.
3.206 + /// \pre The heap must be nonempty.
3.207 + Item top() const {
3.208 + while (_first[_minimum] == -1) {
3.209 + Direction::increase(_minimum);
3.210 + }
3.211 + return _data[_first[_minimum]].item;
3.212 + }
3.213 +
3.214 + /// \brief Returns the minimum priority.
3.215 + ///
3.216 + /// It returns the minimum priority.
3.217 + /// \pre The heap must be nonempty.
3.218 + Prio prio() const {
3.219 + while (_first[_minimum] == -1) {
3.220 + Direction::increase(_minimum);
3.221 + }
3.222 + return _minimum;
3.223 + }
3.224 +
3.225 + /// \brief Deletes the item with minimum priority.
3.226 + ///
3.227 + /// This method deletes the item with minimum priority from the heap.
3.228 + /// \pre The heap must be non-empty.
3.229 + void pop() {
3.230 + while (_first[_minimum] == -1) {
3.231 + Direction::increase(_minimum);
3.232 + }
3.233 + int idx = _first[_minimum];
3.234 + _iim[_data[idx].item] = -2;
3.235 + unlace(idx);
3.236 + relocate_last(idx);
3.237 + }
3.238 +
3.239 + /// \brief Deletes \c i from the heap.
3.240 + ///
3.241 + /// This method deletes item \c i from the heap, if \c i was
3.242 + /// already stored in the heap.
3.243 + /// \param i The item to erase.
3.244 + void erase(const Item &i) {
3.245 + int idx = _iim[i];
3.246 + _iim[_data[idx].item] = -2;
3.247 + unlace(idx);
3.248 + relocate_last(idx);
3.249 + }
3.250 +
3.251 +
3.252 + /// \brief Returns the priority of \c i.
3.253 + ///
3.254 + /// This function returns the priority of item \c i.
3.255 + /// \pre \c i must be in the heap.
3.256 + /// \param i The item.
3.257 + Prio operator[](const Item &i) const {
3.258 + int idx = _iim[i];
3.259 + return _data[idx].value;
3.260 + }
3.261 +
3.262 + /// \brief \c i gets to the heap with priority \c p independently
3.263 + /// if \c i was already there.
3.264 + ///
3.265 + /// This method calls \ref push(\c i, \c p) if \c i is not stored
3.266 + /// in the heap and sets the priority of \c i to \c p otherwise.
3.267 + /// \param i The item.
3.268 + /// \param p The priority.
3.269 + void set(const Item &i, const Prio &p) {
3.270 + int idx = _iim[i];
3.271 + if (idx < 0) {
3.272 + push(i, p);
3.273 + } else if (Direction::less(p, _data[idx].value)) {
3.274 + decrease(i, p);
3.275 + } else {
3.276 + increase(i, p);
3.277 + }
3.278 + }
3.279 +
3.280 + /// \brief Decreases the priority of \c i to \c p.
3.281 + ///
3.282 + /// This method decreases the priority of item \c i to \c p.
3.283 + /// \pre \c i must be stored in the heap with priority at least \c
3.284 + /// p relative to \c Compare.
3.285 + /// \param i The item.
3.286 + /// \param p The priority.
3.287 + void decrease(const Item &i, const Prio &p) {
3.288 + int idx = _iim[i];
3.289 + unlace(idx);
3.290 + _data[idx].value = p;
3.291 + if (Direction::less(p, _minimum)) {
3.292 + _minimum = p;
3.293 + }
3.294 + lace(idx);
3.295 + }
3.296 +
3.297 + /// \brief Increases the priority of \c i to \c p.
3.298 + ///
3.299 + /// This method sets the priority of item \c i to \c p.
3.300 + /// \pre \c i must be stored in the heap with priority at most \c
3.301 + /// p relative to \c Compare.
3.302 + /// \param i The item.
3.303 + /// \param p The priority.
3.304 + void increase(const Item &i, const Prio &p) {
3.305 + int idx = _iim[i];
3.306 + unlace(idx);
3.307 + _data[idx].value = p;
3.308 + lace(idx);
3.309 + }
3.310 +
3.311 + /// \brief Returns if \c item is in, has already been in, or has
3.312 + /// never been in the heap.
3.313 + ///
3.314 + /// This method returns PRE_HEAP if \c item has never been in the
3.315 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
3.316 + /// otherwise. In the latter case it is possible that \c item will
3.317 + /// get back to the heap again.
3.318 + /// \param i The item.
3.319 + State state(const Item &i) const {
3.320 + int idx = _iim[i];
3.321 + if (idx >= 0) idx = 0;
3.322 + return State(idx);
3.323 + }
3.324 +
3.325 + /// \brief Sets the state of the \c item in the heap.
3.326 + ///
3.327 + /// Sets the state of the \c item in the heap. It can be used to
3.328 + /// manually clear the heap when it is important to achive the
3.329 + /// better time complexity.
3.330 + /// \param i The item.
3.331 + /// \param st The state. It should not be \c IN_HEAP.
3.332 + void state(const Item& i, State st) {
3.333 + switch (st) {
3.334 + case POST_HEAP:
3.335 + case PRE_HEAP:
3.336 + if (state(i) == IN_HEAP) {
3.337 + erase(i);
3.338 + }
3.339 + _iim[i] = st;
3.340 + break;
3.341 + case IN_HEAP:
3.342 + break;
3.343 + }
3.344 + }
3.345 +
3.346 + private:
3.347 +
3.348 + struct BucketItem {
3.349 + BucketItem(const Item& _item, int _value)
3.350 + : item(_item), value(_value) {}
3.351 +
3.352 + Item item;
3.353 + int value;
3.354 +
3.355 + int prev, next;
3.356 + };
3.357 +
3.358 + ItemIntMap& _iim;
3.359 + std::vector<int> _first;
3.360 + std::vector<BucketItem> _data;
3.361 + mutable int _minimum;
3.362 +
3.363 + }; // class BucketHeap
3.364 +
3.365 + /// \ingroup auxdat
3.366 + ///
3.367 + /// \brief A Simplified Bucket Heap implementation.
3.368 + ///
3.369 + /// This class implements a simplified \e bucket \e heap data
3.370 + /// structure. It does not provide some functionality but it faster
3.371 + /// and simplier data structure than the BucketHeap. The main
3.372 + /// difference is that the BucketHeap stores for every key a double
3.373 + /// linked list while this class stores just simple lists. In the
3.374 + /// other way it does not support erasing each elements just the
3.375 + /// minimal and it does not supports key increasing, decreasing.
3.376 + ///
3.377 + /// \param IM A read and write Item int map, used internally
3.378 + /// to handle the cross references.
3.379 + /// \param MIN If the given parameter is false then instead of the
3.380 + /// minimum value the maximum can be retrivied with the top() and
3.381 + /// prio() member functions.
3.382 + ///
3.383 + /// \sa BucketHeap
3.384 + template <typename IM, bool MIN = true >
3.385 + class SimpleBucketHeap {
3.386 +
3.387 + public:
3.388 + typedef typename IM::Key Item;
3.389 + typedef int Prio;
3.390 + typedef std::pair<Item, Prio> Pair;
3.391 + typedef IM ItemIntMap;
3.392 +
3.393 + private:
3.394 +
3.395 + typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
3.396 +
3.397 + public:
3.398 +
3.399 + /// \brief Type to represent the items states.
3.400 + ///
3.401 + /// Each Item element have a state associated to it. It may be "in heap",
3.402 + /// "pre heap" or "post heap". The latter two are indifferent from the
3.403 + /// heap's point of view, but may be useful to the user.
3.404 + ///
3.405 + /// The item-int map must be initialized in such way that it assigns
3.406 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
3.407 + enum State {
3.408 + IN_HEAP = 0, ///< = 0.
3.409 + PRE_HEAP = -1, ///< = -1.
3.410 + POST_HEAP = -2 ///< = -2.
3.411 + };
3.412 +
3.413 + public:
3.414 +
3.415 + /// \brief The constructor.
3.416 + ///
3.417 + /// The constructor.
3.418 + /// \param map should be given to the constructor, since it is used
3.419 + /// internally to handle the cross references. The value of the map
3.420 + /// should be PRE_HEAP (-1) for each element.
3.421 + explicit SimpleBucketHeap(ItemIntMap &map)
3.422 + : _iim(map), _free(-1), _num(0), _minimum(0) {}
3.423 +
3.424 + /// \brief Returns the number of items stored in the heap.
3.425 + ///
3.426 + /// The number of items stored in the heap.
3.427 + int size() const { return _num; }
3.428 +
3.429 + /// \brief Checks if the heap stores no items.
3.430 + ///
3.431 + /// Returns \c true if and only if the heap stores no items.
3.432 + bool empty() const { return _num == 0; }
3.433 +
3.434 + /// \brief Make empty this heap.
3.435 + ///
3.436 + /// Make empty this heap. It does not change the cross reference
3.437 + /// map. If you want to reuse a heap what is not surely empty you
3.438 + /// should first clear the heap and after that you should set the
3.439 + /// cross reference map for each item to \c PRE_HEAP.
3.440 + void clear() {
3.441 + _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
3.442 + }
3.443 +
3.444 + /// \brief Insert a pair of item and priority into the heap.
3.445 + ///
3.446 + /// Adds \c p.first to the heap with priority \c p.second.
3.447 + /// \param p The pair to insert.
3.448 + void push(const Pair& p) {
3.449 + push(p.first, p.second);
3.450 + }
3.451 +
3.452 + /// \brief Insert an item into the heap with the given priority.
3.453 + ///
3.454 + /// Adds \c i to the heap with priority \c p.
3.455 + /// \param i The item to insert.
3.456 + /// \param p The priority of the item.
3.457 + void push(const Item &i, const Prio &p) {
3.458 + int idx;
3.459 + if (_free == -1) {
3.460 + idx = _data.size();
3.461 + _data.push_back(BucketItem(i));
3.462 + } else {
3.463 + idx = _free;
3.464 + _free = _data[idx].next;
3.465 + _data[idx].item = i;
3.466 + }
3.467 + _iim[i] = idx;
3.468 + if (p >= int(_first.size())) _first.resize(p + 1, -1);
3.469 + _data[idx].next = _first[p];
3.470 + _first[p] = idx;
3.471 + if (Direction::less(p, _minimum)) {
3.472 + _minimum = p;
3.473 + }
3.474 + ++_num;
3.475 + }
3.476 +
3.477 + /// \brief Returns the item with minimum priority.
3.478 + ///
3.479 + /// This method returns the item with minimum priority.
3.480 + /// \pre The heap must be nonempty.
3.481 + Item top() const {
3.482 + while (_first[_minimum] == -1) {
3.483 + Direction::increase(_minimum);
3.484 + }
3.485 + return _data[_first[_minimum]].item;
3.486 + }
3.487 +
3.488 + /// \brief Returns the minimum priority.
3.489 + ///
3.490 + /// It returns the minimum priority.
3.491 + /// \pre The heap must be nonempty.
3.492 + Prio prio() const {
3.493 + while (_first[_minimum] == -1) {
3.494 + Direction::increase(_minimum);
3.495 + }
3.496 + return _minimum;
3.497 + }
3.498 +
3.499 + /// \brief Deletes the item with minimum priority.
3.500 + ///
3.501 + /// This method deletes the item with minimum priority from the heap.
3.502 + /// \pre The heap must be non-empty.
3.503 + void pop() {
3.504 + while (_first[_minimum] == -1) {
3.505 + Direction::increase(_minimum);
3.506 + }
3.507 + int idx = _first[_minimum];
3.508 + _iim[_data[idx].item] = -2;
3.509 + _first[_minimum] = _data[idx].next;
3.510 + _data[idx].next = _free;
3.511 + _free = idx;
3.512 + --_num;
3.513 + }
3.514 +
3.515 + /// \brief Returns the priority of \c i.
3.516 + ///
3.517 + /// This function returns the priority of item \c i.
3.518 + /// \warning This operator is not a constant time function
3.519 + /// because it scans the whole data structure to find the proper
3.520 + /// value.
3.521 + /// \pre \c i must be in the heap.
3.522 + /// \param i The item.
3.523 + Prio operator[](const Item &i) const {
3.524 + for (int k = 0; k < _first.size(); ++k) {
3.525 + int idx = _first[k];
3.526 + while (idx != -1) {
3.527 + if (_data[idx].item == i) {
3.528 + return k;
3.529 + }
3.530 + idx = _data[idx].next;
3.531 + }
3.532 + }
3.533 + return -1;
3.534 + }
3.535 +
3.536 + /// \brief Returns if \c item is in, has already been in, or has
3.537 + /// never been in the heap.
3.538 + ///
3.539 + /// This method returns PRE_HEAP if \c item has never been in the
3.540 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
3.541 + /// otherwise. In the latter case it is possible that \c item will
3.542 + /// get back to the heap again.
3.543 + /// \param i The item.
3.544 + State state(const Item &i) const {
3.545 + int idx = _iim[i];
3.546 + if (idx >= 0) idx = 0;
3.547 + return State(idx);
3.548 + }
3.549 +
3.550 + private:
3.551 +
3.552 + struct BucketItem {
3.553 + BucketItem(const Item& _item)
3.554 + : item(_item) {}
3.555 +
3.556 + Item item;
3.557 + int next;
3.558 + };
3.559 +
3.560 + ItemIntMap& _iim;
3.561 + std::vector<int> _first;
3.562 + std::vector<BucketItem> _data;
3.563 + int _free, _num;
3.564 + mutable int _minimum;
3.565 +
3.566 + }; // class SimpleBucketHeap
3.567 +
3.568 +}
3.569 +
3.570 +#endif
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/fib_heap.h Sun Aug 02 13:44:45 2009 +0200
4.3 @@ -0,0 +1,468 @@
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_FIB_HEAP_H
4.23 +#define LEMON_FIB_HEAP_H
4.24 +
4.25 +///\file
4.26 +///\ingroup auxdat
4.27 +///\brief Fibonacci Heap implementation.
4.28 +
4.29 +#include <vector>
4.30 +#include <functional>
4.31 +#include <lemon/math.h>
4.32 +
4.33 +namespace lemon {
4.34 +
4.35 + /// \ingroup auxdat
4.36 + ///
4.37 + ///\brief Fibonacci Heap.
4.38 + ///
4.39 + ///This class implements the \e Fibonacci \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. \c CMP specifies the ordering of the priorities. In a heap
4.43 + ///one can change the priority of an item, add or erase an item, etc.
4.44 + ///
4.45 + ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
4.46 + ///heap. In case of many calls to these operations, it is better to use a
4.47 + ///\ref BinHeap "binary heap".
4.48 + ///
4.49 + ///\param PRIO Type of the priority of the items.
4.50 + ///\param IM A read and writable Item int map, used internally
4.51 + ///to handle the cross references.
4.52 + ///\param CMP A class for the ordering of the priorities. The
4.53 + ///default is \c std::less<PRIO>.
4.54 + ///
4.55 + ///\sa BinHeap
4.56 + ///\sa Dijkstra
4.57 +#ifdef DOXYGEN
4.58 + template <typename PRIO, typename IM, typename CMP>
4.59 +#else
4.60 + template <typename PRIO, typename IM, typename CMP = std::less<PRIO> >
4.61 +#endif
4.62 + class FibHeap {
4.63 + public:
4.64 + ///\e
4.65 + typedef IM ItemIntMap;
4.66 + ///\e
4.67 + typedef PRIO Prio;
4.68 + ///\e
4.69 + typedef typename ItemIntMap::Key Item;
4.70 + ///\e
4.71 + typedef std::pair<Item,Prio> Pair;
4.72 + ///\e
4.73 + typedef CMP Compare;
4.74 +
4.75 + private:
4.76 + class Store;
4.77 +
4.78 + std::vector<Store> _data;
4.79 + int _minimum;
4.80 + ItemIntMap &_iim;
4.81 + Compare _comp;
4.82 + int _num;
4.83 +
4.84 + public:
4.85 +
4.86 + /// \brief Type to represent the items states.
4.87 + ///
4.88 + /// Each Item element have a state associated to it. It may be "in heap",
4.89 + /// "pre heap" or "post heap". The latter two are indifferent from the
4.90 + /// heap's point of view, but may be useful to the user.
4.91 + ///
4.92 + /// The item-int map must be initialized in such way that it assigns
4.93 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
4.94 + enum State {
4.95 + IN_HEAP = 0, ///< = 0.
4.96 + PRE_HEAP = -1, ///< = -1.
4.97 + POST_HEAP = -2 ///< = -2.
4.98 + };
4.99 +
4.100 + /// \brief The constructor
4.101 + ///
4.102 + /// \c map should be given to the constructor, since it is
4.103 + /// used internally to handle the cross references.
4.104 + explicit FibHeap(ItemIntMap &map)
4.105 + : _minimum(0), _iim(map), _num() {}
4.106 +
4.107 + /// \brief The constructor
4.108 + ///
4.109 + /// \c map should be given to the constructor, since it is used
4.110 + /// internally to handle the cross references. \c comp is an
4.111 + /// object for ordering of the priorities.
4.112 + FibHeap(ItemIntMap &map, const Compare &comp)
4.113 + : _minimum(0), _iim(map), _comp(comp), _num() {}
4.114 +
4.115 + /// \brief The number of items stored in the heap.
4.116 + ///
4.117 + /// Returns the number of items stored in the heap.
4.118 + int size() const { return _num; }
4.119 +
4.120 + /// \brief Checks if the heap stores no items.
4.121 + ///
4.122 + /// Returns \c true if and only if the heap stores no items.
4.123 + bool empty() const { return _num==0; }
4.124 +
4.125 + /// \brief Make empty this heap.
4.126 + ///
4.127 + /// Make empty this heap. It does not change the cross reference
4.128 + /// map. If you want to reuse a heap what is not surely empty you
4.129 + /// should first clear the heap and after that you should set the
4.130 + /// cross reference map for each item to \c PRE_HEAP.
4.131 + void clear() {
4.132 + _data.clear(); _minimum = 0; _num = 0;
4.133 + }
4.134 +
4.135 + /// \brief \c item gets to the heap with priority \c value independently
4.136 + /// if \c item was already there.
4.137 + ///
4.138 + /// This method calls \ref push(\c item, \c value) if \c item is not
4.139 + /// stored in the heap and it calls \ref decrease(\c item, \c value) or
4.140 + /// \ref increase(\c item, \c value) otherwise.
4.141 + void set (const Item& item, const Prio& value) {
4.142 + int i=_iim[item];
4.143 + if ( i >= 0 && _data[i].in ) {
4.144 + if ( _comp(value, _data[i].prio) ) decrease(item, value);
4.145 + if ( _comp(_data[i].prio, value) ) increase(item, value);
4.146 + } else push(item, value);
4.147 + }
4.148 +
4.149 + /// \brief Adds \c item to the heap with priority \c value.
4.150 + ///
4.151 + /// Adds \c item to the heap with priority \c value.
4.152 + /// \pre \c item must not be stored in the heap.
4.153 + void push (const Item& item, const Prio& value) {
4.154 + int i=_iim[item];
4.155 + if ( i < 0 ) {
4.156 + int s=_data.size();
4.157 + _iim.set( item, s );
4.158 + Store st;
4.159 + st.name=item;
4.160 + _data.push_back(st);
4.161 + i=s;
4.162 + } else {
4.163 + _data[i].parent=_data[i].child=-1;
4.164 + _data[i].degree=0;
4.165 + _data[i].in=true;
4.166 + _data[i].marked=false;
4.167 + }
4.168 +
4.169 + if ( _num ) {
4.170 + _data[_data[_minimum].right_neighbor].left_neighbor=i;
4.171 + _data[i].right_neighbor=_data[_minimum].right_neighbor;
4.172 + _data[_minimum].right_neighbor=i;
4.173 + _data[i].left_neighbor=_minimum;
4.174 + if ( _comp( value, _data[_minimum].prio) ) _minimum=i;
4.175 + } else {
4.176 + _data[i].right_neighbor=_data[i].left_neighbor=i;
4.177 + _minimum=i;
4.178 + }
4.179 + _data[i].prio=value;
4.180 + ++_num;
4.181 + }
4.182 +
4.183 + /// \brief Returns the item with minimum priority relative to \c Compare.
4.184 + ///
4.185 + /// This method returns the item with minimum priority relative to \c
4.186 + /// Compare.
4.187 + /// \pre The heap must be nonempty.
4.188 + Item top() const { return _data[_minimum].name; }
4.189 +
4.190 + /// \brief Returns the minimum priority relative to \c Compare.
4.191 + ///
4.192 + /// It returns the minimum priority relative to \c Compare.
4.193 + /// \pre The heap must be nonempty.
4.194 + const Prio& prio() const { return _data[_minimum].prio; }
4.195 +
4.196 + /// \brief Returns the priority of \c item.
4.197 + ///
4.198 + /// It returns the priority of \c item.
4.199 + /// \pre \c item must be in the heap.
4.200 + const Prio& operator[](const Item& item) const {
4.201 + return _data[_iim[item]].prio;
4.202 + }
4.203 +
4.204 + /// \brief Deletes the item with minimum priority relative to \c Compare.
4.205 + ///
4.206 + /// This method deletes the item with minimum priority relative to \c
4.207 + /// Compare from the heap.
4.208 + /// \pre The heap must be non-empty.
4.209 + void pop() {
4.210 + /*The first case is that there are only one root.*/
4.211 + if ( _data[_minimum].left_neighbor==_minimum ) {
4.212 + _data[_minimum].in=false;
4.213 + if ( _data[_minimum].degree!=0 ) {
4.214 + makeroot(_data[_minimum].child);
4.215 + _minimum=_data[_minimum].child;
4.216 + balance();
4.217 + }
4.218 + } else {
4.219 + int right=_data[_minimum].right_neighbor;
4.220 + unlace(_minimum);
4.221 + _data[_minimum].in=false;
4.222 + if ( _data[_minimum].degree > 0 ) {
4.223 + int left=_data[_minimum].left_neighbor;
4.224 + int child=_data[_minimum].child;
4.225 + int last_child=_data[child].left_neighbor;
4.226 +
4.227 + makeroot(child);
4.228 +
4.229 + _data[left].right_neighbor=child;
4.230 + _data[child].left_neighbor=left;
4.231 + _data[right].left_neighbor=last_child;
4.232 + _data[last_child].right_neighbor=right;
4.233 + }
4.234 + _minimum=right;
4.235 + balance();
4.236 + } // the case where there are more roots
4.237 + --_num;
4.238 + }
4.239 +
4.240 + /// \brief Deletes \c item from the heap.
4.241 + ///
4.242 + /// This method deletes \c item from the heap, if \c item was already
4.243 + /// stored in the heap. It is quite inefficient in Fibonacci heaps.
4.244 + void erase (const Item& item) {
4.245 + int i=_iim[item];
4.246 +
4.247 + if ( i >= 0 && _data[i].in ) {
4.248 + if ( _data[i].parent!=-1 ) {
4.249 + int p=_data[i].parent;
4.250 + cut(i,p);
4.251 + cascade(p);
4.252 + }
4.253 + _minimum=i; //As if its prio would be -infinity
4.254 + pop();
4.255 + }
4.256 + }
4.257 +
4.258 + /// \brief Decreases the priority of \c item to \c value.
4.259 + ///
4.260 + /// This method decreases the priority of \c item to \c value.
4.261 + /// \pre \c item must be stored in the heap with priority at least \c
4.262 + /// value relative to \c Compare.
4.263 + void decrease (Item item, const Prio& value) {
4.264 + int i=_iim[item];
4.265 + _data[i].prio=value;
4.266 + int p=_data[i].parent;
4.267 +
4.268 + if ( p!=-1 && _comp(value, _data[p].prio) ) {
4.269 + cut(i,p);
4.270 + cascade(p);
4.271 + }
4.272 + if ( _comp(value, _data[_minimum].prio) ) _minimum=i;
4.273 + }
4.274 +
4.275 + /// \brief Increases the priority of \c item to \c value.
4.276 + ///
4.277 + /// This method sets the priority of \c item to \c value. Though
4.278 + /// there is no precondition on the priority of \c item, this
4.279 + /// method should be used only if it is indeed necessary to increase
4.280 + /// (relative to \c Compare) the priority of \c item, because this
4.281 + /// method is inefficient.
4.282 + void increase (Item item, const Prio& value) {
4.283 + erase(item);
4.284 + push(item, value);
4.285 + }
4.286 +
4.287 +
4.288 + /// \brief Returns if \c item is in, has already been in, or has never
4.289 + /// been in the heap.
4.290 + ///
4.291 + /// This method returns PRE_HEAP if \c item has never been in the
4.292 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
4.293 + /// otherwise. In the latter case it is possible that \c item will
4.294 + /// get back to the heap again.
4.295 + State state(const Item &item) const {
4.296 + int i=_iim[item];
4.297 + if( i>=0 ) {
4.298 + if ( _data[i].in ) i=0;
4.299 + else i=-2;
4.300 + }
4.301 + return State(i);
4.302 + }
4.303 +
4.304 + /// \brief Sets the state of the \c item in the heap.
4.305 + ///
4.306 + /// Sets the state of the \c item in the heap. It can be used to
4.307 + /// manually clear the heap when it is important to achive the
4.308 + /// better time _complexity.
4.309 + /// \param i The item.
4.310 + /// \param st The state. It should not be \c IN_HEAP.
4.311 + void state(const Item& i, State st) {
4.312 + switch (st) {
4.313 + case POST_HEAP:
4.314 + case PRE_HEAP:
4.315 + if (state(i) == IN_HEAP) {
4.316 + erase(i);
4.317 + }
4.318 + _iim[i] = st;
4.319 + break;
4.320 + case IN_HEAP:
4.321 + break;
4.322 + }
4.323 + }
4.324 +
4.325 + private:
4.326 +
4.327 + void balance() {
4.328 +
4.329 + int maxdeg=int( std::floor( 2.08*log(double(_data.size()))))+1;
4.330 +
4.331 + std::vector<int> A(maxdeg,-1);
4.332 +
4.333 + /*
4.334 + *Recall that now minimum does not point to the minimum prio element.
4.335 + *We set minimum to this during balance().
4.336 + */
4.337 + int anchor=_data[_minimum].left_neighbor;
4.338 + int next=_minimum;
4.339 + bool end=false;
4.340 +
4.341 + do {
4.342 + int active=next;
4.343 + if ( anchor==active ) end=true;
4.344 + int d=_data[active].degree;
4.345 + next=_data[active].right_neighbor;
4.346 +
4.347 + while (A[d]!=-1) {
4.348 + if( _comp(_data[active].prio, _data[A[d]].prio) ) {
4.349 + fuse(active,A[d]);
4.350 + } else {
4.351 + fuse(A[d],active);
4.352 + active=A[d];
4.353 + }
4.354 + A[d]=-1;
4.355 + ++d;
4.356 + }
4.357 + A[d]=active;
4.358 + } while ( !end );
4.359 +
4.360 +
4.361 + while ( _data[_minimum].parent >=0 )
4.362 + _minimum=_data[_minimum].parent;
4.363 + int s=_minimum;
4.364 + int m=_minimum;
4.365 + do {
4.366 + if ( _comp(_data[s].prio, _data[_minimum].prio) ) _minimum=s;
4.367 + s=_data[s].right_neighbor;
4.368 + } while ( s != m );
4.369 + }
4.370 +
4.371 + void makeroot(int c) {
4.372 + int s=c;
4.373 + do {
4.374 + _data[s].parent=-1;
4.375 + s=_data[s].right_neighbor;
4.376 + } while ( s != c );
4.377 + }
4.378 +
4.379 + void cut(int a, int b) {
4.380 + /*
4.381 + *Replacing a from the children of b.
4.382 + */
4.383 + --_data[b].degree;
4.384 +
4.385 + if ( _data[b].degree !=0 ) {
4.386 + int child=_data[b].child;
4.387 + if ( child==a )
4.388 + _data[b].child=_data[child].right_neighbor;
4.389 + unlace(a);
4.390 + }
4.391 +
4.392 +
4.393 + /*Lacing a to the roots.*/
4.394 + int right=_data[_minimum].right_neighbor;
4.395 + _data[_minimum].right_neighbor=a;
4.396 + _data[a].left_neighbor=_minimum;
4.397 + _data[a].right_neighbor=right;
4.398 + _data[right].left_neighbor=a;
4.399 +
4.400 + _data[a].parent=-1;
4.401 + _data[a].marked=false;
4.402 + }
4.403 +
4.404 + void cascade(int a) {
4.405 + if ( _data[a].parent!=-1 ) {
4.406 + int p=_data[a].parent;
4.407 +
4.408 + if ( _data[a].marked==false ) _data[a].marked=true;
4.409 + else {
4.410 + cut(a,p);
4.411 + cascade(p);
4.412 + }
4.413 + }
4.414 + }
4.415 +
4.416 + void fuse(int a, int b) {
4.417 + unlace(b);
4.418 +
4.419 + /*Lacing b under a.*/
4.420 + _data[b].parent=a;
4.421 +
4.422 + if (_data[a].degree==0) {
4.423 + _data[b].left_neighbor=b;
4.424 + _data[b].right_neighbor=b;
4.425 + _data[a].child=b;
4.426 + } else {
4.427 + int child=_data[a].child;
4.428 + int last_child=_data[child].left_neighbor;
4.429 + _data[child].left_neighbor=b;
4.430 + _data[b].right_neighbor=child;
4.431 + _data[last_child].right_neighbor=b;
4.432 + _data[b].left_neighbor=last_child;
4.433 + }
4.434 +
4.435 + ++_data[a].degree;
4.436 +
4.437 + _data[b].marked=false;
4.438 + }
4.439 +
4.440 + /*
4.441 + *It is invoked only if a has siblings.
4.442 + */
4.443 + void unlace(int a) {
4.444 + int leftn=_data[a].left_neighbor;
4.445 + int rightn=_data[a].right_neighbor;
4.446 + _data[leftn].right_neighbor=rightn;
4.447 + _data[rightn].left_neighbor=leftn;
4.448 + }
4.449 +
4.450 +
4.451 + class Store {
4.452 + friend class FibHeap;
4.453 +
4.454 + Item name;
4.455 + int parent;
4.456 + int left_neighbor;
4.457 + int right_neighbor;
4.458 + int child;
4.459 + int degree;
4.460 + bool marked;
4.461 + bool in;
4.462 + Prio prio;
4.463 +
4.464 + Store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
4.465 + };
4.466 + };
4.467 +
4.468 +} //namespace lemon
4.469 +
4.470 +#endif //LEMON_FIB_HEAP_H
4.471 +
5.1 --- a/lemon/maps.h Thu Jul 23 18:13:59 2009 +0200
5.2 +++ b/lemon/maps.h Sun Aug 02 13:44:45 2009 +0200
5.3 @@ -22,6 +22,7 @@
5.4 #include <iterator>
5.5 #include <functional>
5.6 #include <vector>
5.7 +#include <map>
5.8
5.9 #include <lemon/core.h>
5.10
5.11 @@ -29,8 +30,6 @@
5.12 ///\ingroup maps
5.13 ///\brief Miscellaneous property maps
5.14
5.15 -#include <map>
5.16 -
5.17 namespace lemon {
5.18
5.19 /// \addtogroup maps
5.20 @@ -1818,7 +1817,7 @@
5.21 /// \brief Provides an immutable and unique id for each item in a graph.
5.22 ///
5.23 /// IdMap provides a unique and immutable id for each item of the
5.24 - /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
5.25 + /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
5.26 /// - \b unique: different items get different ids,
5.27 /// - \b immutable: the id of an item does not change (even if you
5.28 /// delete other nodes).
5.29 @@ -2281,7 +2280,7 @@
5.30 }
5.31
5.32 /// \brief Gives back the item belonging to a \e RangeId
5.33 - ///
5.34 + ///
5.35 /// Gives back the item belonging to a \e RangeId.
5.36 Item operator()(int id) const {
5.37 return _inv_map[id];
5.38 @@ -2338,6 +2337,903 @@
5.39 }
5.40 };
5.41
5.42 + /// \brief Dynamic iterable \c bool map.
5.43 + ///
5.44 + /// This class provides a special graph map type which can store a
5.45 + /// \c bool value for graph items (\c Node, \c Arc or \c Edge).
5.46 + /// For both \c true and \c false values it is possible to iterate on
5.47 + /// the keys.
5.48 + ///
5.49 + /// This type is a reference map, so it can be modified with the
5.50 + /// subscription operator.
5.51 + ///
5.52 + /// \tparam GR The graph type.
5.53 + /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
5.54 + /// \c GR::Edge).
5.55 + ///
5.56 + /// \see IterableIntMap, IterableValueMap
5.57 + /// \see CrossRefMap
5.58 + template <typename GR, typename K>
5.59 + class IterableBoolMap
5.60 + : protected ItemSetTraits<GR, K>::template Map<int>::Type {
5.61 + private:
5.62 + typedef GR Graph;
5.63 +
5.64 + typedef typename ItemSetTraits<GR, K>::ItemIt KeyIt;
5.65 + typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Parent;
5.66 +
5.67 + std::vector<K> _array;
5.68 + int _sep;
5.69 +
5.70 + public:
5.71 +
5.72 + /// Indicates that the map is reference map.
5.73 + typedef True ReferenceMapTag;
5.74 +
5.75 + /// The key type
5.76 + typedef K Key;
5.77 + /// The value type
5.78 + typedef bool Value;
5.79 + /// The const reference type.
5.80 + typedef const Value& ConstReference;
5.81 +
5.82 + private:
5.83 +
5.84 + int position(const Key& key) const {
5.85 + return Parent::operator[](key);
5.86 + }
5.87 +
5.88 + public:
5.89 +
5.90 + /// \brief Reference to the value of the map.
5.91 + ///
5.92 + /// This class is similar to the \c bool type. It can be converted to
5.93 + /// \c bool and it provides the same operators.
5.94 + class Reference {
5.95 + friend class IterableBoolMap;
5.96 + private:
5.97 + Reference(IterableBoolMap& map, const Key& key)
5.98 + : _key(key), _map(map) {}
5.99 + public:
5.100 +
5.101 + Reference& operator=(const Reference& value) {
5.102 + _map.set(_key, static_cast<bool>(value));
5.103 + return *this;
5.104 + }
5.105 +
5.106 + operator bool() const {
5.107 + return static_cast<const IterableBoolMap&>(_map)[_key];
5.108 + }
5.109 +
5.110 + Reference& operator=(bool value) {
5.111 + _map.set(_key, value);
5.112 + return *this;
5.113 + }
5.114 + Reference& operator&=(bool value) {
5.115 + _map.set(_key, _map[_key] & value);
5.116 + return *this;
5.117 + }
5.118 + Reference& operator|=(bool value) {
5.119 + _map.set(_key, _map[_key] | value);
5.120 + return *this;
5.121 + }
5.122 + Reference& operator^=(bool value) {
5.123 + _map.set(_key, _map[_key] ^ value);
5.124 + return *this;
5.125 + }
5.126 + private:
5.127 + Key _key;
5.128 + IterableBoolMap& _map;
5.129 + };
5.130 +
5.131 + /// \brief Constructor of the map with a default value.
5.132 + ///
5.133 + /// Constructor of the map with a default value.
5.134 + explicit IterableBoolMap(const Graph& graph, bool def = false)
5.135 + : Parent(graph) {
5.136 + typename Parent::Notifier* nf = Parent::notifier();
5.137 + Key it;
5.138 + for (nf->first(it); it != INVALID; nf->next(it)) {
5.139 + Parent::set(it, _array.size());
5.140 + _array.push_back(it);
5.141 + }
5.142 + _sep = (def ? _array.size() : 0);
5.143 + }
5.144 +
5.145 + /// \brief Const subscript operator of the map.
5.146 + ///
5.147 + /// Const subscript operator of the map.
5.148 + bool operator[](const Key& key) const {
5.149 + return position(key) < _sep;
5.150 + }
5.151 +
5.152 + /// \brief Subscript operator of the map.
5.153 + ///
5.154 + /// Subscript operator of the map.
5.155 + Reference operator[](const Key& key) {
5.156 + return Reference(*this, key);
5.157 + }
5.158 +
5.159 + /// \brief Set operation of the map.
5.160 + ///
5.161 + /// Set operation of the map.
5.162 + void set(const Key& key, bool value) {
5.163 + int pos = position(key);
5.164 + if (value) {
5.165 + if (pos < _sep) return;
5.166 + Key tmp = _array[_sep];
5.167 + _array[_sep] = key;
5.168 + Parent::set(key, _sep);
5.169 + _array[pos] = tmp;
5.170 + Parent::set(tmp, pos);
5.171 + ++_sep;
5.172 + } else {
5.173 + if (pos >= _sep) return;
5.174 + --_sep;
5.175 + Key tmp = _array[_sep];
5.176 + _array[_sep] = key;
5.177 + Parent::set(key, _sep);
5.178 + _array[pos] = tmp;
5.179 + Parent::set(tmp, pos);
5.180 + }
5.181 + }
5.182 +
5.183 + /// \brief Set all items.
5.184 + ///
5.185 + /// Set all items in the map.
5.186 + /// \note Constant time operation.
5.187 + void setAll(bool value) {
5.188 + _sep = (value ? _array.size() : 0);
5.189 + }
5.190 +
5.191 + /// \brief Returns the number of the keys mapped to \c true.
5.192 + ///
5.193 + /// Returns the number of the keys mapped to \c true.
5.194 + int trueNum() const {
5.195 + return _sep;
5.196 + }
5.197 +
5.198 + /// \brief Returns the number of the keys mapped to \c false.
5.199 + ///
5.200 + /// Returns the number of the keys mapped to \c false.
5.201 + int falseNum() const {
5.202 + return _array.size() - _sep;
5.203 + }
5.204 +
5.205 + /// \brief Iterator for the keys mapped to \c true.
5.206 + ///
5.207 + /// Iterator for the keys mapped to \c true. It works
5.208 + /// like a graph item iterator, it can be converted to
5.209 + /// the key type of the map, incremented with \c ++ operator, and
5.210 + /// if the iterator leaves the last valid key, it will be equal to
5.211 + /// \c INVALID.
5.212 + class TrueIt : public Key {
5.213 + public:
5.214 + typedef Key Parent;
5.215 +
5.216 + /// \brief Creates an iterator.
5.217 + ///
5.218 + /// Creates an iterator. It iterates on the
5.219 + /// keys mapped to \c true.
5.220 + /// \param map The IterableBoolMap.
5.221 + explicit TrueIt(const IterableBoolMap& map)
5.222 + : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID),
5.223 + _map(&map) {}
5.224 +
5.225 + /// \brief Invalid constructor \& conversion.
5.226 + ///
5.227 + /// This constructor initializes the iterator to be invalid.
5.228 + /// \sa Invalid for more details.
5.229 + TrueIt(Invalid) : Parent(INVALID), _map(0) {}
5.230 +
5.231 + /// \brief Increment operator.
5.232 + ///
5.233 + /// Increment operator.
5.234 + TrueIt& operator++() {
5.235 + int pos = _map->position(*this);
5.236 + Parent::operator=(pos > 0 ? _map->_array[pos - 1] : INVALID);
5.237 + return *this;
5.238 + }
5.239 +
5.240 + private:
5.241 + const IterableBoolMap* _map;
5.242 + };
5.243 +
5.244 + /// \brief Iterator for the keys mapped to \c false.
5.245 + ///
5.246 + /// Iterator for the keys mapped to \c false. It works
5.247 + /// like a graph item iterator, it can be converted to
5.248 + /// the key type of the map, incremented with \c ++ operator, and
5.249 + /// if the iterator leaves the last valid key, it will be equal to
5.250 + /// \c INVALID.
5.251 + class FalseIt : public Key {
5.252 + public:
5.253 + typedef Key Parent;
5.254 +
5.255 + /// \brief Creates an iterator.
5.256 + ///
5.257 + /// Creates an iterator. It iterates on the
5.258 + /// keys mapped to \c false.
5.259 + /// \param map The IterableBoolMap.
5.260 + explicit FalseIt(const IterableBoolMap& map)
5.261 + : Parent(map._sep < int(map._array.size()) ?
5.262 + map._array.back() : INVALID), _map(&map) {}
5.263 +
5.264 + /// \brief Invalid constructor \& conversion.
5.265 + ///
5.266 + /// This constructor initializes the iterator to be invalid.
5.267 + /// \sa Invalid for more details.
5.268 + FalseIt(Invalid) : Parent(INVALID), _map(0) {}
5.269 +
5.270 + /// \brief Increment operator.
5.271 + ///
5.272 + /// Increment operator.
5.273 + FalseIt& operator++() {
5.274 + int pos = _map->position(*this);
5.275 + Parent::operator=(pos > _map->_sep ? _map->_array[pos - 1] : INVALID);
5.276 + return *this;
5.277 + }
5.278 +
5.279 + private:
5.280 + const IterableBoolMap* _map;
5.281 + };
5.282 +
5.283 + /// \brief Iterator for the keys mapped to a given value.
5.284 + ///
5.285 + /// Iterator for the keys mapped to a given value. It works
5.286 + /// like a graph item iterator, it can be converted to
5.287 + /// the key type of the map, incremented with \c ++ operator, and
5.288 + /// if the iterator leaves the last valid key, it will be equal to
5.289 + /// \c INVALID.
5.290 + class ItemIt : public Key {
5.291 + public:
5.292 + typedef Key Parent;
5.293 +
5.294 + /// \brief Creates an iterator with a value.
5.295 + ///
5.296 + /// Creates an iterator with a value. It iterates on the
5.297 + /// keys mapped to the given value.
5.298 + /// \param map The IterableBoolMap.
5.299 + /// \param value The value.
5.300 + ItemIt(const IterableBoolMap& map, bool value)
5.301 + : Parent(value ?
5.302 + (map._sep > 0 ?
5.303 + map._array[map._sep - 1] : INVALID) :
5.304 + (map._sep < int(map._array.size()) ?
5.305 + map._array.back() : INVALID)), _map(&map) {}
5.306 +
5.307 + /// \brief Invalid constructor \& conversion.
5.308 + ///
5.309 + /// This constructor initializes the iterator to be invalid.
5.310 + /// \sa Invalid for more details.
5.311 + ItemIt(Invalid) : Parent(INVALID), _map(0) {}
5.312 +
5.313 + /// \brief Increment operator.
5.314 + ///
5.315 + /// Increment operator.
5.316 + ItemIt& operator++() {
5.317 + int pos = _map->position(*this);
5.318 + int _sep = pos >= _map->_sep ? _map->_sep : 0;
5.319 + Parent::operator=(pos > _sep ? _map->_array[pos - 1] : INVALID);
5.320 + return *this;
5.321 + }
5.322 +
5.323 + private:
5.324 + const IterableBoolMap* _map;
5.325 + };
5.326 +
5.327 + protected:
5.328 +
5.329 + virtual void add(const Key& key) {
5.330 + Parent::add(key);
5.331 + Parent::set(key, _array.size());
5.332 + _array.push_back(key);
5.333 + }
5.334 +
5.335 + virtual void add(const std::vector<Key>& keys) {
5.336 + Parent::add(keys);
5.337 + for (int i = 0; i < int(keys.size()); ++i) {
5.338 + Parent::set(keys[i], _array.size());
5.339 + _array.push_back(keys[i]);
5.340 + }
5.341 + }
5.342 +
5.343 + virtual void erase(const Key& key) {
5.344 + int pos = position(key);
5.345 + if (pos < _sep) {
5.346 + --_sep;
5.347 + Parent::set(_array[_sep], pos);
5.348 + _array[pos] = _array[_sep];
5.349 + Parent::set(_array.back(), _sep);
5.350 + _array[_sep] = _array.back();
5.351 + _array.pop_back();
5.352 + } else {
5.353 + Parent::set(_array.back(), pos);
5.354 + _array[pos] = _array.back();
5.355 + _array.pop_back();
5.356 + }
5.357 + Parent::erase(key);
5.358 + }
5.359 +
5.360 + virtual void erase(const std::vector<Key>& keys) {
5.361 + for (int i = 0; i < int(keys.size()); ++i) {
5.362 + int pos = position(keys[i]);
5.363 + if (pos < _sep) {
5.364 + --_sep;
5.365 + Parent::set(_array[_sep], pos);
5.366 + _array[pos] = _array[_sep];
5.367 + Parent::set(_array.back(), _sep);
5.368 + _array[_sep] = _array.back();
5.369 + _array.pop_back();
5.370 + } else {
5.371 + Parent::set(_array.back(), pos);
5.372 + _array[pos] = _array.back();
5.373 + _array.pop_back();
5.374 + }
5.375 + }
5.376 + Parent::erase(keys);
5.377 + }
5.378 +
5.379 + virtual void build() {
5.380 + Parent::build();
5.381 + typename Parent::Notifier* nf = Parent::notifier();
5.382 + Key it;
5.383 + for (nf->first(it); it != INVALID; nf->next(it)) {
5.384 + Parent::set(it, _array.size());
5.385 + _array.push_back(it);
5.386 + }
5.387 + _sep = 0;
5.388 + }
5.389 +
5.390 + virtual void clear() {
5.391 + _array.clear();
5.392 + _sep = 0;
5.393 + Parent::clear();
5.394 + }
5.395 +
5.396 + };
5.397 +
5.398 +
5.399 + namespace _maps_bits {
5.400 + template <typename Item>
5.401 + struct IterableIntMapNode {
5.402 + IterableIntMapNode() : value(-1) {}
5.403 + IterableIntMapNode(int _value) : value(_value) {}
5.404 + Item prev, next;
5.405 + int value;
5.406 + };
5.407 + }
5.408 +
5.409 + /// \brief Dynamic iterable integer map.
5.410 + ///
5.411 + /// This class provides a special graph map type which can store an
5.412 + /// integer value for graph items (\c Node, \c Arc or \c Edge).
5.413 + /// For each non-negative value it is possible to iterate on the keys
5.414 + /// mapped to the value.
5.415 + ///
5.416 + /// This type is a reference map, so it can be modified with the
5.417 + /// subscription operator.
5.418 + ///
5.419 + /// \note The size of the data structure depends on the largest
5.420 + /// value in the map.
5.421 + ///
5.422 + /// \tparam GR The graph type.
5.423 + /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
5.424 + /// \c GR::Edge).
5.425 + ///
5.426 + /// \see IterableBoolMap, IterableValueMap
5.427 + /// \see CrossRefMap
5.428 + template <typename GR, typename K>
5.429 + class IterableIntMap
5.430 + : protected ItemSetTraits<GR, K>::
5.431 + template Map<_maps_bits::IterableIntMapNode<K> >::Type {
5.432 + public:
5.433 + typedef typename ItemSetTraits<GR, K>::
5.434 + template Map<_maps_bits::IterableIntMapNode<K> >::Type Parent;
5.435 +
5.436 + /// The key type
5.437 + typedef K Key;
5.438 + /// The value type
5.439 + typedef int Value;
5.440 + /// The graph type
5.441 + typedef GR Graph;
5.442 +
5.443 + /// \brief Constructor of the map.
5.444 + ///
5.445 + /// Constructor of the map. It sets all values to -1.
5.446 + explicit IterableIntMap(const Graph& graph)
5.447 + : Parent(graph) {}
5.448 +
5.449 + /// \brief Constructor of the map with a given value.
5.450 + ///
5.451 + /// Constructor of the map with a given value.
5.452 + explicit IterableIntMap(const Graph& graph, int value)
5.453 + : Parent(graph, _maps_bits::IterableIntMapNode<K>(value)) {
5.454 + if (value >= 0) {
5.455 + for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
5.456 + lace(it);
5.457 + }
5.458 + }
5.459 + }
5.460 +
5.461 + private:
5.462 +
5.463 + void unlace(const Key& key) {
5.464 + typename Parent::Value& node = Parent::operator[](key);
5.465 + if (node.value < 0) return;
5.466 + if (node.prev != INVALID) {
5.467 + Parent::operator[](node.prev).next = node.next;
5.468 + } else {
5.469 + _first[node.value] = node.next;
5.470 + }
5.471 + if (node.next != INVALID) {
5.472 + Parent::operator[](node.next).prev = node.prev;
5.473 + }
5.474 + while (!_first.empty() && _first.back() == INVALID) {
5.475 + _first.pop_back();
5.476 + }
5.477 + }
5.478 +
5.479 + void lace(const Key& key) {
5.480 + typename Parent::Value& node = Parent::operator[](key);
5.481 + if (node.value < 0) return;
5.482 + if (node.value >= int(_first.size())) {
5.483 + _first.resize(node.value + 1, INVALID);
5.484 + }
5.485 + node.prev = INVALID;
5.486 + node.next = _first[node.value];
5.487 + if (node.next != INVALID) {
5.488 + Parent::operator[](node.next).prev = key;
5.489 + }
5.490 + _first[node.value] = key;
5.491 + }
5.492 +
5.493 + public:
5.494 +
5.495 + /// Indicates that the map is reference map.
5.496 + typedef True ReferenceMapTag;
5.497 +
5.498 + /// \brief Reference to the value of the map.
5.499 + ///
5.500 + /// This class is similar to the \c int type. It can
5.501 + /// be converted to \c int and it has the same operators.
5.502 + class Reference {
5.503 + friend class IterableIntMap;
5.504 + private:
5.505 + Reference(IterableIntMap& map, const Key& key)
5.506 + : _key(key), _map(map) {}
5.507 + public:
5.508 +
5.509 + Reference& operator=(const Reference& value) {
5.510 + _map.set(_key, static_cast<const int&>(value));
5.511 + return *this;
5.512 + }
5.513 +
5.514 + operator const int&() const {
5.515 + return static_cast<const IterableIntMap&>(_map)[_key];
5.516 + }
5.517 +
5.518 + Reference& operator=(int value) {
5.519 + _map.set(_key, value);
5.520 + return *this;
5.521 + }
5.522 + Reference& operator++() {
5.523 + _map.set(_key, _map[_key] + 1);
5.524 + return *this;
5.525 + }
5.526 + int operator++(int) {
5.527 + int value = _map[_key];
5.528 + _map.set(_key, value + 1);
5.529 + return value;
5.530 + }
5.531 + Reference& operator--() {
5.532 + _map.set(_key, _map[_key] - 1);
5.533 + return *this;
5.534 + }
5.535 + int operator--(int) {
5.536 + int value = _map[_key];
5.537 + _map.set(_key, value - 1);
5.538 + return value;
5.539 + }
5.540 + Reference& operator+=(int value) {
5.541 + _map.set(_key, _map[_key] + value);
5.542 + return *this;
5.543 + }
5.544 + Reference& operator-=(int value) {
5.545 + _map.set(_key, _map[_key] - value);
5.546 + return *this;
5.547 + }
5.548 + Reference& operator*=(int value) {
5.549 + _map.set(_key, _map[_key] * value);
5.550 + return *this;
5.551 + }
5.552 + Reference& operator/=(int value) {
5.553 + _map.set(_key, _map[_key] / value);
5.554 + return *this;
5.555 + }
5.556 + Reference& operator%=(int value) {
5.557 + _map.set(_key, _map[_key] % value);
5.558 + return *this;
5.559 + }
5.560 + Reference& operator&=(int value) {
5.561 + _map.set(_key, _map[_key] & value);
5.562 + return *this;
5.563 + }
5.564 + Reference& operator|=(int value) {
5.565 + _map.set(_key, _map[_key] | value);
5.566 + return *this;
5.567 + }
5.568 + Reference& operator^=(int value) {
5.569 + _map.set(_key, _map[_key] ^ value);
5.570 + return *this;
5.571 + }
5.572 + Reference& operator<<=(int value) {
5.573 + _map.set(_key, _map[_key] << value);
5.574 + return *this;
5.575 + }
5.576 + Reference& operator>>=(int value) {
5.577 + _map.set(_key, _map[_key] >> value);
5.578 + return *this;
5.579 + }
5.580 +
5.581 + private:
5.582 + Key _key;
5.583 + IterableIntMap& _map;
5.584 + };
5.585 +
5.586 + /// The const reference type.
5.587 + typedef const Value& ConstReference;
5.588 +
5.589 + /// \brief Gives back the maximal value plus one.
5.590 + ///
5.591 + /// Gives back the maximal value plus one.
5.592 + int size() const {
5.593 + return _first.size();
5.594 + }
5.595 +
5.596 + /// \brief Set operation of the map.
5.597 + ///
5.598 + /// Set operation of the map.
5.599 + void set(const Key& key, const Value& value) {
5.600 + unlace(key);
5.601 + Parent::operator[](key).value = value;
5.602 + lace(key);
5.603 + }
5.604 +
5.605 + /// \brief Const subscript operator of the map.
5.606 + ///
5.607 + /// Const subscript operator of the map.
5.608 + const Value& operator[](const Key& key) const {
5.609 + return Parent::operator[](key).value;
5.610 + }
5.611 +
5.612 + /// \brief Subscript operator of the map.
5.613 + ///
5.614 + /// Subscript operator of the map.
5.615 + Reference operator[](const Key& key) {
5.616 + return Reference(*this, key);
5.617 + }
5.618 +
5.619 + /// \brief Iterator for the keys with the same value.
5.620 + ///
5.621 + /// Iterator for the keys with the same value. It works
5.622 + /// like a graph item iterator, it can be converted to
5.623 + /// the item type of the map, incremented with \c ++ operator, and
5.624 + /// if the iterator leaves the last valid item, it will be equal to
5.625 + /// \c INVALID.
5.626 + class ItemIt : public Key {
5.627 + public:
5.628 + typedef Key Parent;
5.629 +
5.630 + /// \brief Invalid constructor \& conversion.
5.631 + ///
5.632 + /// This constructor initializes the iterator to be invalid.
5.633 + /// \sa Invalid for more details.
5.634 + ItemIt(Invalid) : Parent(INVALID), _map(0) {}
5.635 +
5.636 + /// \brief Creates an iterator with a value.
5.637 + ///
5.638 + /// Creates an iterator with a value. It iterates on the
5.639 + /// keys mapped to the given value.
5.640 + /// \param map The IterableIntMap.
5.641 + /// \param value The value.
5.642 + ItemIt(const IterableIntMap& map, int value) : _map(&map) {
5.643 + if (value < 0 || value >= int(_map->_first.size())) {
5.644 + Parent::operator=(INVALID);
5.645 + } else {
5.646 + Parent::operator=(_map->_first[value]);
5.647 + }
5.648 + }
5.649 +
5.650 + /// \brief Increment operator.
5.651 + ///
5.652 + /// Increment operator.
5.653 + ItemIt& operator++() {
5.654 + Parent::operator=(_map->IterableIntMap::Parent::
5.655 + operator[](static_cast<Parent&>(*this)).next);
5.656 + return *this;
5.657 + }
5.658 +
5.659 + private:
5.660 + const IterableIntMap* _map;
5.661 + };
5.662 +
5.663 + protected:
5.664 +
5.665 + virtual void erase(const Key& key) {
5.666 + unlace(key);
5.667 + Parent::erase(key);
5.668 + }
5.669 +
5.670 + virtual void erase(const std::vector<Key>& keys) {
5.671 + for (int i = 0; i < int(keys.size()); ++i) {
5.672 + unlace(keys[i]);
5.673 + }
5.674 + Parent::erase(keys);
5.675 + }
5.676 +
5.677 + virtual void clear() {
5.678 + _first.clear();
5.679 + Parent::clear();
5.680 + }
5.681 +
5.682 + private:
5.683 + std::vector<Key> _first;
5.684 + };
5.685 +
5.686 + namespace _maps_bits {
5.687 + template <typename Item, typename Value>
5.688 + struct IterableValueMapNode {
5.689 + IterableValueMapNode(Value _value = Value()) : value(_value) {}
5.690 + Item prev, next;
5.691 + Value value;
5.692 + };
5.693 + }
5.694 +
5.695 + /// \brief Dynamic iterable map for comparable values.
5.696 + ///
5.697 + /// This class provides a special graph map type which can store an
5.698 + /// comparable value for graph items (\c Node, \c Arc or \c Edge).
5.699 + /// For each value it is possible to iterate on the keys mapped to
5.700 + /// the value.
5.701 + ///
5.702 + /// The map stores for each value a linked list with
5.703 + /// the items which mapped to the value, and the values are stored
5.704 + /// in balanced binary tree. The values of the map can be accessed
5.705 + /// with stl compatible forward iterator.
5.706 + ///
5.707 + /// This type is not reference map, so it cannot be modified with
5.708 + /// the subscription operator.
5.709 + ///
5.710 + /// \tparam GR The graph type.
5.711 + /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
5.712 + /// \c GR::Edge).
5.713 + /// \tparam V The value type of the map. It can be any comparable
5.714 + /// value type.
5.715 + ///
5.716 + /// \see IterableBoolMap, IterableIntMap
5.717 + /// \see CrossRefMap
5.718 + template <typename GR, typename K, typename V>
5.719 + class IterableValueMap
5.720 + : protected ItemSetTraits<GR, K>::
5.721 + template Map<_maps_bits::IterableValueMapNode<K, V> >::Type {
5.722 + public:
5.723 + typedef typename ItemSetTraits<GR, K>::
5.724 + template Map<_maps_bits::IterableValueMapNode<K, V> >::Type Parent;
5.725 +
5.726 + /// The key type
5.727 + typedef K Key;
5.728 + /// The value type
5.729 + typedef V Value;
5.730 + /// The graph type
5.731 + typedef GR Graph;
5.732 +
5.733 + public:
5.734 +
5.735 + /// \brief Constructor of the map with a given value.
5.736 + ///
5.737 + /// Constructor of the map with a given value.
5.738 + explicit IterableValueMap(const Graph& graph,
5.739 + const Value& value = Value())
5.740 + : Parent(graph, _maps_bits::IterableValueMapNode<K, V>(value)) {
5.741 + for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
5.742 + lace(it);
5.743 + }
5.744 + }
5.745 +
5.746 + protected:
5.747 +
5.748 + void unlace(const Key& key) {
5.749 + typename Parent::Value& node = Parent::operator[](key);
5.750 + if (node.prev != INVALID) {
5.751 + Parent::operator[](node.prev).next = node.next;
5.752 + } else {
5.753 + if (node.next != INVALID) {
5.754 + _first[node.value] = node.next;
5.755 + } else {
5.756 + _first.erase(node.value);
5.757 + }
5.758 + }
5.759 + if (node.next != INVALID) {
5.760 + Parent::operator[](node.next).prev = node.prev;
5.761 + }
5.762 + }
5.763 +
5.764 + void lace(const Key& key) {
5.765 + typename Parent::Value& node = Parent::operator[](key);
5.766 + typename std::map<Value, Key>::iterator it = _first.find(node.value);
5.767 + if (it == _first.end()) {
5.768 + node.prev = node.next = INVALID;
5.769 + _first.insert(std::make_pair(node.value, key));
5.770 + } else {
5.771 + node.prev = INVALID;
5.772 + node.next = it->second;
5.773 + if (node.next != INVALID) {
5.774 + Parent::operator[](node.next).prev = key;
5.775 + }
5.776 + it->second = key;
5.777 + }
5.778 + }
5.779 +
5.780 + public:
5.781 +
5.782 + /// \brief Forward iterator for values.
5.783 + ///
5.784 + /// This iterator is an stl compatible forward
5.785 + /// iterator on the values of the map. The values can
5.786 + /// be accessed in the <tt>[beginValue, endValue)</tt> range.
5.787 + class ValueIterator
5.788 + : public std::iterator<std::forward_iterator_tag, Value> {
5.789 + friend class IterableValueMap;
5.790 + private:
5.791 + ValueIterator(typename std::map<Value, Key>::const_iterator _it)
5.792 + : it(_it) {}
5.793 + public:
5.794 +
5.795 + ValueIterator() {}
5.796 +
5.797 + ValueIterator& operator++() { ++it; return *this; }
5.798 + ValueIterator operator++(int) {
5.799 + ValueIterator tmp(*this);
5.800 + operator++();
5.801 + return tmp;
5.802 + }
5.803 +
5.804 + const Value& operator*() const { return it->first; }
5.805 + const Value* operator->() const { return &(it->first); }
5.806 +
5.807 + bool operator==(ValueIterator jt) const { return it == jt.it; }
5.808 + bool operator!=(ValueIterator jt) const { return it != jt.it; }
5.809 +
5.810 + private:
5.811 + typename std::map<Value, Key>::const_iterator it;
5.812 + };
5.813 +
5.814 + /// \brief Returns an iterator to the first value.
5.815 + ///
5.816 + /// Returns an stl compatible iterator to the
5.817 + /// first value of the map. The values of the
5.818 + /// map can be accessed in the <tt>[beginValue, endValue)</tt>
5.819 + /// range.
5.820 + ValueIterator beginValue() const {
5.821 + return ValueIterator(_first.begin());
5.822 + }
5.823 +
5.824 + /// \brief Returns an iterator after the last value.
5.825 + ///
5.826 + /// Returns an stl compatible iterator after the
5.827 + /// last value of the map. The values of the
5.828 + /// map can be accessed in the <tt>[beginValue, endValue)</tt>
5.829 + /// range.
5.830 + ValueIterator endValue() const {
5.831 + return ValueIterator(_first.end());
5.832 + }
5.833 +
5.834 + /// \brief Set operation of the map.
5.835 + ///
5.836 + /// Set operation of the map.
5.837 + void set(const Key& key, const Value& value) {
5.838 + unlace(key);
5.839 + Parent::operator[](key).value = value;
5.840 + lace(key);
5.841 + }
5.842 +
5.843 + /// \brief Const subscript operator of the map.
5.844 + ///
5.845 + /// Const subscript operator of the map.
5.846 + const Value& operator[](const Key& key) const {
5.847 + return Parent::operator[](key).value;
5.848 + }
5.849 +
5.850 + /// \brief Iterator for the keys with the same value.
5.851 + ///
5.852 + /// Iterator for the keys with the same value. It works
5.853 + /// like a graph item iterator, it can be converted to
5.854 + /// the item type of the map, incremented with \c ++ operator, and
5.855 + /// if the iterator leaves the last valid item, it will be equal to
5.856 + /// \c INVALID.
5.857 + class ItemIt : public Key {
5.858 + public:
5.859 + typedef Key Parent;
5.860 +
5.861 + /// \brief Invalid constructor \& conversion.
5.862 + ///
5.863 + /// This constructor initializes the iterator to be invalid.
5.864 + /// \sa Invalid for more details.
5.865 + ItemIt(Invalid) : Parent(INVALID), _map(0) {}
5.866 +
5.867 + /// \brief Creates an iterator with a value.
5.868 + ///
5.869 + /// Creates an iterator with a value. It iterates on the
5.870 + /// keys which have the given value.
5.871 + /// \param map The IterableValueMap
5.872 + /// \param value The value
5.873 + ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
5.874 + typename std::map<Value, Key>::const_iterator it =
5.875 + map._first.find(value);
5.876 + if (it == map._first.end()) {
5.877 + Parent::operator=(INVALID);
5.878 + } else {
5.879 + Parent::operator=(it->second);
5.880 + }
5.881 + }
5.882 +
5.883 + /// \brief Increment operator.
5.884 + ///
5.885 + /// Increment Operator.
5.886 + ItemIt& operator++() {
5.887 + Parent::operator=(_map->IterableValueMap::Parent::
5.888 + operator[](static_cast<Parent&>(*this)).next);
5.889 + return *this;
5.890 + }
5.891 +
5.892 +
5.893 + private:
5.894 + const IterableValueMap* _map;
5.895 + };
5.896 +
5.897 + protected:
5.898 +
5.899 + virtual void add(const Key& key) {
5.900 + Parent::add(key);
5.901 + unlace(key);
5.902 + }
5.903 +
5.904 + virtual void add(const std::vector<Key>& keys) {
5.905 + Parent::add(keys);
5.906 + for (int i = 0; i < int(keys.size()); ++i) {
5.907 + lace(keys[i]);
5.908 + }
5.909 + }
5.910 +
5.911 + virtual void erase(const Key& key) {
5.912 + unlace(key);
5.913 + Parent::erase(key);
5.914 + }
5.915 +
5.916 + virtual void erase(const std::vector<Key>& keys) {
5.917 + for (int i = 0; i < int(keys.size()); ++i) {
5.918 + unlace(keys[i]);
5.919 + }
5.920 + Parent::erase(keys);
5.921 + }
5.922 +
5.923 + virtual void build() {
5.924 + Parent::build();
5.925 + for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
5.926 + lace(it);
5.927 + }
5.928 + }
5.929 +
5.930 + virtual void clear() {
5.931 + _first.clear();
5.932 + Parent::clear();
5.933 + }
5.934 +
5.935 + private:
5.936 + std::map<Value, Key> _first;
5.937 + };
5.938 +
5.939 /// \brief Map of the source nodes of arcs in a digraph.
5.940 ///
5.941 /// SourceMap provides access for the source node of each arc in a digraph,
5.942 @@ -2507,7 +3403,7 @@
5.943 /// in constant time. On the other hand, the values are updated automatically
5.944 /// whenever the digraph changes.
5.945 ///
5.946 - /// \warning Besides \c addNode() and \c addArc(), a digraph structure
5.947 + /// \warning Besides \c addNode() and \c addArc(), a digraph structure
5.948 /// may provide alternative ways to modify the digraph.
5.949 /// The correct behavior of InDegMap is not guarantied if these additional
5.950 /// features are used. For example the functions
5.951 @@ -2523,7 +3419,7 @@
5.952 ::ItemNotifier::ObserverBase {
5.953
5.954 public:
5.955 -
5.956 +
5.957 /// The graph type of InDegMap
5.958 typedef GR Graph;
5.959 typedef GR Digraph;
5.960 @@ -2637,7 +3533,7 @@
5.961 /// in constant time. On the other hand, the values are updated automatically
5.962 /// whenever the digraph changes.
5.963 ///
5.964 - /// \warning Besides \c addNode() and \c addArc(), a digraph structure
5.965 + /// \warning Besides \c addNode() and \c addArc(), a digraph structure
5.966 /// may provide alternative ways to modify the digraph.
5.967 /// The correct behavior of OutDegMap is not guarantied if these additional
5.968 /// features are used. For example the functions
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/lemon/radix_heap.h Sun Aug 02 13:44:45 2009 +0200
6.3 @@ -0,0 +1,433 @@
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_RADIX_HEAP_H
6.23 +#define LEMON_RADIX_HEAP_H
6.24 +
6.25 +///\ingroup auxdat
6.26 +///\file
6.27 +///\brief Radix Heap implementation.
6.28 +
6.29 +#include <vector>
6.30 +#include <lemon/error.h>
6.31 +
6.32 +namespace lemon {
6.33 +
6.34 +
6.35 + /// \ingroup auxdata
6.36 + ///
6.37 + /// \brief A Radix Heap implementation.
6.38 + ///
6.39 + /// This class implements the \e radix \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. This heap type can store only items with \e int priority.
6.43 + /// In a heap one can change the priority of an item, add or erase an
6.44 + /// item, but the priority cannot be decreased under the last removed
6.45 + /// item's priority.
6.46 + ///
6.47 + /// \param IM A read and writable Item int map, used internally
6.48 + /// to handle the cross references.
6.49 + ///
6.50 + /// \see BinHeap
6.51 + /// \see Dijkstra
6.52 + template <typename IM>
6.53 + class RadixHeap {
6.54 +
6.55 + public:
6.56 + typedef typename IM::Key Item;
6.57 + typedef int Prio;
6.58 + typedef IM ItemIntMap;
6.59 +
6.60 + /// \brief Exception thrown by RadixHeap.
6.61 + ///
6.62 + /// This Exception is thrown when a smaller priority
6.63 + /// is inserted into the \e RadixHeap then the last time erased.
6.64 + /// \see RadixHeap
6.65 +
6.66 + class UnderFlowPriorityError : public Exception {
6.67 + public:
6.68 + virtual const char* what() const throw() {
6.69 + return "lemon::RadixHeap::UnderFlowPriorityError";
6.70 + }
6.71 + };
6.72 +
6.73 + /// \brief Type to represent the items states.
6.74 + ///
6.75 + /// Each Item element have a state associated to it. It may be "in heap",
6.76 + /// "pre heap" or "post heap". The latter two are indifferent from the
6.77 + /// heap's point of view, but may be useful to the user.
6.78 + ///
6.79 + /// The ItemIntMap \e should be initialized in such way that it maps
6.80 + /// PRE_HEAP (-1) to any element to be put in the heap...
6.81 + enum State {
6.82 + IN_HEAP = 0,
6.83 + PRE_HEAP = -1,
6.84 + POST_HEAP = -2
6.85 + };
6.86 +
6.87 + private:
6.88 +
6.89 + struct RadixItem {
6.90 + int prev, next, box;
6.91 + Item item;
6.92 + int prio;
6.93 + RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
6.94 + };
6.95 +
6.96 + struct RadixBox {
6.97 + int first;
6.98 + int min, size;
6.99 + RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
6.100 + };
6.101 +
6.102 + std::vector<RadixItem> data;
6.103 + std::vector<RadixBox> boxes;
6.104 +
6.105 + ItemIntMap &_iim;
6.106 +
6.107 +
6.108 + public:
6.109 + /// \brief The constructor.
6.110 + ///
6.111 + /// The constructor.
6.112 + ///
6.113 + /// \param map It should be given to the constructor, since it is used
6.114 + /// internally to handle the cross references. The value of the map
6.115 + /// should be PRE_HEAP (-1) for each element.
6.116 + ///
6.117 + /// \param minimal The initial minimal value of the heap.
6.118 + /// \param capacity It determines the initial capacity of the heap.
6.119 + RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)
6.120 + : _iim(map) {
6.121 + boxes.push_back(RadixBox(minimal, 1));
6.122 + boxes.push_back(RadixBox(minimal + 1, 1));
6.123 + while (lower(boxes.size() - 1, capacity + minimal - 1)) {
6.124 + extend();
6.125 + }
6.126 + }
6.127 +
6.128 + /// The number of items stored in the heap.
6.129 + ///
6.130 + /// \brief Returns the number of items stored in the heap.
6.131 + int size() const { return data.size(); }
6.132 + /// \brief Checks if the heap stores no items.
6.133 + ///
6.134 + /// Returns \c true if and only if the heap stores no items.
6.135 + bool empty() const { return data.empty(); }
6.136 +
6.137 + /// \brief Make empty this heap.
6.138 + ///
6.139 + /// Make empty this heap. It does not change the cross reference
6.140 + /// map. If you want to reuse a heap what is not surely empty you
6.141 + /// should first clear the heap and after that you should set the
6.142 + /// cross reference map for each item to \c PRE_HEAP.
6.143 + void clear(int minimal = 0, int capacity = 0) {
6.144 + data.clear(); boxes.clear();
6.145 + boxes.push_back(RadixBox(minimal, 1));
6.146 + boxes.push_back(RadixBox(minimal + 1, 1));
6.147 + while (lower(boxes.size() - 1, capacity + minimal - 1)) {
6.148 + extend();
6.149 + }
6.150 + }
6.151 +
6.152 + private:
6.153 +
6.154 + bool upper(int box, Prio pr) {
6.155 + return pr < boxes[box].min;
6.156 + }
6.157 +
6.158 + bool lower(int box, Prio pr) {
6.159 + return pr >= boxes[box].min + boxes[box].size;
6.160 + }
6.161 +
6.162 + /// \brief Remove item from the box list.
6.163 + void remove(int index) {
6.164 + if (data[index].prev >= 0) {
6.165 + data[data[index].prev].next = data[index].next;
6.166 + } else {
6.167 + boxes[data[index].box].first = data[index].next;
6.168 + }
6.169 + if (data[index].next >= 0) {
6.170 + data[data[index].next].prev = data[index].prev;
6.171 + }
6.172 + }
6.173 +
6.174 + /// \brief Insert item into the box list.
6.175 + void insert(int box, int index) {
6.176 + if (boxes[box].first == -1) {
6.177 + boxes[box].first = index;
6.178 + data[index].next = data[index].prev = -1;
6.179 + } else {
6.180 + data[index].next = boxes[box].first;
6.181 + data[boxes[box].first].prev = index;
6.182 + data[index].prev = -1;
6.183 + boxes[box].first = index;
6.184 + }
6.185 + data[index].box = box;
6.186 + }
6.187 +
6.188 + /// \brief Add a new box to the box list.
6.189 + void extend() {
6.190 + int min = boxes.back().min + boxes.back().size;
6.191 + int bs = 2 * boxes.back().size;
6.192 + boxes.push_back(RadixBox(min, bs));
6.193 + }
6.194 +
6.195 + /// \brief Move an item up into the proper box.
6.196 + void bubble_up(int index) {
6.197 + if (!lower(data[index].box, data[index].prio)) return;
6.198 + remove(index);
6.199 + int box = findUp(data[index].box, data[index].prio);
6.200 + insert(box, index);
6.201 + }
6.202 +
6.203 + /// \brief Find up the proper box for the item with the given prio.
6.204 + int findUp(int start, int pr) {
6.205 + while (lower(start, pr)) {
6.206 + if (++start == int(boxes.size())) {
6.207 + extend();
6.208 + }
6.209 + }
6.210 + return start;
6.211 + }
6.212 +
6.213 + /// \brief Move an item down into the proper box.
6.214 + void bubble_down(int index) {
6.215 + if (!upper(data[index].box, data[index].prio)) return;
6.216 + remove(index);
6.217 + int box = findDown(data[index].box, data[index].prio);
6.218 + insert(box, index);
6.219 + }
6.220 +
6.221 + /// \brief Find up the proper box for the item with the given prio.
6.222 + int findDown(int start, int pr) {
6.223 + while (upper(start, pr)) {
6.224 + if (--start < 0) throw UnderFlowPriorityError();
6.225 + }
6.226 + return start;
6.227 + }
6.228 +
6.229 + /// \brief Find the first not empty box.
6.230 + int findFirst() {
6.231 + int first = 0;
6.232 + while (boxes[first].first == -1) ++first;
6.233 + return first;
6.234 + }
6.235 +
6.236 + /// \brief Gives back the minimal prio of the box.
6.237 + int minValue(int box) {
6.238 + int min = data[boxes[box].first].prio;
6.239 + for (int k = boxes[box].first; k != -1; k = data[k].next) {
6.240 + if (data[k].prio < min) min = data[k].prio;
6.241 + }
6.242 + return min;
6.243 + }
6.244 +
6.245 + /// \brief Rearrange the items of the heap and makes the
6.246 + /// first box not empty.
6.247 + void moveDown() {
6.248 + int box = findFirst();
6.249 + if (box == 0) return;
6.250 + int min = minValue(box);
6.251 + for (int i = 0; i <= box; ++i) {
6.252 + boxes[i].min = min;
6.253 + min += boxes[i].size;
6.254 + }
6.255 + int curr = boxes[box].first, next;
6.256 + while (curr != -1) {
6.257 + next = data[curr].next;
6.258 + bubble_down(curr);
6.259 + curr = next;
6.260 + }
6.261 + }
6.262 +
6.263 + void relocate_last(int index) {
6.264 + if (index != int(data.size()) - 1) {
6.265 + data[index] = data.back();
6.266 + if (data[index].prev != -1) {
6.267 + data[data[index].prev].next = index;
6.268 + } else {
6.269 + boxes[data[index].box].first = index;
6.270 + }
6.271 + if (data[index].next != -1) {
6.272 + data[data[index].next].prev = index;
6.273 + }
6.274 + _iim[data[index].item] = index;
6.275 + }
6.276 + data.pop_back();
6.277 + }
6.278 +
6.279 + public:
6.280 +
6.281 + /// \brief Insert an item into the heap with the given priority.
6.282 + ///
6.283 + /// Adds \c i to the heap with priority \c p.
6.284 + /// \param i The item to insert.
6.285 + /// \param p The priority of the item.
6.286 + void push(const Item &i, const Prio &p) {
6.287 + int n = data.size();
6.288 + _iim.set(i, n);
6.289 + data.push_back(RadixItem(i, p));
6.290 + while (lower(boxes.size() - 1, p)) {
6.291 + extend();
6.292 + }
6.293 + int box = findDown(boxes.size() - 1, p);
6.294 + insert(box, n);
6.295 + }
6.296 +
6.297 + /// \brief Returns the item with minimum priority.
6.298 + ///
6.299 + /// This method returns the item with minimum priority.
6.300 + /// \pre The heap must be nonempty.
6.301 + Item top() const {
6.302 + const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
6.303 + return data[boxes[0].first].item;
6.304 + }
6.305 +
6.306 + /// \brief Returns the minimum priority.
6.307 + ///
6.308 + /// It returns the minimum priority.
6.309 + /// \pre The heap must be nonempty.
6.310 + Prio prio() const {
6.311 + const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
6.312 + return data[boxes[0].first].prio;
6.313 + }
6.314 +
6.315 + /// \brief Deletes the item with minimum priority.
6.316 + ///
6.317 + /// This method deletes the item with minimum priority.
6.318 + /// \pre The heap must be non-empty.
6.319 + void pop() {
6.320 + moveDown();
6.321 + int index = boxes[0].first;
6.322 + _iim[data[index].item] = POST_HEAP;
6.323 + remove(index);
6.324 + relocate_last(index);
6.325 + }
6.326 +
6.327 + /// \brief Deletes \c i from the heap.
6.328 + ///
6.329 + /// This method deletes item \c i from the heap, if \c i was
6.330 + /// already stored in the heap.
6.331 + /// \param i The item to erase.
6.332 + void erase(const Item &i) {
6.333 + int index = _iim[i];
6.334 + _iim[i] = POST_HEAP;
6.335 + remove(index);
6.336 + relocate_last(index);
6.337 + }
6.338 +
6.339 + /// \brief Returns the priority of \c i.
6.340 + ///
6.341 + /// This function returns the priority of item \c i.
6.342 + /// \pre \c i must be in the heap.
6.343 + /// \param i The item.
6.344 + Prio operator[](const Item &i) const {
6.345 + int idx = _iim[i];
6.346 + return data[idx].prio;
6.347 + }
6.348 +
6.349 + /// \brief \c i gets to the heap with priority \c p independently
6.350 + /// if \c i was already there.
6.351 + ///
6.352 + /// This method calls \ref push(\c i, \c p) if \c i is not stored
6.353 + /// in the heap and sets the priority of \c i to \c p otherwise.
6.354 + /// It may throw an \e UnderFlowPriorityException.
6.355 + /// \param i The item.
6.356 + /// \param p The priority.
6.357 + void set(const Item &i, const Prio &p) {
6.358 + int idx = _iim[i];
6.359 + if( idx < 0 ) {
6.360 + push(i, p);
6.361 + }
6.362 + else if( p >= data[idx].prio ) {
6.363 + data[idx].prio = p;
6.364 + bubble_up(idx);
6.365 + } else {
6.366 + data[idx].prio = p;
6.367 + bubble_down(idx);
6.368 + }
6.369 + }
6.370 +
6.371 +
6.372 + /// \brief Decreases the priority of \c i to \c p.
6.373 + ///
6.374 + /// This method decreases the priority of item \c i to \c p.
6.375 + /// \pre \c i must be stored in the heap with priority at least \c p, and
6.376 + /// \c should be greater or equal to the last removed item's priority.
6.377 + /// \param i The item.
6.378 + /// \param p The priority.
6.379 + void decrease(const Item &i, const Prio &p) {
6.380 + int idx = _iim[i];
6.381 + data[idx].prio = p;
6.382 + bubble_down(idx);
6.383 + }
6.384 +
6.385 + /// \brief Increases the priority of \c i to \c p.
6.386 + ///
6.387 + /// This method sets the priority of item \c i to \c p.
6.388 + /// \pre \c i must be stored in the heap with priority at most \c p
6.389 + /// \param i The item.
6.390 + /// \param p The priority.
6.391 + void increase(const Item &i, const Prio &p) {
6.392 + int idx = _iim[i];
6.393 + data[idx].prio = p;
6.394 + bubble_up(idx);
6.395 + }
6.396 +
6.397 + /// \brief Returns if \c item is in, has already been in, or has
6.398 + /// never been in the heap.
6.399 + ///
6.400 + /// This method returns PRE_HEAP if \c item has never been in the
6.401 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
6.402 + /// otherwise. In the latter case it is possible that \c item will
6.403 + /// get back to the heap again.
6.404 + /// \param i The item.
6.405 + State state(const Item &i) const {
6.406 + int s = _iim[i];
6.407 + if( s >= 0 ) s = 0;
6.408 + return State(s);
6.409 + }
6.410 +
6.411 + /// \brief Sets the state of the \c item in the heap.
6.412 + ///
6.413 + /// Sets the state of the \c item in the heap. It can be used to
6.414 + /// manually clear the heap when it is important to achive the
6.415 + /// better time complexity.
6.416 + /// \param i The item.
6.417 + /// \param st The state. It should not be \c IN_HEAP.
6.418 + void state(const Item& i, State st) {
6.419 + switch (st) {
6.420 + case POST_HEAP:
6.421 + case PRE_HEAP:
6.422 + if (state(i) == IN_HEAP) {
6.423 + erase(i);
6.424 + }
6.425 + _iim[i] = st;
6.426 + break;
6.427 + case IN_HEAP:
6.428 + break;
6.429 + }
6.430 + }
6.431 +
6.432 + }; // class RadixHeap
6.433 +
6.434 +} // namespace lemon
6.435 +
6.436 +#endif // LEMON_RADIX_HEAP_H
7.1 --- a/test/heap_test.cc Thu Jul 23 18:13:59 2009 +0200
7.2 +++ b/test/heap_test.cc Sun Aug 02 13:44:45 2009 +0200
7.3 @@ -31,6 +31,9 @@
7.4 #include <lemon/maps.h>
7.5
7.6 #include <lemon/bin_heap.h>
7.7 +#include <lemon/fib_heap.h>
7.8 +#include <lemon/radix_heap.h>
7.9 +#include <lemon/bucket_heap.h>
7.10
7.11 #include "test_tools.h"
7.12
7.13 @@ -183,5 +186,39 @@
7.14 dijkstraHeapTest<NodeHeap>(digraph, length, source);
7.15 }
7.16
7.17 + {
7.18 + typedef FibHeap<Prio, ItemIntMap> IntHeap;
7.19 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
7.20 + heapSortTest<IntHeap>();
7.21 + heapIncreaseTest<IntHeap>();
7.22 +
7.23 + typedef FibHeap<Prio, IntNodeMap > NodeHeap;
7.24 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
7.25 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
7.26 + }
7.27 +
7.28 + {
7.29 + typedef RadixHeap<ItemIntMap> IntHeap;
7.30 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
7.31 + heapSortTest<IntHeap>();
7.32 + heapIncreaseTest<IntHeap>();
7.33 +
7.34 + typedef RadixHeap<IntNodeMap > NodeHeap;
7.35 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
7.36 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
7.37 + }
7.38 +
7.39 + {
7.40 + typedef BucketHeap<ItemIntMap> IntHeap;
7.41 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
7.42 + heapSortTest<IntHeap>();
7.43 + heapIncreaseTest<IntHeap>();
7.44 +
7.45 + typedef BucketHeap<IntNodeMap > NodeHeap;
7.46 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
7.47 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
7.48 + }
7.49 +
7.50 +
7.51 return 0;
7.52 }
8.1 --- a/test/maps_test.cc Thu Jul 23 18:13:59 2009 +0200
8.2 +++ b/test/maps_test.cc Sun Aug 02 13:44:45 2009 +0200
8.3 @@ -23,6 +23,7 @@
8.4 #include <lemon/concepts/maps.h>
8.5 #include <lemon/maps.h>
8.6 #include <lemon/list_graph.h>
8.7 +#include <lemon/smart_graph.h>
8.8
8.9 #include "test_tools.h"
8.10
8.11 @@ -494,5 +495,192 @@
8.12 it == map.endValue(), "Wrong value iterator");
8.13 }
8.14
8.15 + // Iterable bool map
8.16 + {
8.17 + typedef SmartGraph Graph;
8.18 + typedef SmartGraph::Node Item;
8.19 +
8.20 + typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm;
8.21 + checkConcept<ReferenceMap<Item, bool, bool&, const bool&>, Ibm>();
8.22 +
8.23 + const int num = 10;
8.24 + Graph g;
8.25 + std::vector<Item> items;
8.26 + for (int i = 0; i < num; ++i) {
8.27 + items.push_back(g.addNode());
8.28 + }
8.29 +
8.30 + Ibm map1(g, true);
8.31 + int n = 0;
8.32 + for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
8.33 + check(map1[static_cast<Item>(it)], "Wrong TrueIt");
8.34 + ++n;
8.35 + }
8.36 + check(n == num, "Wrong number");
8.37 +
8.38 + n = 0;
8.39 + for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
8.40 + check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
8.41 + ++n;
8.42 + }
8.43 + check(n == num, "Wrong number");
8.44 + check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt");
8.45 + check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false");
8.46 +
8.47 + map1[items[5]] = true;
8.48 +
8.49 + n = 0;
8.50 + for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
8.51 + check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
8.52 + ++n;
8.53 + }
8.54 + check(n == num, "Wrong number");
8.55 +
8.56 + map1[items[num / 2]] = false;
8.57 + check(map1[items[num / 2]] == false, "Wrong map value");
8.58 +
8.59 + n = 0;
8.60 + for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
8.61 + check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
8.62 + ++n;
8.63 + }
8.64 + check(n == num - 1, "Wrong number");
8.65 +
8.66 + n = 0;
8.67 + for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
8.68 + check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
8.69 + ++n;
8.70 + }
8.71 + check(n == 1, "Wrong number");
8.72 +
8.73 + map1[items[0]] = false;
8.74 + check(map1[items[0]] == false, "Wrong map value");
8.75 +
8.76 + map1[items[num - 1]] = false;
8.77 + check(map1[items[num - 1]] == false, "Wrong map value");
8.78 +
8.79 + n = 0;
8.80 + for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
8.81 + check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
8.82 + ++n;
8.83 + }
8.84 + check(n == num - 3, "Wrong number");
8.85 + check(map1.trueNum() == num - 3, "Wrong number");
8.86 +
8.87 + n = 0;
8.88 + for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
8.89 + check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
8.90 + ++n;
8.91 + }
8.92 + check(n == 3, "Wrong number");
8.93 + check(map1.falseNum() == 3, "Wrong number");
8.94 + }
8.95 +
8.96 + // Iterable int map
8.97 + {
8.98 + typedef SmartGraph Graph;
8.99 + typedef SmartGraph::Node Item;
8.100 + typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim;
8.101 +
8.102 + checkConcept<ReferenceMap<Item, int, int&, const int&>, Iim>();
8.103 +
8.104 + const int num = 10;
8.105 + Graph g;
8.106 + std::vector<Item> items;
8.107 + for (int i = 0; i < num; ++i) {
8.108 + items.push_back(g.addNode());
8.109 + }
8.110 +
8.111 + Iim map1(g);
8.112 + check(map1.size() == 0, "Wrong size");
8.113 +
8.114 + for (int i = 0; i < num; ++i) {
8.115 + map1[items[i]] = i;
8.116 + }
8.117 + check(map1.size() == num, "Wrong size");
8.118 +
8.119 + for (int i = 0; i < num; ++i) {
8.120 + Iim::ItemIt it(map1, i);
8.121 + check(static_cast<Item>(it) == items[i], "Wrong value");
8.122 + ++it;
8.123 + check(static_cast<Item>(it) == INVALID, "Wrong value");
8.124 + }
8.125 +
8.126 + for (int i = 0; i < num; ++i) {
8.127 + map1[items[i]] = i % 2;
8.128 + }
8.129 + check(map1.size() == 2, "Wrong size");
8.130 +
8.131 + int n = 0;
8.132 + for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) {
8.133 + check(map1[static_cast<Item>(it)] == 0, "Wrong value");
8.134 + ++n;
8.135 + }
8.136 + check(n == (num + 1) / 2, "Wrong number");
8.137 +
8.138 + for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) {
8.139 + check(map1[static_cast<Item>(it)] == 1, "Wrong value");
8.140 + ++n;
8.141 + }
8.142 + check(n == num, "Wrong number");
8.143 +
8.144 + }
8.145 +
8.146 + // Iterable value map
8.147 + {
8.148 + typedef SmartGraph Graph;
8.149 + typedef SmartGraph::Node Item;
8.150 + typedef IterableValueMap<SmartGraph, SmartGraph::Node, double> Ivm;
8.151 +
8.152 + checkConcept<ReadWriteMap<Item, double>, Ivm>();
8.153 +
8.154 + const int num = 10;
8.155 + Graph g;
8.156 + std::vector<Item> items;
8.157 + for (int i = 0; i < num; ++i) {
8.158 + items.push_back(g.addNode());
8.159 + }
8.160 +
8.161 + Ivm map1(g, 0.0);
8.162 + check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size");
8.163 + check(*map1.beginValue() == 0.0, "Wrong value");
8.164 +
8.165 + for (int i = 0; i < num; ++i) {
8.166 + map1.set(items[i], static_cast<double>(i));
8.167 + }
8.168 + check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size");
8.169 +
8.170 + for (int i = 0; i < num; ++i) {
8.171 + Ivm::ItemIt it(map1, static_cast<double>(i));
8.172 + check(static_cast<Item>(it) == items[i], "Wrong value");
8.173 + ++it;
8.174 + check(static_cast<Item>(it) == INVALID, "Wrong value");
8.175 + }
8.176 +
8.177 + for (Ivm::ValueIterator vit = map1.beginValue();
8.178 + vit != map1.endValue(); ++vit) {
8.179 + check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,
8.180 + "Wrong ValueIterator");
8.181 + }
8.182 +
8.183 + for (int i = 0; i < num; ++i) {
8.184 + map1.set(items[i], static_cast<double>(i % 2));
8.185 + }
8.186 + check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size");
8.187 +
8.188 + int n = 0;
8.189 + for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) {
8.190 + check(map1[static_cast<Item>(it)] == 0.0, "Wrong value");
8.191 + ++n;
8.192 + }
8.193 + check(n == (num + 1) / 2, "Wrong number");
8.194 +
8.195 + for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) {
8.196 + check(map1[static_cast<Item>(it)] == 1.0, "Wrong value");
8.197 + ++n;
8.198 + }
8.199 + check(n == num, "Wrong number");
8.200 +
8.201 + }
8.202 return 0;
8.203 }