Changes in / [858:2305167d2491:868:76689f2fc02d] in lemon
- Files:
-
- 3 added
- 5 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/Makefile.am
r850 r868 60 60 lemon/bfs.h \ 61 61 lemon/bin_heap.h \ 62 lemon/bucket_heap.h \ 62 63 lemon/cbc.h \ 63 64 lemon/circulation.h \ … … 77 78 lemon/error.h \ 78 79 lemon/euler.h \ 80 lemon/fib_heap.h \ 79 81 lemon/full_graph.h \ 80 82 lemon/glpk.h \ … … 99 101 lemon/path.h \ 100 102 lemon/preflow.h \ 103 lemon/radix_heap.h \ 101 104 lemon/radix_sort.h \ 102 105 lemon/random.h \ -
lemon/bin_heap.h
r631 r730 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 ompspecifies the ordering of the priorities.40 ///priority is efficient. \c CMP 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 ompA functor class for the ordering of the priorities.47 ///\tparam CMP 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 omp= std::less<PR> >52 template <typename PR, typename IM, typename CMP = std::less<PR> > 53 53 class BinHeap { 54 54 … … 63 63 typedef std::pair<Item,Prio> Pair; 64 64 ///\e 65 typedef C ompCompare;65 typedef CMP Compare; 66 66 67 67 /// \brief Type to represent the items states. -
lemon/bits/map_extender.h
r664 r867 50 50 typedef typename Parent::ConstReference ConstReference; 51 51 52 typedef typename Parent::ReferenceMapTag ReferenceMapTag; 53 52 54 class MapIt; 53 55 class ConstMapIt; … … 83 85 typedef typename Map::Value Value; 84 86 85 MapIt() {}86 87 MapIt(Invalid i) : Parent(i) {}88 89 explicit MapIt(Map& _map) : map( _map) {90 map .notifier()->first(*this);87 MapIt() : map(NULL) {} 88 89 MapIt(Invalid i) : Parent(i), map(NULL) {} 90 91 explicit MapIt(Map& _map) : map(&_map) { 92 map->notifier()->first(*this); 91 93 } 92 94 93 95 MapIt(const Map& _map, const Item& item) 96 : Parent(item), map(&_map) {} 97 98 MapIt& operator++() { 99 map->notifier()->next(*this); 100 return *this; 101 } 102 103 typename MapTraits<Map>::ConstReturnValue operator*() const { 104 return (*map)[*this]; 105 } 106 107 typename MapTraits<Map>::ReturnValue operator*() { 108 return (*map)[*this]; 109 } 110 111 void set(const Value& value) { 112 map->set(*this, value); 113 } 114 115 protected: 116 Map* map; 117 118 }; 119 120 class ConstMapIt : public Item { 121 typedef Item Parent; 122 123 public: 124 125 typedef typename Map::Value Value; 126 127 ConstMapIt() : map(NULL) {} 128 129 ConstMapIt(Invalid i) : Parent(i), map(NULL) {} 130 131 explicit ConstMapIt(Map& _map) : map(&_map) { 132 map->notifier()->first(*this); 133 } 134 135 ConstMapIt(const Map& _map, const Item& item) 94 136 : Parent(item), map(_map) {} 95 137 96 MapIt& operator++() {97 map .notifier()->next(*this);138 ConstMapIt& operator++() { 139 map->notifier()->next(*this); 98 140 return *this; 99 141 } … … 103 145 } 104 146 105 typename MapTraits<Map>::ReturnValue operator*() { 106 return map[*this]; 107 } 108 109 void set(const Value& value) { 110 map.set(*this, value); 111 } 112 113 protected: 114 Map& map; 115 116 }; 117 118 class ConstMapIt : public Item { 119 typedef Item Parent; 120 121 public: 122 123 typedef typename Map::Value Value; 124 125 ConstMapIt() {} 126 127 ConstMapIt(Invalid i) : Parent(i) { } 128 129 explicit ConstMapIt(Map& _map) : map(_map) { 130 map.notifier()->first(*this); 131 } 132 133 ConstMapIt(const Map& _map, const Item& item) 134 : Parent(item), map(_map) {} 135 136 ConstMapIt& operator++() { 137 map.notifier()->next(*this); 138 return *this; 139 } 140 141 typename MapTraits<Map>::ConstReturnValue operator*() const { 142 return map[*this]; 143 } 144 145 protected: 146 const Map& map; 147 protected: 148 const Map* map; 147 149 }; 148 150 … … 151 153 152 154 public: 153 154 ItemIt() {} 155 156 ItemIt(Invalid i) : Parent(i) {}157 158 explicit ItemIt(Map& _map) : map( _map) {159 map .notifier()->first(*this);155 ItemIt() : map(NULL) {} 156 157 158 ItemIt(Invalid i) : Parent(i), map(NULL) {} 159 160 explicit ItemIt(Map& _map) : map(&_map) { 161 map->notifier()->first(*this); 160 162 } 161 163 162 164 ItemIt(const Map& _map, const Item& item) 163 : Parent(item), map( _map) {}165 : Parent(item), map(&_map) {} 164 166 165 167 ItemIt& operator++() { 166 map .notifier()->next(*this);167 return *this; 168 } 169 170 protected: 171 const Map ↦168 map->notifier()->next(*this); 169 return *this; 170 } 171 172 protected: 173 const Map* map; 172 174 173 175 }; … … 192 194 typedef typename Parent::ConstReference ConstReference; 193 195 196 typedef typename Parent::ReferenceMapTag ReferenceMapTag; 197 194 198 class MapIt; 195 199 class ConstMapIt; … … 228 232 typedef typename Map::Value Value; 229 233 230 MapIt() {}231 232 MapIt(Invalid i) : Parent(i) { }233 234 explicit MapIt(Map& _map) : map( _map) {235 map .graph.first(*this);234 MapIt() : map(NULL) {} 235 236 MapIt(Invalid i) : Parent(i), map(NULL) { } 237 238 explicit MapIt(Map& _map) : map(&_map) { 239 map->graph.first(*this); 236 240 } 237 241 238 242 MapIt(const Map& _map, const Item& item) 239 : Parent(item), map( _map) {}243 : Parent(item), map(&_map) {} 240 244 241 245 MapIt& operator++() { 242 map .graph.next(*this);246 map->graph.next(*this); 243 247 return *this; 244 248 } 245 249 246 250 typename MapTraits<Map>::ConstReturnValue operator*() const { 247 return map[*this];251 return (*map)[*this]; 248 252 } 249 253 250 254 typename MapTraits<Map>::ReturnValue operator*() { 251 return map[*this];255 return (*map)[*this]; 252 256 } 253 257 254 258 void set(const Value& value) { 255 map .set(*this, value);256 } 257 258 protected: 259 Map ↦259 map->set(*this, value); 260 } 261 262 protected: 263 Map* map; 260 264 261 265 }; … … 268 272 typedef typename Map::Value Value; 269 273 270 ConstMapIt() {}271 272 ConstMapIt(Invalid i) : Parent(i) { }273 274 explicit ConstMapIt(Map& _map) : map( _map) {275 map .graph.first(*this);274 ConstMapIt() : map(NULL) {} 275 276 ConstMapIt(Invalid i) : Parent(i), map(NULL) { } 277 278 explicit ConstMapIt(Map& _map) : map(&_map) { 279 map->graph.first(*this); 276 280 } 277 281 278 282 ConstMapIt(const Map& _map, const Item& item) 279 : Parent(item), map( _map) {}283 : Parent(item), map(&_map) {} 280 284 281 285 ConstMapIt& operator++() { 282 map .graph.next(*this);286 map->graph.next(*this); 283 287 return *this; 284 288 } 285 289 286 290 typename MapTraits<Map>::ConstReturnValue operator*() const { 287 return map[*this];288 } 289 290 protected: 291 const Map ↦291 return (*map)[*this]; 292 } 293 294 protected: 295 const Map* map; 292 296 }; 293 297 … … 296 300 297 301 public: 298 299 ItemIt() {} 300 301 ItemIt(Invalid i) : Parent(i) { }302 303 explicit ItemIt(Map& _map) : map( _map) {304 map .graph.first(*this);302 ItemIt() : map(NULL) {} 303 304 305 ItemIt(Invalid i) : Parent(i), map(NULL) { } 306 307 explicit ItemIt(Map& _map) : map(&_map) { 308 map->graph.first(*this); 305 309 } 306 310 307 311 ItemIt(const Map& _map, const Item& item) 308 : Parent(item), map( _map) {}312 : Parent(item), map(&_map) {} 309 313 310 314 ItemIt& operator++() { 311 map .graph.next(*this);312 return *this; 313 } 314 315 protected: 316 const Map ↦315 map->graph.next(*this); 316 return *this; 317 } 318 319 protected: 320 const Map* map; 317 321 318 322 }; -
lemon/concepts/maps.h
r576 r765 183 183 template<typename _ReferenceMap> 184 184 struct Constraints { 185 void constraints() { 185 typename enable_if<typename _ReferenceMap::ReferenceMapTag, void>::type 186 constraints() { 186 187 checkConcept<ReadWriteMap<K, T>, _ReferenceMap >(); 187 188 ref = m[key]; -
test/heap_test.cc
r463 r728 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> 34 37 35 38 #include "test_tools.h" … … 184 187 } 185 188 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 186 223 return 0; 187 224 }
Note: See TracChangeset
for help on using the changeset viewer.