771 inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) { |
771 inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) { |
772 return ForkMap<M1,M2>(m1,m2); |
772 return ForkMap<M1,M2>(m1,m2); |
773 } |
773 } |
774 |
774 |
775 |
775 |
776 /// Simple wrapping of a map |
|
777 |
|
778 /// This \ref concepts::ReadMap "read only map" returns the simple |
|
779 /// wrapping of the given map. Sometimes the reference maps cannot be |
|
780 /// combined with simple read maps. This map adaptor wraps the given |
|
781 /// map to simple read map. |
|
782 /// |
|
783 /// The simplest way of using this map is through the wrapMap() |
|
784 /// function. |
|
785 /// |
|
786 /// \sa WrapWriteMap |
|
787 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 /// Constructor |
|
796 WrapMap(const M &m) : _m(m) {} |
|
797 /// \e |
|
798 Value operator[](const Key &k) const { return _m[k]; } |
|
799 }; |
|
800 |
|
801 /// Returns a \ref WrapMap class |
|
802 |
|
803 /// This function just returns a \ref WrapMap class. |
|
804 /// \relates WrapMap |
|
805 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 map |
|
812 |
|
813 /// This \ref concepts::ReadWriteMap "read-write map" returns the simple |
|
814 /// wrapping of the given map. Sometimes the reference maps cannot be |
|
815 /// combined with simple read-write maps. This map adaptor wraps the |
|
816 /// 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 WrapMap |
|
822 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 /// Constructor |
|
831 WrapWriteMap(M &m) : _m(m) {} |
|
832 /// \e |
|
833 Value operator[](const Key &k) const { return _m[k]; } |
|
834 /// \e |
|
835 void set(const Key &k, const Value &c) { _m.set(k, c); } |
|
836 }; |
|
837 |
|
838 ///Returns a \ref WrapWriteMap class |
|
839 |
|
840 ///This function just returns a \ref WrapWriteMap class. |
|
841 ///\relates WrapWriteMap |
|
842 template<typename M> |
|
843 inline WrapWriteMap<M> wrapWriteMap(M &map) { |
|
844 return WrapWriteMap<M>(map); |
|
845 } |
|
846 |
|
847 |
|
848 /// Sum of two maps |
776 /// Sum of two maps |
849 |
777 |
850 /// This \ref concepts::ReadMap "read only map" returns the sum |
778 /// This \ref concepts::ReadMap "read only map" returns the sum |
851 /// of the values of the two given maps. |
779 /// of the values of the two given maps. |
852 /// Its \c Key and \c Value types are inherited from \c M1. |
780 /// Its \c Key and \c Value types are inherited from \c M1. |
1461 template <typename M> |
1389 template <typename M> |
1462 inline NotWriteMap<M> notWriteMap(M &m) { |
1390 inline NotWriteMap<M> notWriteMap(M &m) { |
1463 return NotWriteMap<M>(m); |
1391 return NotWriteMap<M>(m); |
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 element |
|
1494 /// |
|
1495 /// A \ref concepts::ReadWriteMap "read-write" bool map for logging |
|
1496 /// each \c true assigned element, i.e it copies all the keys set |
|
1497 /// to \c true to the given iterator. |
|
1498 /// |
|
1499 /// \note The container of the iterator should contain space |
|
1500 /// for each element. |
|
1501 /// |
|
1502 /// The following example shows how you can write the edges found by |
|
1503 /// the \ref Prim algorithm directly to the standard output. |
|
1504 /// \code |
|
1505 /// 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 /// \endcode |
|
1516 /// |
|
1517 /// \sa BackInserterBoolMap |
|
1518 /// \sa FrontInserterBoolMap |
|
1519 /// \sa InserterBoolMap |
|
1520 /// |
|
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 /// Constructor |
|
1536 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 key |
|
1540 Iterator begin() const { |
|
1541 return _begin; |
|
1542 } |
|
1543 |
|
1544 /// Gives back the the 'after the last' iterator |
|
1545 Iterator end() const { |
|
1546 return _end; |
|
1547 } |
|
1548 |
|
1549 /// The set function of the map |
|
1550 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 in |
|
1563 /// a back insertable container. |
|
1564 /// |
|
1565 /// Writable bool map for logging each \c true assigned element by pushing |
|
1566 /// them into a back insertable container. |
|
1567 /// It can be used to retrieve the items into a standard |
|
1568 /// container. The next example shows how you can store the |
|
1569 /// edges found by the Prim algorithm in a vector. |
|
1570 /// |
|
1571 /// \code |
|
1572 /// vector<Edge> span_tree_edges; |
|
1573 /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges); |
|
1574 /// prim(graph, cost, inserter_map); |
|
1575 /// \endcode |
|
1576 /// |
|
1577 /// \sa StoreBoolMap |
|
1578 /// \sa FrontInserterBoolMap |
|
1579 /// \sa InserterBoolMap |
|
1580 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 /// Constructor |
|
1589 BackInserterBoolMap(Container& _container, |
|
1590 const Functor& _functor = Functor()) |
|
1591 : container(_container), functor(_functor) {} |
|
1592 |
|
1593 /// The set function of the map |
|
1594 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 in |
|
1606 /// a front insertable container. |
|
1607 /// |
|
1608 /// Writable bool map for logging each \c true assigned element by pushing |
|
1609 /// them into a front insertable container. |
|
1610 /// It can be used to retrieve the items into a standard |
|
1611 /// container. For example see \ref BackInserterBoolMap. |
|
1612 /// |
|
1613 /// \sa BackInserterBoolMap |
|
1614 /// \sa InserterBoolMap |
|
1615 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 /// Constructor |
|
1624 FrontInserterBoolMap(Container& _container, |
|
1625 const Functor& _functor = Functor()) |
|
1626 : container(_container), functor(_functor) {} |
|
1627 |
|
1628 /// The set function of the map |
|
1629 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 in |
|
1641 /// an insertable container. |
|
1642 /// |
|
1643 /// Writable bool map for storing each \c true assigned element in an |
|
1644 /// insertable container. It will insert all the keys set to \c true into |
|
1645 /// the container. |
|
1646 /// |
|
1647 /// For example, if you want to store the cut arcs of the strongly |
|
1648 /// connected components in a set you can use the next code: |
|
1649 /// |
|
1650 /// \code |
|
1651 /// set<Arc> cut_arcs; |
|
1652 /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs); |
|
1653 /// stronglyConnectedCutArcs(digraph, cost, inserter_map); |
|
1654 /// \endcode |
|
1655 /// |
|
1656 /// \sa BackInserterBoolMap |
|
1657 /// \sa FrontInserterBoolMap |
|
1658 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 iterator |
|
1667 |
|
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 /// Constructor |
|
1677 |
|
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 map |
|
1686 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 a |
|
1700 /// given value. |
|
1701 /// |
|
1702 /// Writable bool map for filling each \c true assigned element with a |
|
1703 /// given value. The value can set the container. |
|
1704 /// |
|
1705 /// The following code finds the connected components of a graph |
|
1706 /// and stores it in the \c comp map: |
|
1707 /// \code |
|
1708 /// 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 /// \endcode |
|
1724 template <typename Map> |
|
1725 class FillBoolMap { |
|
1726 public: |
|
1727 typedef typename Map::Key Key; |
|
1728 typedef bool Value; |
|
1729 |
|
1730 /// Constructor |
|
1731 FillBoolMap(Map& _map, const typename Map::Value& _fill) |
|
1732 : map(_map), fill(_fill) {} |
|
1733 |
|
1734 /// Constructor |
|
1735 FillBoolMap(Map& _map) |
|
1736 : map(_map), fill() {} |
|
1737 |
|
1738 /// Gives back the current fill value |
|
1739 const typename Map::Value& fillValue() const { |
|
1740 return fill; |
|
1741 } |
|
1742 |
|
1743 /// Gives back the current fill value |
|
1744 typename Map::Value& fillValue() { |
|
1745 return fill; |
|
1746 } |
|
1747 |
|
1748 /// Sets the current fill value |
|
1749 void fillValue(const typename Map::Value& _fill) { |
|
1750 fill = _fill; |
|
1751 } |
|
1752 |
|
1753 /// The set function of the map |
|
1754 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 of |
|
1767 /// \c true assignments. |
|
1768 /// |
|
1769 /// Writable bool map that stores for each \c true assigned elements |
|
1770 /// the sequence number of this setting. |
|
1771 /// It makes it easy to calculate the leaving |
|
1772 /// order of the nodes in the \ref Dfs algorithm. |
|
1773 /// |
|
1774 /// \code |
|
1775 /// 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 /// \endcode |
|
1789 /// |
|
1790 /// The storing of the discovering order is more difficult because the |
|
1791 /// ReachedMap should be readable in the dfs algorithm but the setting |
|
1792 /// order map is not readable. Thus we must use the fork map: |
|
1793 /// |
|
1794 /// \code |
|
1795 /// 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 /// \endcode |
|
1815 template <typename Map> |
|
1816 class SettingOrderBoolMap { |
|
1817 public: |
|
1818 typedef typename Map::Key Key; |
|
1819 typedef bool Value; |
|
1820 |
|
1821 /// Constructor |
|
1822 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 map |
|
1831 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 } |
1844 |
1396 |
1845 #endif // LEMON_MAPS_H |
1397 #endif // LEMON_MAPS_H |