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 |