gravatar
alpar (Alpar Juttner)
alpar@cs.elte.hu
Merge
0 4 0
merge default
1 file changed with 80 insertions and 26 deletions:
↑ Collapse diff ↑
Ignore white space 12 line context
... ...
@@ -536,13 +536,13 @@
536 536
    template <typename _Value>
537 537
    class ArcMap 
538 538
      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
539 539
      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
540 540

	
541 541
    public:
542
      ArcMap(const Graph& _g) 
542
      explicit ArcMap(const Graph& _g) 
543 543
	: Parent(_g) {}
544 544
      ArcMap(const Graph& _g, const _Value& _v) 
545 545
	: Parent(_g, _v) {}
546 546

	
547 547
      ArcMap& operator=(const ArcMap& cmap) {
548 548
	return operator=<ArcMap>(cmap);
... ...
@@ -560,13 +560,13 @@
560 560
    template <typename _Value>
561 561
    class EdgeMap 
562 562
      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
563 563
      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
564 564

	
565 565
    public:
566
      EdgeMap(const Graph& _g) 
566
      explicit EdgeMap(const Graph& _g) 
567 567
	: Parent(_g) {}
568 568

	
569 569
      EdgeMap(const Graph& _g, const _Value& _v) 
570 570
	: Parent(_g, _v) {}
571 571

	
572 572
      EdgeMap& operator=(const EdgeMap& cmap) {
Ignore white space 12 line context
... ...
@@ -601,13 +601,13 @@
601 601
    template <typename _Value>
602 602
    class NodeMap
603 603
      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
604 604
      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
605 605

	
606 606
    public:
607
      NodeMap(const Graph& graph)
607
      explicit NodeMap(const Graph& graph)
608 608
        : Parent(graph) {}
609 609
      NodeMap(const Graph& graph, const _Value& value)
610 610
        : Parent(graph, value) {}
611 611

	
612 612
    private:
613 613
      NodeMap& operator=(const NodeMap& cmap) {
... ...
@@ -625,13 +625,13 @@
625 625
    template <typename _Value>
626 626
    class ArcMap
627 627
      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
628 628
      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
629 629

	
630 630
    public:
631
      ArcMap(const Graph& graph)
631
      explicit ArcMap(const Graph& graph)
632 632
        : Parent(graph) {}
633 633
      ArcMap(const Graph& graph, const _Value& value)
634 634
        : Parent(graph, value) {}
635 635

	
636 636
    private:
637 637
      ArcMap& operator=(const ArcMap& cmap) {
... ...
@@ -649,13 +649,13 @@
649 649
    template <typename _Value>
650 650
    class EdgeMap
651 651
      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
652 652
      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
653 653

	
654 654
    public:
655
      EdgeMap(const Graph& graph)
655
      explicit EdgeMap(const Graph& graph)
656 656
        : Parent(graph) {}
657 657

	
658 658
      EdgeMap(const Graph& graph, const _Value& value)
659 659
        : Parent(graph, value) {}
660 660

	
661 661
    private:
Ignore white space 12 line context
... ...
@@ -1899,19 +1899,20 @@
1899 1899
  };
1900 1900

	
1901 1901

	
1902 1902
  /// \brief General cross reference graph map type.
1903 1903

	
1904 1904
  /// This class provides simple invertable graph maps.
1905
  /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
1906
  /// and if a key is set to a new value then store it
1907
  /// in the inverse map.
1908
  ///
1905
  /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
1906
  /// and if a key is set to a new value, then stores it in the inverse map.
1909 1907
  /// The values of the map can be accessed
1910 1908
  /// with stl compatible forward iterator.
1911 1909
  ///
1910
  /// This type is not reference map, so it cannot be modified with
1911
  /// the subscript operator.
1912
  ///
1912 1913
  /// \tparam GR The graph type.
1913 1914
  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
1914 1915
  /// \c GR::Edge).
1915 1916
  /// \tparam V The value type of the map.
1916 1917
  ///
1917 1918
  /// \see IterableValueMap
... ...
@@ -1920,13 +1921,13 @@
1920 1921
    : protected ItemSetTraits<GR, K>::template Map<V>::Type {
1921 1922
  private:
1922 1923

	
1923 1924
    typedef typename ItemSetTraits<GR, K>::
1924 1925
      template Map<V>::Type Map;
1925 1926

	
1926
    typedef std::map<V, K> Container;
1927
    typedef std::multimap<V, K> Container;
1927 1928
    Container _inv_map;
1928 1929

	
1929 1930
  public:
1930 1931

	
1931 1932
    /// The graph type of CrossRefMap.
1932 1933
    typedef GR Graph;
... ...
@@ -1945,12 +1946,14 @@
1945 1946

	
1946 1947
    /// \brief Forward iterator for values.
1947 1948
    ///
1948 1949
    /// This iterator is an stl compatible forward
1949 1950
    /// iterator on the values of the map. The values can
1950 1951
    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
1952
    /// They are considered with multiplicity, so each value is
1953
    /// traversed for each item it is assigned to.
1951 1954
    class ValueIterator
1952 1955
      : public std::iterator<std::forward_iterator_tag, Value> {
1953 1956
      friend class CrossRefMap;
1954 1957
    private:
1955 1958
      ValueIterator(typename Container::const_iterator _it)
1956 1959
        : it(_it) {}
... ...
@@ -1997,61 +2000,76 @@
1997 2000

	
1998 2001
    /// \brief Sets the value associated with the given key.
1999 2002
    ///
2000 2003
    /// Sets the value associated with the given key.
2001 2004
    void set(const Key& key, const Value& val) {
2002 2005
      Value oldval = Map::operator[](key);
2003
      typename Container::iterator it = _inv_map.find(oldval);
2004
      if (it != _inv_map.end() && it->second == key) {
2005
        _inv_map.erase(it);
2006
      typename Container::iterator it;
2007
      for (it = _inv_map.equal_range(oldval).first;
2008
           it != _inv_map.equal_range(oldval).second; ++it) {
2009
        if (it->second == key) {
2010
          _inv_map.erase(it);
2011
          break;
2012
        }
2006 2013
      }
2007
      _inv_map.insert(make_pair(val, key));
2014
      _inv_map.insert(std::make_pair(val, key));
2008 2015
      Map::set(key, val);
2009 2016
    }
2010 2017

	
2011 2018
    /// \brief Returns the value associated with the given key.
2012 2019
    ///
2013 2020
    /// Returns the value associated with the given key.
2014 2021
    typename MapTraits<Map>::ConstReturnValue
2015 2022
    operator[](const Key& key) const {
2016 2023
      return Map::operator[](key);
2017 2024
    }
2018 2025

	
2019
    /// \brief Gives back the item by its value.
2026
    /// \brief Gives back an item by its value.
2020 2027
    ///
2021
    /// Gives back the item by its value.
2022
    Key operator()(const Value& key) const {
2023
      typename Container::const_iterator it = _inv_map.find(key);
2028
    /// This function gives back an item that is assigned to
2029
    /// the given value or \c INVALID if no such item exists.
2030
    /// If there are more items with the same associated value,
2031
    /// only one of them is returned.
2032
    Key operator()(const Value& val) const {
2033
      typename Container::const_iterator it = _inv_map.find(val);
2024 2034
      return it != _inv_map.end() ? it->second : INVALID;
2025 2035
    }
2026 2036

	
2027 2037
  protected:
2028 2038

	
2029 2039
    /// \brief Erase the key from the map and the inverse map.
2030 2040
    ///
2031 2041
    /// Erase the key from the map and the inverse map. It is called by the
2032 2042
    /// \c AlterationNotifier.
2033 2043
    virtual void erase(const Key& key) {
2034 2044
      Value val = Map::operator[](key);
2035
      typename Container::iterator it = _inv_map.find(val);
2036
      if (it != _inv_map.end() && it->second == key) {
2037
        _inv_map.erase(it);
2045
      typename Container::iterator it;
2046
      for (it = _inv_map.equal_range(val).first;
2047
           it != _inv_map.equal_range(val).second; ++it) {
2048
        if (it->second == key) {
2049
          _inv_map.erase(it);
2050
          break;
2051
        }
2038 2052
      }
2039 2053
      Map::erase(key);
2040 2054
    }
2041 2055

	
2042 2056
    /// \brief Erase more keys from the map and the inverse map.
2043 2057
    ///
2044 2058
    /// Erase more keys from the map and the inverse map. It is called by the
2045 2059
    /// \c AlterationNotifier.
2046 2060
    virtual void erase(const std::vector<Key>& keys) {
2047 2061
      for (int i = 0; i < int(keys.size()); ++i) {
2048 2062
        Value val = Map::operator[](keys[i]);
2049
        typename Container::iterator it = _inv_map.find(val);
2050
        if (it != _inv_map.end() && it->second == keys[i]) {
2051
          _inv_map.erase(it);
2063
        typename Container::iterator it;
2064
        for (it = _inv_map.equal_range(val).first;
2065
             it != _inv_map.equal_range(val).second; ++it) {
2066
          if (it->second == keys[i]) {
2067
            _inv_map.erase(it);
2068
            break;
2069
          }
2052 2070
        }
2053 2071
      }
2054 2072
      Map::erase(keys);
2055 2073
    }
2056 2074

	
2057 2075
    /// \brief Clear the keys from the map and the inverse map.
... ...
@@ -2081,14 +2099,15 @@
2081 2099
      typedef typename CrossRefMap::Key Value;
2082 2100
      /// The key type of the InverseMap.
2083 2101
      typedef typename CrossRefMap::Value Key;
2084 2102

	
2085 2103
      /// \brief Subscript operator.
2086 2104
      ///
2087
      /// Subscript operator. It gives back the item
2088
      /// that was last assigned to the given value.
2105
      /// Subscript operator. It gives back an item
2106
      /// that is assigned to the given value or \c INVALID
2107
      /// if no such item exists.
2089 2108
      Value operator[](const Key& key) const {
2090 2109
        return _inverted(key);
2091 2110
      }
2092 2111

	
2093 2112
    private:
2094 2113
      const CrossRefMap& _inverted;
Ignore white space 12 line context
... ...
@@ -19,12 +19,13 @@
19 19
#include <deque>
20 20
#include <set>
21 21

	
22 22
#include <lemon/concept_check.h>
23 23
#include <lemon/concepts/maps.h>
24 24
#include <lemon/maps.h>
25
#include <lemon/list_graph.h>
25 26

	
26 27
#include "test_tools.h"
27 28

	
28 29
using namespace lemon;
29 30
using namespace lemon::concepts;
30 31

	
... ...
@@ -345,9 +346,43 @@
345 346

	
346 347
    int i = 0;
347 348
    for ( LoggerBoolMap<vec::iterator>::Iterator it = map2.begin();
348 349
          it != map2.end(); ++it )
349 350
      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
350 351
  }
352
  
353
  // CrossRefMap
354
  {
355
    typedef ListDigraph Graph;
356
    DIGRAPH_TYPEDEFS(Graph);
357

	
358
    checkConcept<ReadWriteMap<Node, int>,
359
                 CrossRefMap<Graph, Node, int> >();
360
    
361
    Graph gr;
362
    typedef CrossRefMap<Graph, Node, char> CRMap;
363
    typedef CRMap::ValueIterator ValueIt;
364
    CRMap map(gr);
365
    
366
    Node n0 = gr.addNode();
367
    Node n1 = gr.addNode();
368
    Node n2 = gr.addNode();
369
    
370
    map.set(n0, 'A');
371
    map.set(n1, 'B');
372
    map.set(n2, 'C');
373
    map.set(n2, 'A');
374
    map.set(n0, 'C');
375

	
376
    check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
377
          "Wrong CrossRefMap");
378
    check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");
379
    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
380
    check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");
381

	
382
    ValueIt it = map.beginValue();
383
    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
384
          it == map.endValue(), "Wrong value iterator");
385
  }
351 386

	
352 387
  return 0;
353 388
}
0 comments (0 inline)