0
4
0
... | ... |
@@ -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) { |
... | ... |
@@ -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: |
... | ... |
@@ -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:: |
|
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 |
|
|
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 |
|
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 |
|
|
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 |
|
|
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 |
|
|
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; |
... | ... |
@@ -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)