/// Simple wrapping of a map

   /// 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.

   ///

   /// The simplest way of using this map is through the wrapMap()

   /// function.

   ///

   /// \sa WrapWriteMap

   template<typename M>

   class WrapMap : public MapBase<typename M::Key, typename M::Value> {

     const M &_m;

   public:

     typedef MapBase<typename M::Key, typename M::Value> Parent;

     typedef typename Parent::Key Key;

     typedef typename Parent::Value Value;

     /// Constructor

     WrapMap(const M &m) : _m(m) {}

     /// \e

     Value operator[](const Key &k) const { return _m[k]; }

   };

   /// Returns a \ref WrapMap class

   /// This function just returns a \ref WrapMap class.

   /// \relates WrapMap

   template<typename M>

   inline WrapMap<M> wrapMap(const M &map) {

     return WrapMap<M>(map);

   }

   /// 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.

   ///

   /// The simplest way of using this map is through the wrapWriteMap()

   /// function.

   ///

   /// \sa WrapMap

   template<typename M>

   class WrapWriteMap : public MapBase<typename M::Key, typename M::Value> {

     M &_m;

   public:

     typedef MapBase<typename M::Key, typename M::Value> Parent;

     typedef typename Parent::Key Key;

     typedef typename Parent::Value Value;

     /// Constructor

     WrapWriteMap(M &m) : _m(m) {}

     /// \e

     Value operator[](const Key &k) const { return _m[k]; }

     /// \e

     void set(const Key &k, const Value &c) { _m.set(k, c); }

   };

   ///Returns a \ref WrapWriteMap class

   ///This function just returns a \ref WrapWriteMap class.

   ///\relates WrapWriteMap

   template<typename M>

   inline WrapWriteMap<M> wrapWriteMap(M &map) {

     return WrapWriteMap<M>(map);

   }

   namespace _maps_bits {

     template <typename Value>

     struct Identity {

       typedef Value argument_type;

       typedef Value result_type;

       Value operator()(const Value& val) const {

 	return val;

       }

     };

     template <typename _Iterator, typename Enable = void>

     struct IteratorTraits {

       typedef typename std::iterator_traits<_Iterator>::value_type Value;

     };

     template <typename _Iterator>

     struct IteratorTraits<_Iterator,

       typename exists<typename _Iterator::container_type>::type>

     {

       typedef typename _Iterator::container_type::value_type Value;

     };

   }

   /// \brief Writable bool map for logging each \c true assigned element

   ///

   /// A \ref concepts::ReadWriteMap "read-write" bool map for logging

   /// 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 following example shows how you can write the edges found by

   /// the \ref Prim algorithm directly to the standard output.

   /// \code

   ///   typedef IdMap<Graph, Edge> EdgeIdMap;

   ///   EdgeIdMap edgeId(graph);

   ///

   ///   typedef MapToFunctor<EdgeIdMap> EdgeIdFunctor;

   ///   EdgeIdFunctor edgeIdFunctor(edgeId);

   ///

   ///   StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor>

   ///     writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor);

   ///

   ///   prim(graph, cost, writerMap);

   /// \endcode

   ///

   /// \sa BackInserterBoolMap

   /// \sa FrontInserterBoolMap

   /// \sa InserterBoolMap

   ///

   /// \todo Revise the name of this class and the related ones.

   template <typename _Iterator,

             typename _Functor =

             _maps_bits::Identity<typename _maps_bits::

                                  IteratorTraits<_Iterator>::Value> >

   class StoreBoolMap {

   public:

     typedef _Iterator Iterator;

     typedef typename _Functor::argument_type Key;

     typedef bool Value;

     typedef _Functor Functor;

     /// Constructor

     StoreBoolMap(Iterator it, const Functor& functor = Functor())

       : _begin(it), _end(it), _functor(functor) {}

     /// Gives back the given iterator set for the first key

     Iterator begin() const {

       return _begin;

     }

     /// Gives back the the 'after the last' iterator

     Iterator end() const {

       return _end;

     }

     /// The set function of the map

     void set(const Key& key, Value value) const {

       if (value) {

 	*_end++ = _functor(key);

       }

     }

   private:

     Iterator _begin;

     mutable Iterator _end;

     Functor _functor;

   };

   /// \brief Writable bool map for logging each \c true assigned element in

   /// a back insertable container.

   ///

   /// Writable bool map for logging each \c true assigned element by pushing

   /// them into a back insertable container.

   /// It can be used to retrieve the items into a standard

   /// container. The next example shows how you can store the

   /// edges found by the Prim algorithm in a vector.

   ///

   /// \code

   ///   vector<Edge> span_tree_edges;

   ///   BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges);

   ///   prim(graph, 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 Functor::argument_type Key;

     typedef bool Value;

     /// Constructor

     BackInserterBoolMap(Container& _container,

                         const Functor& _functor = Functor())

       : container(_container), functor(_functor) {}

     /// The 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 logging each \c true assigned element in

   /// a front insertable container.

   ///

   /// Writable bool map for logging each \c true assigned element by pushing

   /// them into a front insertable container.

   /// 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 Functor::argument_type Key;

     typedef bool Value;

     /// Constructor

     FrontInserterBoolMap(Container& _container,

                          const Functor& _functor = Functor())

       : container(_container), functor(_functor) {}

     /// The set function of the map

     void set(const Key& key, Value value) {

       if (value) {

 	container.push_front(functor(key));

       }

     }

   private:

     Container& container;

     Functor functor;

   };

   /// \brief Writable bool map for storing each \c true assigned element in

   /// an insertable container.

   ///

   /// 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.

   ///

   /// 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<Arc> cut_arcs;

   ///   InserterBoolMap<set<Arc> > inserter_map(cut_arcs);

   ///   stronglyConnectedCutArcs(digraph, 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 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) {}

     /// The set function of the map

     void set(const Key& key, Value value) {

       if (value) {

 	it = container.insert(it, functor(key));

         ++it;

       }

     }

   private:

     Container& container;

     typename Container::iterator it;

     Functor functor;

   };

   /// \brief Writable bool map for filling each \c true assigned element with a

   /// given value.

   ///

   /// Writable bool map for filling each \c true assigned element with a

   /// given value. The value can set the container.

   ///

   /// The following code finds the connected components of a graph

   /// and stores it in the \c comp map:

   /// \code

   ///   typedef Graph::NodeMap<int> ComponentMap;

   ///   ComponentMap comp(graph);

   ///   typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap;

   ///   ComponentFillerMap filler(comp, 0);

   ///

   ///   Dfs<Graph>::DefProcessedMap<ComponentFillerMap>::Create dfs(graph);

   ///   dfs.processedMap(filler);

   ///   dfs.init();

   ///   for (NodeIt it(graph); it != INVALID; ++it) {

   ///     if (!dfs.reached(it)) {

   ///       dfs.addSource(it);

   ///       dfs.start();

   ///       ++filler.fillValue();

   ///     }

   ///   }

   /// \endcode

   template <typename Map>

   class FillBoolMap {

   public:

     typedef typename Map::Key Key;

     typedef bool Value;

     /// Constructor

     FillBoolMap(Map& _map, const typename Map::Value& _fill)

       : map(_map), fill(_fill) {}

     /// Constructor

     FillBoolMap(Map& _map)

       : map(_map), fill() {}

     /// Gives back the current fill value

     const typename Map::Value& fillValue() const {

       return fill;

     }

     /// Gives back the current fill value

     typename Map::Value& fillValue() {

       return fill;

     }

     /// Sets the current fill value

     void fillValue(const typename Map::Value& _fill) {

       fill = _fill;

     }

     /// The set function of the map

     void set(const Key& key, Value value) {

       if (value) {

 	map.set(key, fill);

       }

     }

   private:

     Map& map;

     typename Map::Value fill;

   };

   /// \brief Writable bool map for storing the sequence number of

   /// \c true assignments.

   ///

   /// Writable bool map that stores for each \c true assigned elements

   /// the sequence number of this setting.

   /// It makes it easy to calculate the leaving

   /// order of the nodes in the \ref Dfs algorithm.

   ///

   /// \code

   ///   typedef Digraph::NodeMap<int> OrderMap;

   ///   OrderMap order(digraph);

   ///   typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;

   ///   OrderSetterMap setter(order);

   ///   Dfs<Digraph>::DefProcessedMap<OrderSetterMap>::Create dfs(digraph);

   ///   dfs.processedMap(setter);

   ///   dfs.init();

   ///   for (NodeIt it(digraph); it != INVALID; ++it) {

   ///     if (!dfs.reached(it)) {

   ///       dfs.addSource(it);

   ///       dfs.start();

   ///     }

   ///   }

   /// \endcode

   ///

   /// 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. Thus we must use the fork map:

   ///

   /// \code

   ///   typedef Digraph::NodeMap<int> OrderMap;

   ///   OrderMap order(digraph);

   ///   typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;

   ///   OrderSetterMap setter(order);

   ///   typedef Digraph::NodeMap<bool> StoreMap;

   ///   StoreMap store(digraph);

   ///

   ///   typedef ForkMap<StoreMap, OrderSetterMap> ReachedMap;

   ///   ReachedMap reached(store, setter);

   ///

   ///   Dfs<Digraph>::DefReachedMap<ReachedMap>::Create dfs(digraph);

   ///   dfs.reachedMap(reached);

   ///   dfs.init();

   ///   for (NodeIt it(digraph); it != INVALID; ++it) {

   ///     if (!dfs.reached(it)) {

   ///       dfs.addSource(it);

   ///       dfs.start();

   ///     }

   ///   }

   /// \endcode

   template <typename Map>

   class SettingOrderBoolMap {

   public:

     typedef typename Map::Key Key;

     typedef bool Value;

     /// Constructor

     SettingOrderBoolMap(Map& _map)

       : map(_map), counter(0) {}

     /// Number of set operations.

     int num() const {

       return counter;

     }

     /// The set function of the map

     void set(const Key& key, Value value) {

       if (value) {

 	map.set(key, counter++);

       }

     }

   private:

     Map& map;

     int counter;

   };