lemon-0.x: comparison lemon/maps.h

equal deleted inserted replaced

-:f293408523d3
+:9878f259a295
 /// Base class of maps.
 /// It provides the necessary <tt>typedef</tt>s required by the map concept.
 template<typename K, typename T>
 class MapBase {
 public:
-///\e
+/// The key type of the map.
 typedef K Key;
-///\e
+/// The value type of the map. (The type of objects associated with the keys).
 typedef T Value;
 };
 /// Null map. (a.k.a. DoNothingMap)
-/// If you have to provide a map only for its type definitions,
+/// This map can be used if you have to provide a map only for
-/// or if you have to provide a writable map, but
+/// its type definitions, or if you have to provide a writable map,
-/// data written to it will sent to <tt>/dev/null</tt>...
+/// but data written to it is not required (i.e. it will be sent to
+/// <tt>/dev/null</tt>).
 template<typename K, typename T>
 class NullMap : public MapBase<K, T> {
 public:
 typedef MapBase<K, T> Parent;
 typedef typename Parent::Key Key;
 T operator[](const K&) const { return T(); }
 /// Absorbs the value.
 void set(const K&, const T&) {}
 };
+///Returns a \c NullMap class
+///This function just returns a \c NullMap class.
+///\relates NullMap
 template <typename K, typename V>
 NullMap<K, V> nullMap() {
 return NullMap<K, V>();
 }
 /// Constant map.
-/// This is a readable map which assigns a specified value to each key.
+/// This is a \ref concepts::ReadMap "readable" map which assigns a
-/// In other aspects it is equivalent to the \c NullMap.
+/// specified value to each key.
+/// In other aspects it is equivalent to \c NullMap.
 template<typename K, typename T>
 class ConstMap : public MapBase<K, T> {
 private:
 T v;
 public:
 typedef typename Parent::Key Key;
 typedef typename Parent::Value Value;
 /// Default constructor
+/// Default constructor.
 /// The value of the map will be uninitialized.
 /// (More exactly it will be default constructed.)
 ConstMap() {}
-///\e
+/// Constructor with specified initial value
-/// \param _v The initial value of the map.
-///
+/// Constructor with specified initial value.
+/// \param _v is the initial value of the map.
 ConstMap(const T &_v) : v(_v) {}
 ///\e
 T operator[](const K&) const { return v; }
 template<typename T, T v>
 struct Const { };
 /// Constant map with inlined constant value.
-/// This is a readable map which assigns a specified value to each key.
+/// This is a \ref concepts::ReadMap "readable" map which assigns a
-/// In other aspects it is equivalent to the \c NullMap.
+/// specified value to each key.
+/// In other aspects it is equivalent to \c NullMap.
 template<typename K, typename V, V v>
 class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
 public:
 typedef MapBase<K, V> Parent;
 typedef typename Parent::Key Key;
 V operator[](const K&) const { return v; }
 ///\e
 void set(const K&, const V&) { }
 };
-///Returns a \c ConstMap class
+///Returns a \c ConstMap class with inlined value
 ///This function just returns a \c ConstMap class with inlined value.
 ///\relates ConstMap
 template<typename K, typename V, V v>
 inline ConstMap<K, Const<V, v> > constMap() {
 return ConstMap<K, Const<V, v> >();
 }
-///Map based on std::map
+///Map based on \c std::map
-///This is essentially a wrapper for \c std::map. With addition that
+///This is essentially a wrapper for \c std::map with addition that
 ///you can specify a default value different from \c Value() .
+///It meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
 template <typename K, typename T, typename Compare = std::less<K> >
-class StdMap {
+class StdMap : public MapBase<K, T> {
 template <typename K1, typename T1, typename C1>
 friend class StdMap;
 public:
+typedef MapBase<K, T> Parent;
+///Key type
+typedef typename Parent::Key Key;
+///Value type
+typedef typename Parent::Value Value;
+///Reference Type
+typedef T& Reference;
+///Const reference type
+typedef const T& ConstReference;
 typedef True ReferenceMapTag;
-///\e
-typedef K Key;
-///\e
-typedef T Value;
-///\e
-typedef T& Reference;
-///\e
-typedef const T& ConstReference;
 private:
 typedef std::map<K, T, Compare> Map;
 Value _value;
 public:
 /// Constructor with specified default value
 StdMap(const T& value = T()) : _value(value) {}
-/// \brief Constructs the map from an appropriate std::map, and explicitly
+/// \brief Constructs the map from an appropriate \c std::map, and
-/// specifies a default value.
+/// explicitly specifies a default value.
 template <typename T1, typename Comp1>
 StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T())
 : _map(map.begin(), map.end()), _value(value) {}
-/// \brief Constructs a map from an other StdMap.
+/// \brief Constructs a map from an other \ref StdMap.
 template<typename T1, typename Comp1>
 StdMap(const StdMap<Key, T1, Comp1> &c)
 : _map(c._map.begin(), c._map.end()), _value(c._value) {}
 private:
 struct rebind {
 typedef StdMap<Key, T1, C1> other;
 };
 };
