1.1 --- a/lemon/maps.h Sat Mar 15 21:07:24 2008 +0100
1.2 +++ b/lemon/maps.h Sat Mar 15 21:24:43 2008 +0100
1.3 @@ -773,78 +773,6 @@
1.4 }
1.5
1.6
1.7 - /// Simple wrapping of a map
1.8 -
1.9 - /// This \ref concepts::ReadMap "read only map" returns the simple
1.10 - /// wrapping of the given map. Sometimes the reference maps cannot be
1.11 - /// combined with simple read maps. This map adaptor wraps the given
1.12 - /// map to simple read map.
1.13 - ///
1.14 - /// The simplest way of using this map is through the wrapMap()
1.15 - /// function.
1.16 - ///
1.17 - /// \sa WrapWriteMap
1.18 - template<typename M>
1.19 - class WrapMap : public MapBase<typename M::Key, typename M::Value> {
1.20 - const M &_m;
1.21 - public:
1.22 - typedef MapBase<typename M::Key, typename M::Value> Parent;
1.23 - typedef typename Parent::Key Key;
1.24 - typedef typename Parent::Value Value;
1.25 -
1.26 - /// Constructor
1.27 - WrapMap(const M &m) : _m(m) {}
1.28 - /// \e
1.29 - Value operator[](const Key &k) const { return _m[k]; }
1.30 - };
1.31 -
1.32 - /// Returns a \ref WrapMap class
1.33 -
1.34 - /// This function just returns a \ref WrapMap class.
1.35 - /// \relates WrapMap
1.36 - template<typename M>
1.37 - inline WrapMap<M> wrapMap(const M &map) {
1.38 - return WrapMap<M>(map);
1.39 - }
1.40 -
1.41 -
1.42 - /// Simple writable wrapping of a map
1.43 -
1.44 - /// This \ref concepts::ReadWriteMap "read-write map" returns the simple
1.45 - /// wrapping of the given map. Sometimes the reference maps cannot be
1.46 - /// combined with simple read-write maps. This map adaptor wraps the
1.47 - /// given map to simple read-write map.
1.48 - ///
1.49 - /// The simplest way of using this map is through the wrapWriteMap()
1.50 - /// function.
1.51 - ///
1.52 - /// \sa WrapMap
1.53 - template<typename M>
1.54 - class WrapWriteMap : public MapBase<typename M::Key, typename M::Value> {
1.55 - M &_m;
1.56 - public:
1.57 - typedef MapBase<typename M::Key, typename M::Value> Parent;
1.58 - typedef typename Parent::Key Key;
1.59 - typedef typename Parent::Value Value;
1.60 -
1.61 - /// Constructor
1.62 - WrapWriteMap(M &m) : _m(m) {}
1.63 - /// \e
1.64 - Value operator[](const Key &k) const { return _m[k]; }
1.65 - /// \e
1.66 - void set(const Key &k, const Value &c) { _m.set(k, c); }
1.67 - };
1.68 -
1.69 - ///Returns a \ref WrapWriteMap class
1.70 -
1.71 - ///This function just returns a \ref WrapWriteMap class.
1.72 - ///\relates WrapWriteMap
1.73 - template<typename M>
1.74 - inline WrapWriteMap<M> wrapWriteMap(M &map) {
1.75 - return WrapWriteMap<M>(map);
1.76 - }
1.77 -
1.78 -
1.79 /// Sum of two maps
1.80
1.81 /// This \ref concepts::ReadMap "read only map" returns the sum
1.82 @@ -1463,382 +1391,6 @@
1.83 return NotWriteMap<M>(m);
1.84 }
1.85
1.86 -
1.87 - namespace _maps_bits {
1.88 -
1.89 - template <typename Value>
1.90 - struct Identity {
1.91 - typedef Value argument_type;
1.92 - typedef Value result_type;
1.93 - Value operator()(const Value& val) const {
1.94 - return val;
1.95 - }
1.96 - };
1.97 -
1.98 - template <typename _Iterator, typename Enable = void>
1.99 - struct IteratorTraits {
1.100 - typedef typename std::iterator_traits<_Iterator>::value_type Value;
1.101 - };
1.102 -
1.103 - template <typename _Iterator>
1.104 - struct IteratorTraits<_Iterator,
1.105 - typename exists<typename _Iterator::container_type>::type>
1.106 - {
1.107 - typedef typename _Iterator::container_type::value_type Value;
1.108 - };
1.109 -
1.110 - }
1.111 -
1.112 -
1.113 - /// \brief Writable bool map for logging each \c true assigned element
1.114 - ///
1.115 - /// A \ref concepts::ReadWriteMap "read-write" bool map for logging
1.116 - /// each \c true assigned element, i.e it copies all the keys set
1.117 - /// to \c true to the given iterator.
1.118 - ///
1.119 - /// \note The container of the iterator should contain space
1.120 - /// for each element.
1.121 - ///
1.122 - /// The following example shows how you can write the edges found by
1.123 - /// the \ref Prim algorithm directly to the standard output.
1.124 - /// \code
1.125 - /// typedef IdMap<Graph, Edge> EdgeIdMap;
1.126 - /// EdgeIdMap edgeId(graph);
1.127 - ///
1.128 - /// typedef MapToFunctor<EdgeIdMap> EdgeIdFunctor;
1.129 - /// EdgeIdFunctor edgeIdFunctor(edgeId);
1.130 - ///
1.131 - /// StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor>
1.132 - /// writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor);
1.133 - ///
1.134 - /// prim(graph, cost, writerMap);
1.135 - /// \endcode
1.136 - ///
1.137 - /// \sa BackInserterBoolMap
1.138 - /// \sa FrontInserterBoolMap
1.139 - /// \sa InserterBoolMap
1.140 - ///
1.141 - /// \todo Revise the name of this class and the related ones.
1.142 - template <typename _Iterator,
1.143 - typename _Functor =
1.144 - _maps_bits::Identity<typename _maps_bits::
1.145 - IteratorTraits<_Iterator>::Value> >
1.146 - class StoreBoolMap {
1.147 - public:
1.148 - typedef _Iterator Iterator;
1.149 -
1.150 - typedef typename _Functor::argument_type Key;
1.151 - typedef bool Value;
1.152 -
1.153 - typedef _Functor Functor;
1.154 -
1.155 - /// Constructor
1.156 - StoreBoolMap(Iterator it, const Functor& functor = Functor())
1.157 - : _begin(it), _end(it), _functor(functor) {}
1.158 -
1.159 - /// Gives back the given iterator set for the first key
1.160 - Iterator begin() const {
1.161 - return _begin;
1.162 - }
1.163 -
1.164 - /// Gives back the the 'after the last' iterator
1.165 - Iterator end() const {
1.166 - return _end;
1.167 - }
1.168 -
1.169 - /// The set function of the map
1.170 - void set(const Key& key, Value value) const {
1.171 - if (value) {
1.172 - *_end++ = _functor(key);
1.173 - }
1.174 - }
1.175 -
1.176 - private:
1.177 - Iterator _begin;
1.178 - mutable Iterator _end;
1.179 - Functor _functor;
1.180 - };
1.181 -
1.182 - /// \brief Writable bool map for logging each \c true assigned element in
1.183 - /// a back insertable container.
1.184 - ///
1.185 - /// Writable bool map for logging each \c true assigned element by pushing
1.186 - /// them into a back insertable container.
1.187 - /// It can be used to retrieve the items into a standard
1.188 - /// container. The next example shows how you can store the
1.189 - /// edges found by the Prim algorithm in a vector.
1.190 - ///
1.191 - /// \code
1.192 - /// vector<Edge> span_tree_edges;
1.193 - /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges);
1.194 - /// prim(graph, cost, inserter_map);
1.195 - /// \endcode
1.196 - ///
1.197 - /// \sa StoreBoolMap
1.198 - /// \sa FrontInserterBoolMap
1.199 - /// \sa InserterBoolMap
1.200 - template <typename Container,
1.201 - typename Functor =
1.202 - _maps_bits::Identity<typename Container::value_type> >
1.203 - class BackInserterBoolMap {
1.204 - public:
1.205 - typedef typename Functor::argument_type Key;
1.206 - typedef bool Value;
1.207 -
1.208 - /// Constructor
1.209 - BackInserterBoolMap(Container& _container,
1.210 - const Functor& _functor = Functor())
1.211 - : container(_container), functor(_functor) {}
1.212 -
1.213 - /// The set function of the map
1.214 - void set(const Key& key, Value value) {
1.215 - if (value) {
1.216 - container.push_back(functor(key));
1.217 - }
1.218 - }
1.219 -
1.220 - private:
1.221 - Container& container;
1.222 - Functor functor;
1.223 - };
1.224 -
1.225 - /// \brief Writable bool map for logging each \c true assigned element in
1.226 - /// a front insertable container.
1.227 - ///
1.228 - /// Writable bool map for logging each \c true assigned element by pushing
1.229 - /// them into a front insertable container.
1.230 - /// It can be used to retrieve the items into a standard
1.231 - /// container. For example see \ref BackInserterBoolMap.
1.232 - ///
1.233 - /// \sa BackInserterBoolMap
1.234 - /// \sa InserterBoolMap
1.235 - template <typename Container,
1.236 - typename Functor =
1.237 - _maps_bits::Identity<typename Container::value_type> >
1.238 - class FrontInserterBoolMap {
1.239 - public:
1.240 - typedef typename Functor::argument_type Key;
1.241 - typedef bool Value;
1.242 -
1.243 - /// Constructor
1.244 - FrontInserterBoolMap(Container& _container,
1.245 - const Functor& _functor = Functor())
1.246 - : container(_container), functor(_functor) {}
1.247 -
1.248 - /// The set function of the map
1.249 - void set(const Key& key, Value value) {
1.250 - if (value) {
1.251 - container.push_front(functor(key));
1.252 - }
1.253 - }
1.254 -
1.255 - private:
1.256 - Container& container;
1.257 - Functor functor;
1.258 - };
1.259 -
1.260 - /// \brief Writable bool map for storing each \c true assigned element in
1.261 - /// an insertable container.
1.262 - ///
1.263 - /// Writable bool map for storing each \c true assigned element in an
1.264 - /// insertable container. It will insert all the keys set to \c true into
1.265 - /// the container.
1.266 - ///
1.267 - /// For example, if you want to store the cut arcs of the strongly
1.268 - /// connected components in a set you can use the next code:
1.269 - ///
1.270 - /// \code
1.271 - /// set<Arc> cut_arcs;
1.272 - /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs);
1.273 - /// stronglyConnectedCutArcs(digraph, cost, inserter_map);
1.274 - /// \endcode
1.275 - ///
1.276 - /// \sa BackInserterBoolMap
1.277 - /// \sa FrontInserterBoolMap
1.278 - template <typename Container,
1.279 - typename Functor =
1.280 - _maps_bits::Identity<typename Container::value_type> >
1.281 - class InserterBoolMap {
1.282 - public:
1.283 - typedef typename Container::value_type Key;
1.284 - typedef bool Value;
1.285 -
1.286 - /// Constructor with specified iterator
1.287 -
1.288 - /// Constructor with specified iterator.
1.289 - /// \param _container The container for storing the elements.
1.290 - /// \param _it The elements will be inserted before this iterator.
1.291 - /// \param _functor The functor that is used when an element is stored.
1.292 - InserterBoolMap(Container& _container, typename Container::iterator _it,
1.293 - const Functor& _functor = Functor())
1.294 - : container(_container), it(_it), functor(_functor) {}
1.295 -
1.296 - /// Constructor
1.297 -
1.298 - /// Constructor without specified iterator.
1.299 - /// The elements will be inserted before <tt>_container.end()</tt>.
1.300 - /// \param _container The container for storing the elements.
1.301 - /// \param _functor The functor that is used when an element is stored.
1.302 - InserterBoolMap(Container& _container, const Functor& _functor = Functor())
1.303 - : container(_container), it(_container.end()), functor(_functor) {}
1.304 -
1.305 - /// The set function of the map
1.306 - void set(const Key& key, Value value) {
1.307 - if (value) {
1.308 - it = container.insert(it, functor(key));
1.309 - ++it;
1.310 - }
1.311 - }
1.312 -
1.313 - private:
1.314 - Container& container;
1.315 - typename Container::iterator it;
1.316 - Functor functor;
1.317 - };
1.318 -
1.319 - /// \brief Writable bool map for filling each \c true assigned element with a
1.320 - /// given value.
1.321 - ///
1.322 - /// Writable bool map for filling each \c true assigned element with a
1.323 - /// given value. The value can set the container.
1.324 - ///
1.325 - /// The following code finds the connected components of a graph
1.326 - /// and stores it in the \c comp map:
1.327 - /// \code
1.328 - /// typedef Graph::NodeMap<int> ComponentMap;
1.329 - /// ComponentMap comp(graph);
1.330 - /// typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap;
1.331 - /// ComponentFillerMap filler(comp, 0);
1.332 - ///
1.333 - /// Dfs<Graph>::DefProcessedMap<ComponentFillerMap>::Create dfs(graph);
1.334 - /// dfs.processedMap(filler);
1.335 - /// dfs.init();
1.336 - /// for (NodeIt it(graph); it != INVALID; ++it) {
1.337 - /// if (!dfs.reached(it)) {
1.338 - /// dfs.addSource(it);
1.339 - /// dfs.start();
1.340 - /// ++filler.fillValue();
1.341 - /// }
1.342 - /// }
1.343 - /// \endcode
1.344 - template <typename Map>
1.345 - class FillBoolMap {
1.346 - public:
1.347 - typedef typename Map::Key Key;
1.348 - typedef bool Value;
1.349 -
1.350 - /// Constructor
1.351 - FillBoolMap(Map& _map, const typename Map::Value& _fill)
1.352 - : map(_map), fill(_fill) {}
1.353 -
1.354 - /// Constructor
1.355 - FillBoolMap(Map& _map)
1.356 - : map(_map), fill() {}
1.357 -
1.358 - /// Gives back the current fill value
1.359 - const typename Map::Value& fillValue() const {
1.360 - return fill;
1.361 - }
1.362 -
1.363 - /// Gives back the current fill value
1.364 - typename Map::Value& fillValue() {
1.365 - return fill;
1.366 - }
1.367 -
1.368 - /// Sets the current fill value
1.369 - void fillValue(const typename Map::Value& _fill) {
1.370 - fill = _fill;
1.371 - }
1.372 -
1.373 - /// The set function of the map
1.374 - void set(const Key& key, Value value) {
1.375 - if (value) {
1.376 - map.set(key, fill);
1.377 - }
1.378 - }
1.379 -
1.380 - private:
1.381 - Map& map;
1.382 - typename Map::Value fill;
1.383 - };
1.384 -
1.385 -
1.386 - /// \brief Writable bool map for storing the sequence number of
1.387 - /// \c true assignments.
1.388 - ///
1.389 - /// Writable bool map that stores for each \c true assigned elements
1.390 - /// the sequence number of this setting.
1.391 - /// It makes it easy to calculate the leaving
1.392 - /// order of the nodes in the \ref Dfs algorithm.
1.393 - ///
1.394 - /// \code
1.395 - /// typedef Digraph::NodeMap<int> OrderMap;
1.396 - /// OrderMap order(digraph);
1.397 - /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1.398 - /// OrderSetterMap setter(order);
1.399 - /// Dfs<Digraph>::DefProcessedMap<OrderSetterMap>::Create dfs(digraph);
1.400 - /// dfs.processedMap(setter);
1.401 - /// dfs.init();
1.402 - /// for (NodeIt it(digraph); it != INVALID; ++it) {
1.403 - /// if (!dfs.reached(it)) {
1.404 - /// dfs.addSource(it);
1.405 - /// dfs.start();
1.406 - /// }
1.407 - /// }
1.408 - /// \endcode
1.409 - ///
1.410 - /// The storing of the discovering order is more difficult because the
1.411 - /// ReachedMap should be readable in the dfs algorithm but the setting
1.412 - /// order map is not readable. Thus we must use the fork map:
1.413 - ///
1.414 - /// \code
1.415 - /// typedef Digraph::NodeMap<int> OrderMap;
1.416 - /// OrderMap order(digraph);
1.417 - /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1.418 - /// OrderSetterMap setter(order);
1.419 - /// typedef Digraph::NodeMap<bool> StoreMap;
1.420 - /// StoreMap store(digraph);
1.421 - ///
1.422 - /// typedef ForkMap<StoreMap, OrderSetterMap> ReachedMap;
1.423 - /// ReachedMap reached(store, setter);
1.424 - ///
1.425 - /// Dfs<Digraph>::DefReachedMap<ReachedMap>::Create dfs(digraph);
1.426 - /// dfs.reachedMap(reached);
1.427 - /// dfs.init();
1.428 - /// for (NodeIt it(digraph); it != INVALID; ++it) {
1.429 - /// if (!dfs.reached(it)) {
1.430 - /// dfs.addSource(it);
1.431 - /// dfs.start();
1.432 - /// }
1.433 - /// }
1.434 - /// \endcode
1.435 - template <typename Map>
1.436 - class SettingOrderBoolMap {
1.437 - public:
1.438 - typedef typename Map::Key Key;
1.439 - typedef bool Value;
1.440 -
1.441 - /// Constructor
1.442 - SettingOrderBoolMap(Map& _map)
1.443 - : map(_map), counter(0) {}
1.444 -
1.445 - /// Number of set operations.
1.446 - int num() const {
1.447 - return counter;
1.448 - }
1.449 -
1.450 - /// The set function of the map
1.451 - void set(const Key& key, Value value) {
1.452 - if (value) {
1.453 - map.set(key, counter++);
1.454 - }
1.455 - }
1.456 -
1.457 - private:
1.458 - Map& map;
1.459 - int counter;
1.460 - };
1.461 -
1.462 /// @}
1.463 }
1.464