# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 2009-08-20 22:52:16
# Node ID fb93895f84d9050f68f4e9db6f3d70da4038be69
# Parent  7439dc5fe1b9a0c07af4137887cb4817d67c5dd3
# Parent  a27356ceb5bd30211c7f73bd887feb55804c5664

Merge

diff --git a/lemon/bits/edge_set_extender.h b/lemon/bits/edge_set_extender.h
--- a/lemon/bits/edge_set_extender.h
+++ b/lemon/bits/edge_set_extender.h
@@ -537,7 +537,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) {}
@@ -561,7 +561,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 --git a/lemon/bits/graph_extender.h b/lemon/bits/graph_extender.h
--- a/lemon/bits/graph_extender.h
+++ b/lemon/bits/graph_extender.h
@@ -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 --git a/lemon/maps.h b/lemon/maps.h
--- a/lemon/maps.h
+++ b/lemon/maps.h
@@ -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 --git a/test/maps_test.cc b/test/maps_test.cc
--- a/test/maps_test.cc
+++ b/test/maps_test.cc
@@ -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;
 }