-/// \brief Map for storing values for the range \c [0..size-1] range keys
+///Returns a \c StdMap class
-///
-/// The current map has the \c [0..size-1] keyset and the values
+///This function just returns a \c StdMap class with specified
+///default value.
+///\relates StdMap
+template<typename K, typename V, typename Compare>
+inline StdMap<K, V, Compare> stdMap(const V& value = V()) {
+return StdMap<K, V, Compare>(value);
+}
+template<typename K, typename V>
+inline StdMap<K, V, std::less<K> > stdMap(const V& value = V()) {
+return StdMap<K, V, std::less<K> >(value);
+}
+///Returns a \c StdMap class created from an appropriate \c std::map
+///This function just returns a \c StdMap class created from an
+///appropriate \c std::map.
+///\relates StdMap
+template<typename K, typename V, typename Compare>
+inline StdMap<K, V, Compare> stdMap( const std::map<K, V, Compare> &map,
+const V& value = V() ) {
+return StdMap<K, V, Compare>(map, value);
+}
+/// \brief Map for storing values for keys from the range <tt>[0..size-1]</tt>
+///
+/// This map has the <tt>[0..size-1]</tt> keyset and the values
 /// are stored in a \c std::vector<T>  container. It can be used with
 /// some data structures, for example \c UnionFind, \c BinHeap, when
 /// the used items are small integer numbers.
 template <typename T>
-class IntegerMap {
+class IntegerMap : public MapBase<int, T> {
 template <typename T1>
 friend class IntegerMap;
 public:
+typedef MapBase<int, T> Parent;
+///\e
+typedef typename Parent::Key Key;
+///\e
+typedef typename Parent::Value Value;
+///\e
+typedef T& Reference;
+///\e
+typedef const T& ConstReference;
 typedef True ReferenceMapTag;
-///\e
-typedef int Key;
-///\e
-typedef T Value;
-///\e
-typedef T& Reference;
-///\e
-typedef const T& ConstReference;
 private:
 typedef std::vector<T> Vector;
 Vector _vector;
 public:
 /// Constructor with specified default value
 IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
-/// \brief Constructs the map from an appropriate std::vector.
+/// \brief Constructs the map from an appropriate \c std::vector.
 template <typename T1>
 IntegerMap(const std::vector<T1>& vector)
 : _vector(vector.begin(), vector.end()) {}
-/// \brief Constructs a map from an other IntegerMap.
+/// \brief Constructs a map from an other \ref IntegerMap.
 template <typename T1>
 IntegerMap(const IntegerMap<T1> &c)
 : _vector(c._vector.begin(), c._vector.end()) {}
 /// \brief Resize the container
 _vector[k] = t;
 }
 };
+///Returns an \c IntegerMap class
+///This function just returns an \c IntegerMap class.
+///\relates IntegerMap
+template<typename T>
+inline IntegerMap<T> integerMap(int size = 0, const T& value = T()) {
+return IntegerMap<T>(size, value);
+}
 /// @}
 /// \addtogroup map_adaptors
 /// @{
-/// \brief Identity mapping.
+/// \brief Identity map.
 ///
