1.1 --- a/src/include/fib_heap.h Fri Apr 23 19:15:55 2004 +0000
1.2 +++ b/src/include/fib_heap.h Fri Apr 23 19:41:01 2004 +0000
1.3 @@ -15,21 +15,21 @@
1.4 /// An implementation of the Fibonacci Heap.
1.5
1.6 /**
1.7 - This class implements the \e Fibonacci \e heap data structure. A \e
1.8 - heap is a data structure for storing items with specified priorities,
1.9 - such that finding the item with minimum priority is efficient. In a
1.10 - heap one can change the priority of an item, and to add or erase an
1.11 - item.
1.12 + This class implements the \e Fibonacci \e heap data structure. A \e heap
1.13 + is a data structure for storing items with specified values called \e
1.14 + priorities, such that finding the item with minimum priority with respect
1.15 + to \e Compare is efficient. In a heap one can change the priority of an
1.16 + item, add or erase an item, etc.
1.17
1.18 - The methods \ref increase and \ref erase are not efficient, in
1.19 - case of many calls to these operations, it is better to use
1.20 - a binary heap.
1.21 + The methods \ref increase and \ref erase are not efficient in a Fibonacci
1.22 + heap. In case of many calls to these operations, it is better to use a
1.23 + \e binary \e heap.
1.24
1.25 - /param Item The type of the items to be stored.
1.26 - /param Prio The type of the priority of the items.
1.27 - /param ItemIntMap A read and writable Item int map, for the usage of
1.28 + \param Item The type of the items to be stored.
1.29 + \param Prio The type of the priority of the items.
1.30 + \param ItemIntMap A read and writable Item int map, for the usage of
1.31 the heap.
1.32 - /param Compare A class for the comparison of the priorities. The
1.33 + \param Compare A class for the comparison of the priorities. The
1.34 default is \c std::less<Prio>.
1.35
1.36 */
1.37 @@ -46,7 +46,7 @@
1.38 typename Compare = std::less<Prio> >
1.39 #endif
1.40 class FibHeap {
1.41 - public:
1.42 + public:
1.43 typedef Prio PrioType;
1.44
1.45 private:
1.46 @@ -67,8 +67,6 @@
1.47 POST_HEAP = -2
1.48 };
1.49
1.50 - public :
1.51 -
1.52 FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {}
1.53 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
1.54 iimap(_iimap), comp(_comp), num_items() {}
1.55 @@ -76,25 +74,25 @@
1.56 ///The number of items stored in the heap.
1.57
1.58 /**
1.59 - Returns the number of items stored in the heap.
1.60 + Returns the number of items stored in the heap.
1.61 */
1.62 int size() const { return num_items; }
1.63
1.64 ///Checks if the heap stores no items.
1.65
1.66 /**
1.67 - Returns true iff the heap stores no items.
1.68 + Returns \c true iff the heap stores no items.
1.69 */
1.70 bool empty() const { return num_items==0; }
1.71
1.72 - ///Item \c item gets to the heap with priority \c value independently if \c item was already there.
1.73 + ///\c item gets to the heap with priority \c value independently if \c item was already there.
1.74
1.75 /**
1.76 - This method calls \ref push(item, value) if \c item is not
1.77 - stored in the heap, and it calls \ref decrease(it, \c value) or
1.78 - \ref increase(it, \c value) otherwise.
1.79 + This method calls \ref push(\c item, \c value) if \c item is not
1.80 + stored in the heap and it calls \ref decrease(\c item, \c value) or
1.81 + \ref increase(\c item, \c value) otherwise.
1.82 */
1.83 - void set (Item const item, PrioType const value); //vigyazat: az implementacioban it van
1.84 + void set (Item const item, PrioType const value);
1.85
1.86 ///Adds \c item to the heap with priority \c value.
1.87
1.88 @@ -102,7 +100,7 @@
1.89 Adds \c item to the heap with priority \c value.
1.90 \pre \c item must not be stored in the heap.
1.91 */
1.92 - void push (Item const it, PrioType const value); /*vigyazat: az implementacioban it van*/
1.93 + void push (Item const item, PrioType const value);
1.94
1.95
1.96 ///Returns the item having the minimum priority w.r.t. Compare.
1.97 @@ -129,7 +127,9 @@
1.98 It returns the priority of \c item.
1.99 \pre \c item must be in the heap.
1.100 */
1.101 - PrioType& operator[](const Item& it) { return container[iimap[it]].prio; }
1.102 + PrioType& operator[](const Item& item) {
1.103 + return container[iimap[item]].prio;
1.104 + }
1.105
1.106 ///Returns the priority of \c item.
1.107
1.108 @@ -137,8 +137,8 @@
1.109 It returns the priority of \c item.
1.110 \pre \c item must be in the heap.
1.111 */
1.112 - const PrioType& operator[](const Item& it) const {
1.113 - return container[iimap[it]].prio;
1.114 + const PrioType& operator[](const Item& item) const {
1.115 + return container[iimap[item]].prio;
1.116 }
1.117
1.118
1.119 @@ -157,7 +157,7 @@
1.120 This method deletes \c item from the heap, if \c item was already
1.121 stored in the heap. It is quite inefficient in Fibonacci heaps.
1.122 */
1.123 - void erase (const Item& item); /*vigyazat: az implementacioban it van*/
1.124 + void erase (const Item& item);
1.125
1.126 ///Decreases the priority of \c item to \c value.
1.127
1.128 @@ -166,7 +166,7 @@
1.129 \pre \c item must be stored in the heap with priority at least \c
1.130 value w.r.t. Compare.
1.131 */
1.132 - void decrease (Item item, PrioType const value); /*vigyazat: az implementacioban it van*/
1.133 + void decrease (Item item, PrioType const value);
1.134
1.135
1.136 ///Increases the priority of \c item to \c value.
1.137 @@ -174,17 +174,17 @@
1.138 /**
1.139 This method sets the priority of \c item to \c value. Though
1.140 there is no precondition on the priority of \c item, this
1.141 - method should be used only if one wants to \e increase
1.142 + method should be used only if there is a need to really \e increase
1.143 (w.r.t. Compare) the priority of \c item, because this
1.144 method is inefficient.
1.145 */
1.146 - void increase (Item it, PrioType const value) {
1.147 - erase(it);
1.148 - push(it, value);
1.149 + void increase (Item item, PrioType const value) {
1.150 + erase(item);
1.151 + push(item, value);
1.152 }
1.153
1.154
1.155 - ///Tells if \c item is in, was in, or has not been in the heap.
1.156 + ///Tells if \c item is in, was already in, or has never been in the heap.
1.157
1.158 /**
1.159 This method returns PRE_HEAP if \c item has never been in the
1.160 @@ -192,31 +192,70 @@
1.161 otherwise. In the latter case it is possible that \c item will
1.162 get back to the heap again.
1.163 */
1.164 - state_enum state(const Item &it); /*vigyazat: az implementacioban it van*/
1.165 + state_enum state(const Item &item) const {
1.166 + int i=iimap[item];
1.167 + if( i>=0 ) {
1.168 + if ( container[i].in ) i=0;
1.169 + else i=-2;
1.170 + }
1.171 + return state_enum(i);
1.172 + }
1.173 +
1.174 + private:
1.175 +
1.176 + void balance();
1.177 + void makeroot(int c);
1.178 + void cut(int a, int b);
1.179 + void cascade(int a);
1.180 + void fuse(int a, int b);
1.181 + void unlace(int a);
1.182
1.183
1.184 + class store {
1.185 + friend class FibHeap;
1.186 +
1.187 + Item name;
1.188 + int parent;
1.189 + int left_neighbor;
1.190 + int right_neighbor;
1.191 + int child;
1.192 + int degree;
1.193 + bool marked;
1.194 + bool in;
1.195 + PrioType prio;
1.196 +
1.197 + store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
1.198 + };
1.199 + };
1.200 +
1.201 +
1.202
1.203 // **********************************************************************
1.204 // IMPLEMENTATIONS
1.205 // **********************************************************************
1.206
1.207 -
1.208 - void set (Item const it, PrioType const value) {
1.209 - int i=iimap[it];
1.210 - if ( i >= 0 && container[i].in ) {
1.211 - if ( comp(value, container[i].prio) ) decrease(it, value);
1.212 - if ( comp(container[i].prio, value) ) increase(it, value);
1.213 - } else push(it, value);
1.214 - }
1.215 + template <typename Item, typename Prio, typename ItemIntMap,
1.216 + typename Compare>
1.217 + void FibHeap<Item, Prio, ItemIntMap, Compare>::set
1.218 + (Item const item, PrioType const value)
1.219 + {
1.220 + int i=iimap[item];
1.221 + if ( i >= 0 && container[i].in ) {
1.222 + if ( comp(value, container[i].prio) ) decrease(item, value);
1.223 + if ( comp(container[i].prio, value) ) increase(item, value);
1.224 + } else push(item, value);
1.225 + }
1.226
1.227 -
1.228 - void push (Item const it, PrioType const value) {
1.229 - int i=iimap[it];
1.230 + template <typename Item, typename Prio, typename ItemIntMap,
1.231 + typename Compare>
1.232 + void FibHeap<Item, Prio, ItemIntMap, Compare>::push
1.233 + (Item const item, PrioType const value) {
1.234 + int i=iimap[item];
1.235 if ( i < 0 ) {
1.236 int s=container.size();
1.237 - iimap.set( it, s );
1.238 + iimap.set( item, s );
1.239 store st;
1.240 - st.name=it;
1.241 + st.name=item;
1.242 container.push_back(st);
1.243 i=s;
1.244 } else {
1.245 @@ -240,8 +279,9 @@
1.246 ++num_items;
1.247 }
1.248
1.249 -
1.250 - void pop() {
1.251 + template <typename Item, typename Prio, typename ItemIntMap,
1.252 + typename Compare>
1.253 + void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
1.254 /*The first case is that there are only one root.*/
1.255 if ( container[minimum].left_neighbor==minimum ) {
1.256 container[minimum].in=false;
1.257 @@ -272,9 +312,12 @@
1.258 --num_items;
1.259 }
1.260
1.261 -
1.262 - void erase (const Item& it) {
1.263 - int i=iimap[it];
1.264 +
1.265 + template <typename Item, typename Prio, typename ItemIntMap,
1.266 + typename Compare>
1.267 + void FibHeap<Item, Prio, ItemIntMap, Compare>::erase
1.268 + (const Item& item) {
1.269 + int i=iimap[item];
1.270
1.271 if ( i >= 0 && container[i].in ) {
1.272 if ( container[i].parent!=-1 ) {
1.273 @@ -285,11 +328,13 @@
1.274 minimum=i; //As if its prio would be -infinity
1.275 pop();
1.276 }
1.277 - }
1.278 + }
1.279
1.280 -
1.281 - void decrease (Item it, PrioType const value) {
1.282 - int i=iimap[it];
1.283 + template <typename Item, typename Prio, typename ItemIntMap,
1.284 + typename Compare>
1.285 + void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease
1.286 + (Item item, PrioType const value) {
1.287 + int i=iimap[item];
1.288 container[i].prio=value;
1.289 int p=container[i].parent;
1.290
1.291 @@ -298,22 +343,12 @@
1.292 cascade(p);
1.293 }
1.294 if ( comp(value, container[minimum].prio) ) minimum=i;
1.295 - }
1.296 -
1.297 + }
1.298 +
1.299
1.300 - state_enum state(const Item &it) const {
1.301 - int i=iimap[it];
1.302 - if( i>=0 ) {
1.303 - if ( container[i].in ) i=0;
1.304 - else i=-2;
1.305 - }
1.306 - return state_enum(i);
1.307 - }
1.308 -
1.309 -
1.310 - private:
1.311 -
1.312 - void balance() {
1.313 + template <typename Item, typename Prio, typename ItemIntMap,
1.314 + typename Compare>
1.315 + void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {
1.316
1.317 int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
1.318
1.319 @@ -356,43 +391,51 @@
1.320 } while ( s != m );
1.321 }
1.322
1.323 -
1.324 - void makeroot (int c) {
1.325 + template <typename Item, typename Prio, typename ItemIntMap,
1.326 + typename Compare>
1.327 + void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot
1.328 + (int c) {
1.329 int s=c;
1.330 do {
1.331 container[s].parent=-1;
1.332 s=container[s].right_neighbor;
1.333 } while ( s != c );
1.334 }
1.335 +
1.336 +
1.337 + template <typename Item, typename Prio, typename ItemIntMap,
1.338 + typename Compare>
1.339 + void FibHeap<Item, Prio, ItemIntMap, Compare>::cut
1.340 + (int a, int b) {
1.341 + /*
1.342 + *Replacing a from the children of b.
1.343 + */
1.344 + --container[b].degree;
1.345
1.346 + if ( container[b].degree !=0 ) {
1.347 + int child=container[b].child;
1.348 + if ( child==a )
1.349 + container[b].child=container[child].right_neighbor;
1.350 + unlace(a);
1.351 + }
1.352 +
1.353 +
1.354 + /*Lacing a to the roots.*/
1.355 + int right=container[minimum].right_neighbor;
1.356 + container[minimum].right_neighbor=a;
1.357 + container[a].left_neighbor=minimum;
1.358 + container[a].right_neighbor=right;
1.359 + container[right].left_neighbor=a;
1.360 +
1.361 + container[a].parent=-1;
1.362 + container[a].marked=false;
1.363 + }
1.364 +
1.365
1.366 - void cut (int a, int b) {
1.367 - /*
1.368 - *Replacing a from the children of b.
1.369 - */
1.370 - --container[b].degree;
1.371 -
1.372 - if ( container[b].degree !=0 ) {
1.373 - int child=container[b].child;
1.374 - if ( child==a )
1.375 - container[b].child=container[child].right_neighbor;
1.376 - unlace(a);
1.377 - }
1.378 -
1.379 -
1.380 - /*Lacing a to the roots.*/
1.381 - int right=container[minimum].right_neighbor;
1.382 - container[minimum].right_neighbor=a;
1.383 - container[a].left_neighbor=minimum;
1.384 - container[a].right_neighbor=right;
1.385 - container[right].left_neighbor=a;
1.386 -
1.387 - container[a].parent=-1;
1.388 - container[a].marked=false;
1.389 - }
1.390 -
1.391 -
1.392 - void cascade (int a)
1.393 + template <typename Item, typename Prio, typename ItemIntMap,
1.394 + typename Compare>
1.395 + void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade
1.396 + (int a)
1.397 {
1.398 if ( container[a].parent!=-1 ) {
1.399 int p=container[a].parent;
1.400 @@ -406,7 +449,10 @@
1.401 }
1.402
1.403
1.404 - void fuse (int a, int b) {
1.405 + template <typename Item, typename Prio, typename ItemIntMap,
1.406 + typename Compare>
1.407 + void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse
1.408 + (int a, int b) {
1.409 unlace(b);
1.410
1.411 /*Lacing b under a.*/
1.412 @@ -430,35 +476,19 @@
1.413 container[b].marked=false;
1.414 }
1.415
1.416 -
1.417 - /*
1.418 - *It is invoked only if a has siblings.
1.419 - */
1.420 - void unlace (int a) {
1.421 +
1.422 + /*
1.423 + *It is invoked only if a has siblings.
1.424 + */
1.425 + template <typename Item, typename Prio, typename ItemIntMap,
1.426 + typename Compare>
1.427 + void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace
1.428 + (int a) {
1.429 int leftn=container[a].left_neighbor;
1.430 int rightn=container[a].right_neighbor;
1.431 container[leftn].right_neighbor=rightn;
1.432 container[rightn].left_neighbor=leftn;
1.433 - }
1.434 -
1.435 -
1.436 - class store {
1.437 - friend class FibHeap;
1.438 -
1.439 - Item name;
1.440 - int parent;
1.441 - int left_neighbor;
1.442 - int right_neighbor;
1.443 - int child;
1.444 - int degree;
1.445 - bool marked;
1.446 - bool in;
1.447 - PrioType prio;
1.448 -
1.449 - store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
1.450 - };
1.451 -
1.452 - };
1.453 + }
1.454
1.455 } //namespace hugo
1.456 #endif