Changeset 81:7ff1c348ae0c in lemon-1.1
- Timestamp:
- 03/15/08 21:24:43 (16 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/maps.h
r80 r81 774 774 775 775 776 /// Simple wrapping of a map777 778 /// This \ref concepts::ReadMap "read only map" returns the simple779 /// wrapping of the given map. Sometimes the reference maps cannot be780 /// combined with simple read maps. This map adaptor wraps the given781 /// map to simple read map.782 ///783 /// The simplest way of using this map is through the wrapMap()784 /// function.785 ///786 /// \sa WrapWriteMap787 template<typename M>788 class WrapMap : public MapBase<typename M::Key, typename M::Value> {789 const M &_m;790 public:791 typedef MapBase<typename M::Key, typename M::Value> Parent;792 typedef typename Parent::Key Key;793 typedef typename Parent::Value Value;794 795 /// Constructor796 WrapMap(const M &m) : _m(m) {}797 /// \e798 Value operator[](const Key &k) const { return _m[k]; }799 };800 801 /// Returns a \ref WrapMap class802 803 /// This function just returns a \ref WrapMap class.804 /// \relates WrapMap805 template<typename M>806 inline WrapMap<M> wrapMap(const M &map) {807 return WrapMap<M>(map);808 }809 810 811 /// Simple writable wrapping of a map812 813 /// This \ref concepts::ReadWriteMap "read-write map" returns the simple814 /// wrapping of the given map. Sometimes the reference maps cannot be815 /// combined with simple read-write maps. This map adaptor wraps the816 /// given map to simple read-write map.817 ///818 /// The simplest way of using this map is through the wrapWriteMap()819 /// function.820 ///821 /// \sa WrapMap822 template<typename M>823 class WrapWriteMap : public MapBase<typename M::Key, typename M::Value> {824 M &_m;825 public:826 typedef MapBase<typename M::Key, typename M::Value> Parent;827 typedef typename Parent::Key Key;828 typedef typename Parent::Value Value;829 830 /// Constructor831 WrapWriteMap(M &m) : _m(m) {}832 /// \e833 Value operator[](const Key &k) const { return _m[k]; }834 /// \e835 void set(const Key &k, const Value &c) { _m.set(k, c); }836 };837 838 ///Returns a \ref WrapWriteMap class839 840 ///This function just returns a \ref WrapWriteMap class.841 ///\relates WrapWriteMap842 template<typename M>843 inline WrapWriteMap<M> wrapWriteMap(M &map) {844 return WrapWriteMap<M>(map);845 }846 847 848 776 /// Sum of two maps 849 777 … … 1464 1392 } 1465 1393 1466 1467 namespace _maps_bits {1468 1469 template <typename Value>1470 struct Identity {1471 typedef Value argument_type;1472 typedef Value result_type;1473 Value operator()(const Value& val) const {1474 return val;1475 }1476 };1477 1478 template <typename _Iterator, typename Enable = void>1479 struct IteratorTraits {1480 typedef typename std::iterator_traits<_Iterator>::value_type Value;1481 };1482 1483 template <typename _Iterator>1484 struct IteratorTraits<_Iterator,1485 typename exists<typename _Iterator::container_type>::type>1486 {1487 typedef typename _Iterator::container_type::value_type Value;1488 };1489 1490 }1491 1492 1493 /// \brief Writable bool map for logging each \c true assigned element1494 ///1495 /// A \ref concepts::ReadWriteMap "read-write" bool map for logging1496 /// each \c true assigned element, i.e it copies all the keys set1497 /// to \c true to the given iterator.1498 ///1499 /// \note The container of the iterator should contain space1500 /// for each element.1501 ///1502 /// The following example shows how you can write the edges found by1503 /// the \ref Prim algorithm directly to the standard output.1504 /// \code1505 /// typedef IdMap<Graph, Edge> EdgeIdMap;1506 /// EdgeIdMap edgeId(graph);1507 ///1508 /// typedef MapToFunctor<EdgeIdMap> EdgeIdFunctor;1509 /// EdgeIdFunctor edgeIdFunctor(edgeId);1510 ///1511 /// StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor>1512 /// writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor);1513 ///1514 /// prim(graph, cost, writerMap);1515 /// \endcode1516 ///1517 /// \sa BackInserterBoolMap1518 /// \sa FrontInserterBoolMap1519 /// \sa InserterBoolMap1520 ///1521 /// \todo Revise the name of this class and the related ones.1522 template <typename _Iterator,1523 typename _Functor =1524 _maps_bits::Identity<typename _maps_bits::1525 IteratorTraits<_Iterator>::Value> >1526 class StoreBoolMap {1527 public:1528 typedef _Iterator Iterator;1529 1530 typedef typename _Functor::argument_type Key;1531 typedef bool Value;1532 1533 typedef _Functor Functor;1534 1535 /// Constructor1536 StoreBoolMap(Iterator it, const Functor& functor = Functor())1537 : _begin(it), _end(it), _functor(functor) {}1538 1539 /// Gives back the given iterator set for the first key1540 Iterator begin() const {1541 return _begin;1542 }1543 1544 /// Gives back the the 'after the last' iterator1545 Iterator end() const {1546 return _end;1547 }1548 1549 /// The set function of the map1550 void set(const Key& key, Value value) const {1551 if (value) {1552 *_end++ = _functor(key);1553 }1554 }1555 1556 private:1557 Iterator _begin;1558 mutable Iterator _end;1559 Functor _functor;1560 };1561 1562 /// \brief Writable bool map for logging each \c true assigned element in1563 /// a back insertable container.1564 ///1565 /// Writable bool map for logging each \c true assigned element by pushing1566 /// them into a back insertable container.1567 /// It can be used to retrieve the items into a standard1568 /// container. The next example shows how you can store the1569 /// edges found by the Prim algorithm in a vector.1570 ///1571 /// \code1572 /// vector<Edge> span_tree_edges;1573 /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges);1574 /// prim(graph, cost, inserter_map);1575 /// \endcode1576 ///1577 /// \sa StoreBoolMap1578 /// \sa FrontInserterBoolMap1579 /// \sa InserterBoolMap1580 template <typename Container,1581 typename Functor =1582 _maps_bits::Identity<typename Container::value_type> >1583 class BackInserterBoolMap {1584 public:1585 typedef typename Functor::argument_type Key;1586 typedef bool Value;1587 1588 /// Constructor1589 BackInserterBoolMap(Container& _container,1590 const Functor& _functor = Functor())1591 : container(_container), functor(_functor) {}1592 1593 /// The set function of the map1594 void set(const Key& key, Value value) {1595 if (value) {1596 container.push_back(functor(key));1597 }1598 }1599 1600 private:1601 Container& container;1602 Functor functor;1603 };1604 1605 /// \brief Writable bool map for logging each \c true assigned element in1606 /// a front insertable container.1607 ///1608 /// Writable bool map for logging each \c true assigned element by pushing1609 /// them into a front insertable container.1610 /// It can be used to retrieve the items into a standard1611 /// container. For example see \ref BackInserterBoolMap.1612 ///1613 /// \sa BackInserterBoolMap1614 /// \sa InserterBoolMap1615 template <typename Container,1616 typename Functor =1617 _maps_bits::Identity<typename Container::value_type> >1618 class FrontInserterBoolMap {1619 public:1620 typedef typename Functor::argument_type Key;1621 typedef bool Value;1622 1623 /// Constructor1624 FrontInserterBoolMap(Container& _container,1625 const Functor& _functor = Functor())1626 : container(_container), functor(_functor) {}1627 1628 /// The set function of the map1629 void set(const Key& key, Value value) {1630 if (value) {1631 container.push_front(functor(key));1632 }1633 }1634 1635 private:1636 Container& container;1637 Functor functor;1638 };1639 1640 /// \brief Writable bool map for storing each \c true assigned element in1641 /// an insertable container.1642 ///1643 /// Writable bool map for storing each \c true assigned element in an1644 /// insertable container. It will insert all the keys set to \c true into1645 /// the container.1646 ///1647 /// For example, if you want to store the cut arcs of the strongly1648 /// connected components in a set you can use the next code:1649 ///1650 /// \code1651 /// set<Arc> cut_arcs;1652 /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs);1653 /// stronglyConnectedCutArcs(digraph, cost, inserter_map);1654 /// \endcode1655 ///1656 /// \sa BackInserterBoolMap1657 /// \sa FrontInserterBoolMap1658 template <typename Container,1659 typename Functor =1660 _maps_bits::Identity<typename Container::value_type> >1661 class InserterBoolMap {1662 public:1663 typedef typename Container::value_type Key;1664 typedef bool Value;1665 1666 /// Constructor with specified iterator1667 1668 /// Constructor with specified iterator.1669 /// \param _container The container for storing the elements.1670 /// \param _it The elements will be inserted before this iterator.1671 /// \param _functor The functor that is used when an element is stored.1672 InserterBoolMap(Container& _container, typename Container::iterator _it,1673 const Functor& _functor = Functor())1674 : container(_container), it(_it), functor(_functor) {}1675 1676 /// Constructor1677 1678 /// Constructor without specified iterator.1679 /// The elements will be inserted before <tt>_container.end()</tt>.1680 /// \param _container The container for storing the elements.1681 /// \param _functor The functor that is used when an element is stored.1682 InserterBoolMap(Container& _container, const Functor& _functor = Functor())1683 : container(_container), it(_container.end()), functor(_functor) {}1684 1685 /// The set function of the map1686 void set(const Key& key, Value value) {1687 if (value) {1688 it = container.insert(it, functor(key));1689 ++it;1690 }1691 }1692 1693 private:1694 Container& container;1695 typename Container::iterator it;1696 Functor functor;1697 };1698 1699 /// \brief Writable bool map for filling each \c true assigned element with a1700 /// given value.1701 ///1702 /// Writable bool map for filling each \c true assigned element with a1703 /// given value. The value can set the container.1704 ///1705 /// The following code finds the connected components of a graph1706 /// and stores it in the \c comp map:1707 /// \code1708 /// typedef Graph::NodeMap<int> ComponentMap;1709 /// ComponentMap comp(graph);1710 /// typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap;1711 /// ComponentFillerMap filler(comp, 0);1712 ///1713 /// Dfs<Graph>::DefProcessedMap<ComponentFillerMap>::Create dfs(graph);1714 /// dfs.processedMap(filler);1715 /// dfs.init();1716 /// for (NodeIt it(graph); it != INVALID; ++it) {1717 /// if (!dfs.reached(it)) {1718 /// dfs.addSource(it);1719 /// dfs.start();1720 /// ++filler.fillValue();1721 /// }1722 /// }1723 /// \endcode1724 template <typename Map>1725 class FillBoolMap {1726 public:1727 typedef typename Map::Key Key;1728 typedef bool Value;1729 1730 /// Constructor1731 FillBoolMap(Map& _map, const typename Map::Value& _fill)1732 : map(_map), fill(_fill) {}1733 1734 /// Constructor1735 FillBoolMap(Map& _map)1736 : map(_map), fill() {}1737 1738 /// Gives back the current fill value1739 const typename Map::Value& fillValue() const {1740 return fill;1741 }1742 1743 /// Gives back the current fill value1744 typename Map::Value& fillValue() {1745 return fill;1746 }1747 1748 /// Sets the current fill value1749 void fillValue(const typename Map::Value& _fill) {1750 fill = _fill;1751 }1752 1753 /// The set function of the map1754 void set(const Key& key, Value value) {1755 if (value) {1756 map.set(key, fill);1757 }1758 }1759 1760 private:1761 Map& map;1762 typename Map::Value fill;1763 };1764 1765 1766 /// \brief Writable bool map for storing the sequence number of1767 /// \c true assignments.1768 ///1769 /// Writable bool map that stores for each \c true assigned elements1770 /// the sequence number of this setting.1771 /// It makes it easy to calculate the leaving1772 /// order of the nodes in the \ref Dfs algorithm.1773 ///1774 /// \code1775 /// typedef Digraph::NodeMap<int> OrderMap;1776 /// OrderMap order(digraph);1777 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;1778 /// OrderSetterMap setter(order);1779 /// Dfs<Digraph>::DefProcessedMap<OrderSetterMap>::Create dfs(digraph);1780 /// dfs.processedMap(setter);1781 /// dfs.init();1782 /// for (NodeIt it(digraph); it != INVALID; ++it) {1783 /// if (!dfs.reached(it)) {1784 /// dfs.addSource(it);1785 /// dfs.start();1786 /// }1787 /// }1788 /// \endcode1789 ///1790 /// The storing of the discovering order is more difficult because the1791 /// ReachedMap should be readable in the dfs algorithm but the setting1792 /// order map is not readable. Thus we must use the fork map:1793 ///1794 /// \code1795 /// typedef Digraph::NodeMap<int> OrderMap;1796 /// OrderMap order(digraph);1797 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;1798 /// OrderSetterMap setter(order);1799 /// typedef Digraph::NodeMap<bool> StoreMap;1800 /// StoreMap store(digraph);1801 ///1802 /// typedef ForkMap<StoreMap, OrderSetterMap> ReachedMap;1803 /// ReachedMap reached(store, setter);1804 ///1805 /// Dfs<Digraph>::DefReachedMap<ReachedMap>::Create dfs(digraph);1806 /// dfs.reachedMap(reached);1807 /// dfs.init();1808 /// for (NodeIt it(digraph); it != INVALID; ++it) {1809 /// if (!dfs.reached(it)) {1810 /// dfs.addSource(it);1811 /// dfs.start();1812 /// }1813 /// }1814 /// \endcode1815 template <typename Map>1816 class SettingOrderBoolMap {1817 public:1818 typedef typename Map::Key Key;1819 typedef bool Value;1820 1821 /// Constructor1822 SettingOrderBoolMap(Map& _map)1823 : map(_map), counter(0) {}1824 1825 /// Number of set operations.1826 int num() const {1827 return counter;1828 }1829 1830 /// The set function of the map1831 void set(const Key& key, Value value) {1832 if (value) {1833 map.set(key, counter++);1834 }1835 }1836 1837 private:1838 Map& map;1839 int counter;1840 };1841 1842 1394 /// @} 1843 1395 }
Note: See TracChangeset
for help on using the changeset viewer.