1.1 --- a/lemon/graph_utils.h Mon Jan 30 09:37:41 2006 +0000
1.2 +++ b/lemon/graph_utils.h Tue Jan 31 19:33:48 2006 +0000
1.3 @@ -886,9 +886,15 @@
1.4 /// The InvertableMap wraps an arbitrary ReadWriteMap
1.5 /// and if a key is set to a new value then store it
1.6 /// in the inverse map.
1.7 + ///
1.8 + /// The values of the map can be accessed
1.9 + /// with stl compatible forward iterator.
1.10 + ///
1.11 /// \param _Graph The graph type.
1.12 /// \param _Item The item type of the graph.
1.13 /// \param _Value The value type of the map.
1.14 + ///
1.15 + /// \see IterableValueMap
1.16 #ifndef DOXYGEN
1.17 /// \param _Map A ReadWriteMap mapping from the item type to integer.
1.18 template <
1.19 @@ -899,22 +905,83 @@
1.20 template <typename _Graph, typename _Item, typename _Value>
1.21 #endif
1.22 class InvertableMap : protected _Map {
1.23 -
1.24 public:
1.25 -
1.26 - typedef _Map Map;
1.27 - typedef _Graph Graph;
1.28
1.29 /// The key type of InvertableMap (Node, Edge, UEdge).
1.30 typedef typename _Map::Key Key;
1.31 /// The value type of the InvertableMap.
1.32 typedef typename _Map::Value Value;
1.33
1.34 + private:
1.35 +
1.36 + typedef _Map Map;
1.37 + typedef _Graph Graph;
1.38 +
1.39 + typedef std::map<Value, Key> Container;
1.40 + Container invMap;
1.41 +
1.42 + public:
1.43 +
1.44 +
1.45 +
1.46 /// \brief Constructor.
1.47 ///
1.48 /// Construct a new InvertableMap for the graph.
1.49 ///
1.50 InvertableMap(const Graph& graph) : Map(graph) {}
1.51 +
1.52 + /// \brief Forward iterator for values.
1.53 + ///
1.54 + /// This iterator is an stl compatible forward
1.55 + /// iterator on the values of the map. The values can
1.56 + /// be accessed in the [beginValue, endValue) range.
1.57 + ///
1.58 + class ValueIterator
1.59 + : public std::iterator<std::forward_iterator_tag, Value> {
1.60 + friend class InvertableMap;
1.61 + private:
1.62 + ValueIterator(typename Container::const_iterator _it)
1.63 + : it(_it) {}
1.64 + public:
1.65 +
1.66 + ValueIterator() {}
1.67 +
1.68 + ValueIterator& operator++() { ++it; return *this; }
1.69 + ValueIterator operator++(int) {
1.70 + ValueIterator tmp(*this);
1.71 + operator++();
1.72 + return tmp;
1.73 + }
1.74 +
1.75 + const Value& operator*() const { return it->first; }
1.76 + const Value* operator->() const { return &(it->first); }
1.77 +
1.78 + bool operator==(ValueIterator jt) const { return it == jt.it; }
1.79 + bool operator!=(ValueIterator jt) const { return it != jt.it; }
1.80 +
1.81 + private:
1.82 + typename Container::const_iterator it;
1.83 + };
1.84 +
1.85 + /// \brief Returns an iterator to the first value.
1.86 + ///
1.87 + /// Returns an stl compatible iterator to the
1.88 + /// first value of the map. The values of the
1.89 + /// map can be accessed in the [beginValue, endValue)
1.90 + /// range.
1.91 + ValueIterator beginValue() const {
1.92 + return ValueIterator(invMap.begin());
1.93 + }
1.94 +
1.95 + /// \brief Returns an iterator after the last value.
1.96 + ///
1.97 + /// Returns an stl compatible iterator after the
1.98 + /// last value of the map. The values of the
1.99 + /// map can be accessed in the [beginValue, endValue)
1.100 + /// range.
1.101 + ValueIterator endValue() const {
1.102 + return ValueIterator(invMap.end());
1.103 + }
1.104
1.105 /// \brief The setter function of the map.
1.106 ///
1.107 @@ -932,7 +999,8 @@
1.108 /// \brief The getter function of the map.
1.109 ///
1.110 /// It gives back the value associated with the key.
1.111 - Value operator[](const Key& key) const {
1.112 + typename MapTraits<Map>::ConstReturnValue
1.113 + operator[](const Key& key) const {
1.114 return Map::operator[](key);
1.115 }
1.116
1.117 @@ -975,11 +1043,6 @@
1.118 Map::clear();
1.119 }
1.120
1.121 - private:
1.122 -
1.123 - typedef std::map<Value, Key> Container;
1.124 - Container invMap;
1.125 -
1.126 public:
1.127
1.128 /// \brief The inverse map type.
1.129 @@ -1140,6 +1203,13 @@
1.130
1.131 public:
1.132
1.133 + /// \brief Returns the maximal value plus one.
1.134 + ///
1.135 + /// Returns the maximal value plus one in the map.
1.136 + unsigned int size() const {
1.137 + return invMap.size();
1.138 + }
1.139 +
1.140 /// \brief Swaps the position of the two items in the map.
1.141 ///
1.142 /// Swaps the position of the two items in the map.
1.143 @@ -1193,7 +1263,7 @@
1.144 /// \brief Size of the map.
1.145 ///
1.146 /// Returns the size of the map.
1.147 - int size() const {
1.148 + unsigned int size() const {
1.149 return inverted.invMap.size();
1.150 }
1.151
1.152 @@ -1447,6 +1517,7 @@
1.153 Parent::add(key);
1.154 Parent::set(key, 0);
1.155 }
1.156 +
1.157 virtual void add(const std::vector<Key>& keys) {
1.158 Parent::add(keys);
1.159 for (int i = 0; i < (int)keys.size(); ++i) {
1.160 @@ -1487,10 +1558,22 @@
1.161 ++deg[graph.target(edge)];
1.162 }
1.163
1.164 + virtual void add(const std::vector<Edge>& edges) {
1.165 + for (int i = 0; i < (int)edges.size(); ++i) {
1.166 + ++deg[graph.target(edges[i])];
1.167 + }
1.168 + }
1.169 +
1.170 virtual void erase(const Edge& edge) {
1.171 --deg[graph.target(edge)];
1.172 }
1.173
1.174 + virtual void erase(const std::vector<Edge>& edges) {
1.175 + for (int i = 0; i < (int)edges.size(); ++i) {
1.176 + --deg[graph.target(edges[i])];
1.177 + }
1.178 + }
1.179 +
1.180 virtual void build() {
1.181 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1.182 deg[it] = countInEdges(graph, it);
1.183 @@ -1591,10 +1674,22 @@
1.184 ++deg[graph.source(edge)];
1.185 }
1.186
1.187 + virtual void add(const std::vector<Edge>& edges) {
1.188 + for (int i = 0; i < (int)edges.size(); ++i) {
1.189 + ++deg[graph.source(edges[i])];
1.190 + }
1.191 + }
1.192 +
1.193 virtual void erase(const Edge& edge) {
1.194 --deg[graph.source(edge)];
1.195 }
1.196
1.197 + virtual void erase(const std::vector<Edge>& edges) {
1.198 + for (int i = 0; i < (int)edges.size(); ++i) {
1.199 + --deg[graph.source(edges[i])];
1.200 + }
1.201 + }
1.202 +
1.203 virtual void build() {
1.204 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1.205 deg[it] = countOutEdges(graph, it);
2.1 --- a/lemon/iterable_maps.h Mon Jan 30 09:37:41 2006 +0000
2.2 +++ b/lemon/iterable_maps.h Tue Jan 31 19:33:48 2006 +0000
2.3 @@ -16,7 +16,11 @@
2.4
2.5 #include <lemon/traits.h>
2.6 #include <lemon/invalid.h>
2.7 +
2.8 #include <vector>
2.9 +#include <map>
2.10 +
2.11 +#include <iterator>
2.12 #include <limits>
2.13
2.14 ///\ingroup maps
2.15 @@ -29,7 +33,7 @@
2.16
2.17 namespace lemon {
2.18
2.19 - ///\ingroup maps
2.20 + ///\ingroup graph_maps
2.21 ///
2.22 /// \brief Dynamic iterable bool map.
2.23 ///
2.24 @@ -45,35 +49,35 @@
2.25 : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Parent {
2.26 private:
2.27 typedef _Graph Graph;
2.28 - typedef _Item Item;
2.29
2.30 - typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
2.31 - typedef typename ItemSetTraits<Graph, Item>
2.32 + typedef typename ItemSetTraits<Graph, _Item>::ItemIt KeyIt;
2.33 + typedef typename ItemSetTraits<Graph, _Item>
2.34 ::template Map<int>::Parent Parent;
2.35
2.36 - std::vector<Item> array;
2.37 + std::vector<_Item> array;
2.38 int sep;
2.39
2.40 const Graph& graph;
2.41
2.42 - private:
2.43 -
2.44 - int position(const Item& item) const {
2.45 - return Parent::operator[](item);
2.46 - }
2.47 -
2.48 public:
2.49
2.50 /// Indicates that the map if reference map.
2.51 typedef True ReferenceMapTag;
2.52
2.53 /// The key type
2.54 - typedef Item Key;
2.55 + typedef _Item Key;
2.56 /// The value type
2.57 typedef bool Value;
2.58 /// The const reference type.
2.59 typedef const Value& ConstReference;
2.60
2.61 + private:
2.62 +
2.63 + int position(const Key& key) const {
2.64 + return Parent::operator[](key);
2.65 + }
2.66 +
2.67 + public:
2.68
2.69 /// \brief Refernce to the value of the map.
2.70 ///
2.71 @@ -121,7 +125,7 @@
2.72 /// Constructor of the Map with a default value.
2.73 IterableBoolMap(const Graph& _graph, bool def = false)
2.74 : Parent(_graph), graph(_graph) {
2.75 - for (ItemIt it(graph); it != INVALID; ++it) {
2.76 + for (KeyIt it(graph); it != INVALID; ++it) {
2.77 Parent::set(it, array.size());
2.78 array.push_back(it);
2.79 }
2.80 @@ -131,51 +135,51 @@
2.81 /// \brief Const subscript operator of the map.
2.82 ///
2.83 /// Const subscript operator of the map.
2.84 - bool operator[](const Item& item) const {
2.85 - return position(item) < sep;
2.86 + bool operator[](const Key& key) const {
2.87 + return position(key) < sep;
2.88 }
2.89
2.90 /// \brief Subscript operator of the map.
2.91 ///
2.92 /// Subscript operator of the map.
2.93 - Reference operator[](const Item& item) {
2.94 - return Reference(*this, item);
2.95 + Reference operator[](const Key& key) {
2.96 + return Reference(*this, key);
2.97 }
2.98
2.99 /// \brief Set operation of the map.
2.100 ///
2.101 /// Set operation of the map.
2.102 - void set(const Item& item, bool value) {
2.103 - int pos = position(item);
2.104 + void set(const Key& key, bool value) {
2.105 + int pos = position(key);
2.106 if (value) {
2.107 if (pos < sep) return;
2.108 - Item tmp = array[sep];
2.109 - array[sep] = item;
2.110 - Parent::set(item, sep);
2.111 + Key tmp = array[sep];
2.112 + array[sep] = key;
2.113 + Parent::set(key, sep);
2.114 array[pos] = tmp;
2.115 Parent::set(tmp, pos);
2.116 ++sep;
2.117 } else {
2.118 if (pos >= sep) return;
2.119 --sep;
2.120 - Item tmp = array[sep];
2.121 - array[sep] = item;
2.122 - Parent::set(item, sep);
2.123 + Key tmp = array[sep];
2.124 + array[sep] = key;
2.125 + Parent::set(key, sep);
2.126 array[pos] = tmp;
2.127 Parent::set(tmp, pos);
2.128 }
2.129 }
2.130
2.131 - /// \brief Returns the number of the items mapped to true.
2.132 + /// \brief Returns the number of the keys mapped to true.
2.133 ///
2.134 - /// Returns the number of the items mapped to true.
2.135 + /// Returns the number of the keys mapped to true.
2.136 int trueNum() const {
2.137 return sep;
2.138 }
2.139
2.140 - /// \brief Returns the number of the items mapped to false.
2.141 + /// \brief Returns the number of the keys mapped to false.
2.142 ///
2.143 - /// Returns the number of the items mapped to false.
2.144 + /// Returns the number of the keys mapped to false.
2.145 int falseNum() const {
2.146 return array.size() - sep;
2.147 }
2.148 @@ -184,12 +188,12 @@
2.149 ///
2.150 /// Iterator for the keys mapped to true. It works
2.151 /// like a graph item iterator in the map, it can be converted
2.152 - /// the item type of the map, incremented with \c ++ operator, and
2.153 - /// if the iterator leave the last valid item it will be equal to
2.154 + /// the key type of the map, incremented with \c ++ operator, and
2.155 + /// if the iterator leave the last valid key it will be equal to
2.156 /// \c INVALID.
2.157 - class TrueIt : public Item {
2.158 + class TrueIt : public Key {
2.159 public:
2.160 - typedef Item Parent;
2.161 + typedef Key Parent;
2.162
2.163 /// \brief Creates an iterator.
2.164 ///
2.165 @@ -202,7 +206,7 @@
2.166
2.167 /// \brief Invalid constructor \& conversion.
2.168 ///
2.169 - /// This constructor initializes the item to be invalid.
2.170 + /// This constructor initializes the key to be invalid.
2.171 /// \sa Invalid for more details.
2.172 TrueIt(Invalid) : Parent(INVALID), map(0) {}
2.173
2.174 @@ -224,12 +228,12 @@
2.175 ///
2.176 /// Iterator for the keys mapped to false. It works
2.177 /// like a graph item iterator in the map, it can be converted
2.178 - /// the item type of the map, incremented with \c ++ operator, and
2.179 - /// if the iterator leave the last valid item it will be equal to
2.180 + /// the key type of the map, incremented with \c ++ operator, and
2.181 + /// if the iterator leave the last valid key it will be equal to
2.182 /// \c INVALID.
2.183 - class FalseIt : public Item {
2.184 + class FalseIt : public Key {
2.185 public:
2.186 - typedef Item Parent;
2.187 + typedef Key Parent;
2.188
2.189 /// \brief Creates an iterator.
2.190 ///
2.191 @@ -237,12 +241,12 @@
2.192 /// keys which mapped to false.
2.193 /// \param map The IterableIntMap
2.194 FalseIt(const IterableBoolMap& _map)
2.195 - : Parent(_map.sep < _map.array.size() ? _map.array.back() : INVALID),
2.196 - map(&_map) {}
2.197 + : Parent(_map.sep < (int)_map.array.size() ?
2.198 + _map.array.back() : INVALID), map(&_map) {}
2.199
2.200 /// \brief Invalid constructor \& conversion.
2.201 ///
2.202 - /// This constructor initializes the item to be invalid.
2.203 + /// This constructor initializes the key to be invalid.
2.204 /// \sa Invalid for more details.
2.205 FalseIt(Invalid) : Parent(INVALID), map(0) {}
2.206
2.207 @@ -259,24 +263,66 @@
2.208 const IterableBoolMap* map;
2.209 };
2.210
2.211 + /// \brief Iterator for the keys mapped to a given value.
2.212 + ///
2.213 + /// Iterator for the keys mapped to a given value. It works
2.214 + /// like a graph item iterator in the map, it can be converted
2.215 + /// the key type of the map, incremented with \c ++ operator, and
2.216 + /// if the iterator leave the last valid key it will be equal to
2.217 + /// \c INVALID.
2.218 + class ItemIt : public Key {
2.219 + public:
2.220 + typedef Key Parent;
2.221 +
2.222 + /// \brief Creates an iterator.
2.223 + ///
2.224 + /// Creates an iterator. It iterates on the
2.225 + /// keys which mapped to false.
2.226 + /// \param map The IterableIntMap
2.227 + /// \param value Which elements should be iterated.
2.228 + ItemIt(const IterableBoolMap& _map, bool value)
2.229 + : Parent(value ? (_map.sep > 0 ? _map.array[_map.sep - 1] : INVALID) :
2.230 + (_map.sep < (int)_map.array.size() ?
2.231 + _map.array.back() : INVALID)), map(&_map) {}
2.232 +
2.233 + /// \brief Invalid constructor \& conversion.
2.234 + ///
2.235 + /// This constructor initializes the key to be invalid.
2.236 + /// \sa Invalid for more details.
2.237 + ItemIt(Invalid) : Parent(INVALID), map(0) {}
2.238 +
2.239 + /// \brief Increment operator.
2.240 + ///
2.241 + /// Increment Operator.
2.242 + ItemIt& operator++() {
2.243 + int pos = map->position(*this);
2.244 + int sep = pos >= map->sep ? map->sep : 0;
2.245 + Parent::operator=(pos > sep ? map->array[pos - 1] : INVALID);
2.246 + return *this;
2.247 + }
2.248 +
2.249 + private:
2.250 + const IterableBoolMap* map;
2.251 + };
2.252 +
2.253 protected:
2.254
2.255 - virtual void add(const Item& item) {
2.256 - Parent::add(item);
2.257 - Parent::set(item, array.size());
2.258 - array.push_back(item);
2.259 + virtual void add(const Key& key) {
2.260 + Parent::add(key);
2.261 + Parent::set(key, array.size());
2.262 + array.push_back(key);
2.263 }
2.264
2.265 - virtual void add(const std::vector<Item>& items) {
2.266 - Parent::add(items);
2.267 - for (int i = 0; i < (int)items.size(); ++i) {
2.268 - Parent::set(items[i], array.size());
2.269 - array.push_back(items[i]);
2.270 + virtual void add(const std::vector<Key>& keys) {
2.271 + Parent::add(keys);
2.272 + for (int i = 0; i < (int)keys.size(); ++i) {
2.273 + Parent::set(keys[i], array.size());
2.274 + array.push_back(keys[i]);
2.275 }
2.276 }
2.277
2.278 - virtual void erase(const Item& item) {
2.279 - int pos = position(item);
2.280 + virtual void erase(const Key& key) {
2.281 + int pos = position(key);
2.282 if (pos < sep) {
2.283 --sep;
2.284 Parent::set(array[sep], pos);
2.285 @@ -289,12 +335,12 @@
2.286 array[pos] = array.back();
2.287 array.pop_back();
2.288 }
2.289 - Parent::erase(item);
2.290 + Parent::erase(key);
2.291 }
2.292
2.293 - virtual void erase(const std::vector<Item>& items) {
2.294 - for (int i = 0; i < (int)items.size(); ++i) {
2.295 - int pos = position(items[i]);
2.296 + virtual void erase(const std::vector<Key>& keys) {
2.297 + for (int i = 0; i < (int)keys.size(); ++i) {
2.298 + int pos = position(keys[i]);
2.299 if (pos < sep) {
2.300 --sep;
2.301 Parent::set(array[sep], pos);
2.302 @@ -308,12 +354,12 @@
2.303 array.pop_back();
2.304 }
2.305 }
2.306 - Parent::erase(items);
2.307 + Parent::erase(keys);
2.308 }
2.309
2.310 virtual void build() {
2.311 Parent::build();
2.312 - for (ItemIt it(graph); it != INVALID; ++it) {
2.313 + for (KeyIt it(graph); it != INVALID; ++it) {
2.314 Parent::set(it, array.size());
2.315 array.push_back(it);
2.316 }
2.317 @@ -339,7 +385,7 @@
2.318 };
2.319 }
2.320
2.321 - ///\ingroup maps
2.322 + ///\ingroup graph_maps
2.323 ///
2.324 /// \brief Dynamic iterable integer map.
2.325 ///
2.326 @@ -514,8 +560,8 @@
2.327 /// \brief Gives back the maximal value plus one.
2.328 ///
2.329 /// Gives back the maximal value plus one.
2.330 - int size() const {
2.331 - return (int)first.size();
2.332 + unsigned int size() const {
2.333 + return first.size();
2.334 }
2.335
2.336 /// \brief Set operation of the map.
2.337 @@ -594,7 +640,7 @@
2.338 }
2.339
2.340 virtual void erase(const std::vector<Key>& keys) {
2.341 - for (int i = 0; i < keys.size(); ++i) {
2.342 + for (int i = 0; i < (int)keys.size(); ++i) {
2.343 unlace(keys[i]);
2.344 }
2.345 Parent::erase(keys);
2.346 @@ -609,5 +655,240 @@
2.347 std::vector<_Item> first;
2.348 };
2.349
2.350 + namespace _iterable_maps_bits {
2.351 + template <typename Item, typename Value>
2.352 + struct IterableValueMapNode {
2.353 + IterableValueMapNode(Value _value = Value()) : value(_value) {}
2.354 + Item prev, next;
2.355 + Value value;
2.356 + };
2.357 + }
2.358 +
2.359 + ///\ingroup graph_maps
2.360 + ///
2.361 + /// \brief Dynamic iterable map for comparable values.
2.362 + ///
2.363 + /// This class provides a special graph map type which can store
2.364 + /// for each graph item(node, edge, etc.) a value. For each
2.365 + /// value it is possible to iterate on the keys which mapped to the
2.366 + /// given value. The type stores for each value a linked list with
2.367 + /// the items which mapped to the value, and the values are stored
2.368 + /// in balanced binary tree. The values of the map can be accessed
2.369 + /// with stl compatible forward iterator.
2.370 + ///
2.371 + /// This type is not reference map so it cannot be modified with
2.372 + /// the subscription operator.
2.373 + ///
2.374 + /// \see InvertableMap
2.375 + ///
2.376 + /// \param _Graph The graph type.
2.377 + /// \param _Item One of the graph's item type, the key of the map.
2.378 + /// \param _Value Any comparable value type.
2.379 + template <typename _Graph, typename _Item, typename _Value>
2.380 + class IterableValueMap : protected ItemSetTraits<_Graph, _Item>
2.381 + ::template Map<_iterable_maps_bits::IterableValueMapNode<_Item, _Value> >
2.382 + ::Parent {
2.383 + public:
2.384 + typedef typename ItemSetTraits<_Graph, _Item>
2.385 + ::template Map<_iterable_maps_bits::IterableValueMapNode<_Item, _Value> >
2.386 + ::Parent Parent;
2.387 +
2.388 + /// The key type
2.389 + typedef _Item Key;
2.390 + /// The value type
2.391 + typedef _Value Value;
2.392 + /// The graph type
2.393 + typedef _Graph Graph;
2.394 +
2.395 + /// \brief Constructor of the Map with a given value.
2.396 + ///
2.397 + /// Constructor of the Map with a given value.
2.398 + explicit IterableValueMap(const Graph& graph,
2.399 + const Value& value = Value())
2.400 + : Parent(graph, _iterable_maps_bits::IterableValueMapNode<_Item,
2.401 + _Value>(value)) {
2.402 + for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
2.403 + lace(it);
2.404 + }
2.405 + }
2.406 +
2.407 + private:
2.408 +
2.409 + void unlace(const Key& key) {
2.410 + typename Parent::Value& node = Parent::operator[](key);
2.411 + if (node.prev != INVALID) {
2.412 + Parent::operator[](node.prev).next = node.next;
2.413 + } else {
2.414 + if (node.next != INVALID) {
2.415 + first[node.value] = node.next;
2.416 + } else {
2.417 + first.erase(node.value);
2.418 + }
2.419 + }
2.420 + if (node.next != INVALID) {
2.421 + Parent::operator[](node.next).prev = node.prev;
2.422 + }
2.423 + }
2.424 +
2.425 + void lace(const Key& key) {
2.426 + typename Parent::Value& node = Parent::operator[](key);
2.427 + typename std::map<Value, Key>::iterator it = first.find(node.value);
2.428 + if (it == first.end()) {
2.429 + node.prev = node.next = INVALID;
2.430 + if (node.next != INVALID) {
2.431 + Parent::operator[](node.next).prev = key;
2.432 + }
2.433 + first.insert(make_pair(node.value, key));
2.434 + } else {
2.435 + node.prev = INVALID;
2.436 + node.next = it->second;
2.437 + if (node.next != INVALID) {
2.438 + Parent::operator[](node.next).prev = key;
2.439 + }
2.440 + it->second = key;
2.441 + }
2.442 + }
2.443 +
2.444 + public:
2.445 +
2.446 + /// \brief Forward iterator for values.
2.447 + ///
2.448 + /// This iterator is an stl compatible forward
2.449 + /// iterator on the values of the map. The values can
2.450 + /// be accessed in the [beginValue, endValue) range.
2.451 + ///
2.452 + class ValueIterator
2.453 + : public std::iterator<std::forward_iterator_tag, Value> {
2.454 + friend class IterableValueMap;
2.455 + private:
2.456 + ValueIterator(typename std::map<Value, Key>::const_iterator _it)
2.457 + : it(_it) {}
2.458 + public:
2.459 +
2.460 + ValueIterator() {}
2.461 +
2.462 + ValueIterator& operator++() { ++it; return *this; }
2.463 + ValueIterator operator++(int) {
2.464 + ValueIterator tmp(*this);
2.465 + operator++();
2.466 + return tmp;
2.467 + }
2.468 +
2.469 + const Value& operator*() const { return it->first; }
2.470 + const Value* operator->() const { return &(it->first); }
2.471 +
2.472 + bool operator==(ValueIterator jt) const { return it == jt.it; }
2.473 + bool operator!=(ValueIterator jt) const { return it != jt.it; }
2.474 +
2.475 + private:
2.476 + typename std::map<Value, Key>::const_iterator it;
2.477 + };
2.478 +
2.479 + /// \brief Returns an iterator to the first value.
2.480 + ///
2.481 + /// Returns an stl compatible iterator to the
2.482 + /// first value of the map. The values of the
2.483 + /// map can be accessed in the [beginValue, endValue)
2.484 + /// range.
2.485 + ValueIterator beginValue() const {
2.486 + return ValueIterator(first.begin());
2.487 + }
2.488 +
2.489 + /// \brief Returns an iterator after the last value.
2.490 + ///
2.491 + /// Returns an stl compatible iterator after the
2.492 + /// last value of the map. The values of the
2.493 + /// map can be accessed in the [beginValue, endValue)
2.494 + /// range.
2.495 + ValueIterator endValue() const {
2.496 + return ValueIterator(first.end());
2.497 + }
2.498 +
2.499 + /// \brief Set operation of the map.
2.500 + ///
2.501 + /// Set operation of the map.
2.502 + void set(const Key& key, const Value& value) {
2.503 + unlace(key);
2.504 + Parent::operator[](key).value = value;
2.505 + lace(key);
2.506 + }
2.507 +
2.508 + /// \brief Const subscript operator of the map.
2.509 + ///
2.510 + /// Const subscript operator of the map.
2.511 + const Value& operator[](const Key& key) const {
2.512 + return Parent::operator[](key).value;
2.513 + }
2.514 +
2.515 + /// \brief Iterator for the keys with the same value.
2.516 + ///
2.517 + /// Iterator for the keys with the same value. It works
2.518 + /// like a graph item iterator in the map, it can be converted
2.519 + /// the item type of the map, incremented with \c ++ operator, and
2.520 + /// if the iterator leave the last valid item it will be equal to
2.521 + /// \c INVALID.
2.522 + class ItemIt : public _Item {
2.523 + public:
2.524 + typedef _Item Parent;
2.525 +
2.526 + /// \brief Invalid constructor \& conversion.
2.527 + ///
2.528 + /// This constructor initializes the item to be invalid.
2.529 + /// \sa Invalid for more details.
2.530 + ItemIt(Invalid) : Parent(INVALID), _map(0) {}
2.531 +
2.532 + /// \brief Creates an iterator with a value.
2.533 + ///
2.534 + /// Creates an iterator with a value. It iterates on the
2.535 + /// keys which have the given value.
2.536 + /// \param map The IterableValueMap
2.537 + /// \param value The value
2.538 + ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
2.539 + typename std::map<Value, Key>::const_iterator it =
2.540 + map.first.find(value);
2.541 + if (it == map.first.end()) {
2.542 + Parent::operator=(INVALID);
2.543 + } else {
2.544 + Parent::operator=(it->second);
2.545 + }
2.546 + }
2.547 +
2.548 + /// \brief Increment operator.
2.549 + ///
2.550 + /// Increment Operator.
2.551 + ItemIt& operator++() {
2.552 + Parent::operator=(_map->IterableValueMap::Parent::
2.553 + operator[](static_cast<Parent&>(*this)).next);
2.554 + return *this;
2.555 + }
2.556 +
2.557 +
2.558 + private:
2.559 + const IterableValueMap* _map;
2.560 + };
2.561 +
2.562 + protected:
2.563 +
2.564 + virtual void erase(const Key& key) {
2.565 + unlace(key);
2.566 + Parent::erase(key);
2.567 + }
2.568 +
2.569 + virtual void erase(const std::vector<Key>& keys) {
2.570 + for (int i = 0; i < (int)keys.size(); ++i) {
2.571 + unlace(keys[i]);
2.572 + }
2.573 + Parent::erase(keys);
2.574 + }
2.575 +
2.576 + virtual void clear() {
2.577 + first.clear();
2.578 + Parent::clear();
2.579 + }
2.580 +
2.581 + private:
2.582 + std::map<Value, Key> first;
2.583 + };
2.584 +
2.585 /// @}
2.586 }