1.1 --- a/lemon/maps.h Tue Jan 08 04:26:27 2008 +0100
1.2 +++ b/lemon/maps.h Tue Jan 08 20:26:48 2008 +0100
1.3 @@ -81,8 +81,9 @@
1.4
1.5 /// Constant map.
1.6
1.7 - /// This is a readable map which assigns a specified value to each key.
1.8 - /// In other aspects it is equivalent to the \c NullMap.
1.9 + /// This is a \ref concepts::ReadMap "readable" map which assigns a
1.10 + /// specified value to each key.
1.11 + /// In other aspects it is equivalent to \c NullMap.
1.12 template<typename K, typename T>
1.13 class ConstMap : public MapBase<K, T> {
1.14 private:
1.15 @@ -133,8 +134,9 @@
1.16
1.17 /// Constant map with inlined constant value.
1.18
1.19 - /// This is a readable map which assigns a specified value to each key.
1.20 - /// In other aspects it is equivalent to the \c NullMap.
1.21 + /// This is a \ref concepts::ReadMap "readable" map which assigns a
1.22 + /// specified value to each key.
1.23 + /// In other aspects it is equivalent to \c NullMap.
1.24 template<typename K, typename V, V v>
1.25 class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
1.26 public:
1.27 @@ -149,7 +151,7 @@
1.28 void set(const K&, const V&) { }
1.29 };
1.30
1.31 - ///Returns a \c ConstMap class
1.32 + ///Returns a \c ConstMap class with inlined value
1.33
1.34 ///This function just returns a \c ConstMap class with inlined value.
1.35 ///\relates ConstMap
1.36 @@ -158,26 +160,29 @@
1.37 return ConstMap<K, Const<V, v> >();
1.38 }
1.39
1.40 - ///Map based on std::map
1.41 + ///Map based on \c std::map
1.42
1.43 ///This is essentially a wrapper for \c std::map with addition that
1.44 ///you can specify a default value different from \c Value().
1.45 + ///It meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
1.46 template <typename K, typename T, typename Compare = std::less<K> >
1.47 - class StdMap {
1.48 + class StdMap : public MapBase<K, T> {
1.49 template <typename K1, typename T1, typename C1>
1.50 friend class StdMap;
1.51 public:
1.52
1.53 - typedef True ReferenceMapTag;
1.54 + typedef MapBase<K, T> Parent;
1.55 ///Key type
1.56 - typedef K Key;
1.57 + typedef typename Parent::Key Key;
1.58 ///Value type
1.59 - typedef T Value;
1.60 + typedef typename Parent::Value Value;
1.61 ///Reference Type
1.62 typedef T& Reference;
1.63 ///Const reference type
1.64 typedef const T& ConstReference;
1.65
1.66 + typedef True ReferenceMapTag;
1.67 +
1.68 private:
1.69
1.70 typedef std::map<K, T, Compare> Map;
1.71 @@ -188,13 +193,13 @@
1.72
1.73 /// Constructor with specified default value
1.74 StdMap(const T& value = T()) : _value(value) {}
1.75 - /// \brief Constructs the map from an appropriate std::map, and explicitly
1.76 - /// specifies a default value.
1.77 + /// \brief Constructs the map from an appropriate \c std::map, and
1.78 + /// explicitly specifies a default value.
1.79 template <typename T1, typename Comp1>
1.80 StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T())
1.81 : _map(map.begin(), map.end()), _value(value) {}
1.82
1.83 - /// \brief Constructs a map from an other StdMap.
1.84 + /// \brief Constructs a map from an other \ref StdMap.
1.85 template<typename T1, typename Comp1>
1.86 StdMap(const StdMap<Key, T1, Comp1> &c)
1.87 : _map(c._map.begin(), c._map.end()), _value(c._value) {}
1.88 @@ -239,33 +244,57 @@
1.89 }
1.90
1.91 };
1.92 +
1.93 + ///Returns a \c StdMap class
1.94 +
1.95 + ///This function just returns a \c StdMap class with specified
1.96 + ///default value.
1.97 + ///\relates StdMap
1.98 + template<typename K, typename V, typename Compare = std::less<K> >
1.99 + inline StdMap<K, V, Compare> stdMap(const V& value = V()) {
1.100 + return StdMap<K, V, Compare>(value);
1.101 + }
1.102 +
1.103 + ///Returns a \c StdMap class created from an appropriate std::map
1.104 +
1.105 + ///This function just returns a \c StdMap class created from an
1.106 + ///appropriate std::map.
1.107 + ///\relates StdMap
1.108 + template<typename K, typename V, typename Compare = std::less<K> >
1.109 + inline StdMap<K, V, Compare> stdMap( const std::map<K, V, Compare> &map,
1.110 + const V& value = V() ) {
1.111 + return StdMap<K, V, Compare>(map, value);
1.112 + }
1.113
1.114 /// \brief Map for storing values for keys from the range <tt>[0..size-1]</tt>
1.115 ///
1.116 - /// The current map has the <tt>[0..size-1]</tt> keyset and the values
1.117 + /// This map has the <tt>[0..size-1]</tt> keyset and the values
1.118 /// are stored in a \c std::vector<T> container. It can be used with
1.119 /// some data structures, for example \c UnionFind, \c BinHeap, when
1.120 - /// the used items are small integer numbers.
1.121 + /// the used items are small integer numbers.
1.122 + /// This map meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
1.123 ///
1.124 /// \todo Revise its name
1.125 template <typename T>
1.126 - class IntegerMap {
1.127 + class IntegerMap : public MapBase<int, T> {
1.128
1.129 template <typename T1>
1.130 friend class IntegerMap;
1.131
1.132 public:
1.133
1.134 - typedef True ReferenceMapTag;
1.135 + typedef MapBase<int, T> Parent;
1.136 ///\e
1.137 - typedef int Key;
1.138 + typedef typename Parent::Key Key;
1.139 ///\e
1.140 - typedef T Value;
1.141 + typedef typename Parent::Value Value;
1.142 ///\e
1.143 typedef T& Reference;
1.144 ///\e
1.145 typedef const T& ConstReference;
1.146
1.147 + typedef True ReferenceMapTag;
1.148 +
1.149 private:
1.150
1.151 typedef std::vector<T> Vector;
1.152 @@ -276,12 +305,12 @@
1.153 /// Constructor with specified default value
1.154 IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
1.155
1.156 - /// \brief Constructs the map from an appropriate std::vector.
1.157 + /// \brief Constructs the map from an appropriate \c std::vector.
1.158 template <typename T1>
1.159 IntegerMap(const std::vector<T1>& vector)
1.160 : _vector(vector.begin(), vector.end()) {}
1.161
1.162 - /// \brief Constructs a map from an other IntegerMap.
1.163 + /// \brief Constructs a map from an other \ref IntegerMap.
1.164 template <typename T1>
1.165 IntegerMap(const IntegerMap<T1> &c)
1.166 : _vector(c._vector.begin(), c._vector.end()) {}
1.167 @@ -313,6 +342,15 @@
1.168 }
1.169
1.170 };
1.171 +
1.172 + ///Returns an \c IntegerMap class
1.173 +
1.174 + ///This function just returns an \c IntegerMap class.
1.175 + ///\relates IntegerMap
1.176 + template<typename T>
1.177 + inline IntegerMap<T> integerMap(int size = 0, const T& value = T()) {
1.178 + return IntegerMap<T>(size, value);
1.179 + }
1.180
1.181 /// @}
1.182
1.183 @@ -349,7 +387,7 @@
1.184 ///\brief Convert the \c Value of a map to another type using
1.185 ///the default conversion.
1.186 ///
1.187 - ///This \c concepts::ReadMap "read only map"
1.188 + ///This \ref concepts::ReadMap "read only map"
1.189 ///converts the \c Value of a map to type \c T.
1.190 ///Its \c Key is inherited from \c M.
1.191 template <typename M, typename T>
1.192 @@ -366,9 +404,7 @@
1.193 ///\param _m is the underlying map.
1.194 ConvertMap(const M &_m) : m(_m) {};
1.195
1.196 - /// \brief The subscript operator.
1.197 - ///
1.198 - /// The subscript operator.
1.199 + ///\e
1.200 Value operator[](const Key& k) const {return m[k];}
1.201 };
1.202
1.203 @@ -405,10 +441,19 @@
1.204 ///\e
1.205 Value operator[](Key k) const {return m[k];}
1.206 };
1.207 +
1.208 + ///Returns a \c SimpleMap class
1.209 +
1.210 + ///This function just returns a \c SimpleMap class.
1.211 + ///\relates SimpleMap
1.212 + template<typename M>
1.213 + inline SimpleMap<M> simpleMap(const M &m) {
1.214 + return SimpleMap<M>(m);
1.215 + }
1.216
1.217 ///Simple writable wrapping of a map
1.218
1.219 - ///This \ref concepts::WriteMap "write map" returns the simple
1.220 + ///This \ref concepts::ReadWriteMap "read-write map" returns the simple
1.221 ///wrapping of the given map. Sometimes the reference maps cannot be
1.222 ///combined with simple read-write maps. This map adaptor wraps the
1.223 ///given map to simple read-write map.
1.224 @@ -433,12 +478,21 @@
1.225 void set(Key k, const Value& c) { m.set(k, c); }
1.226 };
1.227
1.228 + ///Returns a \c SimpleWriteMap class
1.229 +
1.230 + ///This function just returns a \c SimpleWriteMap class.
1.231 + ///\relates SimpleWriteMap
1.232 + template<typename M>
1.233 + inline SimpleWriteMap<M> simpleWriteMap(M &m) {
1.234 + return SimpleWriteMap<M>(m);
1.235 + }
1.236 +
1.237 ///Sum of two maps
1.238
1.239 - ///This \c concepts::ReadMap "read only map" returns the sum of the two
1.240 + ///This \ref concepts::ReadMap "read only map" returns the sum of the two
1.241 ///given maps.
1.242 ///Its \c Key and \c Value are inherited from \c M1.
1.243 - ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
1.244 + ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
1.245 template<typename M1, typename M2>
1.246 class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
1.247 const M1& m1;
1.248 @@ -458,7 +512,7 @@
1.249 ///Returns an \c AddMap class
1.250
1.251 ///This function just returns an \c AddMap class.
1.252 - ///\todo How to call these type of functions?
1.253 + ///\todo Extend the documentation: how to call these type of functions?
1.254 ///
1.255 ///\relates AddMap
1.256 template<typename M1, typename M2>
1.257 @@ -468,7 +522,7 @@
1.258
1.259 ///Shift a map with a constant.
1.260
1.261 - ///This \c concepts::ReadMap "read only map" returns the sum of the
1.262 + ///This \ref concepts::ReadMap "read only map" returns the sum of the
1.263 ///given map and a constant value.
1.264 ///Its \c Key and \c Value are inherited from \c M.
1.265 ///
1.266 @@ -504,7 +558,7 @@
1.267
1.268 ///Shift a map with a constant (ReadWrite version).
1.269
1.270 - ///This \c concepts::ReadWriteMap "read-write map" returns the sum of the
1.271 + ///This \ref concepts::ReadWriteMap "read-write map" returns the sum of the
1.272 ///given map and a constant value. It makes also possible to write the map.
1.273 ///Its \c Key and \c Value are inherited from \c M.
1.274 ///
1.275 @@ -550,7 +604,7 @@
1.276
1.277 ///Difference of two maps
1.278
1.279 - ///This \c concepts::ReadMap "read only map" returns the difference
1.280 + ///This \ref concepts::ReadMap "read only map" returns the difference
1.281 ///of the values of the two given maps.
1.282 ///Its \c Key and \c Value are inherited from \c M1.
1.283 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
1.284 @@ -583,7 +637,7 @@
1.285
1.286 ///Product of two maps
1.287
1.288 - ///This \c concepts::ReadMap "read only map" returns the product of the
1.289 + ///This \ref concepts::ReadMap "read only map" returns the product of the
1.290 ///values of the two given maps.
1.291 ///Its \c Key and \c Value are inherited from \c M1.
1.292 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
1.293 @@ -613,7 +667,7 @@
1.294
1.295 ///Scales a map with a constant.
1.296
1.297 - ///This \c concepts::ReadMap "read only map" returns the value of the
1.298 + ///This \ref concepts::ReadMap "read only map" returns the value of the
1.299 ///given map multiplied from the left side with a constant value.
1.300 ///Its \c Key and \c Value are inherited from \c M.
1.301 ///
1.302 @@ -649,7 +703,7 @@
1.303
1.304 ///Scales a map with a constant (ReadWrite version).
1.305
1.306 - ///This \c concepts::ReadWriteMap "read-write map" returns the value of the
1.307 + ///This \ref concepts::ReadWriteMap "read-write map" returns the value of the
1.308 ///given map multiplied from the left side with a constant value. It can
1.309 ///also be used as write map if the \c / operator is defined between
1.310 ///\c Value and \c C and the given multiplier is not zero.
1.311 @@ -697,7 +751,7 @@
1.312
1.313 ///Quotient of two maps
1.314
1.315 - ///This \c concepts::ReadMap "read only map" returns the quotient of the
1.316 + ///This \ref concepts::ReadMap "read only map" returns the quotient of the
1.317 ///values of the two given maps.
1.318 ///Its \c Key and \c Value are inherited from \c M1.
1.319 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
1.320 @@ -727,7 +781,7 @@
1.321
1.322 ///Composition of two maps
1.323
1.324 - ///This \c concepts::ReadMap "read only map" returns the composition of
1.325 + ///This \ref concepts::ReadMap "read only map" returns the composition of
1.326 ///two given maps.
1.327 ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2,
1.328 ///then for
1.329 @@ -778,7 +832,7 @@
1.330
1.331 ///Combine of two maps using an STL (binary) functor.
1.332 ///
1.333 - ///This \c concepts::ReadMap "read only map" takes two maps and a
1.334 + ///This \ref concepts::ReadMap "read only map" takes two maps and a
1.335 ///binary functor and returns the composition of the two
1.336 ///given maps unsing the functor.
1.337 ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
1.338 @@ -851,7 +905,7 @@
1.339
1.340 ///Negative value of a map
1.341
1.342 - ///This \c concepts::ReadMap "read only map" returns the negative
1.343 + ///This \ref concepts::ReadMap "read only map" returns the negative
1.344 ///value of the value returned by the given map.
1.345 ///Its \c Key and \c Value are inherited from \c M.
1.346 ///The unary \c - operator must be defined for \c Value, of course.
1.347 @@ -873,7 +927,7 @@
1.348
1.349 ///Negative value of a map (ReadWrite version)
1.350
1.351 - ///This \c concepts::ReadWriteMap "read-write map" returns the negative
1.352 + ///This \ref concepts::ReadWriteMap "read-write map" returns the negative
1.353 ///value of the value returned by the given map.
1.354 ///Its \c Key and \c Value are inherited from \c M.
1.355 ///The unary \c - operator must be defined for \c Value, of course.
1.356 @@ -915,7 +969,7 @@
1.357
1.358 ///Absolute value of a map
1.359
1.360 - ///This \c concepts::ReadMap "read only map" returns the absolute value
1.361 + ///This \ref concepts::ReadMap "read only map" returns the absolute value
1.362 ///of the value returned by the given map.
1.363 ///Its \c Key and \c Value are inherited from \c M.
1.364 ///\c Value must be comparable to \c 0 and the unary \c -
1.365 @@ -949,13 +1003,14 @@
1.366
1.367 ///Converts an STL style functor to a map
1.368
1.369 - ///This \c concepts::ReadMap "read only map" returns the value
1.370 + ///This \ref concepts::ReadMap "read only map" returns the value
1.371 ///of a given functor.
1.372 ///
1.373 ///Template parameters \c K and \c V will become its
1.374 ///\c Key and \c Value.
1.375 ///In most cases they have to be given explicitly because a
1.376 - ///functor typically does not provide such typedefs.
1.377 + ///functor typically does not provide \c argument_type and
1.378 + ///\c result_type typedefs.
1.379 ///
1.380 ///Parameter \c F is the type of the used functor.
1.381 ///
1.382 @@ -980,8 +1035,9 @@
1.383
1.384 ///This function just returns a \c FunctorMap class.
1.385 ///
1.386 - ///It is specialized for adaptable function classes and
1.387 - ///C++ functions.
1.388 + ///This function is specialized for adaptable binary function
1.389 + ///classes and C++ functions.
1.390 + ///
1.391 ///\relates FunctorMap
1.392 template<typename K, typename V, typename F> inline
1.393 FunctorMap<F, K, V> functorMap(const F &f) {
1.394 @@ -1004,10 +1060,10 @@
1.395 ///Converts a map to an STL style (unary) functor
1.396
1.397 ///This class Converts a map to an STL style (unary) functor.
1.398 - ///that is it provides an <tt>operator()</tt> to read its values.
1.399 + ///That is it provides an <tt>operator()</tt> to read its values.
1.400 ///
1.401 ///For the sake of convenience it also works as
1.402 - ///a ususal \c concepts::ReadMap "readable map",
1.403 + ///a ususal \ref concepts::ReadMap "readable map",
1.404 ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
1.405 ///
1.406 ///\sa FunctorMap
1.407 @@ -1039,14 +1095,14 @@
1.408 return MapFunctor<M>(m);
1.409 }
1.410
1.411 - ///Applies all map setting operations to two maps
1.412 + ///Just readable version of \ref ForkWriteMap
1.413
1.414 - ///This map has two \c concepts::ReadMap "readable map"
1.415 + ///This map has two \ref concepts::ReadMap "readable map"
1.416 ///parameters and each read request will be passed just to the
1.417 - ///first map. This class is the just readable map type of the ForkWriteMap.
1.418 + ///first map. This class is the just readable map type of \c ForkWriteMap.
1.419 ///
1.420 ///The \c Key and \c Value are inherited from \c M1.
1.421 - ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
1.422 + ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
1.423 ///
1.424 ///\sa ForkWriteMap
1.425 ///
1.426 @@ -1069,14 +1125,14 @@
1.427
1.428 ///Applies all map setting operations to two maps
1.429
1.430 - ///This map has two \c concepts::WriteMap "writable map"
1.431 + ///This map has two \ref concepts::WriteMap "writable map"
1.432 ///parameters and each write request will be passed to both of them.
1.433 - ///If \c M1 is also \c concepts::ReadMap "readable",
1.434 + ///If \c M1 is also \ref concepts::ReadMap "readable",
1.435 ///then the read operations will return the
1.436 ///corresponding values of \c M1.
1.437 ///
1.438 ///The \c Key and \c Value are inherited from \c M1.
1.439 - ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
1.440 + ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
1.441 ///
1.442 ///\sa ForkMap
1.443 template<typename M1, typename M2>
1.444 @@ -1120,9 +1176,9 @@
1.445
1.446 ///Logical 'not' of a map
1.447
1.448 - ///This bool \c concepts::ReadMap "read only map" returns the
1.449 + ///This bool \ref concepts::ReadMap "read only map" returns the
1.450 ///logical negation of the value returned by the given map.
1.451 - ///Its \c Key is inherited from \c M, its Value is \c bool.
1.452 + ///Its \c Key is inherited from \c M, its \c Value is \c bool.
1.453 ///
1.454 ///\sa NotWriteMap
1.455 template <typename M>
1.456 @@ -1141,10 +1197,10 @@
1.457
1.458 ///Logical 'not' of a map (ReadWrie version)
1.459
1.460 - ///This bool \c concepts::ReadWriteMap "read-write map" returns the
1.461 + ///This bool \ref concepts::ReadWriteMap "read-write map" returns the
1.462 ///logical negation of the value returned by the given map. When it is set,
1.463 ///the opposite value is set to the original map.
1.464 - ///Its \c Key is inherited from \c M, its Value is \c bool.
1.465 + ///Its \c Key is inherited from \c M, its \c Value is \c bool.
1.466 ///
1.467 ///\sa NotMap
1.468 template <typename M>
1.469 @@ -1209,15 +1265,15 @@
1.470
1.471 /// \brief Writable bool map for logging each \c true assigned element
1.472 ///
1.473 - /// Writable bool map for logging each \c true assigned element, i.e it
1.474 - /// copies all the keys set to \c true to the given iterator.
1.475 + /// A \ref concepts::ReadWriteMap "read-write" bool map for logging
1.476 + /// each \c true assigned element, i.e it copies all the keys set
1.477 + /// to \c true to the given iterator.
1.478 ///
1.479 /// \note The container of the iterator should contain space
1.480 /// for each element.
1.481 ///
1.482 - /// The following example shows how you can write the edges found by the Prim
1.483 - /// algorithm directly
1.484 - /// to the standard output.
1.485 + /// The following example shows how you can write the edges found by
1.486 + /// the \ref Prim algorithm directly to the standard output.
1.487 ///\code
1.488 /// typedef IdMap<Graph, Edge> EdgeIdMap;
1.489 /// EdgeIdMap edgeId(graph);