Changes in / [741:71939d63ae77:768:99124ea4f048] in lemon
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/maps.h
r741 r768 1826 1826 /// the items stored in the graph, which is returned by the \c id() 1827 1827 /// function of the graph. This map can be inverted with its member 1828 /// class \c InverseMap or with the \c operator() member.1828 /// class \c InverseMap or with the \c operator()() member. 1829 1829 /// 1830 1830 /// \tparam GR The graph type. … … 1902 1902 1903 1903 /// This class provides simple invertable graph maps. 1904 /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap" 1905 /// and if a key is set to a new value then store it 1906 /// in the inverse map. 1904 /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap) 1905 /// and if a key is set to a new value, then stores it in the inverse map. 1907 1906 /// The values of the map can be accessed 1908 1907 /// with stl compatible forward iterator. 1909 1908 /// 1910 1909 /// This type is not reference map, so it cannot be modified with 1911 /// the subscript ionoperator.1910 /// the subscript operator. 1912 1911 /// 1913 1912 /// \tparam GR The graph type. … … 1925 1924 template Map<V>::Type Map; 1926 1925 1927 typedef std::m ap<V, K> Container;1926 typedef std::multimap<V, K> Container; 1928 1927 Container _inv_map; 1929 1928 … … 1950 1949 /// iterator on the values of the map. The values can 1951 1950 /// be accessed in the <tt>[beginValue, endValue)</tt> range. 1951 /// They are considered with multiplicity, so each value is 1952 /// traversed for each item it is assigned to. 1952 1953 class ValueIterator 1953 1954 : public std::iterator<std::forward_iterator_tag, Value> { … … 2002 2003 void set(const Key& key, const Value& val) { 2003 2004 Value oldval = Map::operator[](key); 2004 typename Container::iterator it = _inv_map.find(oldval); 2005 if (it != _inv_map.end() && it>second == key) { 2006 _inv_map.erase(it); 2005 typename Container::iterator it; 2006 for (it = _inv_map.equal_range(oldval).first; 2007 it != _inv_map.equal_range(oldval).second; ++it) { 2008 if (it>second == key) { 2009 _inv_map.erase(it); 2010 break; 2011 } 2007 2012 } 2008 2013 _inv_map.insert(std::make_pair(val, key)); … … 2018 2023 } 2019 2024 2020 /// \brief Gives back the item by its value. 2021 /// 2022 /// Gives back the item by its value. 2023 Key operator()(const Value& key) const { 2024 typename Container::const_iterator it = _inv_map.find(key); 2025 /// \brief Gives back an item by its value. 2026 /// 2027 /// This function gives back an item that is assigned to 2028 /// the given value or \c INVALID if no such item exists. 2029 /// If there are more items with the same associated value, 2030 /// only one of them is returned. 2031 Key operator()(const Value& val) const { 2032 typename Container::const_iterator it = _inv_map.find(val); 2025 2033 return it != _inv_map.end() ? it>second : INVALID; 2034 } 2035 2036 /// \brief Returns the number of items with the given value. 2037 /// 2038 /// This function returns the number of items with the given value 2039 /// associated with it. 2040 int count(const Value &val) const { 2041 return _inv_map.count(val); 2026 2042 } 2027 2043 … … 2034 2050 virtual void erase(const Key& key) { 2035 2051 Value val = Map::operator[](key); 2036 typename Container::iterator it = _inv_map.find(val); 2037 if (it != _inv_map.end() && it>second == key) { 2038 _inv_map.erase(it); 2052 typename Container::iterator it; 2053 for (it = _inv_map.equal_range(val).first; 2054 it != _inv_map.equal_range(val).second; ++it) { 2055 if (it>second == key) { 2056 _inv_map.erase(it); 2057 break; 2058 } 2039 2059 } 2040 2060 Map::erase(key); … … 2048 2068 for (int i = 0; i < int(keys.size()); ++i) { 2049 2069 Value val = Map::operator[](keys[i]); 2050 typename Container::iterator it = _inv_map.find(val); 2051 if (it != _inv_map.end() && it>second == keys[i]) { 2052 _inv_map.erase(it); 2070 typename Container::iterator it; 2071 for (it = _inv_map.equal_range(val).first; 2072 it != _inv_map.equal_range(val).second; ++it) { 2073 if (it>second == keys[i]) { 2074 _inv_map.erase(it); 2075 break; 2076 } 2053 2077 } 2054 2078 } … … 2086 2110 /// \brief Subscript operator. 2087 2111 /// 2088 /// Subscript operator. It gives back the item 2089 /// that was last assigned to the given value. 2112 /// Subscript operator. It gives back an item 2113 /// that is assigned to the given value or \c INVALID 2114 /// if no such item exists. 2090 2115 Value operator[](const Key& key) const { 2091 2116 return _inverted(key); … … 2105 2130 }; 2106 2131 2107 /// \brief Provides continuous and unique IDfor the2132 /// \brief Provides continuous and unique id for the 2108 2133 /// items of a graph. 2109 2134 /// 2110 2135 /// RangeIdMap provides a unique and continuous 2111 /// IDfor each item of a given type (\c Node, \c Arc or2136 /// id for each item of a given type (\c Node, \c Arc or 2112 2137 /// \c Edge) in a graph. This id is 2113 2138 ///  \b unique: different items get different ids, … … 2120 2145 /// the \c id() function of the graph or \ref IdMap. 2121 2146 /// This map can be inverted with its member class \c InverseMap, 2122 /// or with the \c operator() member.2147 /// or with the \c operator()() member. 2123 2148 /// 2124 2149 /// \tparam GR The graph type. 
test/maps_test.cc
r741 r768 23 23 #include <lemon/concepts/maps.h> 24 24 #include <lemon/maps.h> 25 #include <lemon/list_graph.h> 25 26 #include <lemon/smart_graph.h> 26 27 … … 330 331 { 331 332 typedef std::vector<int> vec; 333 checkConcept<WriteMap<int, bool>, LoggerBoolMap<vec::iterator> >(); 334 checkConcept<WriteMap<int, bool>, 335 LoggerBoolMap<std::back_insert_iterator<vec> > >(); 336 332 337 vec v1; 333 338 vec v2(10); … … 350 355 check(v1[i++] == *it, "Something is wrong with LoggerBoolMap"); 351 356 } 357 358 // IdMap, RangeIdMap 359 { 360 typedef ListDigraph Graph; 361 DIGRAPH_TYPEDEFS(Graph); 362 363 checkConcept<ReadMap<Node, int>, IdMap<Graph, Node> >(); 364 checkConcept<ReadMap<Arc, int>, IdMap<Graph, Arc> >(); 365 checkConcept<ReadMap<Node, int>, RangeIdMap<Graph, Node> >(); 366 checkConcept<ReadMap<Arc, int>, RangeIdMap<Graph, Arc> >(); 367 368 Graph gr; 369 IdMap<Graph, Node> nmap(gr); 370 IdMap<Graph, Arc> amap(gr); 371 RangeIdMap<Graph, Node> nrmap(gr); 372 RangeIdMap<Graph, Arc> armap(gr); 373 374 Node n0 = gr.addNode(); 375 Node n1 = gr.addNode(); 376 Node n2 = gr.addNode(); 377 378 Arc a0 = gr.addArc(n0, n1); 379 Arc a1 = gr.addArc(n0, n2); 380 Arc a2 = gr.addArc(n2, n1); 381 Arc a3 = gr.addArc(n2, n0); 382 383 check(nmap[n0] == gr.id(n0) && nmap(gr.id(n0)) == n0, "Wrong IdMap"); 384 check(nmap[n1] == gr.id(n1) && nmap(gr.id(n1)) == n1, "Wrong IdMap"); 385 check(nmap[n2] == gr.id(n2) && nmap(gr.id(n2)) == n2, "Wrong IdMap"); 386 387 check(amap[a0] == gr.id(a0) && amap(gr.id(a0)) == a0, "Wrong IdMap"); 388 check(amap[a1] == gr.id(a1) && amap(gr.id(a1)) == a1, "Wrong IdMap"); 389 check(amap[a2] == gr.id(a2) && amap(gr.id(a2)) == a2, "Wrong IdMap"); 390 check(amap[a3] == gr.id(a3) && amap(gr.id(a3)) == a3, "Wrong IdMap"); 391 392 check(nmap.inverse()[gr.id(n0)] == n0, "Wrong IdMap::InverseMap"); 393 check(amap.inverse()[gr.id(a0)] == a0, "Wrong IdMap::InverseMap"); 394 395 check(nrmap.size() == 3 && armap.size() == 4, 396 "Wrong RangeIdMap::size()"); 397 398 check(nrmap[n0] == 0 && nrmap(0) == n0, "Wrong RangeIdMap"); 399 check(nrmap[n1] == 1 && nrmap(1) == n1, "Wrong RangeIdMap"); 400 check(nrmap[n2] == 2 && nrmap(2) == n2, "Wrong RangeIdMap"); 401 402 check(armap[a0] == 0 && armap(0) == a0, "Wrong RangeIdMap"); 403 check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap"); 404 check(armap[a2] == 2 && armap(2) == a2, "Wrong RangeIdMap"); 405 check(armap[a3] == 3 && armap(3) == a3, "Wrong RangeIdMap"); 406 407 check(nrmap.inverse()[0] == n0, "Wrong RangeIdMap::InverseMap"); 408 check(armap.inverse()[0] == a0, "Wrong RangeIdMap::InverseMap"); 409 410 gr.erase(n1); 411 412 if (nrmap[n0] == 1) nrmap.swap(n0, n2); 413 nrmap.swap(n2, n0); 414 if (armap[a1] == 1) armap.swap(a1, a3); 415 armap.swap(a3, a1); 416 417 check(nrmap.size() == 2 && armap.size() == 2, 418 "Wrong RangeIdMap::size()"); 419 420 check(nrmap[n0] == 1 && nrmap(1) == n0, "Wrong RangeIdMap"); 421 check(nrmap[n2] == 0 && nrmap(0) == n2, "Wrong RangeIdMap"); 422 423 check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap"); 424 check(armap[a3] == 0 && armap(0) == a3, "Wrong RangeIdMap"); 425 426 check(nrmap.inverse()[0] == n2, "Wrong RangeIdMap::InverseMap"); 427 check(armap.inverse()[0] == a3, "Wrong RangeIdMap::InverseMap"); 428 } 429 430 // CrossRefMap 431 { 432 typedef ListDigraph Graph; 433 DIGRAPH_TYPEDEFS(Graph); 434 435 checkConcept<ReadWriteMap<Node, int>, 436 CrossRefMap<Graph, Node, int> >(); 437 checkConcept<ReadWriteMap<Node, bool>, 438 CrossRefMap<Graph, Node, bool> >(); 439 checkConcept<ReadWriteMap<Node, double>, 440 CrossRefMap<Graph, Node, double> >(); 441 442 Graph gr; 443 typedef CrossRefMap<Graph, Node, char> CRMap; 444 typedef CRMap::ValueIterator ValueIt; 445 CRMap map(gr); 446 447 Node n0 = gr.addNode(); 448 Node n1 = gr.addNode(); 449 Node n2 = gr.addNode(); 450 451 map.set(n0, 'A'); 452 map.set(n1, 'B'); 453 map.set(n2, 'C'); 454 455 check(map[n0] == 'A' && map('A') == n0 && map.inverse()['A'] == n0, 456 "Wrong CrossRefMap"); 457 check(map[n1] == 'B' && map('B') == n1 && map.inverse()['B'] == n1, 458 "Wrong CrossRefMap"); 459 check(map[n2] == 'C' && map('C') == n2 && map.inverse()['C'] == n2, 460 "Wrong CrossRefMap"); 461 check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1, 462 "Wrong CrossRefMap::count()"); 463 464 ValueIt it = map.beginValue(); 465 check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' && 466 it == map.endValue(), "Wrong value iterator"); 467 468 map.set(n2, 'A'); 469 470 check(map[n0] == 'A' && map[n1] == 'B' && map[n2] == 'A', 471 "Wrong CrossRefMap"); 472 check(map('A') == n0 && map.inverse()['A'] == n0, "Wrong CrossRefMap"); 473 check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap"); 474 check(map('C') == INVALID && map.inverse()['C'] == INVALID, 475 "Wrong CrossRefMap"); 476 check(map.count('A') == 2 && map.count('B') == 1 && map.count('C') == 0, 477 "Wrong CrossRefMap::count()"); 478 479 it = map.beginValue(); 480 check(*it++ == 'A' && *it++ == 'A' && *it++ == 'B' && 481 it == map.endValue(), "Wrong value iterator"); 482 483 map.set(n0, 'C'); 484 485 check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A', 486 "Wrong CrossRefMap"); 487 check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap"); 488 check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap"); 489 check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap"); 490 check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1, 491 "Wrong CrossRefMap::count()"); 492 493 it = map.beginValue(); 494 check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' && 495 it == map.endValue(), "Wrong value iterator"); 496 } 352 497 353 498 // Iterable bool map
Note: See TracChangeset
for help on using the changeset viewer.