-/// This mapping gives back the given key as value without any
+/// This map gives back the given key as value without any
 /// modification.
 template <typename T>
 class IdentityMap : public MapBase<T, T> {
 public:
 typedef MapBase<T, T> Parent;
 inline IdentityMap<T> identityMap() {
 return IdentityMap<T>();
 }
-///Convert the \c Value of a map to another type.
+///\brief Convert the \c Value of a map to another type using
+///the default conversion.
-///This \c concepts::ReadMap "read only map"
+///
-///converts the \c Value of a maps to type \c T.
+///This \ref concepts::ReadMap "read only map"
+///converts the \c Value of a map to type \c T.
 ///Its \c Key is inherited from \c M.
 template <typename M, typename T>
 class ConvertMap : public MapBase<typename M::Key, T> {
 const M& m;
 public:
 ///Constructor
 ///\param _m is the underlying map
 ConvertMap(const M &_m) : m(_m) {};
-/// \brief The subscript operator.
+///\e
-///
-/// The subscript operator.
-/// \param k The key
-/// \return The target of the edge
 Value operator[](const Key& k) const {return m[k];}
 };
-///Returns an \c ConvertMap class
+///Returns a \c ConvertMap class
-///This function just returns an \c ConvertMap class.
+///This function just returns a \c ConvertMap class.
 ///\relates ConvertMap
 template<typename T, typename M>
 inline ConvertMap<M, T> convertMap(const M &m) {
 return ConvertMap<M, T>(m);
 }
-///Simple wrapping of the map
+///Simple wrapping of a map
-///This \c concepts::ReadMap "read only map" returns the simple
+///This \ref concepts::ReadMap "read only map" returns the simple
 ///wrapping of the given map. Sometimes the reference maps cannot be
 ///combined with simple read maps. This map adaptor wraps the given
 ///map to simple read map.
+///
+///\sa SimpleWriteMap
+///
+/// \todo Revise the misleading name
 template<typename M>
 class SimpleMap : public MapBase<typename M::Key, typename M::Value> {
 const M& m;
 public:
 SimpleMap(const M &_m) : m(_m) {};
 ///\e
 Value operator[](Key k) const {return m[k];}
 };
-///Simple writeable wrapping of the map
+///Returns a \c SimpleMap class
-///This \c concepts::ReadMap "read only map" returns the simple
+///This function just returns a \c SimpleMap class.
+///\relates SimpleMap
+template<typename M>
+inline SimpleMap<M> simpleMap(const M &m) {
+return SimpleMap<M>(m);
+}
+///Simple writable wrapping of a map
+///This \ref concepts::ReadWriteMap "read-write map" returns the simple
 ///wrapping of the given map. Sometimes the reference maps cannot be
 ///combined with simple read-write maps. This map adaptor wraps the
 ///given map to simple read-write map.
+///
+///\sa SimpleMap
+///
+/// \todo Revise the misleading name
 template<typename M>
 class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> {
 M& m;
 public:
 Value operator[](Key k) const {return m[k];}
 ///\e
 void set(Key k, const Value& c) { m.set(k, c); }
 };
+///Returns a \c SimpleWriteMap class
+///This function just returns a \c SimpleWriteMap class.
+///\relates SimpleWriteMap
+template<typename M>
+inline SimpleWriteMap<M> simpleWriteMap(M &m) {
+return SimpleWriteMap<M>(m);
+}
 ///Sum of two maps
-///This \c concepts::ReadMap "read only map" returns the sum of the two
+///This \ref concepts::ReadMap "read only map" returns the sum of the two
-///given maps. Its \c Key and \c Value will be inherited from \c M1.
+///given maps.
-///The \c Key and \c Value of M2 must be convertible to those of \c M1.
+///Its \c Key and \c Value are inherited from \c M1.
+///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
 template<typename M1, typename M2>
 class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
 const M1& m1;
 const M2& m2;
 return AddMap<M1, M2>(m1,m2);
 }
 ///Shift a map with a constant.
-///This \c concepts::ReadMap "read only map" returns the sum of the
+///This \ref concepts::ReadMap "read only map" returns the sum of the
 ///given map and a constant value.
 ///Its \c Key and \c Value is inherited from \c M.
 ///
 ///Actually,
 ///\code
 ///  ShiftMap<X> sh(x,v);
 ///\endcode
-///is equivalent with
+///is equivalent to
 ///\code
 ///  ConstMap<X::Key, X::Value> c_tmp(v);
 ///  AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
 ///\endcode
+///
+///\sa ShiftWriteMap
 template<typename M, typename C = typename M::Value>
 class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
 const M& m;
 C v;
 public:
 ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
 ///\e
 Value operator[](Key k) const {return m[k] + v;}
 };
-///Shift a map with a constant.
+///Shift a map with a constant (ReadWrite version).
-///This \c concepts::ReadWriteMap "read-write map" returns the sum of the
+///This \ref concepts::ReadWriteMap "read-write map" returns the sum of the
 ///given map and a constant value. It makes also possible to write the map.
-///Its \c Key and \c Value is inherited from \c M.
+///Its \c Key and \c Value are inherited from \c M.
 ///
-///Actually,
+///\sa ShiftMap
-///\code
-///  ShiftMap<X> sh(x,v);
-///\endcode
-///is equivalent with
-///\code
-///  ConstMap<X::Key, X::Value> c_tmp(v);
-///  AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
-///\endcode
 template<typename M, typename C = typename M::Value>
 class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
 M& m;
 C v;
 public:
 Value operator[](Key k) const {return m[k] + v;}
 /// \e
 void set(Key k, const Value& c) { m.set(k, c - v); }
 };
-///Returns an \c ShiftMap class
+///Returns a \c ShiftMap class
 ///This function just returns an \c ShiftMap class.
 ///\relates ShiftMap
 template<typename M, typename C>
 inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
 return ShiftMap<M, C>(m,v);
 }
+///Returns a \c ShiftWriteMap class
+///This function just returns a \c ShiftWriteMap class.
+///\relates ShiftWriteMap
 template<typename M, typename C>
 inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) {
 return ShiftWriteMap<M, C>(m,v);
 }
 ///Difference of two maps
-///This \c concepts::ReadMap "read only map" returns the difference
+///This \ref concepts::ReadMap "read only map" returns the difference
-///of the values of the two
+///of the values of the two given maps.
-///given maps. Its \c Key and \c Value will be inherited from \c M1.
+///Its \c Key and \c Value are inherited from \c M1.
 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
 template<typename M1, typename M2>
 class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
 const M1& m1;
 return SubMap<M1, M2>(m1, m2);
 }
 ///Product of two maps
