1.1 --- a/lemon/fib_heap.h Thu Oct 26 13:35:35 2006 +0000
1.2 +++ b/lemon/fib_heap.h Thu Oct 26 14:20:17 2006 +0000
1.3 @@ -43,7 +43,6 @@
1.4 ///heap. In case of many calls to these operations, it is better to use a
1.5 ///\e binary \e heap.
1.6 ///
1.7 - ///\param Item Type of the items to be stored.
1.8 ///\param Prio Type of the priority of the items.
1.9 ///\param ItemIntMap A read and writable Item int map, used internally
1.10 ///to handle the cross references.
1.11 @@ -55,18 +54,17 @@
1.12 ///\author Jacint Szabo
1.13
1.14 #ifdef DOXYGEN
1.15 - template <typename Item,
1.16 - typename Prio,
1.17 + template <typename Prio,
1.18 typename ItemIntMap,
1.19 typename Compare>
1.20 #else
1.21 - template <typename Item,
1.22 - typename Prio,
1.23 + template <typename Prio,
1.24 typename ItemIntMap,
1.25 typename Compare = std::less<Prio> >
1.26 #endif
1.27 class FibHeap {
1.28 - public:
1.29 + public:
1.30 + typedef typename ItemIntMap::Key Item;
1.31 typedef Prio PrioType;
1.32
1.33 private:
1.34 @@ -271,9 +269,9 @@
1.35 // IMPLEMENTATIONS
1.36 // **********************************************************************
1.37
1.38 - template <typename Item, typename Prio, typename ItemIntMap,
1.39 + template <typename Prio, typename ItemIntMap,
1.40 typename Compare>
1.41 - void FibHeap<Item, Prio, ItemIntMap, Compare>::set
1.42 + void FibHeap<Prio, ItemIntMap, Compare>::set
1.43 (Item const item, PrioType const value)
1.44 {
1.45 int i=iimap[item];
1.46 @@ -283,9 +281,9 @@
1.47 } else push(item, value);
1.48 }
1.49
1.50 - template <typename Item, typename Prio, typename ItemIntMap,
1.51 + template <typename Prio, typename ItemIntMap,
1.52 typename Compare>
1.53 - void FibHeap<Item, Prio, ItemIntMap, Compare>::push
1.54 + void FibHeap<Prio, ItemIntMap, Compare>::push
1.55 (Item const item, PrioType const value) {
1.56 int i=iimap[item];
1.57 if ( i < 0 ) {
1.58 @@ -316,9 +314,9 @@
1.59 ++num_items;
1.60 }
1.61
1.62 - template <typename Item, typename Prio, typename ItemIntMap,
1.63 + template <typename Prio, typename ItemIntMap,
1.64 typename Compare>
1.65 - void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
1.66 + void FibHeap<Prio, ItemIntMap, Compare>::pop() {
1.67 /*The first case is that there are only one root.*/
1.68 if ( container[minimum].left_neighbor==minimum ) {
1.69 container[minimum].in=false;
1.70 @@ -350,9 +348,9 @@
1.71 }
1.72
1.73
1.74 - template <typename Item, typename Prio, typename ItemIntMap,
1.75 + template <typename Prio, typename ItemIntMap,
1.76 typename Compare>
1.77 - void FibHeap<Item, Prio, ItemIntMap, Compare>::erase
1.78 + void FibHeap<Prio, ItemIntMap, Compare>::erase
1.79 (const Item& item) {
1.80 int i=iimap[item];
1.81
1.82 @@ -367,9 +365,9 @@
1.83 }
1.84 }
1.85
1.86 - template <typename Item, typename Prio, typename ItemIntMap,
1.87 + template <typename Prio, typename ItemIntMap,
1.88 typename Compare>
1.89 - void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease
1.90 + void FibHeap<Prio, ItemIntMap, Compare>::decrease
1.91 (Item item, PrioType const value) {
1.92 int i=iimap[item];
1.93 container[i].prio=value;
1.94 @@ -383,9 +381,9 @@
1.95 }
1.96
1.97
1.98 - template <typename Item, typename Prio, typename ItemIntMap,
1.99 + template <typename Prio, typename ItemIntMap,
1.100 typename Compare>
1.101 - void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {
1.102 + void FibHeap<Prio, ItemIntMap, Compare>::balance() {
1.103
1.104 int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
1.105
1.106 @@ -428,9 +426,9 @@
1.107 } while ( s != m );
1.108 }
1.109
1.110 - template <typename Item, typename Prio, typename ItemIntMap,
1.111 + template <typename Prio, typename ItemIntMap,
1.112 typename Compare>
1.113 - void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot
1.114 + void FibHeap<Prio, ItemIntMap, Compare>::makeroot
1.115 (int c) {
1.116 int s=c;
1.117 do {
1.118 @@ -440,9 +438,9 @@
1.119 }
1.120
1.121
1.122 - template <typename Item, typename Prio, typename ItemIntMap,
1.123 + template <typename Prio, typename ItemIntMap,
1.124 typename Compare>
1.125 - void FibHeap<Item, Prio, ItemIntMap, Compare>::cut
1.126 + void FibHeap<Prio, ItemIntMap, Compare>::cut
1.127 (int a, int b) {
1.128 /*
1.129 *Replacing a from the children of b.
1.130 @@ -469,9 +467,9 @@
1.131 }
1.132
1.133
1.134 - template <typename Item, typename Prio, typename ItemIntMap,
1.135 + template <typename Prio, typename ItemIntMap,
1.136 typename Compare>
1.137 - void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade
1.138 + void FibHeap<Prio, ItemIntMap, Compare>::cascade
1.139 (int a)
1.140 {
1.141 if ( container[a].parent!=-1 ) {
1.142 @@ -486,9 +484,9 @@
1.143 }
1.144
1.145
1.146 - template <typename Item, typename Prio, typename ItemIntMap,
1.147 + template <typename Prio, typename ItemIntMap,
1.148 typename Compare>
1.149 - void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse
1.150 + void FibHeap<Prio, ItemIntMap, Compare>::fuse
1.151 (int a, int b) {
1.152 unlace(b);
1.153
1.154 @@ -517,9 +515,9 @@
1.155 /*
1.156 *It is invoked only if a has siblings.
1.157 */
1.158 - template <typename Item, typename Prio, typename ItemIntMap,
1.159 + template <typename Prio, typename ItemIntMap,
1.160 typename Compare>
1.161 - void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace
1.162 + void FibHeap<Prio, ItemIntMap, Compare>::unlace
1.163 (int a) {
1.164 int leftn=container[a].left_neighbor;
1.165 int rightn=container[a].right_neighbor;