UnionFind moved to include. Test compiles and runs cleanly.
* test/makefile:
minor cleanups
3 #ifndef HUGO_FIB_HEAP_H
4 #define HUGO_FIB_HEAP_H
8 ///\brief Fibonacci Heap implementation.
16 /// \addtogroup auxdat
19 /// An implementation of the Fibonacci Heap.
22 This class implements the \e Fibonacci \e heap data structure. A \e heap
23 is a data structure for storing items with specified values called \e
24 priorities, such that finding the item with minimum priority with respect
25 to \e Compare is efficient. In a heap one can change the priority of an
26 item, add or erase an item, etc.
28 The methods \ref increase and \ref erase are not efficient in a Fibonacci
29 heap. In case of many calls to these operations, it is better to use a
32 \param Item The type of the items to be stored.
33 \param Prio The type of the priority of the items.
34 \param ItemIntMap A read and writable Item int map, for the usage of
36 \param Compare A class for the comparison of the priorities. The
37 default is \c std::less<Prio>.
42 template <typename Item,
47 template <typename Item,
50 typename Compare = std::less<Prio> >
54 typedef Prio PrioType;
59 std::vector<store> container;
72 FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {}
73 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
74 iimap(_iimap), comp(_comp), num_items() {}
76 ///The number of items stored in the heap.
79 Returns the number of items stored in the heap.
81 int size() const { return num_items; }
83 ///Checks if the heap stores no items.
86 Returns \c true iff the heap stores no items.
88 bool empty() const { return num_items==0; }
90 ///\c item gets to the heap with priority \c value independently if \c item was already there.
93 This method calls \ref push(\c item, \c value) if \c item is not
94 stored in the heap and it calls \ref decrease(\c item, \c value) or
95 \ref increase(\c item, \c value) otherwise.
97 void set (Item const item, PrioType const value);
99 ///Adds \c item to the heap with priority \c value.
102 Adds \c item to the heap with priority \c value.
103 \pre \c item must not be stored in the heap.
105 void push (Item const item, PrioType const value);
108 ///Returns the item having the minimum priority w.r.t. Compare.
111 This method returns the item having the minimum priority w.r.t. Compare.
112 \pre The heap must be nonempty.
114 Item top() const { return container[minimum].name; }
117 ///Returns the minimum priority w.r.t. Compare.
120 It returns the minimum priority w.r.t. Compare.
121 \pre The heap must be nonempty.
123 PrioType prio() const { return container[minimum].prio; }
126 ///Returns the priority of \c item.
129 It returns the priority of \c item.
130 \pre \c item must be in the heap.
132 PrioType& operator[](const Item& item) {
133 return container[iimap[item]].prio;
136 ///Returns the priority of \c item.
139 It returns the priority of \c item.
140 \pre \c item must be in the heap.
142 const PrioType& operator[](const Item& item) const {
143 return container[iimap[item]].prio;
147 ///Deletes the item with minimum priority w.r.t. Compare.
150 This method deletes the item with minimum priority w.r.t.
151 Compare from the heap.
152 \pre The heap must be non-empty.
156 ///Deletes \c item from the heap.
159 This method deletes \c item from the heap, if \c item was already
160 stored in the heap. It is quite inefficient in Fibonacci heaps.
162 void erase (const Item& item);
164 ///Decreases the priority of \c item to \c value.
167 This method decreases the priority of \c item to \c value.
168 \pre \c item must be stored in the heap with priority at least \c
169 value w.r.t. Compare.
171 void decrease (Item item, PrioType const value);
174 ///Increases the priority of \c item to \c value.
177 This method sets the priority of \c item to \c value. Though
178 there is no precondition on the priority of \c item, this
179 method should be used only if there is a need to really \e increase
180 (w.r.t. Compare) the priority of \c item, because this
181 method is inefficient.
183 void increase (Item item, PrioType const value) {
189 ///Tells if \c item is in, was already in, or has never been in the heap.
192 This method returns PRE_HEAP if \c item has never been in the
193 heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
194 otherwise. In the latter case it is possible that \c item will
195 get back to the heap again.
197 state_enum state(const Item &item) const {
200 if ( container[i].in ) i=0;
203 return state_enum(i);
209 void makeroot(int c);
210 void cut(int a, int b);
212 void fuse(int a, int b);
217 friend class FibHeap;
229 store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
235 // **********************************************************************
237 // **********************************************************************
239 template <typename Item, typename Prio, typename ItemIntMap,
241 void FibHeap<Item, Prio, ItemIntMap, Compare>::set
242 (Item const item, PrioType const value)
245 if ( i >= 0 && container[i].in ) {
246 if ( comp(value, container[i].prio) ) decrease(item, value);
247 if ( comp(container[i].prio, value) ) increase(item, value);
248 } else push(item, value);
251 template <typename Item, typename Prio, typename ItemIntMap,
253 void FibHeap<Item, Prio, ItemIntMap, Compare>::push
254 (Item const item, PrioType const value) {
257 int s=container.size();
258 iimap.set( item, s );
261 container.push_back(st);
264 container[i].parent=container[i].child=-1;
265 container[i].degree=0;
266 container[i].in=true;
267 container[i].marked=false;
271 container[container[minimum].right_neighbor].left_neighbor=i;
272 container[i].right_neighbor=container[minimum].right_neighbor;
273 container[minimum].right_neighbor=i;
274 container[i].left_neighbor=minimum;
275 if ( comp( value, container[minimum].prio) ) minimum=i;
277 container[i].right_neighbor=container[i].left_neighbor=i;
280 container[i].prio=value;
284 template <typename Item, typename Prio, typename ItemIntMap,
286 void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
287 /*The first case is that there are only one root.*/
288 if ( container[minimum].left_neighbor==minimum ) {
289 container[minimum].in=false;
290 if ( container[minimum].degree!=0 ) {
291 makeroot(container[minimum].child);
292 minimum=container[minimum].child;
296 int right=container[minimum].right_neighbor;
298 container[minimum].in=false;
299 if ( container[minimum].degree > 0 ) {
300 int left=container[minimum].left_neighbor;
301 int child=container[minimum].child;
302 int last_child=container[child].left_neighbor;
306 container[left].right_neighbor=child;
307 container[child].left_neighbor=left;
308 container[right].left_neighbor=last_child;
309 container[last_child].right_neighbor=right;
313 } // the case where there are more roots
318 template <typename Item, typename Prio, typename ItemIntMap,
320 void FibHeap<Item, Prio, ItemIntMap, Compare>::erase
324 if ( i >= 0 && container[i].in ) {
325 if ( container[i].parent!=-1 ) {
326 int p=container[i].parent;
330 minimum=i; //As if its prio would be -infinity
335 template <typename Item, typename Prio, typename ItemIntMap,
337 void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease
338 (Item item, PrioType const value) {
340 container[i].prio=value;
341 int p=container[i].parent;
343 if ( p!=-1 && comp(value, container[p].prio) ) {
347 if ( comp(value, container[minimum].prio) ) minimum=i;
351 template <typename Item, typename Prio, typename ItemIntMap,
353 void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {
355 int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
357 std::vector<int> A(maxdeg,-1);
360 *Recall that now minimum does not point to the minimum prio element.
361 *We set minimum to this during balance().
363 int anchor=container[minimum].left_neighbor;
369 if ( anchor==active ) end=true;
370 int d=container[active].degree;
371 next=container[active].right_neighbor;
374 if( comp(container[active].prio, container[A[d]].prio) ) {
387 while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
391 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
392 s=container[s].right_neighbor;
396 template <typename Item, typename Prio, typename ItemIntMap,
398 void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot
402 container[s].parent=-1;
403 s=container[s].right_neighbor;
408 template <typename Item, typename Prio, typename ItemIntMap,
410 void FibHeap<Item, Prio, ItemIntMap, Compare>::cut
413 *Replacing a from the children of b.
415 --container[b].degree;
417 if ( container[b].degree !=0 ) {
418 int child=container[b].child;
420 container[b].child=container[child].right_neighbor;
425 /*Lacing a to the roots.*/
426 int right=container[minimum].right_neighbor;
427 container[minimum].right_neighbor=a;
428 container[a].left_neighbor=minimum;
429 container[a].right_neighbor=right;
430 container[right].left_neighbor=a;
432 container[a].parent=-1;
433 container[a].marked=false;
437 template <typename Item, typename Prio, typename ItemIntMap,
439 void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade
442 if ( container[a].parent!=-1 ) {
443 int p=container[a].parent;
445 if ( container[a].marked==false ) container[a].marked=true;
454 template <typename Item, typename Prio, typename ItemIntMap,
456 void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse
460 /*Lacing b under a.*/
461 container[b].parent=a;
463 if (container[a].degree==0) {
464 container[b].left_neighbor=b;
465 container[b].right_neighbor=b;
466 container[a].child=b;
468 int child=container[a].child;
469 int last_child=container[child].left_neighbor;
470 container[child].left_neighbor=b;
471 container[b].right_neighbor=child;
472 container[last_child].right_neighbor=b;
473 container[b].left_neighbor=last_child;
476 ++container[a].degree;
478 container[b].marked=false;
483 *It is invoked only if a has siblings.
485 template <typename Item, typename Prio, typename ItemIntMap,
487 void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace
489 int leftn=container[a].left_neighbor;
490 int rightn=container[a].right_neighbor;
491 container[leftn].right_neighbor=rightn;
492 container[rightn].left_neighbor=leftn;
499 #endif //HUGO_FIB_HEAP_H