Changeset 320:12626fc94ccf in lemon-1.0 for lemon
- Timestamp:
- 10/09/08 15:37:44 (16 years ago)
- Branch:
- 1.0
- Parents:
- 303:de38fca76780 (diff), 319:c175e387da19 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent. - Phase:
- public
- Files:
-
- 2 edited
-
lemon/maps.h (modified) (51 diffs)
-
lemon/maps.h (modified) (1 diff)
Legend:
- Unmodified
- Added
- Removed
-
lemon/maps.h
r301 r320 44 44 class MapBase { 45 45 public: 46 /// \b iref The key type of the map.46 /// \brief The key type of the map. 47 47 typedef K Key; 48 48 /// \brief The value type of the map. … … 74 74 }; 75 75 76 /// Returns a \ refNullMap class77 78 /// This function just returns a \ refNullMap class.76 /// Returns a \c NullMap class 77 78 /// This function just returns a \c NullMap class. 79 79 /// \relates NullMap 80 80 template <typename K, typename V> … … 89 89 /// value to each key. 90 90 /// 91 /// In other aspects it is equivalent to \ refNullMap.91 /// In other aspects it is equivalent to \c NullMap. 92 92 /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap" 93 93 /// concept, but it absorbs the data written to it. … … 134 134 }; 135 135 136 /// Returns a \ refConstMap class137 138 /// This function just returns a \ refConstMap class.136 /// Returns a \c ConstMap class 137 138 /// This function just returns a \c ConstMap class. 139 139 /// \relates ConstMap 140 140 template<typename K, typename V> … … 157 157 /// value to each key. 158 158 /// 159 /// In other aspects it is equivalent to \ refNullMap.159 /// In other aspects it is equivalent to \c NullMap. 160 160 /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap" 161 161 /// concept, but it absorbs the data written to it. … … 183 183 }; 184 184 185 /// Returns a \ refConstMap class with inlined constant value186 187 /// This function just returns a \ refConstMap class with inlined185 /// Returns a \c ConstMap class with inlined constant value 186 187 /// This function just returns a \c ConstMap class with inlined 188 188 /// constant value. 189 189 /// \relates ConstMap … … 213 213 }; 214 214 215 /// Returns an \ refIdentityMap class216 217 /// This function just returns an \ refIdentityMap class.215 /// Returns an \c IdentityMap class 216 217 /// This function just returns an \c IdentityMap class. 218 218 /// \relates IdentityMap 219 219 template<typename T> … … 229 229 /// values to integer keys from the range <tt>[0..size-1]</tt>. 230 230 /// It can be used with some data structures, for example 231 /// \ ref UnionFind, \refBinHeap, when the used items are small231 /// \c UnionFind, \c BinHeap, when the used items are small 232 232 /// integers. This map conforms the \ref concepts::ReferenceMap 233 233 /// "ReferenceMap" concept. … … 269 269 : _vector(vector.begin(), vector.end()) {} 270 270 271 /// Constructs the map from another \ refRangeMap.271 /// Constructs the map from another \c RangeMap. 272 272 template <typename V1> 273 273 RangeMap(const RangeMap<V1> &c) … … 312 312 }; 313 313 314 /// Returns a \ refRangeMap class315 316 /// This function just returns a \ refRangeMap class.314 /// Returns a \c RangeMap class 315 316 /// This function just returns a \c RangeMap class. 317 317 /// \relates RangeMap 318 318 template<typename V> … … 321 321 } 322 322 323 /// \brief Returns a \ refRangeMap class created from an appropriate323 /// \brief Returns a \c RangeMap class created from an appropriate 324 324 /// \c std::vector 325 325 326 /// This function just returns a \ refRangeMap class created from an326 /// This function just returns a \c RangeMap class created from an 327 327 /// appropriate \c std::vector. 328 328 /// \relates RangeMap … … 389 389 : _map(map.begin(), map.end()), _value(value) {} 390 390 391 /// \brief Constructs the map from another \ refSparseMap.391 /// \brief Constructs the map from another \c SparseMap. 392 392 template<typename V1, typename Comp1> 393 393 SparseMap(const SparseMap<Key, V1, Comp1> &c) … … 434 434 }; 435 435 436 /// Returns a \ refSparseMap class437 438 /// This function just returns a \ refSparseMap class with specified436 /// Returns a \c SparseMap class 437 438 /// This function just returns a \c SparseMap class with specified 439 439 /// default value. 440 440 /// \relates SparseMap … … 449 449 } 450 450 451 /// \brief Returns a \ refSparseMap class created from an appropriate451 /// \brief Returns a \c SparseMap class created from an appropriate 452 452 /// \c std::map 453 453 454 /// This function just returns a \ refSparseMap class created from an454 /// This function just returns a \c SparseMap class created from an 455 455 /// appropriate \c std::map. 456 456 /// \relates SparseMap … … 502 502 }; 503 503 504 /// Returns a \ refComposeMap class505 506 /// This function just returns a \ refComposeMap class.504 /// Returns a \c ComposeMap class 505 506 /// This function just returns a \c ComposeMap class. 507 507 /// 508 508 /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is … … 557 557 }; 558 558 559 /// Returns a \ refCombineMap class560 561 /// This function just returns a \ refCombineMap class.559 /// Returns a \c CombineMap class 560 561 /// This function just returns a \c CombineMap class. 562 562 /// 563 563 /// For example, if \c m1 and \c m2 are both maps with \c double … … 626 626 }; 627 627 628 /// Returns a \ refFunctorToMap class629 630 /// This function just returns a \ refFunctorToMap class.628 /// Returns a \c FunctorToMap class 629 630 /// This function just returns a \c FunctorToMap class. 631 631 /// 632 632 /// This function is specialized for adaptable binary function … … 685 685 }; 686 686 687 /// Returns a \ refMapToFunctor class688 689 /// This function just returns a \ refMapToFunctor class.687 /// Returns a \c MapToFunctor class 688 689 /// This function just returns a \c MapToFunctor class. 690 690 /// \relates MapToFunctor 691 691 template<typename M> … … 724 724 }; 725 725 726 /// Returns a \ refConvertMap class727 728 /// This function just returns a \ refConvertMap class.726 /// Returns a \c ConvertMap class 727 728 /// This function just returns a \c ConvertMap class. 729 729 /// \relates ConvertMap 730 730 template<typename V, typename M> … … 764 764 }; 765 765 766 /// Returns a \ refForkMap class767 768 /// This function just returns a \ refForkMap class.766 /// Returns a \c ForkMap class 767 768 /// This function just returns a \c ForkMap class. 769 769 /// \relates ForkMap 770 770 template <typename M1, typename M2> … … 808 808 }; 809 809 810 /// Returns an \ refAddMap class811 812 /// This function just returns an \ refAddMap class.810 /// Returns an \c AddMap class 811 812 /// This function just returns an \c AddMap class. 813 813 /// 814 814 /// For example, if \c m1 and \c m2 are both maps with \c double … … 856 856 }; 857 857 858 /// Returns a \ refSubMap class859 860 /// This function just returns a \ refSubMap class.858 /// Returns a \c SubMap class 859 860 /// This function just returns a \c SubMap class. 861 861 /// 862 862 /// For example, if \c m1 and \c m2 are both maps with \c double … … 905 905 }; 906 906 907 /// Returns a \ refMulMap class908 909 /// This function just returns a \ refMulMap class.907 /// Returns a \c MulMap class 908 909 /// This function just returns a \c MulMap class. 910 910 /// 911 911 /// For example, if \c m1 and \c m2 are both maps with \c double … … 953 953 }; 954 954 955 /// Returns a \ refDivMap class956 957 /// This function just returns a \ refDivMap class.955 /// Returns a \c DivMap class 956 957 /// This function just returns a \c DivMap class. 958 958 /// 959 959 /// For example, if \c m1 and \c m2 are both maps with \c double … … 1039 1039 }; 1040 1040 1041 /// Returns a \ refShiftMap class1042 1043 /// This function just returns a \ refShiftMap class.1041 /// Returns a \c ShiftMap class 1042 1043 /// This function just returns a \c ShiftMap class. 1044 1044 /// 1045 1045 /// For example, if \c m is a map with \c double values and \c v is … … 1053 1053 } 1054 1054 1055 /// Returns a \ refShiftWriteMap class1056 1057 /// This function just returns a \ refShiftWriteMap class.1055 /// Returns a \c ShiftWriteMap class 1056 1057 /// This function just returns a \c ShiftWriteMap class. 1058 1058 /// 1059 1059 /// For example, if \c m is a map with \c double values and \c v is … … 1141 1141 }; 1142 1142 1143 /// Returns a \ refScaleMap class1144 1145 /// This function just returns a \ refScaleMap class.1143 /// Returns a \c ScaleMap class 1144 1145 /// This function just returns a \c ScaleMap class. 1146 1146 /// 1147 1147 /// For example, if \c m is a map with \c double values and \c v is … … 1155 1155 } 1156 1156 1157 /// Returns a \ refScaleWriteMap class1158 1159 /// This function just returns a \ refScaleWriteMap class.1157 /// Returns a \c ScaleWriteMap class 1158 1159 /// This function just returns a \c ScaleWriteMap class. 1160 1160 /// 1161 1161 /// For example, if \c m is a map with \c double values and \c v is … … 1241 1241 }; 1242 1242 1243 /// Returns a \ refNegMap class1244 1245 /// This function just returns a \ refNegMap class.1243 /// Returns a \c NegMap class 1244 1245 /// This function just returns a \c NegMap class. 1246 1246 /// 1247 1247 /// For example, if \c m is a map with \c double values, then … … 1254 1254 } 1255 1255 1256 /// Returns a \ refNegWriteMap class1257 1258 /// This function just returns a \ refNegWriteMap class.1256 /// Returns a \c NegWriteMap class 1257 1258 /// This function just returns a \c NegWriteMap class. 1259 1259 /// 1260 1260 /// For example, if \c m is a map with \c double values, then … … 1297 1297 }; 1298 1298 1299 /// Returns an \ refAbsMap class1300 1301 /// This function just returns an \ refAbsMap class.1299 /// Returns an \c AbsMap class 1300 1301 /// This function just returns an \c AbsMap class. 1302 1302 /// 1303 1303 /// For example, if \c m is a map with \c double values, then … … 1346 1346 }; 1347 1347 1348 /// Returns a \ refTrueMap class1349 1350 /// This function just returns a \ refTrueMap class.1348 /// Returns a \c TrueMap class 1349 1350 /// This function just returns a \c TrueMap class. 1351 1351 /// \relates TrueMap 1352 1352 template<typename K> … … 1383 1383 }; 1384 1384 1385 /// Returns a \ refFalseMap class1386 1387 /// This function just returns a \ refFalseMap class.1385 /// Returns a \c FalseMap class 1386 1387 /// This function just returns a \c FalseMap class. 1388 1388 /// \relates FalseMap 1389 1389 template<typename K> … … 1430 1430 }; 1431 1431 1432 /// Returns an \ refAndMap class1433 1434 /// This function just returns an \ refAndMap class.1432 /// Returns an \c AndMap class 1433 1434 /// This function just returns an \c AndMap class. 1435 1435 /// 1436 1436 /// For example, if \c m1 and \c m2 are both maps with \c bool values, … … 1478 1478 }; 1479 1479 1480 /// Returns an \ refOrMap class1481 1482 /// This function just returns an \ refOrMap class.1480 /// Returns an \c OrMap class 1481 1482 /// This function just returns an \c OrMap class. 1483 1483 /// 1484 1484 /// For example, if \c m1 and \c m2 are both maps with \c bool values, … … 1545 1545 }; 1546 1546 1547 /// Returns a \ refNotMap class1548 1549 /// This function just returns a \ refNotMap class.1547 /// Returns a \c NotMap class 1548 1549 /// This function just returns a \c NotMap class. 1550 1550 /// 1551 1551 /// For example, if \c m is a map with \c bool values, then … … 1558 1558 } 1559 1559 1560 /// Returns a \ refNotWriteMap class1561 1562 /// This function just returns a \ refNotWriteMap class.1560 /// Returns a \c NotWriteMap class 1561 1562 /// This function just returns a \c NotWriteMap class. 1563 1563 /// 1564 1564 /// For example, if \c m is a map with \c bool values, then … … 1606 1606 }; 1607 1607 1608 /// Returns an \ refEqualMap class1609 1610 /// This function just returns an \ refEqualMap class.1608 /// Returns an \c EqualMap class 1609 1610 /// This function just returns an \c EqualMap class. 1611 1611 /// 1612 1612 /// For example, if \c m1 and \c m2 are maps with keys and values of … … 1654 1654 }; 1655 1655 1656 /// Returns an \ refLessMap class1657 1658 /// This function just returns an \ refLessMap class.1656 /// Returns an \c LessMap class 1657 1658 /// This function just returns an \c LessMap class. 1659 1659 /// 1660 1660 /// For example, if \c m1 and \c m2 are maps with keys and values of … … 1683 1683 1684 1684 } 1685 1686 /// @} 1687 1688 /// \addtogroup maps 1689 /// @{ 1685 1690 1686 1691 /// \brief Writable bool map for logging each \c true assigned element … … 1746 1751 }; 1747 1752 1748 /// Returns a \ refLoggerBoolMap class1749 1750 /// This function just returns a \ refLoggerBoolMap class.1753 /// Returns a \c LoggerBoolMap class 1754 1755 /// This function just returns a \c LoggerBoolMap class. 1751 1756 /// 1752 1757 /// The most important usage of it is storing certain nodes or arcs … … 1768 1773 /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so 1769 1774 /// it cannot be used when a readable map is needed, for example as 1770 /// \c ReachedMap for \ ref Bfs, \ref Dfs and \refDijkstra algorithms.1775 /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms. 1771 1776 /// 1772 1777 /// \relates LoggerBoolMap … … 1775 1780 return LoggerBoolMap<Iterator>(it); 1776 1781 } 1782 1783 /// @} 1784 1785 /// \addtogroup graph_maps 1786 /// @{ 1777 1787 1778 1788 /// Provides an immutable and unique id for each item in the graph. … … 1862 1872 /// 1863 1873 /// Constructor 1864 /// \param _digraph The digraph that the map belongs to.1874 /// \param digraph The digraph that the map belongs to. 1865 1875 explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {} 1866 1876 … … 1878 1888 }; 1879 1889 1880 /// \brief Returns a \ refSourceMap class.1881 /// 1882 /// This function just returns an \ refSourceMap class.1890 /// \brief Returns a \c SourceMap class. 1891 /// 1892 /// This function just returns an \c SourceMap class. 1883 1893 /// \relates SourceMap 1884 1894 template <typename Digraph> … … 1901 1911 /// 1902 1912 /// Constructor 1903 /// \param _digraph The digraph that the map belongs to.1913 /// \param digraph The digraph that the map belongs to. 1904 1914 explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {} 1905 1915 … … 1917 1927 }; 1918 1928 1919 /// \brief Returns a \ refTargetMap class.1920 /// 1921 /// This function just returns a \ refTargetMap class.1929 /// \brief Returns a \c TargetMap class. 1930 /// 1931 /// This function just returns a \c TargetMap class. 1922 1932 /// \relates TargetMap 1923 1933 template <typename Digraph> … … 1940 1950 /// 1941 1951 /// Constructor 1942 /// \param _graph The graph that the map belongs to.1952 /// \param graph The graph that the map belongs to. 1943 1953 explicit ForwardMap(const Graph& graph) : _graph(graph) {} 1944 1954 … … 1956 1966 }; 1957 1967 1958 /// \brief Returns a \ refForwardMap class.1959 /// 1960 /// This function just returns an \ refForwardMap class.1968 /// \brief Returns a \c ForwardMap class. 1969 /// 1970 /// This function just returns an \c ForwardMap class. 1961 1971 /// \relates ForwardMap 1962 1972 template <typename Graph> … … 1979 1989 /// 1980 1990 /// Constructor 1981 /// \param _graph The graph that the map belongs to.1991 /// \param graph The graph that the map belongs to. 1982 1992 explicit BackwardMap(const Graph& graph) : _graph(graph) {} 1983 1993 … … 1995 2005 }; 1996 2006 1997 /// \brief Returns a \ refBackwardMap class1998 1999 /// This function just returns a \ refBackwardMap class.2007 /// \brief Returns a \c BackwardMap class 2008 2009 /// This function just returns a \c BackwardMap class. 2000 2010 /// \relates BackwardMap 2001 2011 template <typename Graph> -
lemon/maps.h
r318 r320 1856 1856 InverseMap inverse() const { return InverseMap(*_graph);} 1857 1857 1858 };1859 1860 1861 /// \brief General invertable graph-map type.1862 1863 /// This type provides simple invertable graph-maps.1864 /// The InvertableMap wraps an arbitrary ReadWriteMap1865 /// and if a key is set to a new value then store it1866 /// in the inverse map.1867 ///1868 /// The values of the map can be accessed1869 /// with stl compatible forward iterator.1870 ///1871 /// \tparam _Graph The graph type.1872 /// \tparam _Item The item type of the graph.1873 /// \tparam _Value The value type of the map.1874 ///1875 /// \see IterableValueMap1876 template <typename _Graph, typename _Item, typename _Value>1877 class InvertableMap1878 : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {1879 private:1880 1881 typedef typename ItemSetTraits<_Graph, _Item>::1882 template Map<_Value>::Type Map;1883 typedef _Graph Graph;1884 1885 typedef std::map<_Value, _Item> Container;1886 Container _inv_map;1887 1888 public:1889 1890 /// The key type of InvertableMap (Node, Arc, Edge).1891 typedef typename Map::Key Key;1892 /// The value type of the InvertableMap.1893 typedef typename Map::Value Value;1894 1895 /// \brief Constructor.1896 ///1897 /// Construct a new InvertableMap for the graph.1898 ///1899 explicit InvertableMap(const Graph& graph) : Map(graph) {}1900 1901 /// \brief Forward iterator for values.1902 ///1903 /// This iterator is an stl compatible forward1904 /// iterator on the values of the map. The values can1905 /// be accessed in the [beginValue, endValue) range.1906 ///1907 class ValueIterator1908 : public std::iterator<std::forward_iterator_tag, Value> {1909 friend class InvertableMap;1910 private:1911 ValueIterator(typename Container::const_iterator _it)1912 : it(_it) {}1913 public:1914 1915 ValueIterator() {}1916 1917 ValueIterator& operator++() { ++it; return *this; }1918 ValueIterator operator++(int) {1919 ValueIterator tmp(*this);1920 operator++();1921 return tmp;1922 }1923 1924 const Value& operator*() const { return it->first; }1925 const Value* operator->() const { return &(it->first); }1926 1927 bool operator==(ValueIterator jt) const { return it == jt.it; }1928 bool operator!=(ValueIterator jt) const { return it != jt.it; }1929 1930 private:1931 typename Container::const_iterator it;1932 };1933 1934 /// \brief Returns an iterator to the first value.1935 ///1936 /// Returns an stl compatible iterator to the1937 /// first value of the map. The values of the1938 /// map can be accessed in the [beginValue, endValue)1939 /// range.1940 ValueIterator beginValue() const {1941 return ValueIterator(_inv_map.begin());1942 }1943 1944 /// \brief Returns an iterator after the last value.1945 ///1946 /// Returns an stl compatible iterator after the1947 /// last value of the map. The values of the1948 /// map can be accessed in the [beginValue, endValue)1949 /// range.1950 ValueIterator endValue() const {1951 return ValueIterator(_inv_map.end());1952 }1953 1954 /// \brief The setter function of the map.1955 ///1956 /// Sets the mapped value.1957 void set(const Key& key, const Value& val) {1958 Value oldval = Map::operator[](key);1959 typename Container::iterator it = _inv_map.find(oldval);1960 if (it != _inv_map.end() && it->second == key) {1961 _inv_map.erase(it);1962 }1963 _inv_map.insert(make_pair(val, key));1964 Map::set(key, val);1965 }1966 1967 /// \brief The getter function of the map.1968 ///1969 /// It gives back the value associated with the key.1970 typename MapTraits<Map>::ConstReturnValue1971 operator[](const Key& key) const {1972 return Map::operator[](key);1973 }1974 1975 /// \brief Gives back the item by its value.1976 ///1977 /// Gives back the item by its value.1978 Key operator()(const Value& key) const {1979 typename Container::const_iterator it = _inv_map.find(key);1980 return it != _inv_map.end() ? it->second : INVALID;1981 }1982 1983 protected:1984 1985 /// \brief Erase the key from the map.1986 ///1987 /// Erase the key to the map. It is called by the1988 /// \c AlterationNotifier.1989 virtual void erase(const Key& key) {1990 Value val = Map::operator[](key);1991 typename Container::iterator it = _inv_map.find(val);1992 if (it != _inv_map.end() && it->second == key) {1993 _inv_map.erase(it);1994 }1995 Map::erase(key);1996 }1997 1998 /// \brief Erase more keys from the map.1999 ///2000 /// Erase more keys from the map. It is called by the2001 /// \c AlterationNotifier.2002 virtual void erase(const std::vector<Key>& keys) {2003 for (int i = 0; i < int(keys.size()); ++i) {2004 Value val = Map::operator[](keys[i]);2005 typename Container::iterator it = _inv_map.find(val);2006 if (it != _inv_map.end() && it->second == keys[i]) {2007 _inv_map.erase(it);2008 }2009 }2010 Map::erase(keys);2011 }2012 2013 /// \brief Clear the keys from the map and inverse map.2014 ///2015 /// Clear the keys from the map and inverse map. It is called by the2016 /// \c AlterationNotifier.2017 virtual void clear() {2018 _inv_map.clear();2019 Map::clear();2020 }2021 2022 public:2023 2024 /// \brief The inverse map type.2025 ///2026 /// The inverse of this map. The subscript operator of the map2027 /// gives back always the item what was last assigned to the value.2028 class InverseMap {2029 public:2030 /// \brief Constructor of the InverseMap.2031 ///2032 /// Constructor of the InverseMap.2033 explicit InverseMap(const InvertableMap& inverted)2034 : _inverted(inverted) {}2035 2036 /// The value type of the InverseMap.2037 typedef typename InvertableMap::Key Value;2038 /// The key type of the InverseMap.2039 typedef typename InvertableMap::Value Key;2040 2041 /// \brief Subscript operator.2042 ///2043 /// Subscript operator. It gives back always the item2044 /// what was last assigned to the value.2045 Value operator[](const Key& key) const {2046 return _inverted(key);2047 }2048 2049 private:2050 const InvertableMap& _inverted;2051 };2052 2053 /// \brief It gives back the just readable inverse map.2054 ///2055 /// It gives back the just readable inverse map.2056 InverseMap inverse() const {2057 return InverseMap(*this);2058 }2059 2060 };2061 2062 /// \brief Provides a mutable, continuous and unique descriptor for each2063 /// item in the graph.2064 ///2065 /// The DescriptorMap class provides a unique and continuous (but mutable)2066 /// descriptor (id) for each item of the same type (e.g. node) in the2067 /// graph. This id is <ul><li>\b unique: different items (nodes) get2068 /// different ids <li>\b continuous: the range of the ids is the set of2069 /// integers between 0 and \c n-1, where \c n is the number of the items of2070 /// this type (e.g. nodes) (so the id of a node can change if you delete an2071 /// other node, i.e. this id is mutable). </ul> This map can be inverted2072 /// with its member class \c InverseMap, or with the \c operator() member.2073 ///2074 /// \tparam _Graph The graph class the \c DescriptorMap belongs to.2075 /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or2076 /// Edge.2077 template <typename _Graph, typename _Item>2078 class DescriptorMap2079 : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {2080 2081 typedef _Item Item;2082 typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;2083 2084 public:2085 /// The graph class of DescriptorMap.2086 typedef _Graph Graph;2087 2088 /// The key type of DescriptorMap (Node, Arc, Edge).2089 typedef typename Map::Key Key;2090 /// The value type of DescriptorMap.2091 typedef typename Map::Value Value;2092 2093 /// \brief Constructor.2094 ///2095 /// Constructor for descriptor map.2096 explicit DescriptorMap(const Graph& _graph) : Map(_graph) {2097 Item it;2098 const typename Map::Notifier* nf = Map::notifier();2099 for (nf->first(it); it != INVALID; nf->next(it)) {2100 Map::set(it, _inv_map.size());2101 _inv_map.push_back(it);2102 }2103 }2104 2105 protected:2106 2107 /// \brief Add a new key to the map.2108 ///2109 /// Add a new key to the map. It is called by the2110 /// \c AlterationNotifier.2111 virtual void add(const Item& item) {2112 Map::add(item);2113 Map::set(item, _inv_map.size());2114 _inv_map.push_back(item);2115 }2116 2117 /// \brief Add more new keys to the map.2118 ///2119 /// Add more new keys to the map. It is called by the2120 /// \c AlterationNotifier.2121 virtual void add(const std::vector<Item>& items) {2122 Map::add(items);2123 for (int i = 0; i < int(items.size()); ++i) {2124 Map::set(items[i], _inv_map.size());2125 _inv_map.push_back(items[i]);2126 }2127 }2128 2129 /// \brief Erase the key from the map.2130 ///2131 /// Erase the key from the map. It is called by the2132 /// \c AlterationNotifier.2133 virtual void erase(const Item& item) {2134 Map::set(_inv_map.back(), Map::operator[](item));2135 _inv_map[Map::operator[](item)] = _inv_map.back();2136 _inv_map.pop_back();2137 Map::erase(item);2138 }2139 2140 /// \brief Erase more keys from the map.2141 ///2142 /// Erase more keys from the map. It is called by the2143 /// \c AlterationNotifier.2144 virtual void erase(const std::vector<Item>& items) {2145 for (int i = 0; i < int(items.size()); ++i) {2146 Map::set(_inv_map.back(), Map::operator[](items[i]));2147 _inv_map[Map::operator[](items[i])] = _inv_map.back();2148 _inv_map.pop_back();2149 }2150 Map::erase(items);2151 }2152 2153 /// \brief Build the unique map.2154 ///2155 /// Build the unique map. It is called by the2156 /// \c AlterationNotifier.2157 virtual void build() {2158 Map::build();2159 Item it;2160 const typename Map::Notifier* nf = Map::notifier();2161 for (nf->first(it); it != INVALID; nf->next(it)) {2162 Map::set(it, _inv_map.size());2163 _inv_map.push_back(it);2164 }2165 }2166 2167 /// \brief Clear the keys from the map.2168 ///2169 /// Clear the keys from the map. It is called by the2170 /// \c AlterationNotifier.2171 virtual void clear() {2172 _inv_map.clear();2173 Map::clear();2174 }2175 2176 public:2177 2178 /// \brief Returns the maximal value plus one.2179 ///2180 /// Returns the maximal value plus one in the map.2181 unsigned int size() const {2182 return _inv_map.size();2183 }2184 2185 /// \brief Swaps the position of the two items in the map.2186 ///2187 /// Swaps the position of the two items in the map.2188 void swap(const Item& p, const Item& q) {2189 int pi = Map::operator[](p);2190 int qi = Map::operator[](q);2191 Map::set(p, qi);2192 _inv_map[qi] = p;2193 Map::set(q, pi);2194 _inv_map[pi] = q;2195 }2196 2197 /// \brief Gives back the \e descriptor of the item.2198 ///2199 /// Gives back the mutable and unique \e descriptor of the map.2200 int operator[](const Item& item) const {2201 return Map::operator[](item);2202 }2203 2204 /// \brief Gives back the item by its descriptor.2205 ///2206 /// Gives back th item by its descriptor.2207 Item operator()(int id) const {2208 return _inv_map[id];2209 }2210 2211 private:2212 2213 typedef std::vector<Item> Container;2214 Container _inv_map;2215 2216 public:2217 /// \brief The inverse map type of DescriptorMap.2218 ///2219 /// The inverse map type of DescriptorMap.2220 class InverseMap {2221 public:2222 /// \brief Constructor of the InverseMap.2223 ///2224 /// Constructor of the InverseMap.2225 explicit InverseMap(const DescriptorMap& inverted)2226 : _inverted(inverted) {}2227 2228 2229 /// The value type of the InverseMap.2230 typedef typename DescriptorMap::Key Value;2231 /// The key type of the InverseMap.2232 typedef typename DescriptorMap::Value Key;2233 2234 /// \brief Subscript operator.2235 ///2236 /// Subscript operator. It gives back the item2237 /// that the descriptor belongs to currently.2238 Value operator[](const Key& key) const {2239 return _inverted(key);2240 }2241 2242 /// \brief Size of the map.2243 ///2244 /// Returns the size of the map.2245 unsigned int size() const {2246 return _inverted.size();2247 }2248 2249 private:2250 const DescriptorMap& _inverted;2251 };2252 2253 /// \brief Gives back the inverse of the map.2254 ///2255 /// Gives back the inverse of the map.2256 const InverseMap inverse() const {2257 return InverseMap(*this);2258 }2259 1858 }; 2260 1859
Note: See TracChangeset
for help on using the changeset viewer.
