1.1 --- a/lemon/bits/edge_set_extender.h Tue Dec 20 17:38:19 2011 +0100
1.2 +++ b/lemon/bits/edge_set_extender.h Tue Dec 20 17:43:11 2011 +0100
1.3 @@ -539,7 +539,7 @@
1.4 typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
1.5
1.6 public:
1.7 - ArcMap(const Graph& _g)
1.8 + explicit ArcMap(const Graph& _g)
1.9 : Parent(_g) {}
1.10 ArcMap(const Graph& _g, const _Value& _v)
1.11 : Parent(_g, _v) {}
1.12 @@ -563,7 +563,7 @@
1.13 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
1.14
1.15 public:
1.16 - EdgeMap(const Graph& _g)
1.17 + explicit EdgeMap(const Graph& _g)
1.18 : Parent(_g) {}
1.19
1.20 EdgeMap(const Graph& _g, const _Value& _v)
2.1 --- a/lemon/bits/graph_extender.h Tue Dec 20 17:38:19 2011 +0100
2.2 +++ b/lemon/bits/graph_extender.h Tue Dec 20 17:43:11 2011 +0100
2.3 @@ -604,7 +604,7 @@
2.4 typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
2.5
2.6 public:
2.7 - NodeMap(const Graph& graph)
2.8 + explicit NodeMap(const Graph& graph)
2.9 : Parent(graph) {}
2.10 NodeMap(const Graph& graph, const _Value& value)
2.11 : Parent(graph, value) {}
2.12 @@ -628,7 +628,7 @@
2.13 typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
2.14
2.15 public:
2.16 - ArcMap(const Graph& graph)
2.17 + explicit ArcMap(const Graph& graph)
2.18 : Parent(graph) {}
2.19 ArcMap(const Graph& graph, const _Value& value)
2.20 : Parent(graph, value) {}
2.21 @@ -652,7 +652,7 @@
2.22 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
2.23
2.24 public:
2.25 - EdgeMap(const Graph& graph)
2.26 + explicit EdgeMap(const Graph& graph)
2.27 : Parent(graph) {}
2.28
2.29 EdgeMap(const Graph& graph, const _Value& value)
3.1 --- a/lemon/maps.h Tue Dec 20 17:38:19 2011 +0100
3.2 +++ b/lemon/maps.h Tue Dec 20 17:43:11 2011 +0100
3.3 @@ -1902,13 +1902,14 @@
3.4 /// \brief General cross reference graph map type.
3.5
3.6 /// This class provides simple invertable graph maps.
3.7 - /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
3.8 - /// and if a key is set to a new value then store it
3.9 - /// in the inverse map.
3.10 - ///
3.11 + /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
3.12 + /// and if a key is set to a new value, then stores it in the inverse map.
3.13 /// The values of the map can be accessed
3.14 /// with stl compatible forward iterator.
3.15 ///
3.16 + /// This type is not reference map, so it cannot be modified with
3.17 + /// the subscript operator.
3.18 + ///
3.19 /// \tparam GR The graph type.
3.20 /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
3.21 /// \c GR::Edge).
3.22 @@ -1923,7 +1924,7 @@
3.23 typedef typename ItemSetTraits<GR, K>::
3.24 template Map<V>::Type Map;
3.25
3.26 - typedef std::map<V, K> Container;
3.27 + typedef std::multimap<V, K> Container;
3.28 Container _inv_map;
3.29
3.30 public:
3.31 @@ -1948,6 +1949,8 @@
3.32 /// This iterator is an stl compatible forward
3.33 /// iterator on the values of the map. The values can
3.34 /// be accessed in the <tt>[beginValue, endValue)</tt> range.
3.35 + /// They are considered with multiplicity, so each value is
3.36 + /// traversed for each item it is assigned to.
3.37 class ValueIterator
3.38 : public std::iterator<std::forward_iterator_tag, Value> {
3.39 friend class CrossRefMap;
3.40 @@ -2000,11 +2003,15 @@
3.41 /// Sets the value associated with the given key.
3.42 void set(const Key& key, const Value& val) {
3.43 Value oldval = Map::operator[](key);
3.44 - typename Container::iterator it = _inv_map.find(oldval);
3.45 - if (it != _inv_map.end() && it->second == key) {
3.46 - _inv_map.erase(it);
3.47 + typename Container::iterator it;
3.48 + for (it = _inv_map.equal_range(oldval).first;
3.49 + it != _inv_map.equal_range(oldval).second; ++it) {
3.50 + if (it->second == key) {
3.51 + _inv_map.erase(it);
3.52 + break;
3.53 + }
3.54 }
3.55 - _inv_map.insert(make_pair(val, key));
3.56 + _inv_map.insert(std::make_pair(val, key));
3.57 Map::set(key, val);
3.58 }
3.59
3.60 @@ -2016,11 +2023,14 @@
3.61 return Map::operator[](key);
3.62 }
3.63
3.64 - /// \brief Gives back the item by its value.
3.65 + /// \brief Gives back an item by its value.
3.66 ///
3.67 - /// Gives back the item by its value.
3.68 - Key operator()(const Value& key) const {
3.69 - typename Container::const_iterator it = _inv_map.find(key);
3.70 + /// This function gives back an item that is assigned to
3.71 + /// the given value or \c INVALID if no such item exists.
3.72 + /// If there are more items with the same associated value,
3.73 + /// only one of them is returned.
3.74 + Key operator()(const Value& val) const {
3.75 + typename Container::const_iterator it = _inv_map.find(val);
3.76 return it != _inv_map.end() ? it->second : INVALID;
3.77 }
3.78
3.79 @@ -2032,9 +2042,13 @@
3.80 /// \c AlterationNotifier.
3.81 virtual void erase(const Key& key) {
3.82 Value val = Map::operator[](key);
3.83 - typename Container::iterator it = _inv_map.find(val);
3.84 - if (it != _inv_map.end() && it->second == key) {
3.85 - _inv_map.erase(it);
3.86 + typename Container::iterator it;
3.87 + for (it = _inv_map.equal_range(val).first;
3.88 + it != _inv_map.equal_range(val).second; ++it) {
3.89 + if (it->second == key) {
3.90 + _inv_map.erase(it);
3.91 + break;
3.92 + }
3.93 }
3.94 Map::erase(key);
3.95 }
3.96 @@ -2046,9 +2060,13 @@
3.97 virtual void erase(const std::vector<Key>& keys) {
3.98 for (int i = 0; i < int(keys.size()); ++i) {
3.99 Value val = Map::operator[](keys[i]);
3.100 - typename Container::iterator it = _inv_map.find(val);
3.101 - if (it != _inv_map.end() && it->second == keys[i]) {
3.102 - _inv_map.erase(it);
3.103 + typename Container::iterator it;
3.104 + for (it = _inv_map.equal_range(val).first;
3.105 + it != _inv_map.equal_range(val).second; ++it) {
3.106 + if (it->second == keys[i]) {
3.107 + _inv_map.erase(it);
3.108 + break;
3.109 + }
3.110 }
3.111 }
3.112 Map::erase(keys);
3.113 @@ -2084,8 +2102,9 @@
3.114
3.115 /// \brief Subscript operator.
3.116 ///
3.117 - /// Subscript operator. It gives back the item
3.118 - /// that was last assigned to the given value.
3.119 + /// Subscript operator. It gives back an item
3.120 + /// that is assigned to the given value or \c INVALID
3.121 + /// if no such item exists.
3.122 Value operator[](const Key& key) const {
3.123 return _inverted(key);
3.124 }
4.1 --- a/test/maps_test.cc Tue Dec 20 17:38:19 2011 +0100
4.2 +++ b/test/maps_test.cc Tue Dec 20 17:43:11 2011 +0100
4.3 @@ -22,6 +22,7 @@
4.4 #include <lemon/concept_check.h>
4.5 #include <lemon/concepts/maps.h>
4.6 #include <lemon/maps.h>
4.7 +#include <lemon/list_graph.h>
4.8
4.9 #include "test_tools.h"
4.10
4.11 @@ -348,6 +349,40 @@
4.12 it != map2.end(); ++it )
4.13 check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
4.14 }
4.15 +
4.16 + // CrossRefMap
4.17 + {
4.18 + typedef ListDigraph Graph;
4.19 + DIGRAPH_TYPEDEFS(Graph);
4.20 +
4.21 + checkConcept<ReadWriteMap<Node, int>,
4.22 + CrossRefMap<Graph, Node, int> >();
4.23 +
4.24 + Graph gr;
4.25 + typedef CrossRefMap<Graph, Node, char> CRMap;
4.26 + typedef CRMap::ValueIterator ValueIt;
4.27 + CRMap map(gr);
4.28 +
4.29 + Node n0 = gr.addNode();
4.30 + Node n1 = gr.addNode();
4.31 + Node n2 = gr.addNode();
4.32 +
4.33 + map.set(n0, 'A');
4.34 + map.set(n1, 'B');
4.35 + map.set(n2, 'C');
4.36 + map.set(n2, 'A');
4.37 + map.set(n0, 'C');
4.38 +
4.39 + check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
4.40 + "Wrong CrossRefMap");
4.41 + check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");
4.42 + check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
4.43 + check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");
4.44 +
4.45 + ValueIt it = map.beginValue();
4.46 + check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
4.47 + it == map.endValue(), "Wrong value iterator");
4.48 + }
4.49
4.50 return 0;
4.51 }