Changeset 324:fafece417795 in lemon
- Timestamp:
- 10/08/08 13:25:57 (16 years ago)
- Branch:
- 1.0
- Phase:
- public
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/maps.h
r280 r324 1846 1846 InverseMap inverse() const { return InverseMap(*_graph);} 1847 1847 1848 };1849 1850 1851 /// \brief General invertable graph-map type.1852 1853 /// This type provides simple invertable graph-maps.1854 /// The InvertableMap wraps an arbitrary ReadWriteMap1855 /// and if a key is set to a new value then store it1856 /// in the inverse map.1857 ///1858 /// The values of the map can be accessed1859 /// with stl compatible forward iterator.1860 ///1861 /// \tparam _Graph The graph type.1862 /// \tparam _Item The item type of the graph.1863 /// \tparam _Value The value type of the map.1864 ///1865 /// \see IterableValueMap1866 template <typename _Graph, typename _Item, typename _Value>1867 class InvertableMap1868 : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {1869 private:1870 1871 typedef typename ItemSetTraits<_Graph, _Item>::1872 template Map<_Value>::Type Map;1873 typedef _Graph Graph;1874 1875 typedef std::map<_Value, _Item> Container;1876 Container _inv_map;1877 1878 public:1879 1880 /// The key type of InvertableMap (Node, Arc, Edge).1881 typedef typename Map::Key Key;1882 /// The value type of the InvertableMap.1883 typedef typename Map::Value Value;1884 1885 1886 1887 /// \brief Constructor.1888 ///1889 /// Construct a new InvertableMap for the graph.1890 ///1891 explicit InvertableMap(const Graph& graph) : Map(graph) {}1892 1893 /// \brief Forward iterator for values.1894 ///1895 /// This iterator is an stl compatible forward1896 /// iterator on the values of the map. The values can1897 /// be accessed in the [beginValue, endValue) range.1898 ///1899 class ValueIterator1900 : public std::iterator<std::forward_iterator_tag, Value> {1901 friend class InvertableMap;1902 private:1903 ValueIterator(typename Container::const_iterator _it)1904 : it(_it) {}1905 public:1906 1907 ValueIterator() {}1908 1909 ValueIterator& operator++() { ++it; return *this; }1910 ValueIterator operator++(int) {1911 ValueIterator tmp(*this);1912 operator++();1913 return tmp;1914 }1915 1916 const Value& operator*() const { return it->first; }1917 const Value* operator->() const { return &(it->first); }1918 1919 bool operator==(ValueIterator jt) const { return it == jt.it; }1920 bool operator!=(ValueIterator jt) const { return it != jt.it; }1921 1922 private:1923 typename Container::const_iterator it;1924 };1925 1926 /// \brief Returns an iterator to the first value.1927 ///1928 /// Returns an stl compatible iterator to the1929 /// first value of the map. The values of the1930 /// map can be accessed in the [beginValue, endValue)1931 /// range.1932 ValueIterator beginValue() const {1933 return ValueIterator(_inv_map.begin());1934 }1935 1936 /// \brief Returns an iterator after the last value.1937 ///1938 /// Returns an stl compatible iterator after the1939 /// last value of the map. The values of the1940 /// map can be accessed in the [beginValue, endValue)1941 /// range.1942 ValueIterator endValue() const {1943 return ValueIterator(_inv_map.end());1944 }1945 1946 /// \brief The setter function of the map.1947 ///1948 /// Sets the mapped value.1949 void set(const Key& key, const Value& val) {1950 Value oldval = Map::operator[](key);1951 typename Container::iterator it = _inv_map.find(oldval);1952 if (it != _inv_map.end() && it->second == key) {1953 _inv_map.erase(it);1954 }1955 _inv_map.insert(make_pair(val, key));1956 Map::set(key, val);1957 }1958 1959 /// \brief The getter function of the map.1960 ///1961 /// It gives back the value associated with the key.1962 typename MapTraits<Map>::ConstReturnValue1963 operator[](const Key& key) const {1964 return Map::operator[](key);1965 }1966 1967 /// \brief Gives back the item by its value.1968 ///1969 /// Gives back the item by its value.1970 Key operator()(const Value& key) const {1971 typename Container::const_iterator it = _inv_map.find(key);1972 return it != _inv_map.end() ? it->second : INVALID;1973 }1974 1975 protected:1976 1977 /// \brief Erase the key from the map.1978 ///1979 /// Erase the key to the map. It is called by the1980 /// \c AlterationNotifier.1981 virtual void erase(const Key& key) {1982 Value val = Map::operator[](key);1983 typename Container::iterator it = _inv_map.find(val);1984 if (it != _inv_map.end() && it->second == key) {1985 _inv_map.erase(it);1986 }1987 Map::erase(key);1988 }1989 1990 /// \brief Erase more keys from the map.1991 ///1992 /// Erase more keys from the map. It is called by the1993 /// \c AlterationNotifier.1994 virtual void erase(const std::vector<Key>& keys) {1995 for (int i = 0; i < int(keys.size()); ++i) {1996 Value val = Map::operator[](keys[i]);1997 typename Container::iterator it = _inv_map.find(val);1998 if (it != _inv_map.end() && it->second == keys[i]) {1999 _inv_map.erase(it);2000 }2001 }2002 Map::erase(keys);2003 }2004 2005 /// \brief Clear the keys from the map and inverse map.2006 ///2007 /// Clear the keys from the map and inverse map. It is called by the2008 /// \c AlterationNotifier.2009 virtual void clear() {2010 _inv_map.clear();2011 Map::clear();2012 }2013 2014 public:2015 2016 /// \brief The inverse map type.2017 ///2018 /// The inverse of this map. The subscript operator of the map2019 /// gives back always the item what was last assigned to the value.2020 class InverseMap {2021 public:2022 /// \brief Constructor of the InverseMap.2023 ///2024 /// Constructor of the InverseMap.2025 explicit InverseMap(const InvertableMap& inverted)2026 : _inverted(inverted) {}2027 2028 /// The value type of the InverseMap.2029 typedef typename InvertableMap::Key Value;2030 /// The key type of the InverseMap.2031 typedef typename InvertableMap::Value Key;2032 2033 /// \brief Subscript operator.2034 ///2035 /// Subscript operator. It gives back always the item2036 /// what was last assigned to the value.2037 Value operator[](const Key& key) const {2038 return _inverted(key);2039 }2040 2041 private:2042 const InvertableMap& _inverted;2043 };2044 2045 /// \brief It gives back the just readable inverse map.2046 ///2047 /// It gives back the just readable inverse map.2048 InverseMap inverse() const {2049 return InverseMap(*this);2050 }2051 2052 2053 2054 };2055 2056 /// \brief Provides a mutable, continuous and unique descriptor for each2057 /// item in the graph.2058 ///2059 /// The DescriptorMap class provides a unique and continuous (but mutable)2060 /// descriptor (id) for each item of the same type (e.g. node) in the2061 /// graph. This id is <ul><li>\b unique: different items (nodes) get2062 /// different ids <li>\b continuous: the range of the ids is the set of2063 /// integers between 0 and \c n-1, where \c n is the number of the items of2064 /// this type (e.g. nodes) (so the id of a node can change if you delete an2065 /// other node, i.e. this id is mutable). </ul> This map can be inverted2066 /// with its member class \c InverseMap, or with the \c operator() member.2067 ///2068 /// \tparam _Graph The graph class the \c DescriptorMap belongs to.2069 /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or2070 /// Edge.2071 template <typename _Graph, typename _Item>2072 class DescriptorMap2073 : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {2074 2075 typedef _Item Item;2076 typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;2077 2078 public:2079 /// The graph class of DescriptorMap.2080 typedef _Graph Graph;2081 2082 /// The key type of DescriptorMap (Node, Arc, Edge).2083 typedef typename Map::Key Key;2084 /// The value type of DescriptorMap.2085 typedef typename Map::Value Value;2086 2087 /// \brief Constructor.2088 ///2089 /// Constructor for descriptor map.2090 explicit DescriptorMap(const Graph& _graph) : Map(_graph) {2091 Item it;2092 const typename Map::Notifier* nf = Map::notifier();2093 for (nf->first(it); it != INVALID; nf->next(it)) {2094 Map::set(it, _inv_map.size());2095 _inv_map.push_back(it);2096 }2097 }2098 2099 protected:2100 2101 /// \brief Add a new key to the map.2102 ///2103 /// Add a new key to the map. It is called by the2104 /// \c AlterationNotifier.2105 virtual void add(const Item& item) {2106 Map::add(item);2107 Map::set(item, _inv_map.size());2108 _inv_map.push_back(item);2109 }2110 2111 /// \brief Add more new keys to the map.2112 ///2113 /// Add more new keys to the map. It is called by the2114 /// \c AlterationNotifier.2115 virtual void add(const std::vector<Item>& items) {2116 Map::add(items);2117 for (int i = 0; i < int(items.size()); ++i) {2118 Map::set(items[i], _inv_map.size());2119 _inv_map.push_back(items[i]);2120 }2121 }2122 2123 /// \brief Erase the key from the map.2124 ///2125 /// Erase the key from the map. It is called by the2126 /// \c AlterationNotifier.2127 virtual void erase(const Item& item) {2128 Map::set(_inv_map.back(), Map::operator[](item));2129 _inv_map[Map::operator[](item)] = _inv_map.back();2130 _inv_map.pop_back();2131 Map::erase(item);2132 }2133 2134 /// \brief Erase more keys from the map.2135 ///2136 /// Erase more keys from the map. It is called by the2137 /// \c AlterationNotifier.2138 virtual void erase(const std::vector<Item>& items) {2139 for (int i = 0; i < int(items.size()); ++i) {2140 Map::set(_inv_map.back(), Map::operator[](items[i]));2141 _inv_map[Map::operator[](items[i])] = _inv_map.back();2142 _inv_map.pop_back();2143 }2144 Map::erase(items);2145 }2146 2147 /// \brief Build the unique map.2148 ///2149 /// Build the unique map. It is called by the2150 /// \c AlterationNotifier.2151 virtual void build() {2152 Map::build();2153 Item it;2154 const typename Map::Notifier* nf = Map::notifier();2155 for (nf->first(it); it != INVALID; nf->next(it)) {2156 Map::set(it, _inv_map.size());2157 _inv_map.push_back(it);2158 }2159 }2160 2161 /// \brief Clear the keys from the map.2162 ///2163 /// Clear the keys from the map. It is called by the2164 /// \c AlterationNotifier.2165 virtual void clear() {2166 _inv_map.clear();2167 Map::clear();2168 }2169 2170 public:2171 2172 /// \brief Returns the maximal value plus one.2173 ///2174 /// Returns the maximal value plus one in the map.2175 unsigned int size() const {2176 return _inv_map.size();2177 }2178 2179 /// \brief Swaps the position of the two items in the map.2180 ///2181 /// Swaps the position of the two items in the map.2182 void swap(const Item& p, const Item& q) {2183 int pi = Map::operator[](p);2184 int qi = Map::operator[](q);2185 Map::set(p, qi);2186 _inv_map[qi] = p;2187 Map::set(q, pi);2188 _inv_map[pi] = q;2189 }2190 2191 /// \brief Gives back the \e descriptor of the item.2192 ///2193 /// Gives back the mutable and unique \e descriptor of the map.2194 int operator[](const Item& item) const {2195 return Map::operator[](item);2196 }2197 2198 /// \brief Gives back the item by its descriptor.2199 ///2200 /// Gives back th item by its descriptor.2201 Item operator()(int id) const {2202 return _inv_map[id];2203 }2204 2205 private:2206 2207 typedef std::vector<Item> Container;2208 Container _inv_map;2209 2210 public:2211 /// \brief The inverse map type of DescriptorMap.2212 ///2213 /// The inverse map type of DescriptorMap.2214 class InverseMap {2215 public:2216 /// \brief Constructor of the InverseMap.2217 ///2218 /// Constructor of the InverseMap.2219 explicit InverseMap(const DescriptorMap& inverted)2220 : _inverted(inverted) {}2221 2222 2223 /// The value type of the InverseMap.2224 typedef typename DescriptorMap::Key Value;2225 /// The key type of the InverseMap.2226 typedef typename DescriptorMap::Value Key;2227 2228 /// \brief Subscript operator.2229 ///2230 /// Subscript operator. It gives back the item2231 /// that the descriptor belongs to currently.2232 Value operator[](const Key& key) const {2233 return _inverted(key);2234 }2235 2236 /// \brief Size of the map.2237 ///2238 /// Returns the size of the map.2239 unsigned int size() const {2240 return _inverted.size();2241 }2242 2243 private:2244 const DescriptorMap& _inverted;2245 };2246 2247 /// \brief Gives back the inverse of the map.2248 ///2249 /// Gives back the inverse of the map.2250 const InverseMap inverse() const {2251 return InverseMap(*this);2252 }2253 1848 }; 2254 1849 -
test/graph_utils_test.cc
r220 r324 36 36 { 37 37 Digraph digraph; 38 typename Digraph::template NodeMap<int> nodes(digraph); 39 std::vector<Node> invNodes; 38 40 for (int i = 0; i < 10; ++i) { 39 digraph.addNode(); 40 } 41 DescriptorMap<Digraph, Node> nodes(digraph); 42 typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes); 41 invNodes.push_back(digraph.addNode()); 42 nodes[invNodes.back()]=invNodes.size()-1; 43 } 43 44 for (int i = 0; i < 100; ++i) { 44 45 int src = rnd[invNodes.size()]; … … 47 48 } 48 49 typename Digraph::template ArcMap<bool> found(digraph, false); 49 DescriptorMap<Digraph, Arc> arcs(digraph);50 50 for (NodeIt src(digraph); src != INVALID; ++src) { 51 51 for (NodeIt trg(digraph); trg != INVALID; ++trg) { … … 111 111 TEMPLATE_GRAPH_TYPEDEFS(Graph); 112 112 Graph graph; 113 typename Graph::template NodeMap<int> nodes(graph); 114 std::vector<Node> invNodes; 113 115 for (int i = 0; i < 10; ++i) { 114 graph.addNode(); 115 } 116 DescriptorMap<Graph, Node> nodes(graph); 117 typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes); 116 invNodes.push_back(graph.addNode()); 117 nodes[invNodes.back()]=invNodes.size()-1; 118 } 118 119 for (int i = 0; i < 100; ++i) { 119 120 int src = rnd[invNodes.size()]; … … 122 123 } 123 124 typename Graph::template EdgeMap<int> found(graph, 0); 124 DescriptorMap<Graph, Edge> edges(graph);125 125 for (NodeIt src(graph); src != INVALID; ++src) { 126 126 for (NodeIt trg(graph); trg != INVALID; ++trg) {
Note: See TracChangeset
for help on using the changeset viewer.