1.1 --- a/lemon/maps.h Sun Aug 02 13:44:45 2009 +0200
1.2 +++ b/lemon/maps.h Sun Aug 02 17:22:43 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 @@ -1865,9 +1865,11 @@
1.58
1.59 public:
1.60
1.61 - /// \brief This class represents the inverse of its owner (IdMap).
1.62 + /// \brief The inverse map type of IdMap.
1.63 ///
1.64 - /// This class represents the inverse of its owner (IdMap).
1.65 + /// The inverse map type of IdMap. The subscript operator gives back
1.66 + /// an item by its id.
1.67 + /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
1.68 /// \see inverse()
1.69 class InverseMap {
1.70 public:
1.71 @@ -1882,9 +1884,9 @@
1.72 /// Constructor for creating an id-to-item map.
1.73 explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
1.74
1.75 - /// \brief Gives back the given item from its id.
1.76 + /// \brief Gives back an item by its id.
1.77 ///
1.78 - /// Gives back the given item from its id.
1.79 + /// Gives back an item by its id.
1.80 Item operator[](int id) const { return _graph->fromId(id, Item());}
1.81
1.82 private:
1.83 @@ -1903,8 +1905,17 @@
1.84 /// This class provides simple invertable graph maps.
1.85 /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
1.86 /// and if a key is set to a new value, then stores it in the inverse map.
1.87 - /// The values of the map can be accessed
1.88 - /// with stl compatible forward iterator.
1.89 + /// The graph items can be accessed by their values either using
1.90 + /// \c InverseMap or \c operator()(), and the values of the map can be
1.91 + /// accessed with an STL compatible forward iterator (\c ValueIterator).
1.92 + ///
1.93 + /// This map is intended to be used when all associated values are
1.94 + /// different (the map is actually invertable) or there are only a few
1.95 + /// items with the same value.
1.96 + /// Otherwise consider to use \c IterableValueMap, which is more
1.97 + /// suitable and more efficient for such cases. It provides iterators
1.98 + /// to traverse the items with the same associated value, however
1.99 + /// it does not have \c InverseMap.
1.100 ///
1.101 /// This type is not reference map, so it cannot be modified with
1.102 /// the subscript operator.
1.103 @@ -1945,7 +1956,7 @@
1.104
1.105 /// \brief Forward iterator for values.
1.106 ///
1.107 - /// This iterator is an stl compatible forward
1.108 + /// This iterator is an STL compatible forward
1.109 /// iterator on the values of the map. The values can
1.110 /// be accessed in the <tt>[beginValue, endValue)</tt> range.
1.111 /// They are considered with multiplicity, so each value is
1.112 @@ -1958,19 +1969,26 @@
1.113 : it(_it) {}
1.114 public:
1.115
1.116 + /// Constructor
1.117 ValueIterator() {}
1.118
1.119 + /// \e
1.120 ValueIterator& operator++() { ++it; return *this; }
1.121 + /// \e
1.122 ValueIterator operator++(int) {
1.123 ValueIterator tmp(*this);
1.124 operator++();
1.125 return tmp;
1.126 }
1.127
1.128 + /// \e
1.129 const Value& operator*() const { return it->first; }
1.130 + /// \e
1.131 const Value* operator->() const { return &(it->first); }
1.132
1.133 + /// \e
1.134 bool operator==(ValueIterator jt) const { return it == jt.it; }
1.135 + /// \e
1.136 bool operator!=(ValueIterator jt) const { return it != jt.it; }
1.137
1.138 private:
1.139 @@ -1979,7 +1997,7 @@
1.140
1.141 /// \brief Returns an iterator to the first value.
1.142 ///
1.143 - /// Returns an stl compatible iterator to the
1.144 + /// Returns an STL compatible iterator to the
1.145 /// first value of the map. The values of the
1.146 /// map can be accessed in the <tt>[beginValue, endValue)</tt>
1.147 /// range.
1.148 @@ -1989,7 +2007,7 @@
1.149
1.150 /// \brief Returns an iterator after the last value.
1.151 ///
1.152 - /// Returns an stl compatible iterator after the
1.153 + /// Returns an STL compatible iterator after the
1.154 /// last value of the map. The values of the
1.155 /// map can be accessed in the <tt>[beginValue, endValue)</tt>
1.156 /// range.
1.157 @@ -2090,10 +2108,12 @@
1.158
1.159 public:
1.160
1.161 - /// \brief The inverse map type.
1.162 + /// \brief The inverse map type of CrossRefMap.
1.163 ///
1.164 - /// The inverse of this map. The subscript operator of the map
1.165 - /// gives back the item that was last assigned to the value.
1.166 + /// The inverse map type of CrossRefMap. The subscript operator gives
1.167 + /// back an item by its value.
1.168 + /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
1.169 + /// \see inverse()
1.170 class InverseMap {
1.171 public:
1.172 /// \brief Constructor
1.173 @@ -2120,9 +2140,9 @@
1.174 const CrossRefMap& _inverted;
1.175 };
1.176
1.177 - /// \brief It gives back the read-only inverse map.
1.178 + /// \brief Gives back the inverse of the map.
1.179 ///
1.180 - /// It gives back the read-only inverse map.
1.181 + /// Gives back the inverse of the CrossRefMap.
1.182 InverseMap inverse() const {
1.183 return InverseMap(*this);
1.184 }
1.185 @@ -2272,16 +2292,16 @@
1.186 _inv_map[pi] = q;
1.187 }
1.188
1.189 - /// \brief Gives back the \e RangeId of the item
1.190 + /// \brief Gives back the \e range \e id of the item
1.191 ///
1.192 - /// Gives back the \e RangeId of the item.
1.193 + /// Gives back the \e range \e id of the item.
1.194 int operator[](const Item& item) const {
1.195 return Map::operator[](item);
1.196 }
1.197
1.198 - /// \brief Gives back the item belonging to a \e RangeId
1.199 + /// \brief Gives back the item belonging to a \e range \e id
1.200 ///
1.201 - /// Gives back the item belonging to a \e RangeId.
1.202 + /// Gives back the item belonging to the given \e range \e id.
1.203 Item operator()(int id) const {
1.204 return _inv_map[id];
1.205 }
1.206 @@ -2295,7 +2315,9 @@
1.207
1.208 /// \brief The inverse map type of RangeIdMap.
1.209 ///
1.210 - /// The inverse map type of RangeIdMap.
1.211 + /// The inverse map type of RangeIdMap. The subscript operator gives
1.212 + /// back an item by its \e range \e id.
1.213 + /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
1.214 class InverseMap {
1.215 public:
1.216 /// \brief Constructor
1.217 @@ -2313,7 +2335,7 @@
1.218 /// \brief Subscript operator.
1.219 ///
1.220 /// Subscript operator. It gives back the item
1.221 - /// that the descriptor currently belongs to.
1.222 + /// that the given \e range \e id currently belongs to.
1.223 Value operator[](const Key& key) const {
1.224 return _inverted(key);
1.225 }
1.226 @@ -2331,7 +2353,7 @@
1.227
1.228 /// \brief Gives back the inverse of the map.
1.229 ///
1.230 - /// Gives back the inverse of the map.
1.231 + /// Gives back the inverse of the RangeIdMap.
1.232 const InverseMap inverse() const {
1.233 return InverseMap(*this);
1.234 }
1.235 @@ -2342,10 +2364,10 @@
1.236 /// This class provides a special graph map type which can store a
1.237 /// \c bool value for graph items (\c Node, \c Arc or \c Edge).
1.238 /// For both \c true and \c false values it is possible to iterate on
1.239 - /// the keys.
1.240 + /// the keys mapped to the value.
1.241 ///
1.242 /// This type is a reference map, so it can be modified with the
1.243 - /// subscription operator.
1.244 + /// subscript operator.
1.245 ///
1.246 /// \tparam GR The graph type.
1.247 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
1.248 @@ -2711,8 +2733,13 @@
1.249 /// For each non-negative value it is possible to iterate on the keys
1.250 /// mapped to the value.
1.251 ///
1.252 + /// This map is intended to be used with small integer values, for which
1.253 + /// it is efficient, and supports iteration only for non-negative values.
1.254 + /// If you need large values and/or iteration for negative integers,
1.255 + /// consider to use \ref IterableValueMap instead.
1.256 + ///
1.257 /// This type is a reference map, so it can be modified with the
1.258 - /// subscription operator.
1.259 + /// subscript operator.
1.260 ///
1.261 /// \note The size of the data structure depends on the largest
1.262 /// value in the map.
1.263 @@ -2992,18 +3019,20 @@
1.264
1.265 /// \brief Dynamic iterable map for comparable values.
1.266 ///
1.267 - /// This class provides a special graph map type which can store an
1.268 + /// This class provides a special graph map type which can store a
1.269 /// comparable value for graph items (\c Node, \c Arc or \c Edge).
1.270 /// For each value it is possible to iterate on the keys mapped to
1.271 - /// the value.
1.272 + /// the value (\c ItemIt), and the values of the map can be accessed
1.273 + /// with an STL compatible forward iterator (\c ValueIterator).
1.274 + /// The map stores a linked list for each value, which contains
1.275 + /// the items mapped to the value, and the used values are stored
1.276 + /// in balanced binary tree (\c std::map).
1.277 ///
1.278 - /// The map stores for each value a linked list with
1.279 - /// the items which mapped to the value, and the values are stored
1.280 - /// in balanced binary tree. The values of the map can be accessed
1.281 - /// with stl compatible forward iterator.
1.282 + /// \ref IterableBoolMap and \ref IterableIntMap are similar classes
1.283 + /// specialized for \c bool and \c int values, respectively.
1.284 ///
1.285 /// This type is not reference map, so it cannot be modified with
1.286 - /// the subscription operator.
1.287 + /// the subscript operator.
1.288 ///
1.289 /// \tparam GR The graph type.
1.290 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
1.291 @@ -3079,7 +3108,7 @@
1.292
1.293 /// \brief Forward iterator for values.
1.294 ///
1.295 - /// This iterator is an stl compatible forward
1.296 + /// This iterator is an STL compatible forward
1.297 /// iterator on the values of the map. The values can
1.298 /// be accessed in the <tt>[beginValue, endValue)</tt> range.
1.299 class ValueIterator
1.300 @@ -3090,19 +3119,26 @@
1.301 : it(_it) {}
1.302 public:
1.303
1.304 + /// Constructor
1.305 ValueIterator() {}
1.306
1.307 + /// \e
1.308 ValueIterator& operator++() { ++it; return *this; }
1.309 + /// \e
1.310 ValueIterator operator++(int) {
1.311 ValueIterator tmp(*this);
1.312 operator++();
1.313 return tmp;
1.314 }
1.315
1.316 + /// \e
1.317 const Value& operator*() const { return it->first; }
1.318 + /// \e
1.319 const Value* operator->() const { return &(it->first); }
1.320
1.321 + /// \e
1.322 bool operator==(ValueIterator jt) const { return it == jt.it; }
1.323 + /// \e
1.324 bool operator!=(ValueIterator jt) const { return it != jt.it; }
1.325
1.326 private:
1.327 @@ -3111,7 +3147,7 @@
1.328
1.329 /// \brief Returns an iterator to the first value.
1.330 ///
1.331 - /// Returns an stl compatible iterator to the
1.332 + /// Returns an STL compatible iterator to the
1.333 /// first value of the map. The values of the
1.334 /// map can be accessed in the <tt>[beginValue, endValue)</tt>
1.335 /// range.
1.336 @@ -3121,7 +3157,7 @@
1.337
1.338 /// \brief Returns an iterator after the last value.
1.339 ///
1.340 - /// Returns an stl compatible iterator after the
1.341 + /// Returns an STL compatible iterator after the
1.342 /// last value of the map. The values of the
1.343 /// map can be accessed in the <tt>[beginValue, endValue)</tt>
1.344 /// range.