Changeset 159:c7d30f7810e5 in lemon-main
- Timestamp:
- 05/26/08 01:35:59 (16 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/maps.h
r123 r159 1675 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 1677 template <typename _Iterator, typename Enable = void> 1687 1678 struct IteratorTraits { … … 1700 1691 /// \brief Writable bool map for logging each \c true assigned element 1701 1692 /// 1702 /// A \ref concepts:: ReadWriteMap "read-write" bool map for logging1693 /// A \ref concepts::WriteMap "writable" bool map for logging 1703 1694 /// each \c true assigned element, i.e it copies subsequently each 1704 1695 /// keys set to \c true to the given iterator. 1705 /// 1706 /// \tparam It the type of the Iterator. 1707 /// \tparam Ke the type of the map's Key. The default value should 1708 /// work in most cases. 1696 /// The most important usage of it is storing certain nodes or arcs 1697 /// that were marked \c true by an algorithm. 1698 /// 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 1712 /// \note The container of the iterator must contain enough space 1711 /// for the elements. (Or it should be an inserter iterator). 1712 /// 1713 /// \todo Revise the name of this class and give an example code. 1713 /// for the elements or the iterator should be an inserter iterator. 1714 #ifdef DOXYGEN 1715 template <typename It, typename Ke> 1716 #else 1714 1717 template <typename It, 1715 1718 typename Ke=typename _maps_bits::IteratorTraits<It>::Value> 1719 #endif 1716 1720 class StoreBoolMap { 1717 1721 public: … … 1736 1740 1737 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 1743 if (value) { 1740 1744 *_end++ = key; … … 1744 1748 private: 1745 1749 Iterator _begin; 1746 mutable Iterator _end; 1747 }; 1750 Iterator _end; 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 /// @} -
test/maps_test.cc
r136 r159 305 305 "Something is wrong with EqualMap"); 306 306 } 307 308 // StoreBoolMap 309 { 310 typedef std::vector<int> vec; 311 vec v1; 312 vec v2(10); 313 StoreBoolMap<std::back_insert_iterator<vec> > map1(std::back_inserter(v1)); 314 StoreBoolMap<vec::iterator> map2(v2.begin()); 315 map1.set(10, false); 316 map1.set(20, true); map2.set(20, true); 317 map1.set(30, false); map2.set(40, false); 318 map1.set(50, true); map2.set(50, true); 319 map1.set(60, true); map2.set(60, true); 320 check(v1.size() == 3 && v2.size() == 10 && 321 v1[0]==20 && v1[1]==50 && v1[2]==60 && v2[0]==20 && v2[1]==50 && v2[2]==60, 322 "Something is wrong with StoreBoolMap"); 323 324 int i = 0; 325 for ( StoreBoolMap<vec::iterator>::Iterator it = map2.begin(); 326 it != map2.end(); ++it ) 327 check(v1[i++] == *it, "Something is wrong with StoreBoolMap"); 328 } 307 329 308 330 return 0;
Note: See TracChangeset
for help on using the changeset viewer.