Changes in lemon/maps.h [327:12626fc94ccf:314:2cc60866a0c9] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/maps.h
r327 r314 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 ReadWriteMap 1865 /// and if a key is set to a new value then store it 1866 /// in the inverse map. 1867 /// 1868 /// The values of the map can be accessed 1869 /// 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 IterableValueMap 1876 template <typename _Graph, typename _Item, typename _Value> 1877 class InvertableMap 1878 : 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 forward 1904 /// iterator on the values of the map. The values can 1905 /// be accessed in the [beginValue, endValue) range. 1906 /// 1907 class ValueIterator 1908 : 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 the 1937 /// first value of the map. The values of the 1938 /// 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 the 1947 /// last value of the map. The values of the 1948 /// 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>::ConstReturnValue 1971 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 the 1988 /// \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 the 2001 /// \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 the 2016 /// \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 map 2027 /// 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 item 2044 /// 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 each 2063 /// 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 the 2067 /// graph. This id is <ul><li>\b unique: different items (nodes) get 2068 /// different ids <li>\b continuous: the range of the ids is the set of 2069 /// integers between 0 and \c n-1, where \c n is the number of the items of 2070 /// this type (e.g. nodes) (so the id of a node can change if you delete an 2071 /// other node, i.e. this id is mutable). </ul> This map can be inverted 2072 /// 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 or 2076 /// Edge. 2077 template <typename _Graph, typename _Item> 2078 class DescriptorMap 2079 : 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 the 2110 /// \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 the 2120 /// \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 the 2132 /// \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 the 2143 /// \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 the 2156 /// \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 the 2170 /// \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 item 2237 /// 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 } 1858 2259 }; 1859 2260
Note: See TracChangeset
for help on using the changeset viewer.