Merge
authorAlpar Juttner <alpar@cs.elte.hu>
Thu, 20 Aug 2009 22:52:16 +0200
changeset 734fb93895f84d9
parent 733 7439dc5fe1b9
parent 732 a27356ceb5bd
child 737 5795e130402e
child 781 bd72f8d20f33
child 786 32baeb8e5c8f
child 820 cf360f758f25
Merge
     1.1 --- a/lemon/bits/edge_set_extender.h	Thu Aug 20 22:52:03 2009 +0200
     1.2 +++ b/lemon/bits/edge_set_extender.h	Thu Aug 20 22:52:16 2009 +0200
     1.3 @@ -537,7 +537,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 @@ -561,7 +561,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	Thu Aug 20 22:52:03 2009 +0200
     2.2 +++ b/lemon/bits/graph_extender.h	Thu Aug 20 22:52:16 2009 +0200
     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	Thu Aug 20 22:52:03 2009 +0200
     3.2 +++ b/lemon/maps.h	Thu Aug 20 22:52:16 2009 +0200
     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	Thu Aug 20 22:52:03 2009 +0200
     4.2 +++ b/test/maps_test.cc	Thu Aug 20 22:52:16 2009 +0200
     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  }