lemon/maps.h
branch1.0
changeset 303 de38fca76780
parent 280 e7f8647ce760
child 320 12626fc94ccf
equal deleted inserted replaced
24:9541e07287f8 25:beb20f54b1ae
  1843     /// \brief Gives back the inverse of the map.
  1843     /// \brief Gives back the inverse of the map.
  1844     ///
  1844     ///
  1845     /// Gives back the inverse of the IdMap.
  1845     /// Gives back the inverse of the IdMap.
  1846     InverseMap inverse() const { return InverseMap(*_graph);}
  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 ReadWriteMap
       
  1855   /// and if a key is set to a new value then store it
       
  1856   /// in the inverse map.
       
  1857   ///
       
  1858   /// The values of the map can be accessed
       
  1859   /// 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 IterableValueMap
       
  1866   template <typename _Graph, typename _Item, typename _Value>
       
  1867   class InvertableMap
       
  1868     : 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 forward
       
  1896     /// iterator on the values of the map. The values can
       
  1897     /// be accessed in the [beginValue, endValue) range.
       
  1898     ///
       
  1899     class ValueIterator
       
  1900       : 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 the
       
  1929     /// first value of the map. The values of the
       
  1930     /// 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 the
       
  1939     /// last value of the map. The values of the
       
  1940     /// 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>::ConstReturnValue
       
  1963     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 the
       
  1980     /// \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 the
       
  1993     /// \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 the
       
  2008     /// \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 map
       
  2019     /// 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 item
       
  2036       /// 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 each
       
  2057   /// 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 the
       
  2061   /// graph. This id is <ul><li>\b unique: different items (nodes) get
       
  2062   /// different ids <li>\b continuous: the range of the ids is the set of
       
  2063   /// integers between 0 and \c n-1, where \c n is the number of the items of
       
  2064   /// this type (e.g. nodes) (so the id of a node can change if you delete an
       
  2065   /// other node, i.e. this id is mutable).  </ul> This map can be inverted
       
  2066   /// 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 or
       
  2070   /// Edge.
       
  2071   template <typename _Graph, typename _Item>
       
  2072   class DescriptorMap
       
  2073     : 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 the
       
  2104     /// \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 the
       
  2114     /// \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 the
       
  2126     /// \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 the
       
  2137     /// \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 the
       
  2150     /// \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 the
       
  2164     /// \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 item
       
  2231       /// 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 
  2255   /// \brief Returns the source of the given arc.
  1850   /// \brief Returns the source of the given arc.
  2256   ///
  1851   ///
  2257   /// The SourceMap gives back the source Node of the given arc.
  1852   /// The SourceMap gives back the source Node of the given arc.