Changes in / [690:5795e130402e:689:86c49553fea5] in lemon-1.2
- Files:
-
- 3 deleted
- 7 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/Makefile.am
r686 r667 60 60 lemon/bfs.h \ 61 61 lemon/bin_heap.h \ 62 lemon/bucket_heap.h \63 62 lemon/cbc.h \ 64 63 lemon/circulation.h \ … … 78 77 lemon/error.h \ 79 78 lemon/euler.h \ 80 lemon/fib_heap.h \81 79 lemon/full_graph.h \ 82 80 lemon/glpk.h \ … … 93 91 lemon/lp_base.h \ 94 92 lemon/lp_skeleton.h \ 93 lemon/list_graph.h \ 95 94 lemon/maps.h \ 96 95 lemon/matching.h \ … … 101 100 lemon/path.h \ 102 101 lemon/preflow.h \ 103 lemon/radix_heap.h \104 102 lemon/radix_sort.h \ 105 103 lemon/random.h \ -
lemon/bin_heap.h
r683 r584 34 34 ///\brief A Binary Heap implementation. 35 35 /// 36 ///This class implements the \e binary \e heap data structure. 37 /// 36 ///This class implements the \e binary \e heap data structure. 37 /// 38 38 ///A \e heap is a data structure for storing items with specified values 39 39 ///called \e priorities in such a way that finding the item with minimum 40 ///priority is efficient. \c C MPspecifies the ordering of the priorities.40 ///priority is efficient. \c Comp specifies the ordering of the priorities. 41 41 ///In a heap one can change the priority of an item, add or erase an 42 42 ///item, etc. … … 45 45 ///\tparam IM A read and writable item map with int values, used internally 46 46 ///to handle the cross references. 47 ///\tparam C MPA functor class for the ordering of the priorities.47 ///\tparam Comp A functor class for the ordering of the priorities. 48 48 ///The default is \c std::less<PR>. 49 49 /// 50 50 ///\sa FibHeap 51 51 ///\sa Dijkstra 52 template <typename PR, typename IM, typename C MP= std::less<PR> >52 template <typename PR, typename IM, typename Comp = std::less<PR> > 53 53 class BinHeap { 54 54 … … 63 63 typedef std::pair<Item,Prio> Pair; 64 64 ///\e 65 typedef C MPCompare;65 typedef Comp Compare; 66 66 67 67 /// \brief Type to represent the items states. -
lemon/bits/edge_set_extender.h
r685 r617 538 538 539 539 public: 540 explicitArcMap(const Graph& _g)540 ArcMap(const Graph& _g) 541 541 : Parent(_g) {} 542 542 ArcMap(const Graph& _g, const _Value& _v) … … 562 562 563 563 public: 564 explicitEdgeMap(const Graph& _g)564 EdgeMap(const Graph& _g) 565 565 : Parent(_g) {} 566 566 -
lemon/bits/graph_extender.h
r685 r617 605 605 606 606 public: 607 explicitNodeMap(const Graph& graph)607 NodeMap(const Graph& graph) 608 608 : Parent(graph) {} 609 609 NodeMap(const Graph& graph, const _Value& value) … … 629 629 630 630 public: 631 explicitArcMap(const Graph& graph)631 ArcMap(const Graph& graph) 632 632 : Parent(graph) {} 633 633 ArcMap(const Graph& graph, const _Value& value) … … 653 653 654 654 public: 655 explicitEdgeMap(const Graph& graph)655 EdgeMap(const Graph& graph) 656 656 : Parent(graph) {} 657 657 -
lemon/maps.h
r684 r617 1903 1903 1904 1904 /// This class provides simple invertable graph maps. 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. 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 /// 1907 1909 /// The values of the map can be accessed 1908 1910 /// with stl compatible forward iterator. 1909 ///1910 /// This type is not reference map, so it cannot be modified with1911 /// 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 ultimap<V, K> Container;1926 typedef std::map<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. 1952 /// They are considered with multiplicity, so each value is1953 /// traversed for each item it is assigned to.1954 1951 class ValueIterator 1955 1952 : public std::iterator<std::forward_iterator_tag, Value> { … … 2004 2001 void set(const Key& key, const Value& val) { 2005 2002 Value oldval = Map::operator[](key); 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 } 2003 typename Container::iterator it = _inv_map.find(oldval); 2004 if (it != _inv_map.end() && it->second == key) { 2005 _inv_map.erase(it); 2013 2006 } 2014 _inv_map.insert( std::make_pair(val, key));2007 _inv_map.insert(make_pair(val, key)); 2015 2008 Map::set(key, val); 2016 2009 } … … 2024 2017 } 2025 2018 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); 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); 2034 2024 return it != _inv_map.end() ? it->second : INVALID; 2035 2025 } … … 2043 2033 virtual void erase(const Key& key) { 2044 2034 Value val = Map::operator[](key); 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 } 2035 typename Container::iterator it = _inv_map.find(val); 2036 if (it != _inv_map.end() && it->second == key) { 2037 _inv_map.erase(it); 2052 2038 } 2053 2039 Map::erase(key); … … 2061 2047 for (int i = 0; i < int(keys.size()); ++i) { 2062 2048 Value val = Map::operator[](keys[i]); 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 } 2049 typename Container::iterator it = _inv_map.find(val); 2050 if (it != _inv_map.end() && it->second == keys[i]) { 2051 _inv_map.erase(it); 2070 2052 } 2071 2053 } … … 2103 2085 /// \brief Subscript operator. 2104 2086 /// 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. 2087 /// Subscript operator. It gives back the item 2088 /// that was last assigned to the given value. 2108 2089 Value operator[](const Key& key) const { 2109 2090 return _inverted(key); -
test/heap_test.cc
r681 r440 32 32 33 33 #include <lemon/bin_heap.h> 34 #include <lemon/fib_heap.h>35 #include <lemon/radix_heap.h>36 #include <lemon/bucket_heap.h>37 34 38 35 #include "test_tools.h" … … 187 184 } 188 185 189 {190 typedef FibHeap<Prio, ItemIntMap> IntHeap;191 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();192 heapSortTest<IntHeap>();193 heapIncreaseTest<IntHeap>();194 195 typedef FibHeap<Prio, IntNodeMap > NodeHeap;196 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();197 dijkstraHeapTest<NodeHeap>(digraph, length, source);198 }199 200 {201 typedef RadixHeap<ItemIntMap> IntHeap;202 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();203 heapSortTest<IntHeap>();204 heapIncreaseTest<IntHeap>();205 206 typedef RadixHeap<IntNodeMap > NodeHeap;207 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();208 dijkstraHeapTest<NodeHeap>(digraph, length, source);209 }210 211 {212 typedef BucketHeap<ItemIntMap> IntHeap;213 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();214 heapSortTest<IntHeap>();215 heapIncreaseTest<IntHeap>();216 217 typedef BucketHeap<IntNodeMap > NodeHeap;218 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();219 dijkstraHeapTest<NodeHeap>(digraph, length, source);220 }221 222 223 186 return 0; 224 187 } -
test/maps_test.cc
r684 r507 23 23 #include <lemon/concepts/maps.h> 24 24 #include <lemon/maps.h> 25 #include <lemon/list_graph.h>26 25 27 26 #include "test_tools.h" … … 350 349 check(v1[i++] == *it, "Something is wrong with LoggerBoolMap"); 351 350 } 352 353 // CrossRefMap354 {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 }386 351 387 352 return 0;
Note: See TracChangeset
for help on using the changeset viewer.