1.1 --- a/lemon/maps.h	Sun May 25 17:01:11 2008 +0200
     1.2 +++ b/lemon/maps.h	Mon May 26 01:35:59 2008 +0200
     1.3 @@ -1674,15 +1674,6 @@
     1.4  
     1.5    namespace _maps_bits {
     1.6  
     1.7 -    template <typename Value>
     1.8 -    struct Identity {
     1.9 -      typedef Value argument_type;
    1.10 -      typedef Value result_type;
    1.11 -      Value operator()(const Value& val) const {
    1.12 -	return val;
    1.13 -      }
    1.14 -    };
    1.15 -
    1.16      template <typename _Iterator, typename Enable = void>
    1.17      struct IteratorTraits {
    1.18        typedef typename std::iterator_traits<_Iterator>::value_type Value;
    1.19 @@ -1699,20 +1690,33 @@
    1.20  
    1.21    /// \brief Writable bool map for logging each \c true assigned element
    1.22    ///
    1.23 -  /// A \ref concepts::ReadWriteMap "read-write" bool map for logging
    1.24 +  /// A \ref concepts::WriteMap "writable" bool map for logging
    1.25    /// each \c true assigned element, i.e it copies subsequently each
    1.26    /// keys set to \c true to the given iterator.
    1.27 +  /// The most important usage of it is storing certain nodes or arcs
    1.28 +  /// that were marked \c true by an algorithm.
    1.29    ///
    1.30 -  /// \tparam It the type of the Iterator.
    1.31 -  /// \tparam Ke the type of the map's Key. The default value should
    1.32 -  /// work in most cases.
    1.33 +  /// There are several algorithms that provide solutions through bool
    1.34 +  /// maps and most of them assign \c true at most once for each key.
    1.35 +  /// In these cases it is a natural request to store each \c true
    1.36 +  /// assigned elements (in order of the assignment), which can be
    1.37 +  /// easily done with StoreBoolMap.
    1.38 +  ///
    1.39 +  /// The simplest way of using this map is through the storeBoolMap()
    1.40 +  /// function.
    1.41 +  ///
    1.42 +  /// \tparam It The type of the iterator.
    1.43 +  /// \tparam Ke The key type of the map. The default value set
    1.44 +  /// according to the iterator type should work in most cases.
    1.45    ///
    1.46    /// \note The container of the iterator must contain enough space
    1.47 -  /// for the elements. (Or it should be an inserter iterator).
    1.48 -  ///
    1.49 -  /// \todo Revise the name of this class and give an example code.
    1.50 +  /// for the elements or the iterator should be an inserter iterator.
    1.51 +#ifdef DOXYGEN
    1.52 +  template <typename It, typename Ke>
    1.53 +#else
    1.54    template <typename It,
    1.55  	    typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
    1.56 +#endif
    1.57    class StoreBoolMap {
    1.58    public:
    1.59      typedef It Iterator;
    1.60 @@ -1735,7 +1739,7 @@
    1.61      }
    1.62  
    1.63      /// The set function of the map
    1.64 -    void set(const Key& key, Value value) const {
    1.65 +    void set(const Key& key, Value value) {
    1.66        if (value) {
    1.67  	*_end++ = key;
    1.68        }
    1.69 @@ -1743,8 +1747,38 @@
    1.70  
    1.71    private:
    1.72      Iterator _begin;
    1.73 -    mutable Iterator _end;
    1.74 +    Iterator _end;
    1.75    };
    1.76 +  
    1.77 +  /// Returns a \ref StoreBoolMap class
    1.78 +
    1.79 +  /// This function just returns a \ref StoreBoolMap class.
    1.80 +  ///
    1.81 +  /// The most important usage of it is storing certain nodes or arcs
    1.82 +  /// that were marked \c true by an algorithm.
    1.83 +  /// For example it makes easier to store the nodes in the processing
    1.84 +  /// order of Dfs algorithm, as the following examples show.
    1.85 +  /// \code
    1.86 +  ///   std::vector<Node> v;
    1.87 +  ///   dfs(g,s).processedMap(storeBoolMap(std::back_inserter(v))).run();
    1.88 +  /// \endcode
    1.89 +  /// \code
    1.90 +  ///   std::vector<Node> v(countNodes(g));
    1.91 +  ///   dfs(g,s).processedMap(storeBoolMap(v.begin())).run();
    1.92 +  /// \endcode
    1.93 +  ///
    1.94 +  /// \note The container of the iterator must contain enough space
    1.95 +  /// for the elements or the iterator should be an inserter iterator.
    1.96 +  ///
    1.97 +  /// \note StoreBoolMap is just \ref concepts::WriteMap "writable", so
    1.98 +  /// it cannot be used when a readable map is needed, for example as
    1.99 +  /// \c ReachedMap for Bfs, Dfs and Dijkstra algorithms.
   1.100 +  ///
   1.101 +  /// \relates StoreBoolMap
   1.102 +  template<typename Iterator>
   1.103 +  inline StoreBoolMap<Iterator> storeBoolMap(Iterator it) {
   1.104 +    return StoreBoolMap<Iterator>(it);
   1.105 +  }
   1.106  
   1.107    /// @}
   1.108  }