Changes in lemon/maps.h [314:2cc60866a0c9:327:12626fc94ccf] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/maps.h
r314 r327 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.