-///This \c concepts::ReadMap "read only map" returns the product of the
+///This \ref concepts::ReadMap "read only map" returns the product of the
-///values of the two
+///values of the two given maps.
-///given
+///Its \c Key and \c Value are inherited from \c M1.
-///maps. Its \c Key and \c Value will be inherited from \c M1.
 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
 template<typename M1, typename M2>
 class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
 const M1& m1;
 const M2& m2;
 public:
 template<typename M1, typename M2>
 inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
 return MulMap<M1, M2>(m1,m2);
 }
-///Scales a maps with a constant.
+///Scales a map with a constant.
-///This \c concepts::ReadMap "read only map" returns the value of the
+///This \ref concepts::ReadMap "read only map" returns the value of the
 ///given map multiplied from the left side with a constant value.
-///Its \c Key and \c Value is inherited from \c M.
+///Its \c Key and \c Value are inherited from \c M.
 ///
 ///Actually,
 ///\code
 ///  ScaleMap<X> sc(x,v);
 ///\endcode
-///is equivalent with
+///is equivalent to
 ///\code
 ///  ConstMap<X::Key, X::Value> c_tmp(v);
 ///  MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
 ///\endcode
+///
+///\sa ScaleWriteMap
 template<typename M, typename C = typename M::Value>
 class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
 const M& m;
 C v;
 public:
 ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
 /// \e
 Value operator[](Key k) const {return v * m[k];}
 };
-///Scales a maps with a constant.
+///Scales a map with a constant (ReadWrite version).
-///This \c concepts::ReadWriteMap "read-write map" returns the value of the
+///This \ref concepts::ReadWriteMap "read-write map" returns the value of the
 ///given map multiplied from the left side with a constant value. It can
-///be used as write map also if the given multiplier is not zero.
+///also be used as write map if the \c / operator is defined between
-///Its \c Key and \c Value is inherited from \c M.
+///\c Value and \c C and the given multiplier is not zero.
+///Its \c Key and \c Value are inherited from \c M.
+///
+///\sa ScaleMap
 template<typename M, typename C = typename M::Value>
 class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
 M& m;
 C v;
 public:
 Value operator[](Key k) const {return v * m[k];}
 /// \e
 void set(Key k, const Value& c) { m.set(k, c / v);}
 };
-///Returns an \c ScaleMap class
+///Returns a \c ScaleMap class
-///This function just returns an \c ScaleMap class.
+///This function just returns a \c ScaleMap class.
 ///\relates ScaleMap
 template<typename M, typename C>
 inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
 return ScaleMap<M, C>(m,v);
 }
+///Returns a \c ScaleWriteMap class
+///This function just returns a \c ScaleWriteMap class.
+///\relates ScaleWriteMap
 template<typename M, typename C>
 inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) {
 return ScaleWriteMap<M, C>(m,v);
 }
 ///Quotient of two maps
-///This \c concepts::ReadMap "read only map" returns the quotient of the
+///This \ref concepts::ReadMap "read only map" returns the quotient of the
-///values of the two
+///values of the two given maps.
-///given maps. Its \c Key and \c Value will be inherited from \c M1.
+///Its \c Key and \c Value are inherited from \c M1.
 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
 template<typename M1, typename M2>
 class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
 const M1& m1;
 const M2& m2;
 public:
 return DivMap<M1, M2>(m1,m2);
 }
 ///Composition of two maps
-///This \c concepts::ReadMap "read only map" returns the composition of
+///This \ref concepts::ReadMap "read only map" returns the composition of
-///two
+///two given maps.
-///given maps. That is to say, if \c m1 is of type \c M1 and \c m2 is
+///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2,
-///of \c M2,
 ///then for
 ///\code
 ///  ComposeMap<M1, M2> cm(m1,m2);
 ///\endcode
-/// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>
+/// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
 ///
-///Its \c Key is inherited from \c M2 and its \c Value is from
+///Its \c Key is inherited from \c M2 and its \c Value is from \c M1.
-///\c M1.
+///\c M2::Value must be convertible to \c M1::Key.
-///The \c M2::Value must be convertible to \c M1::Key.
+///
+///\sa CombineMap
+///
 ///\todo Check the requirements.
 template <typename M1, typename M2>
 class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
 const M1& m1;
 const M2& m2;
 template <typename M1, typename M2>
 inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
 return ComposeMap<M1, M2>(m1,m2);
 }
-///Combines of two maps using an STL (binary) functor.
+///Combine of two maps using an STL (binary) functor.
-///Combines of two maps using an STL (binary) functor.
+///Combine of two maps using an STL (binary) functor.
 ///
-///
+///This \ref concepts::ReadMap "read only map" takes two maps and a
-///This \c concepts::ReadMap "read only map" takes two maps and a
+///binary functor and returns the composition of the two
-///binary functor and returns the composition of
-///the two
 ///given maps unsing the functor.
 ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
-///and \c f is of \c F,
+///and \c f is of \c F, then for
-///then for
 ///\code
 ///  CombineMap<M1, M2,F,V> cm(m1,m2,f);
 ///\endcode
 /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
 ///
 ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
