lemon/maps.h
changeset 162 33247f6fff16
parent 123 8899d1891a3c
child 167 d57ae6f0a335
equal deleted inserted replaced
19:3ccafee98600 20:d88b96802e40
  1672     return LessMap<M1, M2>(m1,m2);
  1672     return LessMap<M1, M2>(m1,m2);
  1673   }
  1673   }
  1674 
  1674 
  1675   namespace _maps_bits {
  1675   namespace _maps_bits {
  1676 
  1676 
  1677     template <typename Value>
       
  1678     struct Identity {
       
  1679       typedef Value argument_type;
       
  1680       typedef Value result_type;
       
  1681       Value operator()(const Value& val) const {
       
  1682 	return val;
       
  1683       }
       
  1684     };
       
  1685 
       
  1686     template <typename _Iterator, typename Enable = void>
  1677     template <typename _Iterator, typename Enable = void>
  1687     struct IteratorTraits {
  1678     struct IteratorTraits {
  1688       typedef typename std::iterator_traits<_Iterator>::value_type Value;
  1679       typedef typename std::iterator_traits<_Iterator>::value_type Value;
  1689     };
  1680     };
  1690 
  1681 
  1697 
  1688 
  1698   }
  1689   }
  1699 
  1690 
  1700   /// \brief Writable bool map for logging each \c true assigned element
  1691   /// \brief Writable bool map for logging each \c true assigned element
  1701   ///
  1692   ///
  1702   /// A \ref concepts::ReadWriteMap "read-write" bool map for logging
  1693   /// A \ref concepts::WriteMap "writable" bool map for logging
  1703   /// each \c true assigned element, i.e it copies subsequently each
  1694   /// each \c true assigned element, i.e it copies subsequently each
  1704   /// keys set to \c true to the given iterator.
  1695   /// keys set to \c true to the given iterator.
  1705   ///
  1696   /// The most important usage of it is storing certain nodes or arcs
  1706   /// \tparam It the type of the Iterator.
  1697   /// that were marked \c true by an algorithm.
  1707   /// \tparam Ke the type of the map's Key. The default value should
  1698   ///
  1708   /// work in most cases.
  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.
       
  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
       
  1703   /// easily done with StoreBoolMap.
       
  1704   ///
       
  1705   /// The simplest way of using this map is through the storeBoolMap()
       
  1706   /// function.
       
  1707   ///
       
  1708   /// \tparam It The type of the iterator.
       
  1709   /// \tparam Ke The key type of the map. The default value set
       
  1710   /// according to the iterator type should work in most cases.
  1709   ///
  1711   ///
  1710   /// \note The container of the iterator must contain enough space
  1712   /// \note The container of the iterator must contain enough space
  1711   /// for the elements. (Or it should be an inserter iterator).
  1713   /// for the elements or the iterator should be an inserter iterator.
  1712   ///
  1714 #ifdef DOXYGEN
  1713   /// \todo Revise the name of this class and give an example code.
  1715   template <typename It, typename Ke>
       
  1716 #else
  1714   template <typename It,
  1717   template <typename It,
  1715 	    typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
  1718 	    typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
       
  1719 #endif
  1716   class StoreBoolMap {
  1720   class StoreBoolMap {
  1717   public:
  1721   public:
  1718     typedef It Iterator;
  1722     typedef It Iterator;
  1719 
  1723 
  1720     typedef Ke Key;
  1724     typedef Ke Key;
  1733     Iterator end() const {
  1737     Iterator end() const {
  1734       return _end;
  1738       return _end;
  1735     }
  1739     }
  1736 
  1740 
  1737     /// The set function of the map
  1741     /// The set function of the map
  1738     void set(const Key& key, Value value) const {
  1742     void set(const Key& key, Value value) {
  1739       if (value) {
  1743       if (value) {
  1740 	*_end++ = key;
  1744 	*_end++ = key;
  1741       }
  1745       }
  1742     }
  1746     }
  1743 
  1747 
  1744   private:
  1748   private:
  1745     Iterator _begin;
  1749     Iterator _begin;
  1746     mutable Iterator _end;
  1750     Iterator _end;
  1747   };
  1751   };
       
  1752   
       
  1753   /// Returns a \ref StoreBoolMap class
       
  1754 
       
  1755   /// This function just returns a \ref StoreBoolMap class.
       
  1756   ///
       
  1757   /// The most important usage of it is storing certain nodes or arcs
       
  1758   /// that were marked \c true by an algorithm.
       
  1759   /// For example it makes easier to store the nodes in the processing
       
  1760   /// order of Dfs algorithm, as the following examples show.
       
  1761   /// \code
       
  1762   ///   std::vector<Node> v;
       
  1763   ///   dfs(g,s).processedMap(storeBoolMap(std::back_inserter(v))).run();
       
  1764   /// \endcode
       
  1765   /// \code
       
  1766   ///   std::vector<Node> v(countNodes(g));
       
  1767   ///   dfs(g,s).processedMap(storeBoolMap(v.begin())).run();
       
  1768   /// \endcode
       
  1769   ///
       
  1770   /// \note The container of the iterator must contain enough space
       
  1771   /// for the elements or the iterator should be an inserter iterator.
       
  1772   ///
       
  1773   /// \note StoreBoolMap is just \ref concepts::WriteMap "writable", so
       
  1774   /// it cannot be used when a readable map is needed, for example as
       
  1775   /// \c ReachedMap for Bfs, Dfs and Dijkstra algorithms.
       
  1776   ///
       
  1777   /// \relates StoreBoolMap
       
  1778   template<typename Iterator>
       
  1779   inline StoreBoolMap<Iterator> storeBoolMap(Iterator it) {
       
  1780     return StoreBoolMap<Iterator>(it);
       
  1781   }
  1748 
  1782 
  1749   /// @}
  1783   /// @}
  1750 }
  1784 }
  1751 
  1785 
  1752 #endif // LEMON_MAPS_H
  1786 #endif // LEMON_MAPS_H