1.1 --- a/lemon/maps.h Fri May 29 17:46:48 2009 +0100
1.2 +++ b/lemon/maps.h Thu Jul 23 18:09:41 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 }
2.1 --- a/test/maps_test.cc Fri May 29 17:46:48 2009 +0100
2.2 +++ b/test/maps_test.cc Thu Jul 23 18:09:41 2009 +0200
2.3 @@ -22,6 +22,7 @@
2.4 #include <lemon/concept_check.h>
2.5 #include <lemon/concepts/maps.h>
2.6 #include <lemon/maps.h>
2.7 +#include <lemon/list_graph.h>
2.8
2.9 #include "test_tools.h"
2.10
2.11 @@ -348,6 +349,40 @@
2.12 it != map2.end(); ++it )
2.13 check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
2.14 }
2.15 +
2.16 + // CrossRefMap
2.17 + {
2.18 + typedef ListDigraph Graph;
2.19 + DIGRAPH_TYPEDEFS(Graph);
2.20 +
2.21 + checkConcept<ReadWriteMap<Node, int>,
2.22 + CrossRefMap<Graph, Node, int> >();
2.23 +
2.24 + Graph gr;
2.25 + typedef CrossRefMap<Graph, Node, char> CRMap;
2.26 + typedef CRMap::ValueIterator ValueIt;
2.27 + CRMap map(gr);
2.28 +
2.29 + Node n0 = gr.addNode();
2.30 + Node n1 = gr.addNode();
2.31 + Node n2 = gr.addNode();
2.32 +
2.33 + map.set(n0, 'A');
2.34 + map.set(n1, 'B');
2.35 + map.set(n2, 'C');
2.36 + map.set(n2, 'A');
2.37 + map.set(n0, 'C');
2.38 +
2.39 + check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
2.40 + "Wrong CrossRefMap");
2.41 + check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");
2.42 + check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
2.43 + check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");
2.44 +
2.45 + ValueIt it = map.beginValue();
2.46 + check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
2.47 + it == map.endValue(), "Wrong value iterator");
2.48 + }
2.49
2.50 return 0;
2.51 }