1.1 --- a/lemon/maps.h Sat Sep 26 07:16:22 2009 +0200
1.2 +++ b/lemon/maps.h Sat Sep 26 07:21:54 2009 +0200
1.3 @@ -56,7 +56,7 @@
1.4 /// its type definitions, or if you have to provide a writable map,
1.5 /// but data written to it is not required (i.e. it will be sent to
1.6 /// <tt>/dev/null</tt>).
1.7 - /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.8 + /// It conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.9 ///
1.10 /// \sa ConstMap
1.11 template<typename K, typename V>
1.12 @@ -89,7 +89,7 @@
1.13 /// value to each key.
1.14 ///
1.15 /// In other aspects it is equivalent to \c NullMap.
1.16 - /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
1.17 + /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
1.18 /// concept, but it absorbs the data written to it.
1.19 ///
1.20 /// The simplest way of using this map is through the constMap()
1.21 @@ -158,7 +158,7 @@
1.22 /// value to each key.
1.23 ///
1.24 /// In other aspects it is equivalent to \c NullMap.
1.25 - /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
1.26 + /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
1.27 /// concept, but it absorbs the data written to it.
1.28 ///
1.29 /// The simplest way of using this map is through the constMap()
1.30 @@ -232,7 +232,7 @@
1.31 /// values to integer keys from the range <tt>[0..size-1]</tt>.
1.32 /// It can be used with some data structures, for example
1.33 /// \c UnionFind, \c BinHeap, when the used items are small
1.34 - /// integers. This map conforms the \ref concepts::ReferenceMap
1.35 + /// integers. This map conforms to the \ref concepts::ReferenceMap
1.36 /// "ReferenceMap" concept.
1.37 ///
1.38 /// The simplest way of using this map is through the rangeMap()
1.39 @@ -340,7 +340,7 @@
1.40 /// that you can specify a default value for the keys that are not
1.41 /// stored actually. This value can be different from the default
1.42 /// contructed value (i.e. \c %Value()).
1.43 - /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
1.44 + /// This type conforms to the \ref concepts::ReferenceMap "ReferenceMap"
1.45 /// concept.
1.46 ///
1.47 /// This map is useful if a default value should be assigned to most of
1.48 @@ -706,7 +706,7 @@
1.49 /// "readable map" to another type using the default conversion.
1.50 /// The \c Key type of it is inherited from \c M and the \c Value
1.51 /// type is \c V.
1.52 - /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
1.53 + /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
1.54 ///
1.55 /// The simplest way of using this map is through the convertMap()
1.56 /// function.
1.57 @@ -1789,11 +1789,11 @@
1.58 /// order of Dfs algorithm, as the following examples show.
1.59 /// \code
1.60 /// std::vector<Node> v;
1.61 - /// dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
1.62 + /// dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s);
1.63 /// \endcode
1.64 /// \code
1.65 /// std::vector<Node> v(countNodes(g));
1.66 - /// dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
1.67 + /// dfs(g).processedMap(loggerBoolMap(v.begin())).run(s);
1.68 /// \endcode
1.69 ///
1.70 /// \note The container of the iterator must contain enough space
1.71 @@ -1825,7 +1825,7 @@
1.72 /// Using this map you get access (i.e. can read) the inner id values of
1.73 /// the items stored in the graph, which is returned by the \c id()
1.74 /// function of the graph. This map can be inverted with its member
1.75 - /// class \c InverseMap or with the \c operator() member.
1.76 + /// class \c InverseMap or with the \c operator()() member.
1.77 ///
1.78 /// \tparam GR The graph type.
1.79 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
1.80 @@ -1865,9 +1865,11 @@
1.81
1.82 public:
1.83
1.84 - /// \brief This class represents the inverse of its owner (IdMap).
1.85 + /// \brief The inverse map type of IdMap.
1.86 ///
1.87 - /// This class represents the inverse of its owner (IdMap).
1.88 + /// The inverse map type of IdMap. The subscript operator gives back
1.89 + /// an item by its id.
1.90 + /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
1.91 /// \see inverse()
1.92 class InverseMap {
1.93 public:
1.94 @@ -1882,9 +1884,9 @@
1.95 /// Constructor for creating an id-to-item map.
1.96 explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
1.97
1.98 - /// \brief Gives back the given item from its id.
1.99 + /// \brief Gives back an item by its id.
1.100 ///
1.101 - /// Gives back the given item from its id.
1.102 + /// Gives back an item by its id.
1.103 Item operator[](int id) const { return _graph->fromId(id, Item());}
1.104
1.105 private:
1.106 @@ -1897,14 +1899,31 @@
1.107 InverseMap inverse() const { return InverseMap(*_graph);}
1.108 };
1.109
1.110 + /// \brief Returns an \c IdMap class.
1.111 + ///
1.112 + /// This function just returns an \c IdMap class.
1.113 + /// \relates IdMap
1.114 + template <typename K, typename GR>
1.115 + inline IdMap<GR, K> idMap(const GR& graph) {
1.116 + return IdMap<GR, K>(graph);
1.117 + }
1.118
1.119 /// \brief General cross reference graph map type.
1.120
1.121 /// This class provides simple invertable graph maps.
1.122 /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
1.123 /// and if a key is set to a new value, then stores it in the inverse map.
1.124 - /// The values of the map can be accessed
1.125 - /// with stl compatible forward iterator.
1.126 + /// The graph items can be accessed by their values either using
1.127 + /// \c InverseMap or \c operator()(), and the values of the map can be
1.128 + /// accessed with an STL compatible forward iterator (\c ValueIt).
1.129 + ///
1.130 + /// This map is intended to be used when all associated values are
1.131 + /// different (the map is actually invertable) or there are only a few
1.132 + /// items with the same value.
1.133 + /// Otherwise consider to use \c IterableValueMap, which is more
1.134 + /// suitable and more efficient for such cases. It provides iterators
1.135 + /// to traverse the items with the same associated value, however
1.136 + /// it does not have \c InverseMap.
1.137 ///
1.138 /// This type is not reference map, so it cannot be modified with
1.139 /// the subscript operator.
1.140 @@ -1945,56 +1964,66 @@
1.141
1.142 /// \brief Forward iterator for values.
1.143 ///
1.144 - /// This iterator is an stl compatible forward
1.145 + /// This iterator is an STL compatible forward
1.146 /// iterator on the values of the map. The values can
1.147 /// be accessed in the <tt>[beginValue, endValue)</tt> range.
1.148 /// They are considered with multiplicity, so each value is
1.149 /// traversed for each item it is assigned to.
1.150 - class ValueIterator
1.151 + class ValueIt
1.152 : public std::iterator<std::forward_iterator_tag, Value> {
1.153 friend class CrossRefMap;
1.154 private:
1.155 - ValueIterator(typename Container::const_iterator _it)
1.156 + ValueIt(typename Container::const_iterator _it)
1.157 : it(_it) {}
1.158 public:
1.159
1.160 - ValueIterator() {}
1.161 -
1.162 - ValueIterator& operator++() { ++it; return *this; }
1.163 - ValueIterator operator++(int) {
1.164 - ValueIterator tmp(*this);
1.165 + /// Constructor
1.166 + ValueIt() {}
1.167 +
1.168 + /// \e
1.169 + ValueIt& operator++() { ++it; return *this; }
1.170 + /// \e
1.171 + ValueIt operator++(int) {
1.172 + ValueIt tmp(*this);
1.173 operator++();
1.174 return tmp;
1.175 }
1.176
1.177 + /// \e
1.178 const Value& operator*() const { return it->first; }
1.179 + /// \e
1.180 const Value* operator->() const { return &(it->first); }
1.181
1.182 - bool operator==(ValueIterator jt) const { return it == jt.it; }
1.183 - bool operator!=(ValueIterator jt) const { return it != jt.it; }
1.184 + /// \e
1.185 + bool operator==(ValueIt jt) const { return it == jt.it; }
1.186 + /// \e
1.187 + bool operator!=(ValueIt jt) const { return it != jt.it; }
1.188
1.189 private:
1.190 typename Container::const_iterator it;
1.191 };
1.192 +
1.193 + /// Alias for \c ValueIt
1.194 + typedef ValueIt ValueIterator;
1.195
1.196 /// \brief Returns an iterator to the first value.
1.197 ///
1.198 - /// Returns an stl compatible iterator to the
1.199 + /// Returns an STL compatible iterator to the
1.200 /// first value of the map. The values of the
1.201 /// map can be accessed in the <tt>[beginValue, endValue)</tt>
1.202 /// range.
1.203 - ValueIterator beginValue() const {
1.204 - return ValueIterator(_inv_map.begin());
1.205 + ValueIt beginValue() const {
1.206 + return ValueIt(_inv_map.begin());
1.207 }
1.208
1.209 /// \brief Returns an iterator after the last value.
1.210 ///
1.211 - /// Returns an stl compatible iterator after the
1.212 + /// Returns an STL compatible iterator after the
1.213 /// last value of the map. The values of the
1.214 /// map can be accessed in the <tt>[beginValue, endValue)</tt>
1.215 /// range.
1.216 - ValueIterator endValue() const {
1.217 - return ValueIterator(_inv_map.end());
1.218 + ValueIt endValue() const {
1.219 + return ValueIt(_inv_map.end());
1.220 }
1.221
1.222 /// \brief Sets the value associated with the given key.
1.223 @@ -2032,6 +2061,14 @@
1.224 typename Container::const_iterator it = _inv_map.find(val);
1.225 return it != _inv_map.end() ? it->second : INVALID;
1.226 }
1.227 +
1.228 + /// \brief Returns the number of items with the given value.
1.229 + ///
1.230 + /// This function returns the number of items with the given value
1.231 + /// associated with it.
1.232 + int count(const Value &val) const {
1.233 + return _inv_map.count(val);
1.234 + }
1.235
1.236 protected:
1.237
1.238 @@ -2082,10 +2119,12 @@
1.239
1.240 public:
1.241
1.242 - /// \brief The inverse map type.
1.243 + /// \brief The inverse map type of CrossRefMap.
1.244 ///
1.245 - /// The inverse of this map. The subscript operator of the map
1.246 - /// gives back the item that was last assigned to the value.
1.247 + /// The inverse map type of CrossRefMap. The subscript operator gives
1.248 + /// back an item by its value.
1.249 + /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
1.250 + /// \see inverse()
1.251 class InverseMap {
1.252 public:
1.253 /// \brief Constructor
1.254 @@ -2112,20 +2151,20 @@
1.255 const CrossRefMap& _inverted;
1.256 };
1.257
1.258 - /// \brief It gives back the read-only inverse map.
1.259 + /// \brief Gives back the inverse of the map.
1.260 ///
1.261 - /// It gives back the read-only inverse map.
1.262 + /// Gives back the inverse of the CrossRefMap.
1.263 InverseMap inverse() const {
1.264 return InverseMap(*this);
1.265 }
1.266
1.267 };
1.268
1.269 - /// \brief Provides continuous and unique ID for the
1.270 + /// \brief Provides continuous and unique id for the
1.271 /// items of a graph.
1.272 ///
1.273 /// RangeIdMap provides a unique and continuous
1.274 - /// ID for each item of a given type (\c Node, \c Arc or
1.275 + /// id for each item of a given type (\c Node, \c Arc or
1.276 /// \c Edge) in a graph. This id is
1.277 /// - \b unique: different items get different ids,
1.278 /// - \b continuous: the range of the ids is the set of integers
1.279 @@ -2136,7 +2175,7 @@
1.280 /// Thus this id is not (necessarily) the same as what can get using
1.281 /// the \c id() function of the graph or \ref IdMap.
1.282 /// This map can be inverted with its member class \c InverseMap,
1.283 - /// or with the \c operator() member.
1.284 + /// or with the \c operator()() member.
1.285 ///
1.286 /// \tparam GR The graph type.
1.287 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
1.288 @@ -2264,16 +2303,16 @@
1.289 _inv_map[pi] = q;
1.290 }
1.291
1.292 - /// \brief Gives back the \e RangeId of the item
1.293 + /// \brief Gives back the \e range \e id of the item
1.294 ///
1.295 - /// Gives back the \e RangeId of the item.
1.296 + /// Gives back the \e range \e id of the item.
1.297 int operator[](const Item& item) const {
1.298 return Map::operator[](item);
1.299 }
1.300
1.301 - /// \brief Gives back the item belonging to a \e RangeId
1.302 + /// \brief Gives back the item belonging to a \e range \e id
1.303 ///
1.304 - /// Gives back the item belonging to a \e RangeId.
1.305 + /// Gives back the item belonging to the given \e range \e id.
1.306 Item operator()(int id) const {
1.307 return _inv_map[id];
1.308 }
1.309 @@ -2287,7 +2326,9 @@
1.310
1.311 /// \brief The inverse map type of RangeIdMap.
1.312 ///
1.313 - /// The inverse map type of RangeIdMap.
1.314 + /// The inverse map type of RangeIdMap. The subscript operator gives
1.315 + /// back an item by its \e range \e id.
1.316 + /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
1.317 class InverseMap {
1.318 public:
1.319 /// \brief Constructor
1.320 @@ -2305,7 +2346,7 @@
1.321 /// \brief Subscript operator.
1.322 ///
1.323 /// Subscript operator. It gives back the item
1.324 - /// that the descriptor currently belongs to.
1.325 + /// that the given \e range \e id currently belongs to.
1.326 Value operator[](const Key& key) const {
1.327 return _inverted(key);
1.328 }
1.329 @@ -2323,18 +2364,27 @@
1.330
1.331 /// \brief Gives back the inverse of the map.
1.332 ///
1.333 - /// Gives back the inverse of the map.
1.334 + /// Gives back the inverse of the RangeIdMap.
1.335 const InverseMap inverse() const {
1.336 return InverseMap(*this);
1.337 }
1.338 };
1.339
1.340 + /// \brief Returns a \c RangeIdMap class.
1.341 + ///
1.342 + /// This function just returns an \c RangeIdMap class.
1.343 + /// \relates RangeIdMap
1.344 + template <typename K, typename GR>
1.345 + inline RangeIdMap<GR, K> rangeIdMap(const GR& graph) {
1.346 + return RangeIdMap<GR, K>(graph);
1.347 + }
1.348 +
1.349 /// \brief Dynamic iterable \c bool map.
1.350 ///
1.351 /// This class provides a special graph map type which can store a
1.352 /// \c bool value for graph items (\c Node, \c Arc or \c Edge).
1.353 /// For both \c true and \c false values it is possible to iterate on
1.354 - /// the keys.
1.355 + /// the keys mapped to the value.
1.356 ///
1.357 /// This type is a reference map, so it can be modified with the
1.358 /// subscript operator.
1.359 @@ -2703,6 +2753,11 @@
1.360 /// For each non-negative value it is possible to iterate on the keys
1.361 /// mapped to the value.
1.362 ///
1.363 + /// This map is intended to be used with small integer values, for which
1.364 + /// it is efficient, and supports iteration only for non-negative values.
1.365 + /// If you need large values and/or iteration for negative integers,
1.366 + /// consider to use \ref IterableValueMap instead.
1.367 + ///
1.368 /// This type is a reference map, so it can be modified with the
1.369 /// subscript operator.
1.370 ///
1.371 @@ -2984,15 +3039,17 @@
1.372
1.373 /// \brief Dynamic iterable map for comparable values.
1.374 ///
1.375 - /// This class provides a special graph map type which can store an
1.376 + /// This class provides a special graph map type which can store a
1.377 /// comparable value for graph items (\c Node, \c Arc or \c Edge).
1.378 /// For each value it is possible to iterate on the keys mapped to
1.379 - /// the value.
1.380 + /// the value (\c ItemIt), and the values of the map can be accessed
1.381 + /// with an STL compatible forward iterator (\c ValueIt).
1.382 + /// The map stores a linked list for each value, which contains
1.383 + /// the items mapped to the value, and the used values are stored
1.384 + /// in balanced binary tree (\c std::map).
1.385 ///
1.386 - /// The map stores for each value a linked list with
1.387 - /// the items which mapped to the value, and the values are stored
1.388 - /// in balanced binary tree. The values of the map can be accessed
1.389 - /// with stl compatible forward iterator.
1.390 + /// \ref IterableBoolMap and \ref IterableIntMap are similar classes
1.391 + /// specialized for \c bool and \c int values, respectively.
1.392 ///
1.393 /// This type is not reference map, so it cannot be modified with
1.394 /// the subscript operator.
1.395 @@ -3071,31 +3128,38 @@
1.396
1.397 /// \brief Forward iterator for values.
1.398 ///
1.399 - /// This iterator is an stl compatible forward
1.400 + /// This iterator is an STL compatible forward
1.401 /// iterator on the values of the map. The values can
1.402 /// be accessed in the <tt>[beginValue, endValue)</tt> range.
1.403 - class ValueIterator
1.404 + class ValueIt
1.405 : public std::iterator<std::forward_iterator_tag, Value> {
1.406 friend class IterableValueMap;
1.407 private:
1.408 - ValueIterator(typename std::map<Value, Key>::const_iterator _it)
1.409 + ValueIt(typename std::map<Value, Key>::const_iterator _it)
1.410 : it(_it) {}
1.411 public:
1.412
1.413 - ValueIterator() {}
1.414 -
1.415 - ValueIterator& operator++() { ++it; return *this; }
1.416 - ValueIterator operator++(int) {
1.417 - ValueIterator tmp(*this);
1.418 + /// Constructor
1.419 + ValueIt() {}
1.420 +
1.421 + /// \e
1.422 + ValueIt& operator++() { ++it; return *this; }
1.423 + /// \e
1.424 + ValueIt operator++(int) {
1.425 + ValueIt tmp(*this);
1.426 operator++();
1.427 return tmp;
1.428 }
1.429
1.430 + /// \e
1.431 const Value& operator*() const { return it->first; }
1.432 + /// \e
1.433 const Value* operator->() const { return &(it->first); }
1.434
1.435 - bool operator==(ValueIterator jt) const { return it == jt.it; }
1.436 - bool operator!=(ValueIterator jt) const { return it != jt.it; }
1.437 + /// \e
1.438 + bool operator==(ValueIt jt) const { return it == jt.it; }
1.439 + /// \e
1.440 + bool operator!=(ValueIt jt) const { return it != jt.it; }
1.441
1.442 private:
1.443 typename std::map<Value, Key>::const_iterator it;
1.444 @@ -3103,22 +3167,22 @@
1.445
1.446 /// \brief Returns an iterator to the first value.
1.447 ///
1.448 - /// Returns an stl compatible iterator to the
1.449 + /// Returns an STL compatible iterator to the
1.450 /// first value of the map. The values of the
1.451 /// map can be accessed in the <tt>[beginValue, endValue)</tt>
1.452 /// range.
1.453 - ValueIterator beginValue() const {
1.454 - return ValueIterator(_first.begin());
1.455 + ValueIt beginValue() const {
1.456 + return ValueIt(_first.begin());
1.457 }
1.458
1.459 /// \brief Returns an iterator after the last value.
1.460 ///
1.461 - /// Returns an stl compatible iterator after the
1.462 + /// Returns an STL compatible iterator after the
1.463 /// last value of the map. The values of the
1.464 /// map can be accessed in the <tt>[beginValue, endValue)</tt>
1.465 /// range.
1.466 - ValueIterator endValue() const {
1.467 - return ValueIterator(_first.end());
1.468 + ValueIt endValue() const {
1.469 + return ValueIt(_first.end());
1.470 }
1.471
1.472 /// \brief Set operation of the map.
1.473 @@ -3236,9 +3300,9 @@
1.474 class SourceMap {
1.475 public:
1.476
1.477 - ///\e
1.478 + /// The key type (the \c Arc type of the digraph).
1.479 typedef typename GR::Arc Key;
1.480 - ///\e
1.481 + /// The value type (the \c Node type of the digraph).
1.482 typedef typename GR::Node Value;
1.483
1.484 /// \brief Constructor
1.485 @@ -3277,9 +3341,9 @@
1.486 class TargetMap {
1.487 public:
1.488
1.489 - ///\e
1.490 + /// The key type (the \c Arc type of the digraph).
1.491 typedef typename GR::Arc Key;
1.492 - ///\e
1.493 + /// The value type (the \c Node type of the digraph).
1.494 typedef typename GR::Node Value;
1.495
1.496 /// \brief Constructor
1.497 @@ -3319,8 +3383,10 @@
1.498 class ForwardMap {
1.499 public:
1.500
1.501 + /// The key type (the \c Edge type of the digraph).
1.502 + typedef typename GR::Edge Key;
1.503 + /// The value type (the \c Arc type of the digraph).
1.504 typedef typename GR::Arc Value;
1.505 - typedef typename GR::Edge Key;
1.506
1.507 /// \brief Constructor
1.508 ///
1.509 @@ -3359,8 +3425,10 @@
1.510 class BackwardMap {
1.511 public:
1.512
1.513 + /// The key type (the \c Edge type of the digraph).
1.514 + typedef typename GR::Edge Key;
1.515 + /// The value type (the \c Arc type of the digraph).
1.516 typedef typename GR::Arc Value;
1.517 - typedef typename GR::Edge Key;
1.518
1.519 /// \brief Constructor
1.520 ///