1.1 --- a/lemon/concept_check.h Sat Dec 22 12:35:00 2007 +0000
1.2 +++ b/lemon/concept_check.h Sat Dec 22 14:04:22 2007 +0000
1.3 @@ -16,10 +16,10 @@
1.4 *
1.5 */
1.6
1.7 -// Modified for use in LEMON.
1.8 -// We should really consider using Boost...
1.9 +// This file contains a modified version of the concept checking
1.10 +// utility from BOOST.
1.11 +// See the appropriate copyright notice below.
1.12
1.13 -//
1.14 // (C) Copyright Jeremy Siek 2000.
1.15 // Distributed under the Boost Software License, Version 1.0. (See
1.16 // accompanying file LICENSE_1_0.txt or copy at
2.1 --- a/lemon/maps.h Sat Dec 22 12:35:00 2007 +0000
2.2 +++ b/lemon/maps.h Sat Dec 22 14:04:22 2007 +0000
2.3 @@ -247,7 +247,9 @@
2.4 /// The current map has the \c [0..size-1] keyset and the values
2.5 /// are stored in a \c std::vector<T> container. It can be used with
2.6 /// some data structures, for example \c UnionFind, \c BinHeap, when
2.7 - /// the used items are small integer numbers.
2.8 + /// the used items are small integer numbers.
2.9 + ///
2.10 + /// \todo Revise its name
2.11 template <typename T>
2.12 class IntegerMap {
2.13
2.14 @@ -346,8 +348,9 @@
2.15 }
2.16
2.17
2.18 - ///Convert the \c Value of a map to another type.
2.19 -
2.20 + ///\brief Convert the \c Value of a map to another type using
2.21 + ///the default conversion.
2.22 + ///
2.23 ///This \c concepts::ReadMap "read only map"
2.24 ///converts the \c Value of a maps to type \c T.
2.25 ///Its \c Key is inherited from \c M.
2.26 @@ -368,8 +371,6 @@
2.27 /// \brief The subscript operator.
2.28 ///
2.29 /// The subscript operator.
2.30 - /// \param k The key
2.31 - /// \return The target of the arc
2.32 Value operator[](const Key& k) const {return m[k];}
2.33 };
2.34
2.35 @@ -388,6 +389,8 @@
2.36 ///wrapping of the given map. Sometimes the reference maps cannot be
2.37 ///combined with simple read maps. This map adaptor wraps the given
2.38 ///map to simple read map.
2.39 + ///
2.40 + /// \todo Revise the misleading name
2.41 template<typename M>
2.42 class SimpleMap : public MapBase<typename M::Key, typename M::Value> {
2.43 const M& m;
2.44 @@ -405,10 +408,12 @@
2.45
2.46 ///Simple writeable wrapping of the map
2.47
2.48 - ///This \c concepts::ReadMap "read only map" returns the simple
2.49 + ///This \c concepts::WriteMap "write map" returns the simple
2.50 ///wrapping of the given map. Sometimes the reference maps cannot be
2.51 ///combined with simple read-write maps. This map adaptor wraps the
2.52 ///given map to simple read-write map.
2.53 + ///
2.54 + /// \todo Revise the misleading name
2.55 template<typename M>
2.56 class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> {
2.57 M& m;
2.58 @@ -493,7 +498,7 @@
2.59 Value operator[](Key k) const {return m[k] + v;}
2.60 };
2.61
2.62 - ///Shift a map with a constant.
2.63 + ///Shift a map with a constant. This map is also writable.
2.64
2.65 ///This \c concepts::ReadWriteMap "read-write map" returns the sum of the
2.66 ///given map and a constant value. It makes also possible to write the map.
2.67 @@ -549,7 +554,8 @@
2.68 ///of the values of the two
2.69 ///given maps. Its \c Key and \c Value will be inherited from \c M1.
2.70 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
2.71 -
2.72 + ///
2.73 + /// \todo Revise the misleading name
2.74 template<typename M1, typename M2>
2.75 class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
2.76 const M1& m1;
2.77 @@ -641,7 +647,7 @@
2.78 Value operator[](Key k) const {return v * m[k];}
2.79 };
2.80
2.81 - ///Scales a maps with a constant.
2.82 + ///Scales a maps with a constant (ReadWrite version).
2.83
2.84 ///This \c concepts::ReadWriteMap "read-write map" returns the value of the
2.85 ///given map multiplied from the left side with a constant value. It can
2.86 @@ -858,7 +864,7 @@
2.87 Value operator[](Key k) const {return -m[k];}
2.88 };
2.89
2.90 - ///Negative value of a map
2.91 + ///Negative value of a map (ReadWrite version)
2.92
2.93 ///This \c concepts::ReadWriteMap "read-write map" returns the negative
2.94 ///value of the value returned by the
2.95 @@ -905,18 +911,6 @@
2.96 ///must be comparable to <tt>0</tt> and the unary <tt>-</tt>
2.97 ///operator must be defined for it, of course.
2.98 ///
2.99 - ///\bug We need a unified way to handle the situation below:
2.100 - ///\code
2.101 - /// struct _UnConvertible {};
2.102 - /// template<class A> inline A t_abs(A a) {return _UnConvertible();}
2.103 - /// template<> inline int t_abs<>(int n) {return abs(n);}
2.104 - /// template<> inline long int t_abs<>(long int n) {return labs(n);}
2.105 - /// template<> inline long long int t_abs<>(long long int n) {return ::llabs(n);}
2.106 - /// template<> inline float t_abs<>(float n) {return fabsf(n);}
2.107 - /// template<> inline double t_abs<>(double n) {return fabs(n);}
2.108 - /// template<> inline long double t_abs<>(long double n) {return fabsl(n);}
2.109 - ///\endcode
2.110 -
2.111
2.112 template<typename M>
2.113 class AbsMap : public MapBase<typename M::Key, typename M::Value> {
2.114 @@ -1041,6 +1035,8 @@
2.115 ///
2.116 ///The \c Key and \c Value will be inherited from \c M1.
2.117 ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
2.118 + ///
2.119 + /// \todo Why is it needed?
2.120 template<typename M1, typename M2>
2.121 class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
2.122 const M1& m1;
2.123 @@ -1124,7 +1120,7 @@
2.124 Value operator[](Key k) const {return !m[k];}
2.125 };
2.126
2.127 - ///Logical 'not' of a map with writing possibility
2.128 + ///Logical 'not' of a map (ReadWrie version)
2.129
2.130 ///This bool \c concepts::ReadWriteMap "read-write map" returns the
2.131 ///logical negation of value returned by the given map. When it is set,
2.132 @@ -1187,15 +1183,16 @@
2.133 }
2.134
2.135
2.136 - /// \brief Writable bool map for store each true assigned elements.
2.137 + /// \brief Writable bool map for logging each true assigned elements
2.138 ///
2.139 - /// Writable bool map to store each true assigned elements. It will
2.140 + /// Writable bool map for logging each true assigned elements, i.e it
2.141 /// copies all the keys set to true to the given iterator.
2.142 ///
2.143 /// \note The container of the iterator should contain space
2.144 /// for each element.
2.145 ///
2.146 - /// The next example shows how can you write the nodes directly
2.147 + /// The following example shows how you can write the edges found by the Prim
2.148 + /// algorithm directly
2.149 /// to the standard output.
2.150 ///\code
2.151 /// typedef IdMap<Graph, Edge> EdgeIdMap;
2.152 @@ -1209,6 +1206,8 @@
2.153 ///
2.154 /// prim(graph, cost, writerMap);
2.155 ///\endcode
2.156 + ///
2.157 + ///\todo Revise the name of this class and the relates ones.
2.158 template <typename _Iterator,
2.159 typename _Functor =
2.160 _maps_bits::Identity<typename _maps_bits::
2.161 @@ -1226,12 +1225,12 @@
2.162 StoreBoolMap(Iterator it, const Functor& functor = Functor())
2.163 : _begin(it), _end(it), _functor(functor) {}
2.164
2.165 - /// Gives back the given iterator set for the first time.
2.166 + /// Gives back the given iterator set for the first key
2.167 Iterator begin() const {
2.168 return _begin;
2.169 }
2.170
2.171 - /// Gives back the iterator after the last set operation.
2.172 + /// Gives back the the 'after the last' iterator
2.173 Iterator end() const {
2.174 return _end;
2.175 }
2.176 @@ -1249,14 +1248,14 @@
2.177 Functor _functor;
2.178 };
2.179
2.180 - /// \brief Writable bool map for store each true assigned elements in
2.181 - /// a back insertable container.
2.182 + /// \brief Writable bool map for logging each true assigned elements in
2.183 + /// a back insertable container
2.184 ///
2.185 - /// Writable bool map for store each true assigned elements in a back
2.186 - /// insertable container. It will push back all the keys set to true into
2.187 - /// the container. It can be used to retrieve the items into a standard
2.188 - /// container. The next example shows how can you store the undirected
2.189 - /// arcs in a vector with prim algorithm.
2.190 + /// Writable bool map for logging each true assigned elements by pushing
2.191 + /// back them into a back insertable container.
2.192 + /// It can be used to retrieve the items into a standard
2.193 + /// container. The next example shows how you can store the
2.194 + /// edges found by the Prim algorithm in a vector.
2.195 ///
2.196 ///\code
2.197 /// vector<Edge> span_tree_edges;
2.198 @@ -1288,10 +1287,10 @@
2.199 Functor functor;
2.200 };
2.201
2.202 - /// \brief Writable bool map for store each true assigned elements in
2.203 + /// \brief Writable bool map for storing each true assignments in
2.204 /// a front insertable container.
2.205 ///
2.206 - /// Writable bool map for store each true assigned elements in a front
2.207 + /// Writable bool map for storing each true assignment in a front
2.208 /// insertable container. It will push front all the keys set to \c true into
2.209 /// the container. For example see the BackInserterBoolMap.
2.210 template <typename Container,
2.211 @@ -1319,12 +1318,14 @@
2.212 Functor functor;
2.213 };
2.214
2.215 - /// \brief Writable bool map for store each true assigned elements in
2.216 + /// \brief Writable bool map for storing each true assigned elements in
2.217 /// an insertable container.
2.218 ///
2.219 - /// Writable bool map for store each true assigned elements in an
2.220 + /// Writable bool map for storing each true assigned elements in an
2.221 /// insertable container. It will insert all the keys set to \c true into
2.222 - /// the container. If you want to store the cut arcs of the strongly
2.223 + /// the container.
2.224 + ///
2.225 + /// For example, if you want to store the cut arcs of the strongly
2.226 /// connected components in a set you can use the next code:
2.227 ///
2.228 ///\code
2.229 @@ -1369,7 +1370,7 @@
2.230 /// The value can set
2.231 /// the container.
2.232 ///
2.233 - /// The next code finds the connected components of the undirected digraph
2.234 + /// The following code finds the connected components of a graph
2.235 /// and stores it in the \c comp map:
2.236 ///\code
2.237 /// typedef Graph::NodeMap<int> ComponentMap;
2.238 @@ -1417,7 +1418,7 @@
2.239 fill = _fill;
2.240 }
2.241
2.242 - /// Setter function of the map
2.243 + /// Set function of the map
2.244 void set(const Key& key, Value value) {
2.245 if (value) {
2.246 map.set(key, fill);
2.247 @@ -1430,11 +1431,12 @@
2.248 };
2.249
2.250
2.251 - /// \brief Writable bool map which stores for each true assigned elements
2.252 - /// the setting order number.
2.253 - ///
2.254 + /// \brief Writable bool map which stores the sequence number of
2.255 + /// true assignments.
2.256 + ///
2.257 /// Writable bool map which stores for each true assigned elements
2.258 - /// the setting order number. It make easy to calculate the leaving
2.259 + /// the sequence number of this setting.
2.260 + /// It makes it easy to calculate the leaving
2.261 /// order of the nodes in the \c Dfs algorithm.
2.262 ///
2.263 ///\code
2.264 @@ -1453,9 +1455,9 @@
2.265 /// }
2.266 ///\endcode
2.267 ///
2.268 - /// The discovering order can be stored a little harder because the
2.269 + /// The storing of the discovering order is more difficult because the
2.270 /// ReachedMap should be readable in the dfs algorithm but the setting
2.271 - /// order map is not readable. Now we should use the fork map:
2.272 + /// order map is not readable. Thus we must use the fork map:
2.273 ///
2.274 ///\code
2.275 /// typedef Digraph::NodeMap<int> OrderMap;