1.1 --- a/lemon/iterable_maps.h Mon Jan 30 09:37:41 2006 +0000
1.2 +++ b/lemon/iterable_maps.h Tue Jan 31 19:33:48 2006 +0000
1.3 @@ -16,7 +16,11 @@
1.4
1.5 #include <lemon/traits.h>
1.6 #include <lemon/invalid.h>
1.7 +
1.8 #include <vector>
1.9 +#include <map>
1.10 +
1.11 +#include <iterator>
1.12 #include <limits>
1.13
1.14 ///\ingroup maps
1.15 @@ -29,7 +33,7 @@
1.16
1.17 namespace lemon {
1.18
1.19 - ///\ingroup maps
1.20 + ///\ingroup graph_maps
1.21 ///
1.22 /// \brief Dynamic iterable bool map.
1.23 ///
1.24 @@ -45,35 +49,35 @@
1.25 : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Parent {
1.26 private:
1.27 typedef _Graph Graph;
1.28 - typedef _Item Item;
1.29
1.30 - typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
1.31 - typedef typename ItemSetTraits<Graph, Item>
1.32 + typedef typename ItemSetTraits<Graph, _Item>::ItemIt KeyIt;
1.33 + typedef typename ItemSetTraits<Graph, _Item>
1.34 ::template Map<int>::Parent Parent;
1.35
1.36 - std::vector<Item> array;
1.37 + std::vector<_Item> array;
1.38 int sep;
1.39
1.40 const Graph& graph;
1.41
1.42 - private:
1.43 -
1.44 - int position(const Item& item) const {
1.45 - return Parent::operator[](item);
1.46 - }
1.47 -
1.48 public:
1.49
1.50 /// Indicates that the map if reference map.
1.51 typedef True ReferenceMapTag;
1.52
1.53 /// The key type
1.54 - typedef Item Key;
1.55 + typedef _Item Key;
1.56 /// The value type
1.57 typedef bool Value;
1.58 /// The const reference type.
1.59 typedef const Value& ConstReference;
1.60
1.61 + private:
1.62 +
1.63 + int position(const Key& key) const {
1.64 + return Parent::operator[](key);
1.65 + }
1.66 +
1.67 + public:
1.68
1.69 /// \brief Refernce to the value of the map.
1.70 ///
1.71 @@ -121,7 +125,7 @@
1.72 /// Constructor of the Map with a default value.
1.73 IterableBoolMap(const Graph& _graph, bool def = false)
1.74 : Parent(_graph), graph(_graph) {
1.75 - for (ItemIt it(graph); it != INVALID; ++it) {
1.76 + for (KeyIt it(graph); it != INVALID; ++it) {
1.77 Parent::set(it, array.size());
1.78 array.push_back(it);
1.79 }
1.80 @@ -131,51 +135,51 @@
1.81 /// \brief Const subscript operator of the map.
1.82 ///
1.83 /// Const subscript operator of the map.
1.84 - bool operator[](const Item& item) const {
1.85 - return position(item) < sep;
1.86 + bool operator[](const Key& key) const {
1.87 + return position(key) < sep;
1.88 }
1.89
1.90 /// \brief Subscript operator of the map.
1.91 ///
1.92 /// Subscript operator of the map.
1.93 - Reference operator[](const Item& item) {
1.94 - return Reference(*this, item);
1.95 + Reference operator[](const Key& key) {
1.96 + return Reference(*this, key);
1.97 }
1.98
1.99 /// \brief Set operation of the map.
1.100 ///
1.101 /// Set operation of the map.
1.102 - void set(const Item& item, bool value) {
1.103 - int pos = position(item);
1.104 + void set(const Key& key, bool value) {
1.105 + int pos = position(key);
1.106 if (value) {
1.107 if (pos < sep) return;
1.108 - Item tmp = array[sep];
1.109 - array[sep] = item;
1.110 - Parent::set(item, sep);
1.111 + Key tmp = array[sep];
1.112 + array[sep] = key;
1.113 + Parent::set(key, sep);
1.114 array[pos] = tmp;
1.115 Parent::set(tmp, pos);
1.116 ++sep;
1.117 } else {
1.118 if (pos >= sep) return;
1.119 --sep;
1.120 - Item tmp = array[sep];
1.121 - array[sep] = item;
1.122 - Parent::set(item, sep);
1.123 + Key tmp = array[sep];
1.124 + array[sep] = key;
1.125 + Parent::set(key, sep);
1.126 array[pos] = tmp;
1.127 Parent::set(tmp, pos);
1.128 }
1.129 }
1.130
1.131 - /// \brief Returns the number of the items mapped to true.
1.132 + /// \brief Returns the number of the keys mapped to true.
1.133 ///
1.134 - /// Returns the number of the items mapped to true.
1.135 + /// Returns the number of the keys mapped to true.
1.136 int trueNum() const {
1.137 return sep;
1.138 }
1.139
1.140 - /// \brief Returns the number of the items mapped to false.
1.141 + /// \brief Returns the number of the keys mapped to false.
1.142 ///
1.143 - /// Returns the number of the items mapped to false.
1.144 + /// Returns the number of the keys mapped to false.
1.145 int falseNum() const {
1.146 return array.size() - sep;
1.147 }
1.148 @@ -184,12 +188,12 @@
1.149 ///
1.150 /// Iterator for the keys mapped to true. It works
1.151 /// like a graph item iterator in the map, it can be converted
1.152 - /// the item type of the map, incremented with \c ++ operator, and
1.153 - /// if the iterator leave the last valid item it will be equal to
1.154 + /// the key type of the map, incremented with \c ++ operator, and
1.155 + /// if the iterator leave the last valid key it will be equal to
1.156 /// \c INVALID.
1.157 - class TrueIt : public Item {
1.158 + class TrueIt : public Key {
1.159 public:
1.160 - typedef Item Parent;
1.161 + typedef Key Parent;
1.162
1.163 /// \brief Creates an iterator.
1.164 ///
1.165 @@ -202,7 +206,7 @@
1.166
1.167 /// \brief Invalid constructor \& conversion.
1.168 ///
1.169 - /// This constructor initializes the item to be invalid.
1.170 + /// This constructor initializes the key to be invalid.
1.171 /// \sa Invalid for more details.
1.172 TrueIt(Invalid) : Parent(INVALID), map(0) {}
1.173
1.174 @@ -224,12 +228,12 @@
1.175 ///
1.176 /// Iterator for the keys mapped to false. It works
1.177 /// like a graph item iterator in the map, it can be converted
1.178 - /// the item type of the map, incremented with \c ++ operator, and
1.179 - /// if the iterator leave the last valid item it will be equal to
1.180 + /// the key type of the map, incremented with \c ++ operator, and
1.181 + /// if the iterator leave the last valid key it will be equal to
1.182 /// \c INVALID.
1.183 - class FalseIt : public Item {
1.184 + class FalseIt : public Key {
1.185 public:
1.186 - typedef Item Parent;
1.187 + typedef Key Parent;
1.188
1.189 /// \brief Creates an iterator.
1.190 ///
1.191 @@ -237,12 +241,12 @@
1.192 /// keys which mapped to false.
1.193 /// \param map The IterableIntMap
1.194 FalseIt(const IterableBoolMap& _map)
1.195 - : Parent(_map.sep < _map.array.size() ? _map.array.back() : INVALID),
1.196 - map(&_map) {}
1.197 + : Parent(_map.sep < (int)_map.array.size() ?
1.198 + _map.array.back() : INVALID), map(&_map) {}
1.199
1.200 /// \brief Invalid constructor \& conversion.
1.201 ///
1.202 - /// This constructor initializes the item to be invalid.
1.203 + /// This constructor initializes the key to be invalid.
1.204 /// \sa Invalid for more details.
1.205 FalseIt(Invalid) : Parent(INVALID), map(0) {}
1.206
1.207 @@ -259,24 +263,66 @@
1.208 const IterableBoolMap* map;
1.209 };
1.210
1.211 + /// \brief Iterator for the keys mapped to a given value.
1.212 + ///
1.213 + /// Iterator for the keys mapped to a given value. It works
1.214 + /// like a graph item iterator in the map, it can be converted
1.215 + /// the key type of the map, incremented with \c ++ operator, and
1.216 + /// if the iterator leave the last valid key it will be equal to
1.217 + /// \c INVALID.
1.218 + class ItemIt : public Key {
1.219 + public:
1.220 + typedef Key Parent;
1.221 +
1.222 + /// \brief Creates an iterator.
1.223 + ///
1.224 + /// Creates an iterator. It iterates on the
1.225 + /// keys which mapped to false.
1.226 + /// \param map The IterableIntMap
1.227 + /// \param value Which elements should be iterated.
1.228 + ItemIt(const IterableBoolMap& _map, bool value)
1.229 + : Parent(value ? (_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID) :
1.230 + (_map.sep < (int)_map.array.size() ?
1.231 + _map.array.back() : INVALID)), map(&_map) {}
1.232 +
1.233 + /// \brief Invalid constructor \& conversion.
1.234 + ///
1.235 + /// This constructor initializes the key to be invalid.
1.236 + /// \sa Invalid for more details.
1.237 + ItemIt(Invalid) : Parent(INVALID), map(0) {}
1.238 +
1.239 + /// \brief Increment operator.
1.240 + ///
1.241 + /// Increment Operator.
1.242 + ItemIt& operator++() {
1.243 + int pos = map->position(*this);
1.244 + int sep = pos >= map->sep ? map->sep : 0;
1.245 + Parent::operator=(pos > sep ? map->array[pos - 1] : INVALID);
1.246 + return *this;
1.247 + }
1.248 +
1.249 + private:
1.250 + const IterableBoolMap* map;
1.251 + };
1.252 +
1.253 protected:
1.254
1.255 - virtual void add(const Item& item) {
1.256 - Parent::add(item);
1.257 - Parent::set(item, array.size());
1.258 - array.push_back(item);
1.259 + virtual void add(const Key& key) {
1.260 + Parent::add(key);
1.261 + Parent::set(key, array.size());
1.262 + array.push_back(key);
1.263 }
1.264
1.265 - virtual void add(const std::vector<Item>& items) {
1.266 - Parent::add(items);
1.267 - for (int i = 0; i < (int)items.size(); ++i) {
1.268 - Parent::set(items[i], array.size());
1.269 - array.push_back(items[i]);
1.270 + virtual void add(const std::vector<Key>& keys) {
1.271 + Parent::add(keys);
1.272 + for (int i = 0; i < (int)keys.size(); ++i) {
1.273 + Parent::set(keys[i], array.size());
1.274 + array.push_back(keys[i]);
1.275 }
1.276 }
1.277
1.278 - virtual void erase(const Item& item) {
1.279 - int pos = position(item);
1.280 + virtual void erase(const Key& key) {
1.281 + int pos = position(key);
1.282 if (pos < sep) {
1.283 --sep;
1.284 Parent::set(array[sep], pos);
1.285 @@ -289,12 +335,12 @@
1.286 array[pos] = array.back();
1.287 array.pop_back();
1.288 }
1.289 - Parent::erase(item);
1.290 + Parent::erase(key);
1.291 }
1.292
1.293 - virtual void erase(const std::vector<Item>& items) {
1.294 - for (int i = 0; i < (int)items.size(); ++i) {
1.295 - int pos = position(items[i]);
1.296 + virtual void erase(const std::vector<Key>& keys) {
1.297 + for (int i = 0; i < (int)keys.size(); ++i) {
1.298 + int pos = position(keys[i]);
1.299 if (pos < sep) {
1.300 --sep;
1.301 Parent::set(array[sep], pos);
1.302 @@ -308,12 +354,12 @@
1.303 array.pop_back();
1.304 }
1.305 }
1.306 - Parent::erase(items);
1.307 + Parent::erase(keys);
1.308 }
1.309
1.310 virtual void build() {
1.311 Parent::build();
1.312 - for (ItemIt it(graph); it != INVALID; ++it) {
1.313 + for (KeyIt it(graph); it != INVALID; ++it) {
1.314 Parent::set(it, array.size());
1.315 array.push_back(it);
1.316 }
1.317 @@ -339,7 +385,7 @@
1.318 };
1.319 }
1.320
1.321 - ///\ingroup maps
1.322 + ///\ingroup graph_maps
1.323 ///
1.324 /// \brief Dynamic iterable integer map.
1.325 ///
1.326 @@ -514,8 +560,8 @@
1.327 /// \brief Gives back the maximal value plus one.
1.328 ///
1.329 /// Gives back the maximal value plus one.
1.330 - int size() const {
1.331 - return (int)first.size();
1.332 + unsigned int size() const {
1.333 + return first.size();
1.334 }
1.335
1.336 /// \brief Set operation of the map.
1.337 @@ -594,7 +640,7 @@
1.338 }
1.339
1.340 virtual void erase(const std::vector<Key>& keys) {
1.341 - for (int i = 0; i < keys.size(); ++i) {
1.342 + for (int i = 0; i < (int)keys.size(); ++i) {
1.343 unlace(keys[i]);
1.344 }
1.345 Parent::erase(keys);
1.346 @@ -609,5 +655,240 @@
1.347 std::vector<_Item> first;
1.348 };
1.349
1.350 + namespace _iterable_maps_bits {
1.351 + template <typename Item, typename Value>
1.352 + struct IterableValueMapNode {
1.353 + IterableValueMapNode(Value _value = Value()) : value(_value) {}
1.354 + Item prev, next;
1.355 + Value value;
1.356 + };
1.357 + }
1.358 +
1.359 + ///\ingroup graph_maps
1.360 + ///
1.361 + /// \brief Dynamic iterable map for comparable values.
1.362 + ///
1.363 + /// This class provides a special graph map type which can store
1.364 + /// for each graph item(node, edge, etc.) a value. For each
1.365 + /// value it is possible to iterate on the keys which mapped to the
1.366 + /// given value. The type stores for each value a linked list with
1.367 + /// the items which mapped to the value, and the values are stored
1.368 + /// in balanced binary tree. The values of the map can be accessed
1.369 + /// with stl compatible forward iterator.
1.370 + ///
1.371 + /// This type is not reference map so it cannot be modified with
1.372 + /// the subscription operator.
1.373 + ///
1.374 + /// \see InvertableMap
1.375 + ///
1.376 + /// \param _Graph The graph type.
1.377 + /// \param _Item One of the graph's item type, the key of the map.
1.378 + /// \param _Value Any comparable value type.
1.379 + template <typename _Graph, typename _Item, typename _Value>
1.380 + class IterableValueMap : protected ItemSetTraits<_Graph, _Item>
1.381 + ::template Map<_iterable_maps_bits::IterableValueMapNode<_Item, _Value> >
1.382 + ::Parent {
1.383 + public:
1.384 + typedef typename ItemSetTraits<_Graph, _Item>
1.385 + ::template Map<_iterable_maps_bits::IterableValueMapNode<_Item, _Value> >
1.386 + ::Parent Parent;
1.387 +
1.388 + /// The key type
1.389 + typedef _Item Key;
1.390 + /// The value type
1.391 + typedef _Value Value;
1.392 + /// The graph type
1.393 + typedef _Graph Graph;
1.394 +
1.395 + /// \brief Constructor of the Map with a given value.
1.396 + ///
1.397 + /// Constructor of the Map with a given value.
1.398 + explicit IterableValueMap(const Graph& graph,
1.399 + const Value& value = Value())
1.400 + : Parent(graph, _iterable_maps_bits::IterableValueMapNode<_Item,
1.401 + _Value>(value)) {
1.402 + for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
1.403 + lace(it);
1.404 + }
1.405 + }
1.406 +
1.407 + private:
1.408 +
1.409 + void unlace(const Key& key) {
1.410 + typename Parent::Value& node = Parent::operator[](key);
1.411 + if (node.prev != INVALID) {
1.412 + Parent::operator[](node.prev).next = node.next;
1.413 + } else {
1.414 + if (node.next != INVALID) {
1.415 + first[node.value] = node.next;
1.416 + } else {
1.417 + first.erase(node.value);
1.418 + }
1.419 + }
1.420 + if (node.next != INVALID) {
1.421 + Parent::operator[](node.next).prev = node.prev;
1.422 + }
1.423 + }
1.424 +
1.425 + void lace(const Key& key) {
1.426 + typename Parent::Value& node = Parent::operator[](key);
1.427 + typename std::map<Value, Key>::iterator it = first.find(node.value);
1.428 + if (it == first.end()) {
1.429 + node.prev = node.next = INVALID;
1.430 + if (node.next != INVALID) {
1.431 + Parent::operator[](node.next).prev = key;
1.432 + }
1.433 + first.insert(make_pair(node.value, key));
1.434 + } else {
1.435 + node.prev = INVALID;
1.436 + node.next = it->second;
1.437 + if (node.next != INVALID) {
1.438 + Parent::operator[](node.next).prev = key;
1.439 + }
1.440 + it->second = key;
1.441 + }
1.442 + }
1.443 +
1.444 + public:
1.445 +
1.446 + /// \brief Forward iterator for values.
1.447 + ///
1.448 + /// This iterator is an stl compatible forward
1.449 + /// iterator on the values of the map. The values can
1.450 + /// be accessed in the [beginValue, endValue) range.
1.451 + ///
1.452 + class ValueIterator
1.453 + : public std::iterator<std::forward_iterator_tag, Value> {
1.454 + friend class IterableValueMap;
1.455 + private:
1.456 + ValueIterator(typename std::map<Value, Key>::const_iterator _it)
1.457 + : it(_it) {}
1.458 + public:
1.459 +
1.460 + ValueIterator() {}
1.461 +
1.462 + ValueIterator& operator++() { ++it; return *this; }
1.463 + ValueIterator operator++(int) {
1.464 + ValueIterator tmp(*this);
1.465 + operator++();
1.466 + return tmp;
1.467 + }
1.468 +
1.469 + const Value& operator*() const { return it->first; }
1.470 + const Value* operator->() const { return &(it->first); }
1.471 +
1.472 + bool operator==(ValueIterator jt) const { return it == jt.it; }
1.473 + bool operator!=(ValueIterator jt) const { return it != jt.it; }
1.474 +
1.475 + private:
1.476 + typename std::map<Value, Key>::const_iterator it;
1.477 + };
1.478 +
1.479 + /// \brief Returns an iterator to the first value.
1.480 + ///
1.481 + /// Returns an stl compatible iterator to the
1.482 + /// first value of the map. The values of the
1.483 + /// map can be accessed in the [beginValue, endValue)
1.484 + /// range.
1.485 + ValueIterator beginValue() const {
1.486 + return ValueIterator(first.begin());
1.487 + }
1.488 +
1.489 + /// \brief Returns an iterator after the last value.
1.490 + ///
1.491 + /// Returns an stl compatible iterator after the
1.492 + /// last value of the map. The values of the
1.493 + /// map can be accessed in the [beginValue, endValue)
1.494 + /// range.
1.495 + ValueIterator endValue() const {
1.496 + return ValueIterator(first.end());
1.497 + }
1.498 +
1.499 + /// \brief Set operation of the map.
1.500 + ///
1.501 + /// Set operation of the map.
1.502 + void set(const Key& key, const Value& value) {
1.503 + unlace(key);
1.504 + Parent::operator[](key).value = value;
1.505 + lace(key);
1.506 + }
1.507 +
1.508 + /// \brief Const subscript operator of the map.
1.509 + ///
1.510 + /// Const subscript operator of the map.
1.511 + const Value& operator[](const Key& key) const {
1.512 + return Parent::operator[](key).value;
1.513 + }
1.514 +
1.515 + /// \brief Iterator for the keys with the same value.
1.516 + ///
1.517 + /// Iterator for the keys with the same value. It works
1.518 + /// like a graph item iterator in the map, it can be converted
1.519 + /// the item type of the map, incremented with \c ++ operator, and
1.520 + /// if the iterator leave the last valid item it will be equal to
1.521 + /// \c INVALID.
1.522 + class ItemIt : public _Item {
1.523 + public:
1.524 + typedef _Item Parent;
1.525 +
1.526 + /// \brief Invalid constructor \& conversion.
1.527 + ///
1.528 + /// This constructor initializes the item to be invalid.
1.529 + /// \sa Invalid for more details.
1.530 + ItemIt(Invalid) : Parent(INVALID), _map(0) {}
1.531 +
1.532 + /// \brief Creates an iterator with a value.
1.533 + ///
1.534 + /// Creates an iterator with a value. It iterates on the
1.535 + /// keys which have the given value.
1.536 + /// \param map The IterableValueMap
1.537 + /// \param value The value
1.538 + ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
1.539 + typename std::map<Value, Key>::const_iterator it =
1.540 + map.first.find(value);
1.541 + if (it == map.first.end()) {
1.542 + Parent::operator=(INVALID);
1.543 + } else {
1.544 + Parent::operator=(it->second);
1.545 + }
1.546 + }
1.547 +
1.548 + /// \brief Increment operator.
1.549 + ///
1.550 + /// Increment Operator.
1.551 + ItemIt& operator++() {
1.552 + Parent::operator=(_map->IterableValueMap::Parent::
1.553 + operator[](static_cast<Parent&>(*this)).next);
1.554 + return *this;
1.555 + }
1.556 +
1.557 +
1.558 + private:
1.559 + const IterableValueMap* _map;
1.560 + };
1.561 +
1.562 + protected:
1.563 +
1.564 + virtual void erase(const Key& key) {
1.565 + unlace(key);
1.566 + Parent::erase(key);
1.567 + }
1.568 +
1.569 + virtual void erase(const std::vector<Key>& keys) {
1.570 + for (int i = 0; i < (int)keys.size(); ++i) {
1.571 + unlace(keys[i]);
1.572 + }
1.573 + Parent::erase(keys);
1.574 + }
1.575 +
1.576 + virtual void clear() {
1.577 + first.clear();
1.578 + Parent::clear();
1.579 + }
1.580 +
1.581 + private:
1.582 + std::map<Value, Key> first;
1.583 + };
1.584 +
1.585 /// @}
1.586 }