1.1 --- a/lemon/maps.h Mon May 26 13:31:41 2008 +0200
1.2 +++ b/lemon/maps.h Mon May 26 13:50:47 2008 +0100
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 }