1.1 --- a/lemon/concepts/maps.h Tue Jan 08 04:26:27 2008 +0100
1.2 +++ b/lemon/concepts/maps.h Tue Jan 08 20:26:48 2008 +0100
1.3 @@ -48,6 +48,7 @@
1.4
1.5 /// Returns the value associated with a key.
1.6
1.7 + /// Returns the value associated with a key.
1.8 /// \bug Value shouldn't need to be default constructible.
1.9 ///
1.10 Value operator[](const Key &) const {return Value();}
1.11 @@ -113,7 +114,7 @@
1.12 };
1.13 };
1.14
1.15 - /// Read/Writable map concept
1.16 + /// Read/writable map concept
1.17
1.18 /// Read/writable map concept.
1.19 ///
1.20 @@ -146,6 +147,7 @@
1.21
1.22 /// Dereferable map concept.
1.23 ///
1.24 + /// \todo Rethink this concept.
1.25 template<typename K, typename T, typename R, typename CR>
1.26 class ReferenceMap : public ReadWriteMap<K,T>
1.27 {
1.28 @@ -165,14 +167,13 @@
1.29 Value tmp;
1.30 public:
1.31
1.32 - ///Returns a reference to the value associated to a key.
1.33 + ///Returns a reference to the value associated with a key.
1.34 Reference operator[](const Key &) { return tmp; }
1.35 - ///Returns a const reference to the value associated to a key.
1.36 + ///Returns a const reference to the value associated with a key.
1.37 ConstReference operator[](const Key &) const { return tmp; }
1.38 /// Sets the value associated with a key.
1.39 void set(const Key &k,const Value &t) { operator[](k)=t; }
1.40
1.41 - /// \todo Rethink this concept.
1.42 template<typename _ReferenceMap>
1.43 struct ReferenceMapConcept {
1.44
2.1 --- a/lemon/maps.h Tue Jan 08 04:26:27 2008 +0100
2.2 +++ b/lemon/maps.h Tue Jan 08 20:26:48 2008 +0100
2.3 @@ -81,8 +81,9 @@
2.4
2.5 /// Constant map.
2.6
2.7 - /// This is a readable map which assigns a specified value to each key.
2.8 - /// In other aspects it is equivalent to the \c NullMap.
2.9 + /// This is a \ref concepts::ReadMap "readable" map which assigns a
2.10 + /// specified value to each key.
2.11 + /// In other aspects it is equivalent to \c NullMap.
2.12 template<typename K, typename T>
2.13 class ConstMap : public MapBase<K, T> {
2.14 private:
2.15 @@ -133,8 +134,9 @@
2.16
2.17 /// Constant map with inlined constant value.
2.18
2.19 - /// This is a readable map which assigns a specified value to each key.
2.20 - /// In other aspects it is equivalent to the \c NullMap.
2.21 + /// This is a \ref concepts::ReadMap "readable" map which assigns a
2.22 + /// specified value to each key.
2.23 + /// In other aspects it is equivalent to \c NullMap.
2.24 template<typename K, typename V, V v>
2.25 class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
2.26 public:
2.27 @@ -149,7 +151,7 @@
2.28 void set(const K&, const V&) { }
2.29 };
2.30
2.31 - ///Returns a \c ConstMap class
2.32 + ///Returns a \c ConstMap class with inlined value
2.33
2.34 ///This function just returns a \c ConstMap class with inlined value.
2.35 ///\relates ConstMap
2.36 @@ -158,26 +160,29 @@
2.37 return ConstMap<K, Const<V, v> >();
2.38 }
2.39
2.40 - ///Map based on std::map
2.41 + ///Map based on \c std::map
2.42
2.43 ///This is essentially a wrapper for \c std::map with addition that
2.44 ///you can specify a default value different from \c Value().
2.45 + ///It meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
2.46 template <typename K, typename T, typename Compare = std::less<K> >
2.47 - class StdMap {
2.48 + class StdMap : public MapBase<K, T> {
2.49 template <typename K1, typename T1, typename C1>
2.50 friend class StdMap;
2.51 public:
2.52
2.53 - typedef True ReferenceMapTag;
2.54 + typedef MapBase<K, T> Parent;
2.55 ///Key type
2.56 - typedef K Key;
2.57 + typedef typename Parent::Key Key;
2.58 ///Value type
2.59 - typedef T Value;
2.60 + typedef typename Parent::Value Value;
2.61 ///Reference Type
2.62 typedef T& Reference;
2.63 ///Const reference type
2.64 typedef const T& ConstReference;
2.65
2.66 + typedef True ReferenceMapTag;
2.67 +
2.68 private:
2.69
2.70 typedef std::map<K, T, Compare> Map;
2.71 @@ -188,13 +193,13 @@
2.72
2.73 /// Constructor with specified default value
2.74 StdMap(const T& value = T()) : _value(value) {}
2.75 - /// \brief Constructs the map from an appropriate std::map, and explicitly
2.76 - /// specifies a default value.
2.77 + /// \brief Constructs the map from an appropriate \c std::map, and
2.78 + /// explicitly specifies a default value.
2.79 template <typename T1, typename Comp1>
2.80 StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T())
2.81 : _map(map.begin(), map.end()), _value(value) {}
2.82
2.83 - /// \brief Constructs a map from an other StdMap.
2.84 + /// \brief Constructs a map from an other \ref StdMap.
2.85 template<typename T1, typename Comp1>
2.86 StdMap(const StdMap<Key, T1, Comp1> &c)
2.87 : _map(c._map.begin(), c._map.end()), _value(c._value) {}
2.88 @@ -239,33 +244,57 @@
2.89 }
2.90
2.91 };
2.92 +
2.93 + ///Returns a \c StdMap class
2.94 +
2.95 + ///This function just returns a \c StdMap class with specified
2.96 + ///default value.
2.97 + ///\relates StdMap
2.98 + template<typename K, typename V, typename Compare = std::less<K> >
2.99 + inline StdMap<K, V, Compare> stdMap(const V& value = V()) {
2.100 + return StdMap<K, V, Compare>(value);
2.101 + }
2.102 +
2.103 + ///Returns a \c StdMap class created from an appropriate std::map
2.104 +
2.105 + ///This function just returns a \c StdMap class created from an
2.106 + ///appropriate std::map.
2.107 + ///\relates StdMap
2.108 + template<typename K, typename V, typename Compare = std::less<K> >
2.109 + inline StdMap<K, V, Compare> stdMap( const std::map<K, V, Compare> &map,
2.110 + const V& value = V() ) {
2.111 + return StdMap<K, V, Compare>(map, value);
2.112 + }
2.113
2.114 /// \brief Map for storing values for keys from the range <tt>[0..size-1]</tt>
2.115 ///
2.116 - /// The current map has the <tt>[0..size-1]</tt> keyset and the values
2.117 + /// This map has the <tt>[0..size-1]</tt> keyset and the values
2.118 /// are stored in a \c std::vector<T> container. It can be used with
2.119 /// some data structures, for example \c UnionFind, \c BinHeap, when
2.120 - /// the used items are small integer numbers.
2.121 + /// the used items are small integer numbers.
2.122 + /// This map meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
2.123 ///
2.124 /// \todo Revise its name
2.125 template <typename T>
2.126 - class IntegerMap {
2.127 + class IntegerMap : public MapBase<int, T> {
2.128
2.129 template <typename T1>
2.130 friend class IntegerMap;
2.131
2.132 public:
2.133
2.134 - typedef True ReferenceMapTag;
2.135 + typedef MapBase<int, T> Parent;
2.136 ///\e
2.137 - typedef int Key;
2.138 + typedef typename Parent::Key Key;
2.139 ///\e
2.140 - typedef T Value;
2.141 + typedef typename Parent::Value Value;
2.142 ///\e
2.143 typedef T& Reference;
2.144 ///\e
2.145 typedef const T& ConstReference;
2.146
2.147 + typedef True ReferenceMapTag;
2.148 +
2.149 private:
2.150
2.151 typedef std::vector<T> Vector;
2.152 @@ -276,12 +305,12 @@
2.153 /// Constructor with specified default value
2.154 IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
2.155
2.156 - /// \brief Constructs the map from an appropriate std::vector.
2.157 + /// \brief Constructs the map from an appropriate \c std::vector.
2.158 template <typename T1>
2.159 IntegerMap(const std::vector<T1>& vector)
2.160 : _vector(vector.begin(), vector.end()) {}
2.161
2.162 - /// \brief Constructs a map from an other IntegerMap.
2.163 + /// \brief Constructs a map from an other \ref IntegerMap.
2.164 template <typename T1>
2.165 IntegerMap(const IntegerMap<T1> &c)
2.166 : _vector(c._vector.begin(), c._vector.end()) {}
2.167 @@ -313,6 +342,15 @@
2.168 }
2.169
2.170 };
2.171 +
2.172 + ///Returns an \c IntegerMap class
2.173 +
2.174 + ///This function just returns an \c IntegerMap class.
2.175 + ///\relates IntegerMap
2.176 + template<typename T>
2.177 + inline IntegerMap<T> integerMap(int size = 0, const T& value = T()) {
2.178 + return IntegerMap<T>(size, value);
2.179 + }
2.180
2.181 /// @}
2.182
2.183 @@ -349,7 +387,7 @@
2.184 ///\brief Convert the \c Value of a map to another type using
2.185 ///the default conversion.
2.186 ///
2.187 - ///This \c concepts::ReadMap "read only map"
2.188 + ///This \ref concepts::ReadMap "read only map"
2.189 ///converts the \c Value of a map to type \c T.
2.190 ///Its \c Key is inherited from \c M.
2.191 template <typename M, typename T>
2.192 @@ -366,9 +404,7 @@
2.193 ///\param _m is the underlying map.
2.194 ConvertMap(const M &_m) : m(_m) {};
2.195
2.196 - /// \brief The subscript operator.
2.197 - ///
2.198 - /// The subscript operator.
2.199 + ///\e
2.200 Value operator[](const Key& k) const {return m[k];}
2.201 };
2.202
2.203 @@ -405,10 +441,19 @@
2.204 ///\e
2.205 Value operator[](Key k) const {return m[k];}
2.206 };
2.207 +
2.208 + ///Returns a \c SimpleMap class
2.209 +
2.210 + ///This function just returns a \c SimpleMap class.
2.211 + ///\relates SimpleMap
2.212 + template<typename M>
2.213 + inline SimpleMap<M> simpleMap(const M &m) {
2.214 + return SimpleMap<M>(m);
2.215 + }
2.216
2.217 ///Simple writable wrapping of a map
2.218
2.219 - ///This \ref concepts::WriteMap "write map" returns the simple
2.220 + ///This \ref concepts::ReadWriteMap "read-write map" returns the simple
2.221 ///wrapping of the given map. Sometimes the reference maps cannot be
2.222 ///combined with simple read-write maps. This map adaptor wraps the
2.223 ///given map to simple read-write map.
2.224 @@ -433,12 +478,21 @@
2.225 void set(Key k, const Value& c) { m.set(k, c); }
2.226 };
2.227
2.228 + ///Returns a \c SimpleWriteMap class
2.229 +
2.230 + ///This function just returns a \c SimpleWriteMap class.
2.231 + ///\relates SimpleWriteMap
2.232 + template<typename M>
2.233 + inline SimpleWriteMap<M> simpleWriteMap(M &m) {
2.234 + return SimpleWriteMap<M>(m);
2.235 + }
2.236 +
2.237 ///Sum of two maps
2.238
2.239 - ///This \c concepts::ReadMap "read only map" returns the sum of the two
2.240 + ///This \ref concepts::ReadMap "read only map" returns the sum of the two
2.241 ///given maps.
2.242 ///Its \c Key and \c Value are inherited from \c M1.
2.243 - ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
2.244 + ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
2.245 template<typename M1, typename M2>
2.246 class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
2.247 const M1& m1;
2.248 @@ -458,7 +512,7 @@
2.249 ///Returns an \c AddMap class
2.250
2.251 ///This function just returns an \c AddMap class.
2.252 - ///\todo How to call these type of functions?
2.253 + ///\todo Extend the documentation: how to call these type of functions?
2.254 ///
2.255 ///\relates AddMap
2.256 template<typename M1, typename M2>
2.257 @@ -468,7 +522,7 @@
2.258
2.259 ///Shift a map with a constant.
2.260
2.261 - ///This \c concepts::ReadMap "read only map" returns the sum of the
2.262 + ///This \ref concepts::ReadMap "read only map" returns the sum of the
2.263 ///given map and a constant value.
2.264 ///Its \c Key and \c Value are inherited from \c M.
2.265 ///
2.266 @@ -504,7 +558,7 @@
2.267
2.268 ///Shift a map with a constant (ReadWrite version).
2.269
2.270 - ///This \c concepts::ReadWriteMap "read-write map" returns the sum of the
2.271 + ///This \ref concepts::ReadWriteMap "read-write map" returns the sum of the
2.272 ///given map and a constant value. It makes also possible to write the map.
2.273 ///Its \c Key and \c Value are inherited from \c M.
2.274 ///
2.275 @@ -550,7 +604,7 @@
2.276
2.277 ///Difference of two maps
2.278
2.279 - ///This \c concepts::ReadMap "read only map" returns the difference
2.280 + ///This \ref concepts::ReadMap "read only map" returns the difference
2.281 ///of the values of the two given maps.
2.282 ///Its \c Key and \c Value are inherited from \c M1.
2.283 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
2.284 @@ -583,7 +637,7 @@
2.285
2.286 ///Product of two maps
2.287
2.288 - ///This \c concepts::ReadMap "read only map" returns the product of the
2.289 + ///This \ref concepts::ReadMap "read only map" returns the product of the
2.290 ///values of the two given maps.
2.291 ///Its \c Key and \c Value are inherited from \c M1.
2.292 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
2.293 @@ -613,7 +667,7 @@
2.294
2.295 ///Scales a map with a constant.
2.296
2.297 - ///This \c concepts::ReadMap "read only map" returns the value of the
2.298 + ///This \ref concepts::ReadMap "read only map" returns the value of the
2.299 ///given map multiplied from the left side with a constant value.
2.300 ///Its \c Key and \c Value are inherited from \c M.
2.301 ///
2.302 @@ -649,7 +703,7 @@
2.303
2.304 ///Scales a map with a constant (ReadWrite version).
2.305
2.306 - ///This \c concepts::ReadWriteMap "read-write map" returns the value of the
2.307 + ///This \ref concepts::ReadWriteMap "read-write map" returns the value of the
2.308 ///given map multiplied from the left side with a constant value. It can
2.309 ///also be used as write map if the \c / operator is defined between
2.310 ///\c Value and \c C and the given multiplier is not zero.
2.311 @@ -697,7 +751,7 @@
2.312
2.313 ///Quotient of two maps
2.314
2.315 - ///This \c concepts::ReadMap "read only map" returns the quotient of the
2.316 + ///This \ref concepts::ReadMap "read only map" returns the quotient of the
2.317 ///values of the two given maps.
2.318 ///Its \c Key and \c Value are inherited from \c M1.
2.319 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
2.320 @@ -727,7 +781,7 @@
2.321
2.322 ///Composition of two maps
2.323
2.324 - ///This \c concepts::ReadMap "read only map" returns the composition of
2.325 + ///This \ref concepts::ReadMap "read only map" returns the composition of
2.326 ///two given maps.
2.327 ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2,
2.328 ///then for
2.329 @@ -778,7 +832,7 @@
2.330
2.331 ///Combine of two maps using an STL (binary) functor.
2.332 ///
2.333 - ///This \c concepts::ReadMap "read only map" takes two maps and a
2.334 + ///This \ref concepts::ReadMap "read only map" takes two maps and a
2.335 ///binary functor and returns the composition of the two
2.336 ///given maps unsing the functor.
2.337 ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
2.338 @@ -851,7 +905,7 @@
2.339
2.340 ///Negative value of a map
2.341
2.342 - ///This \c concepts::ReadMap "read only map" returns the negative
2.343 + ///This \ref concepts::ReadMap "read only map" returns the negative
2.344 ///value of the value returned by the given map.
2.345 ///Its \c Key and \c Value are inherited from \c M.
2.346 ///The unary \c - operator must be defined for \c Value, of course.
2.347 @@ -873,7 +927,7 @@
2.348
2.349 ///Negative value of a map (ReadWrite version)
2.350
2.351 - ///This \c concepts::ReadWriteMap "read-write map" returns the negative
2.352 + ///This \ref concepts::ReadWriteMap "read-write map" returns the negative
2.353 ///value of the value returned by the given map.
2.354 ///Its \c Key and \c Value are inherited from \c M.
2.355 ///The unary \c - operator must be defined for \c Value, of course.
2.356 @@ -915,7 +969,7 @@
2.357
2.358 ///Absolute value of a map
2.359
2.360 - ///This \c concepts::ReadMap "read only map" returns the absolute value
2.361 + ///This \ref concepts::ReadMap "read only map" returns the absolute value
2.362 ///of the value returned by the given map.
2.363 ///Its \c Key and \c Value are inherited from \c M.
2.364 ///\c Value must be comparable to \c 0 and the unary \c -
2.365 @@ -949,13 +1003,14 @@
2.366
2.367 ///Converts an STL style functor to a map
2.368
2.369 - ///This \c concepts::ReadMap "read only map" returns the value
2.370 + ///This \ref concepts::ReadMap "read only map" returns the value
2.371 ///of a given functor.
2.372 ///
2.373 ///Template parameters \c K and \c V will become its
2.374 ///\c Key and \c Value.
2.375 ///In most cases they have to be given explicitly because a
2.376 - ///functor typically does not provide such typedefs.
2.377 + ///functor typically does not provide \c argument_type and
2.378 + ///\c result_type typedefs.
2.379 ///
2.380 ///Parameter \c F is the type of the used functor.
2.381 ///
2.382 @@ -980,8 +1035,9 @@
2.383
2.384 ///This function just returns a \c FunctorMap class.
2.385 ///
2.386 - ///It is specialized for adaptable function classes and
2.387 - ///C++ functions.
2.388 + ///This function is specialized for adaptable binary function
2.389 + ///classes and C++ functions.
2.390 + ///
2.391 ///\relates FunctorMap
2.392 template<typename K, typename V, typename F> inline
2.393 FunctorMap<F, K, V> functorMap(const F &f) {
2.394 @@ -1004,10 +1060,10 @@
2.395 ///Converts a map to an STL style (unary) functor
2.396
2.397 ///This class Converts a map to an STL style (unary) functor.
2.398 - ///that is it provides an <tt>operator()</tt> to read its values.
2.399 + ///That is it provides an <tt>operator()</tt> to read its values.
2.400 ///
2.401 ///For the sake of convenience it also works as
2.402 - ///a ususal \c concepts::ReadMap "readable map",
2.403 + ///a ususal \ref concepts::ReadMap "readable map",
2.404 ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
2.405 ///
2.406 ///\sa FunctorMap
2.407 @@ -1039,14 +1095,14 @@
2.408 return MapFunctor<M>(m);
2.409 }
2.410
2.411 - ///Applies all map setting operations to two maps
2.412 + ///Just readable version of \ref ForkWriteMap
2.413
2.414 - ///This map has two \c concepts::ReadMap "readable map"
2.415 + ///This map has two \ref concepts::ReadMap "readable map"
2.416 ///parameters and each read request will be passed just to the
2.417 - ///first map. This class is the just readable map type of the ForkWriteMap.
2.418 + ///first map. This class is the just readable map type of \c ForkWriteMap.
2.419 ///
2.420 ///The \c Key and \c Value are inherited from \c M1.
2.421 - ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
2.422 + ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
2.423 ///
2.424 ///\sa ForkWriteMap
2.425 ///
2.426 @@ -1069,14 +1125,14 @@
2.427
2.428 ///Applies all map setting operations to two maps
2.429
2.430 - ///This map has two \c concepts::WriteMap "writable map"
2.431 + ///This map has two \ref concepts::WriteMap "writable map"
2.432 ///parameters and each write request will be passed to both of them.
2.433 - ///If \c M1 is also \c concepts::ReadMap "readable",
2.434 + ///If \c M1 is also \ref concepts::ReadMap "readable",
2.435 ///then the read operations will return the
2.436 ///corresponding values of \c M1.
2.437 ///
2.438 ///The \c Key and \c Value are inherited from \c M1.
2.439 - ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
2.440 + ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
2.441 ///
2.442 ///\sa ForkMap
2.443 template<typename M1, typename M2>
2.444 @@ -1120,9 +1176,9 @@
2.445
2.446 ///Logical 'not' of a map
2.447
2.448 - ///This bool \c concepts::ReadMap "read only map" returns the
2.449 + ///This bool \ref concepts::ReadMap "read only map" returns the
2.450 ///logical negation of the value returned by the given map.
2.451 - ///Its \c Key is inherited from \c M, its Value is \c bool.
2.452 + ///Its \c Key is inherited from \c M, its \c Value is \c bool.
2.453 ///
2.454 ///\sa NotWriteMap
2.455 template <typename M>
2.456 @@ -1141,10 +1197,10 @@
2.457
2.458 ///Logical 'not' of a map (ReadWrie version)
2.459
2.460 - ///This bool \c concepts::ReadWriteMap "read-write map" returns the
2.461 + ///This bool \ref concepts::ReadWriteMap "read-write map" returns the
2.462 ///logical negation of the value returned by the given map. When it is set,
2.463 ///the opposite value is set to the original map.
2.464 - ///Its \c Key is inherited from \c M, its Value is \c bool.
2.465 + ///Its \c Key is inherited from \c M, its \c Value is \c bool.
2.466 ///
2.467 ///\sa NotMap
2.468 template <typename M>
2.469 @@ -1209,15 +1265,15 @@
2.470
2.471 /// \brief Writable bool map for logging each \c true assigned element
2.472 ///
2.473 - /// Writable bool map for logging each \c true assigned element, i.e it
2.474 - /// copies all the keys set to \c true to the given iterator.
2.475 + /// A \ref concepts::ReadWriteMap "read-write" bool map for logging
2.476 + /// each \c true assigned element, i.e it copies all the keys set
2.477 + /// to \c true to the given iterator.
2.478 ///
2.479 /// \note The container of the iterator should contain space
2.480 /// for each element.
2.481 ///
2.482 - /// The following example shows how you can write the edges found by the Prim
2.483 - /// algorithm directly
2.484 - /// to the standard output.
2.485 + /// The following example shows how you can write the edges found by
2.486 + /// the \ref Prim algorithm directly to the standard output.
2.487 ///\code
2.488 /// typedef IdMap<Graph, Edge> EdgeIdMap;
2.489 /// EdgeIdMap edgeId(graph);