1.1 --- a/lemon/maps.h	Thu Aug 20 22:52:03 2009 +0200
     1.2 +++ b/lemon/maps.h	Thu Aug 20 22:52:16 2009 +0200
     1.3 @@ -1902,13 +1902,14 @@
     1.4    /// \brief General cross reference graph map type.
     1.5  
     1.6    /// This class provides simple invertable graph maps.
     1.7 -  /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
     1.8 -  /// and if a key is set to a new value then store it
     1.9 -  /// in the inverse map.
    1.10 -  ///
    1.11 +  /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
    1.12 +  /// and if a key is set to a new value, then stores it in the inverse map.
    1.13    /// The values of the map can be accessed
    1.14    /// with stl compatible forward iterator.
    1.15    ///
    1.16 +  /// This type is not reference map, so it cannot be modified with
    1.17 +  /// the subscript operator.
    1.18 +  ///
    1.19    /// \tparam GR The graph type.
    1.20    /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
    1.21    /// \c GR::Edge).
    1.22 @@ -1923,7 +1924,7 @@
    1.23      typedef typename ItemSetTraits<GR, K>::
    1.24        template Map<V>::Type Map;
    1.25  
    1.26 -    typedef std::map<V, K> Container;
    1.27 +    typedef std::multimap<V, K> Container;
    1.28      Container _inv_map;
    1.29  
    1.30    public:
    1.31 @@ -1948,6 +1949,8 @@
    1.32      /// This iterator is an stl compatible forward
    1.33      /// iterator on the values of the map. The values can
    1.34      /// be accessed in the <tt>[beginValue, endValue)</tt> range.
    1.35 +    /// They are considered with multiplicity, so each value is
    1.36 +    /// traversed for each item it is assigned to.
    1.37      class ValueIterator
    1.38        : public std::iterator<std::forward_iterator_tag, Value> {
    1.39        friend class CrossRefMap;
    1.40 @@ -2000,11 +2003,15 @@
    1.41      /// Sets the value associated with the given key.
    1.42      void set(const Key& key, const Value& val) {
    1.43        Value oldval = Map::operator[](key);
    1.44 -      typename Container::iterator it = _inv_map.find(oldval);
    1.45 -      if (it != _inv_map.end() && it->second == key) {
    1.46 -        _inv_map.erase(it);
    1.47 +      typename Container::iterator it;
    1.48 +      for (it = _inv_map.equal_range(oldval).first;
    1.49 +           it != _inv_map.equal_range(oldval).second; ++it) {
    1.50 +        if (it->second == key) {
    1.51 +          _inv_map.erase(it);
    1.52 +          break;
    1.53 +        }
    1.54        }
    1.55 -      _inv_map.insert(make_pair(val, key));
    1.56 +      _inv_map.insert(std::make_pair(val, key));
    1.57        Map::set(key, val);
    1.58      }
    1.59  
    1.60 @@ -2016,11 +2023,14 @@
    1.61        return Map::operator[](key);
    1.62      }
    1.63  
    1.64 -    /// \brief Gives back the item by its value.
    1.65 +    /// \brief Gives back an item by its value.
    1.66      ///
    1.67 -    /// Gives back the item by its value.
    1.68 -    Key operator()(const Value& key) const {
    1.69 -      typename Container::const_iterator it = _inv_map.find(key);
    1.70 +    /// This function gives back an item that is assigned to
    1.71 +    /// the given value or \c INVALID if no such item exists.
    1.72 +    /// If there are more items with the same associated value,
    1.73 +    /// only one of them is returned.
    1.74 +    Key operator()(const Value& val) const {
    1.75 +      typename Container::const_iterator it = _inv_map.find(val);
    1.76        return it != _inv_map.end() ? it->second : INVALID;
    1.77      }
    1.78  
    1.79 @@ -2032,9 +2042,13 @@
    1.80      /// \c AlterationNotifier.
    1.81      virtual void erase(const Key& key) {
    1.82        Value val = Map::operator[](key);
    1.83 -      typename Container::iterator it = _inv_map.find(val);
    1.84 -      if (it != _inv_map.end() && it->second == key) {
    1.85 -        _inv_map.erase(it);
    1.86 +      typename Container::iterator it;
    1.87 +      for (it = _inv_map.equal_range(val).first;
    1.88 +           it != _inv_map.equal_range(val).second; ++it) {
    1.89 +        if (it->second == key) {
    1.90 +          _inv_map.erase(it);
    1.91 +          break;
    1.92 +        }
    1.93        }
    1.94        Map::erase(key);
    1.95      }
    1.96 @@ -2046,9 +2060,13 @@
    1.97      virtual void erase(const std::vector<Key>& keys) {
    1.98        for (int i = 0; i < int(keys.size()); ++i) {
    1.99          Value val = Map::operator[](keys[i]);
   1.100 -        typename Container::iterator it = _inv_map.find(val);
   1.101 -        if (it != _inv_map.end() && it->second == keys[i]) {
   1.102 -          _inv_map.erase(it);
   1.103 +        typename Container::iterator it;
   1.104 +        for (it = _inv_map.equal_range(val).first;
   1.105 +             it != _inv_map.equal_range(val).second; ++it) {
   1.106 +          if (it->second == keys[i]) {
   1.107 +            _inv_map.erase(it);
   1.108 +            break;
   1.109 +          }
   1.110          }
   1.111        }
   1.112        Map::erase(keys);
   1.113 @@ -2084,8 +2102,9 @@
   1.114  
   1.115        /// \brief Subscript operator.
   1.116        ///
   1.117 -      /// Subscript operator. It gives back the item
   1.118 -      /// that was last assigned to the given value.
   1.119 +      /// Subscript operator. It gives back an item
   1.120 +      /// that is assigned to the given value or \c INVALID
   1.121 +      /// if no such item exists.
   1.122        Value operator[](const Key& key) const {
   1.123          return _inverted(key);
   1.124        }