lemon/maps.h
changeset 692 33f417de9e70
parent 617 4137ef9aacc6
child 695 8dae88c5943e
child 720 6e8c27ee9079
equal deleted inserted replaced
32:be941891c143 33:d3ddbcf08d47
  1900 
  1900 
  1901 
  1901 
  1902   /// \brief General cross reference graph map type.
  1902   /// \brief General cross reference graph map type.
  1903 
  1903 
  1904   /// This class provides simple invertable graph maps.
  1904   /// This class provides simple invertable graph maps.
  1905   /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
  1905   /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
  1906   /// and if a key is set to a new value then store it
  1906   /// and if a key is set to a new value, then stores it in the inverse map.
  1907   /// in the inverse map.
       
  1908   ///
       
  1909   /// The values of the map can be accessed
  1907   /// The values of the map can be accessed
  1910   /// with stl compatible forward iterator.
  1908   /// with stl compatible forward iterator.
       
  1909   ///
       
  1910   /// This type is not reference map, so it cannot be modified with
       
  1911   /// the subscript operator.
  1911   ///
  1912   ///
  1912   /// \tparam GR The graph type.
  1913   /// \tparam GR The graph type.
  1913   /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
  1914   /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
  1914   /// \c GR::Edge).
  1915   /// \c GR::Edge).
  1915   /// \tparam V The value type of the map.
  1916   /// \tparam V The value type of the map.
  1921   private:
  1922   private:
  1922 
  1923 
  1923     typedef typename ItemSetTraits<GR, K>::
  1924     typedef typename ItemSetTraits<GR, K>::
  1924       template Map<V>::Type Map;
  1925       template Map<V>::Type Map;
  1925 
  1926 
  1926     typedef std::map<V, K> Container;
  1927     typedef std::multimap<V, K> Container;
  1927     Container _inv_map;
  1928     Container _inv_map;
  1928 
  1929 
  1929   public:
  1930   public:
  1930 
  1931 
  1931     /// The graph type of CrossRefMap.
  1932     /// The graph type of CrossRefMap.
  1946     /// \brief Forward iterator for values.
  1947     /// \brief Forward iterator for values.
  1947     ///
  1948     ///
  1948     /// This iterator is an stl compatible forward
  1949     /// This iterator is an stl compatible forward
  1949     /// iterator on the values of the map. The values can
  1950     /// iterator on the values of the map. The values can
  1950     /// be accessed in the <tt>[beginValue, endValue)</tt> range.
  1951     /// be accessed in the <tt>[beginValue, endValue)</tt> range.
       
  1952     /// They are considered with multiplicity, so each value is
       
  1953     /// traversed for each item it is assigned to.
  1951     class ValueIterator
  1954     class ValueIterator
  1952       : public std::iterator<std::forward_iterator_tag, Value> {
  1955       : public std::iterator<std::forward_iterator_tag, Value> {
  1953       friend class CrossRefMap;
  1956       friend class CrossRefMap;
  1954     private:
  1957     private:
  1955       ValueIterator(typename Container::const_iterator _it)
  1958       ValueIterator(typename Container::const_iterator _it)
  1998     /// \brief Sets the value associated with the given key.
  2001     /// \brief Sets the value associated with the given key.
  1999     ///
  2002     ///
  2000     /// Sets the value associated with the given key.
  2003     /// Sets the value associated with the given key.
  2001     void set(const Key& key, const Value& val) {
  2004     void set(const Key& key, const Value& val) {
  2002       Value oldval = Map::operator[](key);
  2005       Value oldval = Map::operator[](key);
  2003       typename Container::iterator it = _inv_map.find(oldval);
  2006       typename Container::iterator it;
  2004       if (it != _inv_map.end() && it->second == key) {
  2007       for (it = _inv_map.equal_range(oldval).first;
  2005         _inv_map.erase(it);
  2008            it != _inv_map.equal_range(oldval).second; ++it) {
       
  2009         if (it->second == key) {
       
  2010           _inv_map.erase(it);
       
  2011           break;
       
  2012         }
  2006       }
  2013       }
  2007       _inv_map.insert(make_pair(val, key));
  2014       _inv_map.insert(std::make_pair(val, key));
  2008       Map::set(key, val);
  2015       Map::set(key, val);
  2009     }
  2016     }
  2010 
  2017 
  2011     /// \brief Returns the value associated with the given key.
  2018     /// \brief Returns the value associated with the given key.
  2012     ///
  2019     ///
  2014     typename MapTraits<Map>::ConstReturnValue
  2021     typename MapTraits<Map>::ConstReturnValue
  2015     operator[](const Key& key) const {
  2022     operator[](const Key& key) const {
  2016       return Map::operator[](key);
  2023       return Map::operator[](key);
  2017     }
  2024     }
  2018 
  2025 
  2019     /// \brief Gives back the item by its value.
  2026     /// \brief Gives back an item by its value.
  2020     ///
  2027     ///
  2021     /// Gives back the item by its value.
  2028     /// This function gives back an item that is assigned to
  2022     Key operator()(const Value& key) const {
  2029     /// the given value or \c INVALID if no such item exists.
  2023       typename Container::const_iterator it = _inv_map.find(key);
  2030     /// If there are more items with the same associated value,
       
  2031     /// only one of them is returned.
       
  2032     Key operator()(const Value& val) const {
       
  2033       typename Container::const_iterator it = _inv_map.find(val);
  2024       return it != _inv_map.end() ? it->second : INVALID;
  2034       return it != _inv_map.end() ? it->second : INVALID;
  2025     }
  2035     }
  2026 
  2036 
  2027   protected:
  2037   protected:
  2028 
  2038 
  2030     ///
  2040     ///
  2031     /// Erase the key from the map and the inverse map. It is called by the
  2041     /// Erase the key from the map and the inverse map. It is called by the
  2032     /// \c AlterationNotifier.
  2042     /// \c AlterationNotifier.
  2033     virtual void erase(const Key& key) {
  2043     virtual void erase(const Key& key) {
  2034       Value val = Map::operator[](key);
  2044       Value val = Map::operator[](key);
  2035       typename Container::iterator it = _inv_map.find(val);
  2045       typename Container::iterator it;
  2036       if (it != _inv_map.end() && it->second == key) {
  2046       for (it = _inv_map.equal_range(val).first;
  2037         _inv_map.erase(it);
  2047            it != _inv_map.equal_range(val).second; ++it) {
       
  2048         if (it->second == key) {
       
  2049           _inv_map.erase(it);
       
  2050           break;
       
  2051         }
  2038       }
  2052       }
  2039       Map::erase(key);
  2053       Map::erase(key);
  2040     }
  2054     }
  2041 
  2055 
  2042     /// \brief Erase more keys from the map and the inverse map.
  2056     /// \brief Erase more keys from the map and the inverse map.
  2044     /// Erase more keys from the map and the inverse map. It is called by the
  2058     /// Erase more keys from the map and the inverse map. It is called by the
  2045     /// \c AlterationNotifier.
  2059     /// \c AlterationNotifier.
  2046     virtual void erase(const std::vector<Key>& keys) {
  2060     virtual void erase(const std::vector<Key>& keys) {
  2047       for (int i = 0; i < int(keys.size()); ++i) {
  2061       for (int i = 0; i < int(keys.size()); ++i) {
  2048         Value val = Map::operator[](keys[i]);
  2062         Value val = Map::operator[](keys[i]);
  2049         typename Container::iterator it = _inv_map.find(val);
  2063         typename Container::iterator it;
  2050         if (it != _inv_map.end() && it->second == keys[i]) {
  2064         for (it = _inv_map.equal_range(val).first;
  2051           _inv_map.erase(it);
  2065              it != _inv_map.equal_range(val).second; ++it) {
       
  2066           if (it->second == keys[i]) {
       
  2067             _inv_map.erase(it);
       
  2068             break;
       
  2069           }
  2052         }
  2070         }
  2053       }
  2071       }
  2054       Map::erase(keys);
  2072       Map::erase(keys);
  2055     }
  2073     }
  2056 
  2074 
  2082       /// The key type of the InverseMap.
  2100       /// The key type of the InverseMap.
  2083       typedef typename CrossRefMap::Value Key;
  2101       typedef typename CrossRefMap::Value Key;
  2084 
  2102 
  2085       /// \brief Subscript operator.
  2103       /// \brief Subscript operator.
  2086       ///
  2104       ///
  2087       /// Subscript operator. It gives back the item
  2105       /// Subscript operator. It gives back an item
  2088       /// that was last assigned to the given value.
  2106       /// that is assigned to the given value or \c INVALID
       
  2107       /// if no such item exists.
  2089       Value operator[](const Key& key) const {
  2108       Value operator[](const Key& key) const {
  2090         return _inverted(key);
  2109         return _inverted(key);
  2091       }
  2110       }
  2092 
  2111 
  2093     private:
  2112     private: