# HG changeset patch # User Peter Kovacs # Date 2009-07-23 18:09:41 # Node ID 7b1a6e9630188b425c35b77110d67547eb1c2a00 # Parent 257e91516e09d8d6be58236c587e3e0199770412 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. 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:: template Map::Type Map; - typedef std::map Container; + typedef std::multimap 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 [beginValue, endValue) range. + /// They are considered with multiplicity, so each value is + /// traversed for each item it is assigned to. class ValueIterator : public std::iterator { 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& 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 #include #include +#include #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, + CrossRefMap >(); + + Graph gr; + typedef CrossRefMap 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; }