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 |