COIN-OR::LEMON - Graph Library

Changeset 684:7b1a6e963018 in lemon-main


Ignore:
Timestamp:
07/23/09 18:09:41 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Children:
685:a27356ceb5bd, 720:6e8c27ee9079
Phase:
public
Message:

Fix the implementation and doc of CrossRefMap? (#302)

  • Handle multiple values correctly with std::multimap.
  • Clarify the problematic points in the doc.
  • Add some basic tests for the class.
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/maps.h

    r617 r684  
    19031903
    19041904  /// 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.
    19091907  /// The values of the map can be accessed
    19101908  /// with stl compatible forward iterator.
     1909  ///
     1910  /// This type is not reference map, so it cannot be modified with
     1911  /// the subscript operator.
    19111912  ///
    19121913  /// \tparam GR The graph type.
     
    19241925      template Map<V>::Type Map;
    19251926
    1926     typedef std::map<V, K> Container;
     1927    typedef std::multimap<V, K> Container;
    19271928    Container _inv_map;
    19281929
     
    19491950    /// iterator on the values of the map. The values can
    19501951    /// 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.
    19511954    class ValueIterator
    19521955      : public std::iterator<std::forward_iterator_tag, Value> {
     
    20012004    void set(const Key& key, const Value& val) {
    20022005      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        }
    20062013      }
    2007       _inv_map.insert(make_pair(val, key));
     2014      _inv_map.insert(std::make_pair(val, key));
    20082015      Map::set(key, val);
    20092016    }
     
    20172024    }
    20182025
    2019     /// \brief Gives back the item by its value.
    2020     ///
    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);
     2026    /// \brief Gives back an item by its value.
     2027    ///
     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);
    20242034      return it != _inv_map.end() ? it->second : INVALID;
    20252035    }
     
    20332043    virtual void erase(const Key& key) {
    20342044      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        }
    20382052      }
    20392053      Map::erase(key);
     
    20472061      for (int i = 0; i < int(keys.size()); ++i) {
    20482062        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          }
    20522070        }
    20532071      }
     
    20852103      /// \brief Subscript operator.
    20862104      ///
    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.
    20892108      Value operator[](const Key& key) const {
    20902109        return _inverted(key);
  • test/maps_test.cc

    r477 r684  
    2323#include <lemon/concepts/maps.h>
    2424#include <lemon/maps.h>
     25#include <lemon/list_graph.h>
    2526
    2627#include "test_tools.h"
     
    349350      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
    350351  }
     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  }
    351386
    352387  return 0;
Note: See TracChangeset for help on using the changeset viewer.