r159:c7d30f7810e5
Mon, 26 May 2008 01:35:59
[Not Reviewed]
0 comments (0 inline)
0
2
0
52
18
| ... | ... |
@@ -1669,55 +1669,59 @@ |
| 1669 | 1669 |
/// \relates LessMap |
| 1670 | 1670 |
template<typename M1, typename M2> |
| 1671 | 1671 |
inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) {
|
| 1672 | 1672 |
return LessMap<M1, M2>(m1,m2); |
| 1673 | 1673 |
} |
| 1674 | 1674 |
|
| 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 {
|
| 1688 | 1679 |
typedef typename std::iterator_traits<_Iterator>::value_type Value; |
| 1689 | 1680 |
}; |
| 1690 | 1681 |
|
| 1691 | 1682 |
template <typename _Iterator> |
| 1692 | 1683 |
struct IteratorTraits<_Iterator, |
| 1693 | 1684 |
typename exists<typename _Iterator::container_type>::type> |
| 1694 | 1685 |
{
|
| 1695 | 1686 |
typedef typename _Iterator::container_type::value_type Value; |
| 1696 | 1687 |
}; |
| 1697 | 1688 |
|
| 1698 | 1689 |
} |
| 1699 | 1690 |
|
| 1700 | 1691 |
/// \brief Writable bool map for logging each \c true assigned element |
| 1701 | 1692 |
/// |
| 1702 |
/// A \ref concepts:: |
|
| 1693 |
/// 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. |
| 1696 |
/// The most important usage of it is storing certain nodes or arcs |
|
| 1697 |
/// that were marked \c true by an algorithm. |
|
| 1705 | 1698 |
/// |
| 1706 |
/// \tparam It the type of the Iterator. |
|
| 1707 |
/// \tparam Ke the type of the map's Key. The default value should |
|
| 1708 |
/// |
|
| 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 |
/// |
|
| 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: |
| 1718 | 1722 |
typedef It Iterator; |
| 1719 | 1723 |
|
| 1720 | 1724 |
typedef Ke Key; |
| 1721 | 1725 |
typedef bool Value; |
| 1722 | 1726 |
|
| 1723 | 1727 |
/// Constructor |
| ... | ... |
@@ -1730,23 +1734,53 @@ |
| 1730 | 1734 |
} |
| 1731 | 1735 |
|
| 1732 | 1736 |
/// Gives back the the 'after the last' iterator |
| 1733 | 1737 |
Iterator end() const {
|
| 1734 | 1738 |
return _end; |
| 1735 | 1739 |
} |
| 1736 | 1740 |
|
| 1737 | 1741 |
/// The set function of the map |
| 1738 |
void set(const Key& key, Value value) |
|
| 1742 |
void set(const Key& key, Value value) {
|
|
| 1739 | 1743 |
if (value) {
|
| 1740 | 1744 |
*_end++ = key; |
| 1741 | 1745 |
} |
| 1742 | 1746 |
} |
| 1743 | 1747 |
|
| 1744 | 1748 |
private: |
| 1745 | 1749 |
Iterator _begin; |
| 1746 |
|
|
| 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 | 1786 |
#endif // LEMON_MAPS_H |
| ... | ... |
@@ -299,11 +299,33 @@ |
| 299 | 299 |
ConstMap<int, double> cm(2.0); |
| 300 | 300 |
IdentityMap<int> im; |
| 301 | 301 |
ConvertMap<IdentityMap<int>, double> id(im); |
| 302 | 302 |
check(lessMap(id,cm)[1] && !lessMap(id,cm)[2] && !lessMap(id,cm)[3], |
| 303 | 303 |
"Something is wrong with LessMap"); |
| 304 | 304 |
check(!equalMap(id,cm)[1] && equalMap(id,cm)[2] && !equalMap(id,cm)[3], |
| 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; |
| 309 | 331 |
} |
0 comments (0 inline)