-///The \c M2::Value and \c M1::Value must be convertible to the corresponding
+///\c M2::Value and \c M1::Value must be convertible to the corresponding
 ///input parameter of \c F and the return type of \c F must be convertible
 ///to \c V.
+///
+///\sa ComposeMap
+///
 ///\todo Check the requirements.
 template<typename M1, typename M2, typename F,
 	   typename V = typename F::result_type>
 class CombineMap : public MapBase<typename M1::Key, V> {
 const M1& m1;
 ///This function just returns a \c CombineMap class.
 ///
 ///For example if \c m1 and \c m2 are both \c double valued maps, then
 ///\code
-///combineMap<double>(m1,m2,std::plus<double>())
+///combineMap(m1,m2,std::plus<double>())
 ///\endcode
-///is equivalent with
+///is equivalent to
 ///\code
 ///addMap(m1,m2)
 ///\endcode
 ///
 ///This function is specialized for adaptable binary function
-///classes and c++ functions.
+///classes and C++ functions.
 ///
 ///\relates CombineMap
 template<typename M1, typename M2, typename F, typename V>
 inline CombineMap<M1, M2, F, V>
 combineMap(const M1& m1,const M2& m2, const F& f) {
 return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
 }
 ///Negative value of a map
-///This \c concepts::ReadMap "read only map" returns the negative
+///This \ref concepts::ReadMap "read only map" returns the negative
-///value of the
+///value of the value returned by the given map.
-///value returned by the
+///Its \c Key and \c Value are inherited from \c M.
-///given map. Its \c Key and \c Value will be inherited from \c M.
 ///The unary \c - operator must be defined for \c Value, of course.
+///
+///\sa NegWriteMap
 template<typename M>
 class NegMap : public MapBase<typename M::Key, typename M::Value> {
 const M& m;
 public:
 typedef MapBase<typename M::Key, typename M::Value> Parent;
 NegMap(const M &_m) : m(_m) {};
 /// \e
 Value operator[](Key k) const {return -m[k];}
 };
-///Negative value of a map
+///Negative value of a map (ReadWrite version)
-///This \c concepts::ReadWriteMap "read-write map" returns the negative
+///This \ref concepts::ReadWriteMap "read-write map" returns the negative
-///value of the value returned by the
+///value of the value returned by the given map.
-///given map. Its \c Key and \c Value will be inherited from \c M.
+///Its \c Key and \c Value are inherited from \c M.
 ///The unary \c - operator must be defined for \c Value, of course.
+///
+/// \sa NegMap
 template<typename M>
 class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
 M& m;
 public:
 typedef MapBase<typename M::Key, typename M::Value> Parent;
 template <typename M>
 inline NegMap<M> negMap(const M &m) {
 return NegMap<M>(m);
 }
+///Returns a \c NegWriteMap class
+///This function just returns a \c NegWriteMap class.
+///\relates NegWriteMap
 template <typename M>
 inline NegWriteMap<M> negMap(M &m) {
 return NegWriteMap<M>(m);
 }
 ///Absolute value of a map
-///This \c concepts::ReadMap "read only map" returns the absolute value
+///This \ref concepts::ReadMap "read only map" returns the absolute value
-///of the
+///of the value returned by the given map.
-///value returned by the
+///Its \c Key and \c Value are inherited from \c M.
-///given map. Its \c Key and \c Value will be inherited
+///\c Value must be comparable to \c 0 and the unary \c -
-///from <tt>M</tt>. <tt>Value</tt>
-///must be comparable to <tt>0</tt> and the unary <tt>-</tt>
 ///operator must be defined for it, of course.
 ///
 ///\bug We need a unified way to handle the situation below:
 ///\code
 ///  struct _UnConvertible {};
 return tmp >= 0 ? tmp : -tmp;
 }
 };
-///Returns a \c AbsMap class
+///Returns an \c AbsMap class
-///This function just returns a \c AbsMap class.
+///This function just returns an \c AbsMap class.
 ///\relates AbsMap
 template<typename M>
 inline AbsMap<M> absMap(const M &m) {
 return AbsMap<M>(m);
 }
 ///Converts an STL style functor to a map
-///This \c concepts::ReadMap "read only map" returns the value
+///This \ref concepts::ReadMap "read only map" returns the value
-///of a
+///of a given functor.
-///given map.
 ///
 ///Template parameters \c K and \c V will become its
-///\c Key and \c Value. They must be given explicitely
+///\c Key and \c Value.
-///because a functor does not provide such typedefs.
+///In most cases they have to be given explicitly because a
+///functor typically does not provide \c argument_type and
+///\c result_type typedefs.
 ///
 ///Parameter \c F is the type of the used functor.
