lemon/maps.h
changeset 576 745e182d0139
parent 559 c5fd2d996909
child 584 33c6b6e755cd
equal deleted inserted replaced
29:a57b20ae1999 30:9c531ecc48f9
  1830   ///
  1830   ///
  1831   /// \tparam GR The graph type.
  1831   /// \tparam GR The graph type.
  1832   /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
  1832   /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
  1833   /// \c GR::Edge).
  1833   /// \c GR::Edge).
  1834   ///
  1834   ///
  1835   /// \see DescriptorMap
  1835   /// \see RangeIdMap
  1836   template <typename GR, typename K>
  1836   template <typename GR, typename K>
  1837   class IdMap : public MapBase<K, int> {
  1837   class IdMap : public MapBase<K, int> {
  1838   public:
  1838   public:
  1839     /// The graph type of IdMap.
  1839     /// The graph type of IdMap.
  1840     typedef GR Graph;
  1840     typedef GR Graph;
  1896     /// Gives back the inverse of the IdMap.
  1896     /// Gives back the inverse of the IdMap.
  1897     InverseMap inverse() const { return InverseMap(*_graph);}
  1897     InverseMap inverse() const { return InverseMap(*_graph);}
  1898   };
  1898   };
  1899 
  1899 
  1900 
  1900 
  1901   /// \brief General invertable graph map type.
  1901   /// \brief General cross reference graph map type.
  1902 
  1902 
  1903   /// This class provides simple invertable graph maps.
  1903   /// This class provides simple invertable graph maps.
  1904   /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
  1904   /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
  1905   /// and if a key is set to a new value then store it
  1905   /// and if a key is set to a new value then store it
  1906   /// in the inverse map.
  1906   /// in the inverse map.
  1913   /// \c GR::Edge).
  1913   /// \c GR::Edge).
  1914   /// \tparam V The value type of the map.
  1914   /// \tparam V The value type of the map.
  1915   ///
  1915   ///
  1916   /// \see IterableValueMap
  1916   /// \see IterableValueMap
  1917   template <typename GR, typename K, typename V>
  1917   template <typename GR, typename K, typename V>
  1918   class InvertableMap
  1918   class CrossRefMap
  1919     : protected ItemSetTraits<GR, K>::template Map<V>::Type {
  1919     : protected ItemSetTraits<GR, K>::template Map<V>::Type {
  1920   private:
  1920   private:
  1921 
  1921 
  1922     typedef typename ItemSetTraits<GR, K>::
  1922     typedef typename ItemSetTraits<GR, K>::
  1923       template Map<V>::Type Map;
  1923       template Map<V>::Type Map;
  1925     typedef std::map<V, K> Container;
  1925     typedef std::map<V, K> Container;
  1926     Container _inv_map;
  1926     Container _inv_map;
  1927 
  1927 
  1928   public:
  1928   public:
  1929 
  1929 
  1930     /// The graph type of InvertableMap.
  1930     /// The graph type of CrossRefMap.
  1931     typedef GR Graph;
  1931     typedef GR Graph;
  1932     /// The key type of InvertableMap (\c Node, \c Arc or \c Edge).
  1932     /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
  1933     typedef K Item;
  1933     typedef K Item;
  1934     /// The key type of InvertableMap (\c Node, \c Arc or \c Edge).
  1934     /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
  1935     typedef K Key;
  1935     typedef K Key;
  1936     /// The value type of InvertableMap.
  1936     /// The value type of CrossRefMap.
  1937     typedef V Value;
  1937     typedef V Value;
  1938 
  1938 
  1939     /// \brief Constructor.
  1939     /// \brief Constructor.
  1940     ///
  1940     ///
  1941     /// Construct a new InvertableMap for the given graph.
  1941     /// Construct a new CrossRefMap for the given graph.
  1942     explicit InvertableMap(const Graph& graph) : Map(graph) {}
  1942     explicit CrossRefMap(const Graph& graph) : Map(graph) {}
  1943 
  1943 
  1944     /// \brief Forward iterator for values.
  1944     /// \brief Forward iterator for values.
  1945     ///
  1945     ///
  1946     /// This iterator is an stl compatible forward
  1946     /// This iterator is an stl compatible forward
  1947     /// iterator on the values of the map. The values can
  1947     /// iterator on the values of the map. The values can
  1948     /// be accessed in the <tt>[beginValue, endValue)</tt> range.
  1948     /// be accessed in the <tt>[beginValue, endValue)</tt> range.
  1949     class ValueIterator
  1949     class ValueIterator
  1950       : public std::iterator<std::forward_iterator_tag, Value> {
  1950       : public std::iterator<std::forward_iterator_tag, Value> {
  1951       friend class InvertableMap;
  1951       friend class CrossRefMap;
  1952     private:
  1952     private:
  1953       ValueIterator(typename Container::const_iterator _it)
  1953       ValueIterator(typename Container::const_iterator _it)
  1954         : it(_it) {}
  1954         : it(_it) {}
  1955     public:
  1955     public:
  1956 
  1956 
  2070     class InverseMap {
  2070     class InverseMap {
  2071     public:
  2071     public:
  2072       /// \brief Constructor
  2072       /// \brief Constructor
  2073       ///
  2073       ///
  2074       /// Constructor of the InverseMap.
  2074       /// Constructor of the InverseMap.
  2075       explicit InverseMap(const InvertableMap& inverted)
  2075       explicit InverseMap(const CrossRefMap& inverted)
  2076         : _inverted(inverted) {}
  2076         : _inverted(inverted) {}
  2077 
  2077 
  2078       /// The value type of the InverseMap.
  2078       /// The value type of the InverseMap.
  2079       typedef typename InvertableMap::Key Value;
  2079       typedef typename CrossRefMap::Key Value;
  2080       /// The key type of the InverseMap.
  2080       /// The key type of the InverseMap.
  2081       typedef typename InvertableMap::Value Key;
  2081       typedef typename CrossRefMap::Value Key;
  2082 
  2082 
  2083       /// \brief Subscript operator.
  2083       /// \brief Subscript operator.
  2084       ///
  2084       ///
  2085       /// Subscript operator. It gives back the item
  2085       /// Subscript operator. It gives back the item
  2086       /// that was last assigned to the given value.
  2086       /// that was last assigned to the given value.
  2087       Value operator[](const Key& key) const {
  2087       Value operator[](const Key& key) const {
  2088         return _inverted(key);
  2088         return _inverted(key);
  2089       }
  2089       }
  2090 
  2090 
  2091     private:
  2091     private:
  2092       const InvertableMap& _inverted;
  2092       const CrossRefMap& _inverted;
  2093     };
  2093     };
  2094 
  2094 
  2095     /// \brief It gives back the read-only inverse map.
  2095     /// \brief It gives back the read-only inverse map.
  2096     ///
  2096     ///
  2097     /// It gives back the read-only inverse map.
  2097     /// It gives back the read-only inverse map.
  2099       return InverseMap(*this);
  2099       return InverseMap(*this);
  2100     }
  2100     }
  2101 
  2101 
  2102   };
  2102   };
  2103 
  2103 
  2104   /// \brief Provides a mutable, continuous and unique descriptor for each
  2104   /// \brief Provides continuous and unique ID for the
  2105   /// item in a graph.
  2105   /// items of a graph.
  2106   ///
  2106   ///
  2107   /// DescriptorMap provides a unique and continuous (but mutable)
  2107   /// RangeIdMap provides a unique and continuous
  2108   /// descriptor (id) for each item of the same type (\c Node, \c Arc or
  2108   /// ID for each item of a given type (\c Node, \c Arc or
  2109   /// \c Edge) in a graph. This id is
  2109   /// \c Edge) in a graph. This id is
  2110   ///  - \b unique: different items get different ids,
  2110   ///  - \b unique: different items get different ids,
  2111   ///  - \b continuous: the range of the ids is the set of integers
  2111   ///  - \b continuous: the range of the ids is the set of integers
  2112   ///    between 0 and \c n-1, where \c n is the number of the items of
  2112   ///    between 0 and \c n-1, where \c n is the number of the items of
  2113   ///    this type (\c Node, \c Arc or \c Edge). So the id of an item can
  2113   ///    this type (\c Node, \c Arc or \c Edge).
  2114   ///    change if you delete an other item of the same type, i.e. this
  2114   ///  - So, the ids can change when deleting an item of the same type.
  2115   ///    id is mutable.
       
  2116   ///
  2115   ///
  2117   /// Thus this id is not (necessarily) the same as what can get using
  2116   /// Thus this id is not (necessarily) the same as what can get using
  2118   /// the \c id() function of the graph or \ref IdMap.
  2117   /// the \c id() function of the graph or \ref IdMap.
  2119   /// This map can be inverted with its member class \c InverseMap,
  2118   /// This map can be inverted with its member class \c InverseMap,
  2120   /// or with the \c operator() member.
  2119   /// or with the \c operator() member.
  2123   /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
  2122   /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
  2124   /// \c GR::Edge).
  2123   /// \c GR::Edge).
  2125   ///
  2124   ///
  2126   /// \see IdMap
  2125   /// \see IdMap
  2127   template <typename GR, typename K>
  2126   template <typename GR, typename K>
  2128   class DescriptorMap
  2127   class RangeIdMap
  2129     : protected ItemSetTraits<GR, K>::template Map<int>::Type {
  2128     : protected ItemSetTraits<GR, K>::template Map<int>::Type {
  2130 
  2129 
  2131     typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Map;
  2130     typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Map;
  2132 
  2131 
  2133   public:
  2132   public:
  2134     /// The graph type of DescriptorMap.
  2133     /// The graph type of RangeIdMap.
  2135     typedef GR Graph;
  2134     typedef GR Graph;
  2136     /// The key type of DescriptorMap (\c Node, \c Arc or \c Edge).
  2135     /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge).
  2137     typedef K Item;
  2136     typedef K Item;
  2138     /// The key type of DescriptorMap (\c Node, \c Arc or \c Edge).
  2137     /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge).
  2139     typedef K Key;
  2138     typedef K Key;
  2140     /// The value type of DescriptorMap.
  2139     /// The value type of RangeIdMap.
  2141     typedef int Value;
  2140     typedef int Value;
  2142 
  2141 
  2143     /// \brief Constructor.
  2142     /// \brief Constructor.
  2144     ///
  2143     ///
  2145     /// Constructor for descriptor map.
  2144     /// Constructor.
  2146     explicit DescriptorMap(const Graph& gr) : Map(gr) {
  2145     explicit RangeIdMap(const Graph& gr) : Map(gr) {
  2147       Item it;
  2146       Item it;
  2148       const typename Map::Notifier* nf = Map::notifier();
  2147       const typename Map::Notifier* nf = Map::notifier();
  2149       for (nf->first(it); it != INVALID; nf->next(it)) {
  2148       for (nf->first(it); it != INVALID; nf->next(it)) {
  2150         Map::set(it, _inv_map.size());
  2149         Map::set(it, _inv_map.size());
  2151         _inv_map.push_back(it);
  2150         _inv_map.push_back(it);
  2242       _inv_map[qi] = p;
  2241       _inv_map[qi] = p;
  2243       Map::set(q, pi);
  2242       Map::set(q, pi);
  2244       _inv_map[pi] = q;
  2243       _inv_map[pi] = q;
  2245     }
  2244     }
  2246 
  2245 
  2247     /// \brief Gives back the \e descriptor of the item.
  2246     /// \brief Gives back the \e RangeId of the item
  2248     ///
  2247     ///
  2249     /// Gives back the mutable and unique \e descriptor of the map.
  2248     /// Gives back the \e RangeId of the item.
  2250     int operator[](const Item& item) const {
  2249     int operator[](const Item& item) const {
  2251       return Map::operator[](item);
  2250       return Map::operator[](item);
  2252     }
  2251     }
  2253 
  2252 
  2254     /// \brief Gives back the item by its descriptor.
  2253     /// \brief Gives back the item belonging to a \e RangeId
  2255     ///
  2254     /// 
  2256     /// Gives back th item by its descriptor.
  2255     /// Gives back the item belonging to a \e RangeId.
  2257     Item operator()(int id) const {
  2256     Item operator()(int id) const {
  2258       return _inv_map[id];
  2257       return _inv_map[id];
  2259     }
  2258     }
  2260 
  2259 
  2261   private:
  2260   private:
  2263     typedef std::vector<Item> Container;
  2262     typedef std::vector<Item> Container;
  2264     Container _inv_map;
  2263     Container _inv_map;
  2265 
  2264 
  2266   public:
  2265   public:
  2267 
  2266 
  2268     /// \brief The inverse map type of DescriptorMap.
  2267     /// \brief The inverse map type of RangeIdMap.
  2269     ///
  2268     ///
  2270     /// The inverse map type of DescriptorMap.
  2269     /// The inverse map type of RangeIdMap.
  2271     class InverseMap {
  2270     class InverseMap {
  2272     public:
  2271     public:
  2273       /// \brief Constructor
  2272       /// \brief Constructor
  2274       ///
  2273       ///
  2275       /// Constructor of the InverseMap.
  2274       /// Constructor of the InverseMap.
  2276       explicit InverseMap(const DescriptorMap& inverted)
  2275       explicit InverseMap(const RangeIdMap& inverted)
  2277         : _inverted(inverted) {}
  2276         : _inverted(inverted) {}
  2278 
  2277 
  2279 
  2278 
  2280       /// The value type of the InverseMap.
  2279       /// The value type of the InverseMap.
  2281       typedef typename DescriptorMap::Key Value;
  2280       typedef typename RangeIdMap::Key Value;
  2282       /// The key type of the InverseMap.
  2281       /// The key type of the InverseMap.
  2283       typedef typename DescriptorMap::Value Key;
  2282       typedef typename RangeIdMap::Value Key;
  2284 
  2283 
  2285       /// \brief Subscript operator.
  2284       /// \brief Subscript operator.
  2286       ///
  2285       ///
  2287       /// Subscript operator. It gives back the item
  2286       /// Subscript operator. It gives back the item
  2288       /// that the descriptor currently belongs to.
  2287       /// that the descriptor currently belongs to.
  2296       unsigned int size() const {
  2295       unsigned int size() const {
  2297         return _inverted.size();
  2296         return _inverted.size();
  2298       }
  2297       }
  2299 
  2298 
  2300     private:
  2299     private:
  2301       const DescriptorMap& _inverted;
  2300       const RangeIdMap& _inverted;
  2302     };
  2301     };
  2303 
  2302 
  2304     /// \brief Gives back the inverse of the map.
  2303     /// \brief Gives back the inverse of the map.
  2305     ///
  2304     ///
  2306     /// Gives back the inverse of the map.
  2305     /// Gives back the inverse of the map.