equal
deleted
inserted
replaced
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: |