# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1324399391 -3600
# Node ID 4efe7b32b13405d775fb48f24afcdaab96a010b8
# Parent 71fd280363d5b8298df27c62c51b5a1a8130f88b# Parent a27356ceb5bd30211c7f73bd887feb55804c5664
Merge
diff -r 71fd280363d5 -r 4efe7b32b134 lemon/bits/edge_set_extender.h
--- a/lemon/bits/edge_set_extender.h Tue Dec 20 17:38:19 2011 +0100
+++ b/lemon/bits/edge_set_extender.h Tue Dec 20 17:43:11 2011 +0100
@@ -539,7 +539,7 @@
typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
public:
- ArcMap(const Graph& _g)
+ explicit ArcMap(const Graph& _g)
: Parent(_g) {}
ArcMap(const Graph& _g, const _Value& _v)
: Parent(_g, _v) {}
@@ -563,7 +563,7 @@
typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
public:
- EdgeMap(const Graph& _g)
+ explicit EdgeMap(const Graph& _g)
: Parent(_g) {}
EdgeMap(const Graph& _g, const _Value& _v)
diff -r 71fd280363d5 -r 4efe7b32b134 lemon/bits/graph_extender.h
--- a/lemon/bits/graph_extender.h Tue Dec 20 17:38:19 2011 +0100
+++ b/lemon/bits/graph_extender.h Tue Dec 20 17:43:11 2011 +0100
@@ -604,7 +604,7 @@
typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
public:
- NodeMap(const Graph& graph)
+ explicit NodeMap(const Graph& graph)
: Parent(graph) {}
NodeMap(const Graph& graph, const _Value& value)
: Parent(graph, value) {}
@@ -628,7 +628,7 @@
typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
public:
- ArcMap(const Graph& graph)
+ explicit ArcMap(const Graph& graph)
: Parent(graph) {}
ArcMap(const Graph& graph, const _Value& value)
: Parent(graph, value) {}
@@ -652,7 +652,7 @@
typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
public:
- EdgeMap(const Graph& graph)
+ explicit EdgeMap(const Graph& graph)
: Parent(graph) {}
EdgeMap(const Graph& graph, const _Value& value)
diff -r 71fd280363d5 -r 4efe7b32b134 lemon/maps.h
--- a/lemon/maps.h Tue Dec 20 17:38:19 2011 +0100
+++ b/lemon/maps.h Tue Dec 20 17:43:11 2011 +0100
@@ -1902,13 +1902,14 @@
/// \brief General cross reference graph map type.
/// This class provides simple invertable graph maps.
- /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
- /// and if a key is set to a new value then store it
- /// in the inverse map.
- ///
+ /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
+ /// and if a key is set to a new value, then stores it in the inverse map.
/// The values of the map can be accessed
/// with stl compatible forward iterator.
///
+ /// This type is not reference map, so it cannot be modified with
+ /// the subscript operator.
+ ///
/// \tparam GR The graph type.
/// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
/// \c GR::Edge).
@@ -1923,7 +1924,7 @@
typedef typename ItemSetTraits<GR, K>::
template Map<V>::Type Map;
- typedef std::map<V, K> Container;
+ typedef std::multimap<V, K> Container;
Container _inv_map;
public:
@@ -1948,6 +1949,8 @@
/// This iterator is an stl compatible forward
/// iterator on the values of the map. The values can
/// be accessed in the <tt>[beginValue, endValue)</tt> range.
+ /// They are considered with multiplicity, so each value is
+ /// traversed for each item it is assigned to.
class ValueIterator
: public std::iterator<std::forward_iterator_tag, Value> {
friend class CrossRefMap;
@@ -2000,11 +2003,15 @@
/// Sets the value associated with the given key.
void set(const Key& key, const Value& val) {
Value oldval = Map::operator[](key);
- typename Container::iterator it = _inv_map.find(oldval);
- if (it != _inv_map.end() && it->second == key) {
- _inv_map.erase(it);
+ typename Container::iterator it;
+ for (it = _inv_map.equal_range(oldval).first;
+ it != _inv_map.equal_range(oldval).second; ++it) {
+ if (it->second == key) {
+ _inv_map.erase(it);
+ break;
+ }
}
- _inv_map.insert(make_pair(val, key));
+ _inv_map.insert(std::make_pair(val, key));
Map::set(key, val);
}
@@ -2016,11 +2023,14 @@
return Map::operator[](key);
}
- /// \brief Gives back the item by its value.
+ /// \brief Gives back an item by its value.
///
- /// Gives back the item by its value.
- Key operator()(const Value& key) const {
- typename Container::const_iterator it = _inv_map.find(key);
+ /// This function gives back an item that is assigned to
+ /// the given value or \c INVALID if no such item exists.
+ /// If there are more items with the same associated value,
+ /// only one of them is returned.
+ Key operator()(const Value& val) const {
+ typename Container::const_iterator it = _inv_map.find(val);
return it != _inv_map.end() ? it->second : INVALID;
}
@@ -2032,9 +2042,13 @@
/// \c AlterationNotifier.
virtual void erase(const Key& key) {
Value val = Map::operator[](key);
- typename Container::iterator it = _inv_map.find(val);
- if (it != _inv_map.end() && it->second == key) {
- _inv_map.erase(it);
+ typename Container::iterator it;
+ for (it = _inv_map.equal_range(val).first;
+ it != _inv_map.equal_range(val).second; ++it) {
+ if (it->second == key) {
+ _inv_map.erase(it);
+ break;
+ }
}
Map::erase(key);
}
@@ -2046,9 +2060,13 @@
virtual void erase(const std::vector<Key>& keys) {
for (int i = 0; i < int(keys.size()); ++i) {
Value val = Map::operator[](keys[i]);
- typename Container::iterator it = _inv_map.find(val);
- if (it != _inv_map.end() && it->second == keys[i]) {
- _inv_map.erase(it);
+ typename Container::iterator it;
+ for (it = _inv_map.equal_range(val).first;
+ it != _inv_map.equal_range(val).second; ++it) {
+ if (it->second == keys[i]) {
+ _inv_map.erase(it);
+ break;
+ }
}
}
Map::erase(keys);
@@ -2084,8 +2102,9 @@
/// \brief Subscript operator.
///
- /// Subscript operator. It gives back the item
- /// that was last assigned to the given value.
+ /// Subscript operator. It gives back an item
+ /// that is assigned to the given value or \c INVALID
+ /// if no such item exists.
Value operator[](const Key& key) const {
return _inverted(key);
}
diff -r 71fd280363d5 -r 4efe7b32b134 test/maps_test.cc
--- a/test/maps_test.cc Tue Dec 20 17:38:19 2011 +0100
+++ b/test/maps_test.cc Tue Dec 20 17:43:11 2011 +0100
@@ -22,6 +22,7 @@
#include <lemon/concept_check.h>
#include <lemon/concepts/maps.h>
#include <lemon/maps.h>
+#include <lemon/list_graph.h>
#include "test_tools.h"
@@ -348,6 +349,40 @@
it != map2.end(); ++it )
check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
}
+
+ // CrossRefMap
+ {
+ typedef ListDigraph Graph;
+ DIGRAPH_TYPEDEFS(Graph);
+
+ checkConcept<ReadWriteMap<Node, int>,
+ CrossRefMap<Graph, Node, int> >();
+
+ Graph gr;
+ typedef CrossRefMap<Graph, Node, char> CRMap;
+ typedef CRMap::ValueIterator ValueIt;
+ CRMap map(gr);
+
+ Node n0 = gr.addNode();
+ Node n1 = gr.addNode();
+ Node n2 = gr.addNode();
+
+ map.set(n0, 'A');
+ map.set(n1, 'B');
+ map.set(n2, 'C');
+ map.set(n2, 'A');
+ map.set(n0, 'C');
+
+ check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
+ "Wrong CrossRefMap");
+ check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");
+ check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
+ check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");
+
+ ValueIt it = map.beginValue();
+ check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
+ it == map.endValue(), "Wrong value iterator");
+ }
return 0;
}