+///
+///\sa MapFunctor
 template<typename F,
 	   typename K = typename F::argument_type,
 	   typename V = typename F::result_type>
 class FunctorMap : public MapBase<K, V> {
 F f;
 ///Returns a \c FunctorMap class
 ///This function just returns a \c FunctorMap class.
 ///
-///It is specialized for adaptable function classes and
+///This function is specialized for adaptable binary function
-///c++ functions.
+///classes and C++ functions.
+///
 ///\relates FunctorMap
 template<typename K, typename V, typename F> inline
 FunctorMap<F, K, V> functorMap(const F &f) {
 return FunctorMap<F, K, V>(f);
 }
 ///Converts a map to an STL style (unary) functor
 ///This class Converts a map to an STL style (unary) functor.
-///that is it provides an <tt>operator()</tt> to read its values.
+///That is it provides an <tt>operator()</tt> to read its values.
 ///
 ///For the sake of convenience it also works as
-///a ususal \c concepts::ReadMap "readable map",
+///a ususal \ref concepts::ReadMap "readable map",
 ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
+///
+///\sa FunctorMap
 template <typename M>
 class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
 const M& m;
 public:
 typedef MapBase<typename M::Key, typename M::Value> Parent;
 template<typename M>
 inline MapFunctor<M> mapFunctor(const M &m) {
 return MapFunctor<M>(m);
 }
-///Applies all map setting operations to two maps
+///Just readable version of \ref ForkWriteMap
-///This map has two \c concepts::ReadMap "readable map"
+///This map has two \ref concepts::ReadMap "readable map"
 ///parameters and each read request will be passed just to the
-///first map. This class is the just readable map type of the ForkWriteMap.
+///first map. This class is the just readable map type of \c ForkWriteMap.
 ///
-///The \c Key and \c Value will be inherited from \c M1.
+///The \c Key and \c Value are inherited from \c M1.
-///The \c Key and \c Value of M2 must be convertible from those of \c M1.
+///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
+///
+///\sa ForkWriteMap
 template<typename  M1, typename M2>
 class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
 const M1& m1;
 const M2& m2;
 public:
 };
 ///Applies all map setting operations to two maps
-///This map has two \c concepts::WriteMap "writable map"
+///This map has two \ref concepts::WriteMap "writable map"
 ///parameters and each write request will be passed to both of them.
-///If \c M1 is also \c concepts::ReadMap "readable",
+///If \c M1 is also \ref concepts::ReadMap "readable",
 ///then the read operations will return the
 ///corresponding values of \c M1.
 ///
-///The \c Key and \c Value will be inherited from \c M1.
+///The \c Key and \c Value are inherited from \c M1.
-///The \c Key and \c Value of M2 must be convertible from those of \c M1.
+///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
+///
+///\sa ForkMap
 template<typename  M1, typename M2>
 class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
 M1& m1;
 M2& m2;
 public:
 Value operator[](Key k) const {return m1[k];}
 ///\e
 void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
 };
-///Returns an \c ForkMap class
+///Returns a \c ForkMap class
-///This function just returns an \c ForkMap class.
+///This function just returns a \c ForkMap class.
-///
 ///\relates ForkMap
 template <typename M1, typename M2>
 inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) {
 return ForkMap<M1, M2>(m1,m2);
 }
+///Returns a \c ForkWriteMap class
+///This function just returns a \c ForkWriteMap class.
+///\relates ForkWriteMap
 template <typename M1, typename M2>
 inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) {
 return ForkWriteMap<M1, M2>(m1,m2);
 }
 /* ************* BOOL MAPS ******************* */
 ///Logical 'not' of a map
-///This bool \c concepts::ReadMap "read only map" returns the
+///This bool \ref concepts::ReadMap "read only map" returns the
-///logical negation of
+///logical negation of the value returned by the given map.
-///value returned by the
+///Its \c Key is inherited from \c M, its \c Value is \c bool.
-///given map. Its \c Key and will be inherited from \c M,
+///
-///its Value is <tt>bool</tt>.
+///\sa NotWriteMap
 template <typename M>
 class NotMap : public MapBase<typename M::Key, bool> {
 const M& m;
 public:
 typedef MapBase<typename M::Key, bool> Parent;
 NotMap(const M &_m) : m(_m) {};
 ///\e
 Value operator[](Key k) const {return !m[k];}
 };
-///Logical 'not' of a map with writing possibility
+///Logical 'not' of a map (ReadWrie version)
-///This bool \c concepts::ReadWriteMap "read-write map" returns the
+///This bool \ref concepts::ReadWriteMap "read-write map" returns the
-///logical negation of value returned by the given map. When it is set,
+///logical negation of the value returned by the given map. When it is set,
 ///the opposite value is set to the original map.
-///Its \c Key and will be inherited from \c M,
+///Its \c Key is inherited from \c M, its \c Value is \c bool.
-///its Value is <tt>bool</tt>.
+///
+///\sa NotMap
 template <typename M>
 class NotWriteMap : public MapBase<typename M::Key, bool> {
 M& m;
 public:
 typedef MapBase<typename M::Key, bool> Parent;
 template <typename M>
 inline NotMap<M> notMap(const M &m) {
 return NotMap<M>(m);
 }
+///Returns a \c NotWriteMap class
+///This function just returns a \c NotWriteMap class.
+///\relates NotWriteMap
 template <typename M>
 inline NotWriteMap<M> notMap(M &m) {
 return NotWriteMap<M>(m);
 }
 };
 }
