A strange compilation failure (under cygwin) is fixed.
Version 0.3 should be fixed as well.
2 * src/lemon/fib_heap.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_FIB_HEAP_H
18 #define LEMON_FIB_HEAP_H
22 ///\brief Fibonacci Heap implementation.
30 /// \addtogroup auxdat
35 ///This class implements the \e Fibonacci \e heap data structure. A \e heap
36 ///is a data structure for storing items with specified values called \e
37 ///priorities in such a way that finding the item with minimum priority is
38 ///efficient. \c Compare specifies the ordering of the priorities. In a heap
39 ///one can change the priority of an item, add or erase an item, etc.
41 ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
42 ///heap. In case of many calls to these operations, it is better to use a
45 ///\param Item Type of the items to be stored.
46 ///\param Prio Type of the priority of the items.
47 ///\param ItemIntMap A read and writable Item int map, used internally
48 ///to handle the cross references.
49 ///\param Compare A class for the ordering of the priorities. The
50 ///default is \c std::less<Prio>.
54 ///\author Jacint Szabo
57 template <typename Item,
62 template <typename Item,
65 typename Compare = std::less<Prio> >
69 typedef Prio PrioType;
74 std::vector<store> container;
81 ///Status of the nodes
83 ///The node is in the heap
85 ///The node has never been in the heap
87 ///The node was in the heap but it got out of it
91 explicit FibHeap(ItemIntMap &_iimap)
92 : minimum(0), iimap(_iimap), num_items() {}
93 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
94 iimap(_iimap), comp(_comp), num_items() {}
96 ///The number of items stored in the heap.
99 Returns the number of items stored in the heap.
101 int size() const { return num_items; }
103 ///Checks if the heap stores no items.
106 Returns \c true if and only if the heap stores no items.
108 bool empty() const { return num_items==0; }
110 ///\c item gets to the heap with priority \c value independently if \c item was already there.
113 This method calls \ref push(\c item, \c value) if \c item is not
114 stored in the heap and it calls \ref decrease(\c item, \c value) or
115 \ref increase(\c item, \c value) otherwise.
117 void set (Item const item, PrioType const value);
119 ///Adds \c item to the heap with priority \c value.
122 Adds \c item to the heap with priority \c value.
123 \pre \c item must not be stored in the heap.
125 void push (Item const item, PrioType const value);
127 ///Returns the item with minimum priority relative to \c Compare.
130 This method returns the item with minimum priority relative to \c
132 \pre The heap must be nonempty.
134 Item top() const { return container[minimum].name; }
136 ///Returns the minimum priority relative to \c Compare.
139 It returns the minimum priority relative to \c Compare.
140 \pre The heap must be nonempty.
142 PrioType prio() const { return container[minimum].prio; }
144 ///Returns the priority of \c item.
147 This function returns the priority of \c item.
148 \pre \c item must be in the heap.
150 PrioType& operator[](const Item& item) {
151 return container[iimap[item]].prio;
154 ///Returns the priority of \c item.
157 It returns the priority of \c item.
158 \pre \c item must be in the heap.
160 const PrioType& operator[](const Item& item) const {
161 return container[iimap[item]].prio;
165 ///Deletes the item with minimum priority relative to \c Compare.
168 This method deletes the item with minimum priority relative to \c
169 Compare from the heap.
170 \pre The heap must be non-empty.
174 ///Deletes \c item from the heap.
177 This method deletes \c item from the heap, if \c item was already
178 stored in the heap. It is quite inefficient in Fibonacci heaps.
180 void erase (const Item& item);
182 ///Decreases the priority of \c item to \c value.
185 This method decreases the priority of \c item to \c value.
186 \pre \c item must be stored in the heap with priority at least \c
187 value relative to \c Compare.
189 void decrease (Item item, PrioType const value);
191 ///Increases the priority of \c item to \c value.
194 This method sets the priority of \c item to \c value. Though
195 there is no precondition on the priority of \c item, this
196 method should be used only if it is indeed necessary to increase
197 (relative to \c Compare) the priority of \c item, because this
198 method is inefficient.
200 void increase (Item item, PrioType const value) {
206 ///Returns if \c item is in, has already been in, or has never been in the heap.
209 This method returns PRE_HEAP if \c item has never been in the
210 heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
211 otherwise. In the latter case it is possible that \c item will
212 get back to the heap again.
214 state_enum state(const Item &item) const {
217 if ( container[i].in ) i=0;
220 return state_enum(i);
226 void makeroot(int c);
227 void cut(int a, int b);
229 void fuse(int a, int b);
234 friend class FibHeap;
246 store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
252 // **********************************************************************
254 // **********************************************************************
256 template <typename Item, typename Prio, typename ItemIntMap,
258 void FibHeap<Item, Prio, ItemIntMap, Compare>::set
259 (Item const item, PrioType const value)
262 if ( i >= 0 && container[i].in ) {
263 if ( comp(value, container[i].prio) ) decrease(item, value);
264 if ( comp(container[i].prio, value) ) increase(item, value);
265 } else push(item, value);
268 template <typename Item, typename Prio, typename ItemIntMap,
270 void FibHeap<Item, Prio, ItemIntMap, Compare>::push
271 (Item const item, PrioType const value) {
274 int s=container.size();
275 iimap.set( item, s );
278 container.push_back(st);
281 container[i].parent=container[i].child=-1;
282 container[i].degree=0;
283 container[i].in=true;
284 container[i].marked=false;
288 container[container[minimum].right_neighbor].left_neighbor=i;
289 container[i].right_neighbor=container[minimum].right_neighbor;
290 container[minimum].right_neighbor=i;
291 container[i].left_neighbor=minimum;
292 if ( comp( value, container[minimum].prio) ) minimum=i;
294 container[i].right_neighbor=container[i].left_neighbor=i;
297 container[i].prio=value;
301 template <typename Item, typename Prio, typename ItemIntMap,
303 void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
304 /*The first case is that there are only one root.*/
305 if ( container[minimum].left_neighbor==minimum ) {
306 container[minimum].in=false;
307 if ( container[minimum].degree!=0 ) {
308 makeroot(container[minimum].child);
309 minimum=container[minimum].child;
313 int right=container[minimum].right_neighbor;
315 container[minimum].in=false;
316 if ( container[minimum].degree > 0 ) {
317 int left=container[minimum].left_neighbor;
318 int child=container[minimum].child;
319 int last_child=container[child].left_neighbor;
323 container[left].right_neighbor=child;
324 container[child].left_neighbor=left;
325 container[right].left_neighbor=last_child;
326 container[last_child].right_neighbor=right;
330 } // the case where there are more roots
335 template <typename Item, typename Prio, typename ItemIntMap,
337 void FibHeap<Item, Prio, ItemIntMap, Compare>::erase
341 if ( i >= 0 && container[i].in ) {
342 if ( container[i].parent!=-1 ) {
343 int p=container[i].parent;
347 minimum=i; //As if its prio would be -infinity
352 template <typename Item, typename Prio, typename ItemIntMap,
354 void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease
355 (Item item, PrioType const value) {
357 container[i].prio=value;
358 int p=container[i].parent;
360 if ( p!=-1 && comp(value, container[p].prio) ) {
364 if ( comp(value, container[minimum].prio) ) minimum=i;
368 template <typename Item, typename Prio, typename ItemIntMap,
370 void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {
372 int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
374 std::vector<int> A(maxdeg,-1);
377 *Recall that now minimum does not point to the minimum prio element.
378 *We set minimum to this during balance().
380 int anchor=container[minimum].left_neighbor;
386 if ( anchor==active ) end=true;
387 int d=container[active].degree;
388 next=container[active].right_neighbor;
391 if( comp(container[active].prio, container[A[d]].prio) ) {
404 while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
408 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
409 s=container[s].right_neighbor;
413 template <typename Item, typename Prio, typename ItemIntMap,
415 void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot
419 container[s].parent=-1;
420 s=container[s].right_neighbor;
425 template <typename Item, typename Prio, typename ItemIntMap,
427 void FibHeap<Item, Prio, ItemIntMap, Compare>::cut
430 *Replacing a from the children of b.
432 --container[b].degree;
434 if ( container[b].degree !=0 ) {
435 int child=container[b].child;
437 container[b].child=container[child].right_neighbor;
442 /*Lacing a to the roots.*/
443 int right=container[minimum].right_neighbor;
444 container[minimum].right_neighbor=a;
445 container[a].left_neighbor=minimum;
446 container[a].right_neighbor=right;
447 container[right].left_neighbor=a;
449 container[a].parent=-1;
450 container[a].marked=false;
454 template <typename Item, typename Prio, typename ItemIntMap,
456 void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade
459 if ( container[a].parent!=-1 ) {
460 int p=container[a].parent;
462 if ( container[a].marked==false ) container[a].marked=true;
471 template <typename Item, typename Prio, typename ItemIntMap,
473 void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse
477 /*Lacing b under a.*/
478 container[b].parent=a;
480 if (container[a].degree==0) {
481 container[b].left_neighbor=b;
482 container[b].right_neighbor=b;
483 container[a].child=b;
485 int child=container[a].child;
486 int last_child=container[child].left_neighbor;
487 container[child].left_neighbor=b;
488 container[b].right_neighbor=child;
489 container[last_child].right_neighbor=b;
490 container[b].left_neighbor=last_child;
493 ++container[a].degree;
495 container[b].marked=false;
500 *It is invoked only if a has siblings.
502 template <typename Item, typename Prio, typename ItemIntMap,
504 void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace
506 int leftn=container[a].left_neighbor;
507 int rightn=container[a].right_neighbor;
508 container[leftn].right_neighbor=rightn;
509 container[rightn].left_neighbor=leftn;
516 #endif //LEMON_FIB_HEAP_H