Changeset 2263:9273fe7d850c in lemon-0.x for lemon
- Timestamp:
- 10/26/06 16:20:17 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3021
- Location:
- lemon
- Files:
-
- 12 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bin_heap.h
r2258 r2263 40 40 ///one can change the priority of an item, add or erase an item, etc. 41 41 /// 42 ///\param Item Type of the items to be stored.43 42 ///\param Prio Type of the priority of the items. 44 43 ///\param ItemIntMap A read and writable Item int map, used internally … … 49 48 ///\sa FibHeap 50 49 ///\sa Dijkstra 51 template <typename Item, typenamePrio, typename ItemIntMap,50 template <typename Prio, typename ItemIntMap, 52 51 typename Compare = std::less<Prio> > 53 52 class BinHeap { 54 53 55 54 public: 56 typedef ItemItemType;55 typedef typename ItemIntMap::Key ItemType; 57 56 typedef Prio PrioType; 58 57 typedef std::pair<ItemType,PrioType> PairType; … … 162 161 /// \param i The item to insert. 163 162 /// \param p The priority of the item. 164 void push(const Item &i, const Prio &p) { push(PairType(i,p)); }163 void push(const ItemType &i, const Prio &p) { push(PairType(i,p)); } 165 164 166 165 /// \brief Returns the item with minimum priority relative to \c Compare. … … 169 168 /// Compare. 170 169 /// \pre The heap must be nonempty. 171 Item top() const {170 ItemType top() const { 172 171 return data[0].first; 173 172 } … … 195 194 /// already stored in the heap. 196 195 /// \param i The item to erase. 197 void erase(const Item &i) {196 void erase(const ItemType &i) { 198 197 rmidx(iim[i]); 199 198 } … … 205 204 /// \pre \c i must be in the heap. 206 205 /// \param i The item. 207 Prio operator[](const Item &i) const {206 Prio operator[](const ItemType &i) const { 208 207 int idx = iim[i]; 209 208 return data[idx].second; … … 217 216 /// \param i The item. 218 217 /// \param p The priority. 219 void set(const Item &i, const Prio &p) {218 void set(const ItemType &i, const Prio &p) { 220 219 int idx = iim[i]; 221 220 if( idx < 0 ) { … … 237 236 /// \param i The item. 238 237 /// \param p The priority. 239 void decrease(const Item &i, const Prio &p) {238 void decrease(const ItemType &i, const Prio &p) { 240 239 int idx = iim[i]; 241 240 bubble_up(idx, PairType(i,p)); … … 249 248 /// \param i The item. 250 249 /// \param p The priority. 251 void increase(const Item &i, const Prio &p) {250 void increase(const ItemType &i, const Prio &p) { 252 251 int idx = iim[i]; 253 252 bubble_down(idx, PairType(i,p), data.size()); … … 262 261 /// get back to the heap again. 263 262 /// \param i The item. 264 state_enum state(const Item &i) const {263 state_enum state(const ItemType &i) const { 265 264 int s = iim[i]; 266 265 if( s>=0 ) … … 276 275 /// \param i The item. 277 276 /// \param st The state. It should not be \c IN_HEAP. 278 void state(const Item & i, state_enum st) {277 void state(const ItemType& i, state_enum st) { 279 278 switch (st) { 280 279 case POST_HEAP: … … 293 292 294 293 295 template <typename K, typenameV, typename M, typename C>296 int BinHeap< K,V,M,C>::bubble_up(int hole, PairType p) {294 template <typename V, typename M, typename C> 295 int BinHeap<V,M,C>::bubble_up(int hole, PairType p) { 297 296 int par = parent(hole); 298 297 while( hole>0 && less(p,data[par]) ) { … … 305 304 } 306 305 307 template <typename K, typenameV, typename M, typename C>308 int BinHeap< K,V,M,C>::bubble_down(int hole, PairType p, int length) {306 template <typename V, typename M, typename C> 307 int BinHeap<V,M,C>::bubble_down(int hole, PairType p, int length) { 309 308 int child = second_child(hole); 310 309 while(child < length) { -
lemon/bipartite_matching.h
r2151 r2263 522 522 /// 523 523 /// \sa BinHeap 524 typedef BinHeap< typename BpUGraph::Node,Value, HeapCrossRef> Heap;524 typedef BinHeap<Value, HeapCrossRef> Heap; 525 525 526 526 /// \brief Instantiates a Heap. -
lemon/bucket_heap.h
r2110 r2263 42 42 /// the priorities are small. It is not intended to use as dijkstra heap. 43 43 /// 44 /// \param _Item Type of the items to be stored.45 44 /// \param _ItemIntMap A read and writable Item int map, used internally 46 45 /// to handle the cross references. 47 46 /// \param minimize If the given parameter is true then the heap gives back 48 47 /// the lowest priority. 49 template <typename _Item , typename _ItemIntMap, bool minimize = true >48 template <typename _ItemIntMap, bool minimize = true > 50 49 class BucketHeap { 51 50 52 51 public: 53 typedef _ItemItem;52 typedef typename _ItemIntMap::Key Item; 54 53 typedef int Prio; 55 54 typedef std::pair<Item, Prio> Pair; … … 327 326 328 327 329 template <typename _Item , typename _ItemIntMap>330 class BucketHeap<_Item , _ItemIntMap, false> {331 332 public: 333 typedef _ItemItem;328 template <typename _ItemIntMap> 329 class BucketHeap<_ItemIntMap, false> { 330 331 public: 332 typedef typename _ItemIntMap::Key Item; 334 333 typedef int Prio; 335 334 typedef std::pair<Item, Prio> Pair; … … 525 524 /// minimal and it does not supports key increasing, decreasing. 526 525 /// 527 /// \param _Item Type of the items to be stored.528 526 /// \param _ItemIntMap A read and writable Item int map, used internally 529 527 /// to handle the cross references. … … 532 530 /// 533 531 /// \sa BucketHeap 534 template <typename _Item , typename _ItemIntMap, bool minimize = true >532 template <typename _ItemIntMap, bool minimize = true > 535 533 class SimpleBucketHeap { 536 534 537 535 public: 538 typedef _ItemItem;536 typedef typename _ItemIntMap::Key Item; 539 537 typedef int Prio; 540 538 typedef std::pair<Item, Prio> Pair; … … 710 708 }; // class SimpleBucketHeap 711 709 712 template <typename _Item , typename _ItemIntMap>713 class SimpleBucketHeap<_Item , _ItemIntMap, false> {714 715 public: 716 typedef _ItemItem;710 template <typename _ItemIntMap> 711 class SimpleBucketHeap<_ItemIntMap, false> { 712 713 public: 714 typedef typename _ItemIntMap::Key Item; 717 715 typedef int Prio; 718 716 typedef std::pair<Item, Prio> Pair; -
lemon/concepts/heap.h
r2260 r2263 37 37 /// A concept structure describes the main interface of heaps. 38 38 /// 39 template <typename Item, typenamePrio, typename ItemIntMap>39 template <typename Prio, typename ItemIntMap> 40 40 class Heap { 41 41 public: 42 43 ///\brief Type of the items stored in the heap. 44 typedef typename ItemIntMap::Key Item; 42 45 43 46 -
lemon/dijkstra.h
r2260 r2263 74 74 ///\sa BinHeap 75 75 ///\sa Dijkstra 76 typedef BinHeap<typename Graph::Node, typename LM::Value, 77 HeapCrossRef, std::less<Value> > Heap; 76 typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap; 78 77 79 78 static Heap *createHeap(HeapCrossRef& R) … … 848 847 ///\sa BinHeap 849 848 ///\sa Dijkstra 850 typedef BinHeap<typename Graph::Node, typename LM::Value, 851 typename GR::template NodeMap<int>, 849 typedef BinHeap<typename LM::Value, typename GR::template NodeMap<int>, 852 850 std::less<Value> > Heap; 853 851 -
lemon/fib_heap.h
r2050 r2263 44 44 ///\e binary \e heap. 45 45 /// 46 ///\param Item Type of the items to be stored.47 46 ///\param Prio Type of the priority of the items. 48 47 ///\param ItemIntMap A read and writable Item int map, used internally … … 56 55 57 56 #ifdef DOXYGEN 58 template <typename Item, 59 typename Prio, 57 template <typename Prio, 60 58 typename ItemIntMap, 61 59 typename Compare> 62 60 #else 63 template <typename Item, 64 typename Prio, 61 template <typename Prio, 65 62 typename ItemIntMap, 66 63 typename Compare = std::less<Prio> > 67 64 #endif 68 65 class FibHeap { 69 public: 66 public: 67 typedef typename ItemIntMap::Key Item; 70 68 typedef Prio PrioType; 71 69 … … 272 270 // ********************************************************************** 273 271 274 template <typename Item, typenamePrio, typename ItemIntMap,275 typename Compare> 276 void FibHeap< Item,Prio, ItemIntMap, Compare>::set272 template <typename Prio, typename ItemIntMap, 273 typename Compare> 274 void FibHeap<Prio, ItemIntMap, Compare>::set 277 275 (Item const item, PrioType const value) 278 276 { … … 284 282 } 285 283 286 template <typename Item, typenamePrio, typename ItemIntMap,287 typename Compare> 288 void FibHeap< Item,Prio, ItemIntMap, Compare>::push284 template <typename Prio, typename ItemIntMap, 285 typename Compare> 286 void FibHeap<Prio, ItemIntMap, Compare>::push 289 287 (Item const item, PrioType const value) { 290 288 int i=iimap[item]; … … 317 315 } 318 316 319 template <typename Item, typenamePrio, typename ItemIntMap,320 typename Compare> 321 void FibHeap< Item,Prio, ItemIntMap, Compare>::pop() {317 template <typename Prio, typename ItemIntMap, 318 typename Compare> 319 void FibHeap<Prio, ItemIntMap, Compare>::pop() { 322 320 /*The first case is that there are only one root.*/ 323 321 if ( container[minimum].left_neighbor==minimum ) { … … 351 349 352 350 353 template <typename Item, typenamePrio, typename ItemIntMap,354 typename Compare> 355 void FibHeap< Item,Prio, ItemIntMap, Compare>::erase351 template <typename Prio, typename ItemIntMap, 352 typename Compare> 353 void FibHeap<Prio, ItemIntMap, Compare>::erase 356 354 (const Item& item) { 357 355 int i=iimap[item]; … … 368 366 } 369 367 370 template <typename Item, typenamePrio, typename ItemIntMap,371 typename Compare> 372 void FibHeap< Item,Prio, ItemIntMap, Compare>::decrease368 template <typename Prio, typename ItemIntMap, 369 typename Compare> 370 void FibHeap<Prio, ItemIntMap, Compare>::decrease 373 371 (Item item, PrioType const value) { 374 372 int i=iimap[item]; … … 384 382 385 383 386 template <typename Item, typenamePrio, typename ItemIntMap,387 typename Compare> 388 void FibHeap< Item,Prio, ItemIntMap, Compare>::balance() {384 template <typename Prio, typename ItemIntMap, 385 typename Compare> 386 void FibHeap<Prio, ItemIntMap, Compare>::balance() { 389 387 390 388 int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1; … … 429 427 } 430 428 431 template <typename Item, typenamePrio, typename ItemIntMap,432 typename Compare> 433 void FibHeap< Item,Prio, ItemIntMap, Compare>::makeroot429 template <typename Prio, typename ItemIntMap, 430 typename Compare> 431 void FibHeap<Prio, ItemIntMap, Compare>::makeroot 434 432 (int c) { 435 433 int s=c; … … 441 439 442 440 443 template <typename Item, typenamePrio, typename ItemIntMap,444 typename Compare> 445 void FibHeap< Item,Prio, ItemIntMap, Compare>::cut441 template <typename Prio, typename ItemIntMap, 442 typename Compare> 443 void FibHeap<Prio, ItemIntMap, Compare>::cut 446 444 (int a, int b) { 447 445 /* … … 470 468 471 469 472 template <typename Item, typenamePrio, typename ItemIntMap,473 typename Compare> 474 void FibHeap< Item,Prio, ItemIntMap, Compare>::cascade470 template <typename Prio, typename ItemIntMap, 471 typename Compare> 472 void FibHeap<Prio, ItemIntMap, Compare>::cascade 475 473 (int a) 476 474 { … … 487 485 488 486 489 template <typename Item, typenamePrio, typename ItemIntMap,490 typename Compare> 491 void FibHeap< Item,Prio, ItemIntMap, Compare>::fuse487 template <typename Prio, typename ItemIntMap, 488 typename Compare> 489 void FibHeap<Prio, ItemIntMap, Compare>::fuse 492 490 (int a, int b) { 493 491 unlace(b); … … 518 516 *It is invoked only if a has siblings. 519 517 */ 520 template <typename Item, typenamePrio, typename ItemIntMap,521 typename Compare> 522 void FibHeap< Item,Prio, ItemIntMap, Compare>::unlace518 template <typename Prio, typename ItemIntMap, 519 typename Compare> 520 void FibHeap<Prio, ItemIntMap, Compare>::unlace 523 521 (int a) { 524 522 int leftn=container[a].left_neighbor; -
lemon/fredman_tarjan.h
r2260 r2263 281 281 typedef typename SrcGraph::template NodeMap<UEdge> PredMap; 282 282 HeapCrossRef crossref(graph,-1); 283 FibHeap< Node,Value,HeapCrossRef> heap(crossref);283 FibHeap<Value,HeapCrossRef> heap(crossref); 284 284 PredMap pred(graph,INVALID); 285 285 int rate=2*edgenum/countNodes(graph); -
lemon/johnson.h
r2260 r2263 131 131 ///\sa BinHeap 132 132 ///\sa Dijkstra 133 typedef BinHeap<typename Graph::Node, typenameLengthMap::Value,133 typedef BinHeap<typename LengthMap::Value, 134 134 HeapCrossRef, std::less<Value> > Heap; 135 135 -
lemon/min_cost_arborescence.h
r2260 r2263 225 225 HeapCrossRef *_heap_cross_ref; 226 226 227 typedef BinHeap< Node,int, HeapCrossRef> Heap;227 typedef BinHeap<int, HeapCrossRef> Heap; 228 228 229 229 Heap *_heap; -
lemon/min_cut.h
r2260 r2263 39 39 template <typename CapacityMap> 40 40 struct HeapSelector { 41 template <typename Key, typenameValue, typename Ref>41 template <typename Value, typename Ref> 42 42 struct Selector { 43 typedef BinHeap< Key,Value, Ref, std::greater<Value> > Heap;43 typedef BinHeap<Value, Ref, std::greater<Value> > Heap; 44 44 }; 45 45 }; … … 47 47 template <typename CapacityKey> 48 48 struct HeapSelector<ConstMap<CapacityKey, Const<int, 1> > > { 49 template <typename Key, typenameValue, typename Ref>49 template <typename Value, typename Ref> 50 50 struct Selector { 51 typedef BucketHeap< Key,Ref, false > Heap;51 typedef BucketHeap<Ref, false > Heap; 52 52 }; 53 53 }; … … 100 100 typedef typename _min_cut_bits 101 101 ::HeapSelector<CapacityMap> 102 ::template Selector< typename Graph::Node,Value, HeapCrossRef>102 ::template Selector<Value, HeapCrossRef> 103 103 ::Heap Heap; 104 104 … … 767 767 typedef typename _min_cut_bits 768 768 ::HeapSelector<CapacityMap> 769 ::template Selector< typename AuxGraph::Node,Value, HeapCrossRef>769 ::template Selector<Value, HeapCrossRef> 770 770 ::Heap Heap; 771 771 -
lemon/prim.h
r2260 r2263 71 71 ///\sa BinHeap 72 72 ///\sa Prim 73 typedef BinHeap<typename UGraph::Node, typenameCM::Value,73 typedef BinHeap<typename CM::Value, 74 74 HeapCrossRef, std::less<Value> > Heap; 75 75 -
lemon/radix_heap.h
r2151 r2263 55 55 /// item's priority. 56 56 /// 57 /// \param _Item Type of the items to be stored.58 57 /// \param _ItemIntMap A read and writable Item int map, used internally 59 58 /// to handle the cross references. … … 63 62 /// \author Balazs Dezso 64 63 65 template <typename _Item , typename _ItemIntMap>64 template <typename _ItemIntMap> 66 65 class RadixHeap { 67 66 68 67 public: 69 typedef _ItemItem;68 typedef typename _ItemIntMap::Key Item; 70 69 typedef int Prio; 71 70 typedef _ItemIntMap ItemIntMap; … … 300 299 /// \pre The heap must be nonempty. 301 300 Item top() const { 302 const_cast<RadixHeap<Item , ItemIntMap>&>(*this).moveDown();301 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown(); 303 302 return data[boxes[0].first].item; 304 303 } … … 309 308 /// \pre The heap must be nonempty. 310 309 Prio prio() const { 311 const_cast<RadixHeap<Item , ItemIntMap>&>(*this).moveDown();310 const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown(); 312 311 return data[boxes[0].first].prio; 313 312 }
Note: See TracChangeset
for help on using the changeset viewer.