-/// \brief Writable bool map for store each true assigned elements.
+/// \brief Writable bool map for logging each \c true assigned element
 ///
-/// Writable bool map to store each true assigned elements. It will
+/// A \ref concepts::ReadWriteMap "read-write" bool map for logging
-/// copies all the keys set to true to the given iterator.
+/// each \c true assigned element, i.e it copies all the keys set
+/// to \c true to the given iterator.
 ///
 /// \note The container of the iterator should contain space
 /// for each element.
 ///
-/// The next example shows how can you write the nodes directly
+/// The following example shows how you can write the edges found by
-/// to the standard output.
+/// the \ref Prim algorithm directly to the standard output.
 ///\code
 /// typedef IdMap<UGraph, UEdge> UEdgeIdMap;
 /// UEdgeIdMap uedgeId(ugraph);
 ///
 /// typedef MapFunctor<UEdgeIdMap> UEdgeIdFunctor;
 /// StoreBoolMap<ostream_iterator<int>, UEdgeIdFunctor>
 ///   writerMap(ostream_iterator<int>(cout, " "), uedgeIdFunctor);
 ///
 /// prim(ugraph, cost, writerMap);
 ///\endcode
+///
+///\sa BackInserterBoolMap
+///\sa FrontInserterBoolMap
+///\sa InserterBoolMap
 template <typename _Iterator,
 typename _Functor =
 _maps_bits::Identity<typename _maps_bits::
 IteratorTraits<_Iterator>::Value> >
 class StoreBoolMap {
 /// Constructor
 StoreBoolMap(Iterator it, const Functor& functor = Functor())
 : _begin(it), _end(it), _functor(functor) {}
-/// Gives back the given iterator set for the first time.
+/// Gives back the given iterator set for the first key
 Iterator begin() const {
 return _begin;
 }
-/// Gives back the iterator after the last set operation.
+/// Gives back the the 'after the last' iterator
 Iterator end() const {
 return _end;
 }
-/// Setter function of the map
+/// The \c set function of the map
 void set(const Key& key, Value value) const {
 if (value) {
 	*_end++ = _functor(key);
 }
 }
 Iterator _begin;
 mutable Iterator _end;
 Functor _functor;
 };
-/// \brief Writable bool map for store each true assigned elements in
+/// \brief Writable bool map for logging each \c true assigned element in
 /// a back insertable container.
 ///
-/// Writable bool map for store each true assigned elements in a back
+/// Writable bool map for logging each \c true assigned element by pushing
-/// insertable container. It will push back all the keys set to true into
+/// them into a back insertable container.
-/// the container. It can be used to retrieve the items into a standard
+/// It can be used to retrieve the items into a standard
-/// container. The next example shows how can you store the undirected
+/// container. The next example shows how you can store the
-/// edges in a vector with prim algorithm.
+/// edges found by the Prim algorithm in a vector.
 ///
 ///\code
 /// vector<UEdge> span_tree_uedges;
 /// BackInserterBoolMap<vector<UEdge> > inserter_map(span_tree_uedges);
 /// prim(ugraph, cost, inserter_map);
 ///\endcode
+///
+///\sa StoreBoolMap
+///\sa FrontInserterBoolMap
+///\sa InserterBoolMap
 template <typename Container,
 typename Functor =
 _maps_bits::Identity<typename Container::value_type> >
 class BackInserterBoolMap {
 public:
-typedef typename Container::value_type Key;
+typedef typename Functor::argument_type Key;
 typedef bool Value;
 /// Constructor
 BackInserterBoolMap(Container& _container,
 const Functor& _functor = Functor())
 : container(_container), functor(_functor) {}
-/// Setter function of the map
+/// The \c set function of the map
 void set(const Key& key, Value value) {
 if (value) {
 	container.push_back(functor(key));
 }
 }
 private:
 Container& container;
 Functor functor;
 };
-/// \brief Writable bool map for store each true assigned elements in
+/// \brief Writable bool map for logging each \c true assigned element in
 /// a front insertable container.
 ///
-/// Writable bool map for store each true assigned elements in a front
+/// Writable bool map for logging each \c true assigned element by pushing
-/// insertable container. It will push front all the keys set to \c true into
+/// them into a front insertable container.
-/// the container. For example see the BackInserterBoolMap.
+/// It can be used to retrieve the items into a standard
+/// container. For example see \ref BackInserterBoolMap.
+///
+///\sa BackInserterBoolMap
+///\sa InserterBoolMap
 template <typename Container,
 typename Functor =
 _maps_bits::Identity<typename Container::value_type> >
 class FrontInserterBoolMap {
 public:
-typedef typename Container::value_type Key;
+typedef typename Functor::argument_type Key;
 typedef bool Value;
 /// Constructor
 FrontInserterBoolMap(Container& _container,
 const Functor& _functor = Functor())
 : container(_container), functor(_functor) {}
-/// Setter function of the map
+/// The \c set function of the map
 void set(const Key& key, Value value) {
 if (value) {
-	container.push_front(key);
+	container.push_front(functor(key));
 }
 }
 private:
 Container& container;
 Functor functor;
 };
