r684:7b1a6e963018
Thu, 23 Jul 2009 18:09:41
[Not Reviewed]
0 comments (0 inline)
0
2
0
40
21
| ... | ... |
@@ -1901,15 +1901,16 @@ |
| 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. |
| ... | ... |
@@ -1922,9 +1923,9 @@ |
| 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 |
|
| ... | ... |
@@ -1947,8 +1948,10 @@ |
| 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: |
| ... | ... |
@@ -1999,13 +2002,17 @@ |
| 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. |
| ... | ... |
@@ -2015,13 +2022,16 @@ |
| 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: |
| ... | ... |
@@ -2031,11 +2041,15 @@ |
| 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 |
|
| ... | ... |
@@ -2045,11 +2059,15 @@ |
| 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 |
} |
| ... | ... |
@@ -2083,10 +2101,11 @@ |
| 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 |
| ... | ... |
@@ -21,8 +21,9 @@ |
| 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; |
| ... | ... |
@@ -347,7 +348,41 @@ |
| 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)