lemon/maps.h
changeset 203 215bfc30b14f
parent 159 c7d30f7810e5
child 209 765619b7cbb2
equal deleted inserted replaced
20:d88b96802e40 21:448562babf44
  1698   ///
  1698   ///
  1699   /// There are several algorithms that provide solutions through bool
  1699   /// There are several algorithms that provide solutions through bool
  1700   /// maps and most of them assign \c true at most once for each key.
  1700   /// maps and most of them assign \c true at most once for each key.
  1701   /// In these cases it is a natural request to store each \c true
  1701   /// In these cases it is a natural request to store each \c true
  1702   /// assigned elements (in order of the assignment), which can be
  1702   /// assigned elements (in order of the assignment), which can be
  1703   /// easily done with StoreBoolMap.
  1703   /// easily done with LoggerBoolMap.
  1704   ///
  1704   ///
  1705   /// The simplest way of using this map is through the storeBoolMap()
  1705   /// The simplest way of using this map is through the loggerBoolMap()
  1706   /// function.
  1706   /// function.
  1707   ///
  1707   ///
  1708   /// \tparam It The type of the iterator.
  1708   /// \tparam It The type of the iterator.
  1709   /// \tparam Ke The key type of the map. The default value set
  1709   /// \tparam Ke The key type of the map. The default value set
  1710   /// according to the iterator type should work in most cases.
  1710   /// according to the iterator type should work in most cases.
  1715   template <typename It, typename Ke>
  1715   template <typename It, typename Ke>
  1716 #else
  1716 #else
  1717   template <typename It,
  1717   template <typename It,
  1718 	    typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
  1718 	    typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
  1719 #endif
  1719 #endif
  1720   class StoreBoolMap {
  1720   class LoggerBoolMap {
  1721   public:
  1721   public:
  1722     typedef It Iterator;
  1722     typedef It Iterator;
  1723 
  1723 
  1724     typedef Ke Key;
  1724     typedef Ke Key;
  1725     typedef bool Value;
  1725     typedef bool Value;
  1726 
  1726 
  1727     /// Constructor
  1727     /// Constructor
  1728     StoreBoolMap(Iterator it)
  1728     LoggerBoolMap(Iterator it)
  1729       : _begin(it), _end(it) {}
  1729       : _begin(it), _end(it) {}
  1730 
  1730 
  1731     /// Gives back the given iterator set for the first key
  1731     /// Gives back the given iterator set for the first key
  1732     Iterator begin() const {
  1732     Iterator begin() const {
  1733       return _begin;
  1733       return _begin;
  1748   private:
  1748   private:
  1749     Iterator _begin;
  1749     Iterator _begin;
  1750     Iterator _end;
  1750     Iterator _end;
  1751   };
  1751   };
  1752   
  1752   
  1753   /// Returns a \ref StoreBoolMap class
  1753   /// Returns a \ref LoggerBoolMap class
  1754 
  1754 
  1755   /// This function just returns a \ref StoreBoolMap class.
  1755   /// This function just returns a \ref LoggerBoolMap class.
  1756   ///
  1756   ///
  1757   /// The most important usage of it is storing certain nodes or arcs
  1757   /// The most important usage of it is storing certain nodes or arcs
  1758   /// that were marked \c true by an algorithm.
  1758   /// that were marked \c true by an algorithm.
  1759   /// For example it makes easier to store the nodes in the processing
  1759   /// For example it makes easier to store the nodes in the processing
  1760   /// order of Dfs algorithm, as the following examples show.
  1760   /// order of Dfs algorithm, as the following examples show.
  1761   /// \code
  1761   /// \code
  1762   ///   std::vector<Node> v;
  1762   ///   std::vector<Node> v;
  1763   ///   dfs(g,s).processedMap(storeBoolMap(std::back_inserter(v))).run();
  1763   ///   dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
  1764   /// \endcode
  1764   /// \endcode
  1765   /// \code
  1765   /// \code
  1766   ///   std::vector<Node> v(countNodes(g));
  1766   ///   std::vector<Node> v(countNodes(g));
  1767   ///   dfs(g,s).processedMap(storeBoolMap(v.begin())).run();
  1767   ///   dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
  1768   /// \endcode
  1768   /// \endcode
  1769   ///
  1769   ///
  1770   /// \note The container of the iterator must contain enough space
  1770   /// \note The container of the iterator must contain enough space
  1771   /// for the elements or the iterator should be an inserter iterator.
  1771   /// for the elements or the iterator should be an inserter iterator.
  1772   ///
  1772   ///
  1773   /// \note StoreBoolMap is just \ref concepts::WriteMap "writable", so
  1773   /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
  1774   /// it cannot be used when a readable map is needed, for example as
  1774   /// it cannot be used when a readable map is needed, for example as
  1775   /// \c ReachedMap for Bfs, Dfs and Dijkstra algorithms.
  1775   /// \c ReachedMap for \ref Bfs, \ref Dfs and \ref Dijkstra algorithms.
  1776   ///
  1776   ///
  1777   /// \relates StoreBoolMap
  1777   /// \relates LoggerBoolMap
  1778   template<typename Iterator>
  1778   template<typename Iterator>
  1779   inline StoreBoolMap<Iterator> storeBoolMap(Iterator it) {
  1779   inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
  1780     return StoreBoolMap<Iterator>(it);
  1780     return LoggerBoolMap<Iterator>(it);
  1781   }
  1781   }
  1782 
  1782 
  1783   /// @}
  1783   /// @}
  1784 }
  1784 }
  1785 
  1785