-/// \brief Writable bool map for store each true assigned elements in
+/// \brief Writable bool map for storing each \c true assigned element in
 /// an insertable container.
 ///
-/// Writable bool map for store each true assigned elements in an
+/// Writable bool map for storing each \c true assigned element in an
 /// insertable container. It will insert all the keys set to \c true into
-/// the container. If you want to store the cut edges of the strongly
+/// the container.
+///
+/// For example, if you want to store the cut arcs of the strongly
 /// connected components in a set you can use the next code:
 ///
 ///\code
 /// set<Edge> cut_edges;
 /// InserterBoolMap<set<Edge> > inserter_map(cut_edges);
 /// stronglyConnectedCutEdges(graph, cost, inserter_map);
 ///\endcode
+///
+///\sa BackInserterBoolMap
+///\sa FrontInserterBoolMap
 template <typename Container,
 typename Functor =
 _maps_bits::Identity<typename Container::value_type> >
 class InserterBoolMap {
 public:
 typedef typename Container::value_type Key;
 typedef bool Value;
-/// Constructor
+/// Constructor with specified iterator
+/// Constructor with specified iterator.
+/// \param _container The container for storing the elements.
+/// \param _it The elements will be inserted before this iterator.
+/// \param _functor The functor that is used when an element is stored.
 InserterBoolMap(Container& _container, typename Container::iterator _it,
 const Functor& _functor = Functor())
 : container(_container), it(_it), functor(_functor) {}
 /// Constructor
+/// Constructor without specified iterator.
+/// The elements will be inserted before <tt>_container.end()</tt>.
+/// \param _container The container for storing the elements.
+/// \param _functor The functor that is used when an element is stored.
 InserterBoolMap(Container& _container, const Functor& _functor = Functor())
 : container(_container), it(_container.end()), functor(_functor) {}
-/// Setter function of the map
+/// The \c set function of the map
 void set(const Key& key, Value value) {
 if (value) {
-	it = container.insert(it, key);
+	it = container.insert(it, functor(key));
 ++it;
 }
 }
 private:
 Container& container;
 typename Container::iterator it;
 Functor functor;
 };
-/// \brief Fill the true set elements with a given value.
+/// \brief Writable bool map for filling each \c true assigned element with a
-///
+/// given value.
-/// Writable bool map to fill the elements set to \c true with a given value.
+///
-/// The value can set
+/// Writable bool map for filling each \c true assigned element with a
-/// the container.
+/// given value. The value can set the container.
 ///
-/// The next code finds the connected components of the undirected graph
+/// The following code finds the connected components of a graph
 /// and stores it in the \c comp map:
 ///\code
 /// typedef UGraph::NodeMap<int> ComponentMap;
 /// ComponentMap comp(ugraph);
 /// typedef FillBoolMap<UGraph::NodeMap<int> > ComponentFillerMap;
 /// Sets the current fill value
 void fillValue(const typename Map::Value& _fill) {
 fill = _fill;
 }
-/// Setter function of the map
+/// The \c set function of the map
 void set(const Key& key, Value value) {
 if (value) {
 	map.set(key, fill);
 }
 }
 Map& map;
 typename Map::Value fill;
 };
-/// \brief Writable bool map which stores for each true assigned elements
+/// \brief Writable bool map for storing the sequence number of
-/// the setting order number.
+/// \c true assignments.
 ///
-/// Writable bool map which stores for each true assigned elements
+/// Writable bool map that stores for each \c true assigned elements
-/// the setting order number. It make easy to calculate the leaving
+/// the sequence number of this setting.
+/// It makes it easy to calculate the leaving
 /// order of the nodes in the \c Dfs algorithm.
 ///
 ///\code
 /// typedef Graph::NodeMap<int> OrderMap;
 /// OrderMap order(graph);
 ///     dfs.start();
 ///   }
 /// }
 ///\endcode
 ///
-/// The discovering order can be stored a little harder because the
+/// The storing of the discovering order is more difficult because the
 /// ReachedMap should be readable in the dfs algorithm but the setting
-/// order map is not readable. Now we should use the fork map:
+/// order map is not readable. Thus we must use the fork map:
 ///
 ///\code
 /// typedef Graph::NodeMap<int> OrderMap;
 /// OrderMap order(graph);
 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
 /// Number of set operations.
 int num() const {
 return counter;
 }
-/// Setter function of the map
+/// The \c set function of the map
 void set(const Key& key, Value value) {
 if (value) {
 	map.set(key, counter++);
 }
 }

changeset 2583	7216b6a52ab9
parent 2553	bfced05fa852