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  }

     2.1 --- a/test/maps_test.cc	Sun May 25 17:01:11 2008 +0200
     2.2 +++ b/test/maps_test.cc	Mon May 26 01:35:59 2008 +0200
     2.3 @@ -304,6 +304,28 @@
     2.4      check(!equalMap(id,cm)[1] && equalMap(id,cm)[2] && !equalMap(id,cm)[3],
     2.5            "Something is wrong with EqualMap");
     2.6    }
     2.7 +  
     2.8 +  // StoreBoolMap
     2.9 +  {
    2.10 +    typedef std::vector<int> vec;
    2.11 +    vec v1;
    2.12 +    vec v2(10);
    2.13 +    StoreBoolMap<std::back_insert_iterator<vec> > map1(std::back_inserter(v1));
    2.14 +    StoreBoolMap<vec::iterator> map2(v2.begin());
    2.15 +    map1.set(10, false);
    2.16 +    map1.set(20, true);   map2.set(20, true);
    2.17 +    map1.set(30, false);  map2.set(40, false);
    2.18 +    map1.set(50, true);   map2.set(50, true);
    2.19 +    map1.set(60, true);   map2.set(60, true);
    2.20 +    check(v1.size() == 3 && v2.size() == 10 &&
    2.21 +          v1[0]==20 && v1[1]==50 && v1[2]==60 && v2[0]==20 && v2[1]==50 && v2[2]==60,
    2.22 +          "Something is wrong with StoreBoolMap");
    2.23 +          
    2.24 +    int i = 0;
    2.25 +    for ( StoreBoolMap<vec::iterator>::Iterator it = map2.begin();
    2.26 +          it != map2.end(); ++it )
    2.27 +      check(v1[i++] == *it, "Something is wrong with StoreBoolMap");
    2.28 +  }
    2.29  
    2.30    return 0;
    2.31  }