Functions added to compute the gradient of Bezier curve.
2 * src/lemon/fib_heap.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2004 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, for the usage of
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;
87 FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {}
88 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
89 iimap(_iimap), comp(_comp), num_items() {}
91 ///The number of items stored in the heap.
94 Returns the number of items stored in the heap.
96 int size() const { return num_items; }
98 ///Checks if the heap stores no items.
101 Returns \c true if and only if the heap stores no items.
103 bool empty() const { return num_items==0; }
105 ///\c item gets to the heap with priority \c value independently if \c item was already there.
108 This method calls \ref push(\c item, \c value) if \c item is not
109 stored in the heap and it calls \ref decrease(\c item, \c value) or
110 \ref increase(\c item, \c value) otherwise.
112 void set (Item const item, PrioType const value);
114 ///Adds \c item to the heap with priority \c value.
117 Adds \c item to the heap with priority \c value.
118 \pre \c item must not be stored in the heap.
120 void push (Item const item, PrioType const value);
122 ///Returns the item with minimum priority relative to \c Compare.
125 This method returns the item with minimum priority relative to \c
127 \pre The heap must be nonempty.
129 Item top() const { return container[minimum].name; }
131 ///Returns the minimum priority relative to \c Compare.
134 It returns the minimum priority relative to \c Compare.
135 \pre The heap must be nonempty.
137 PrioType prio() const { return container[minimum].prio; }
139 ///Returns the priority of \c item.
142 This function returns the priority of \c item.
143 \pre \c item must be in the heap.
145 PrioType& operator[](const Item& item) {
146 return container[iimap[item]].prio;
149 ///Returns the priority of \c item.
152 It returns the priority of \c item.
153 \pre \c item must be in the heap.
155 const PrioType& operator[](const Item& item) const {
156 return container[iimap[item]].prio;
160 ///Deletes the item with minimum priority relative to \c Compare.
163 This method deletes the item with minimum priority relative to \c
164 Compare from the heap.
165 \pre The heap must be non-empty.
169 ///Deletes \c item from the heap.
172 This method deletes \c item from the heap, if \c item was already
173 stored in the heap. It is quite inefficient in Fibonacci heaps.
175 void erase (const Item& item);
177 ///Decreases the priority of \c item to \c value.
180 This method decreases the priority of \c item to \c value.
181 \pre \c item must be stored in the heap with priority at least \c
182 value relative to \c Compare.
184 void decrease (Item item, PrioType const value);
186 ///Increases the priority of \c item to \c value.
189 This method sets the priority of \c item to \c value. Though
190 there is no precondition on the priority of \c item, this
191 method should be used only if it is indeed necessary to increase
192 (relative to \c Compare) the priority of \c item, because this
193 method is inefficient.
195 void increase (Item item, PrioType const value) {
201 ///Returns if \c item is in, has already been in, or has never been in the heap.
204 This method returns PRE_HEAP if \c item has never been in the
205 heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
206 otherwise. In the latter case it is possible that \c item will
207 get back to the heap again.
209 state_enum state(const Item &item) const {
212 if ( container[i].in ) i=0;
215 return state_enum(i);
221 void makeroot(int c);
222 void cut(int a, int b);
224 void fuse(int a, int b);
229 friend class FibHeap;
241 store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
247 // **********************************************************************
249 // **********************************************************************
251 template <typename Item, typename Prio, typename ItemIntMap,
253 void FibHeap<Item, Prio, ItemIntMap, Compare>::set
254 (Item const item, PrioType const value)
257 if ( i >= 0 && container[i].in ) {
258 if ( comp(value, container[i].prio) ) decrease(item, value);
259 if ( comp(container[i].prio, value) ) increase(item, value);
260 } else push(item, value);
263 template <typename Item, typename Prio, typename ItemIntMap,
265 void FibHeap<Item, Prio, ItemIntMap, Compare>::push
266 (Item const item, PrioType const value) {
269 int s=container.size();
270 iimap.set( item, s );
273 container.push_back(st);
276 container[i].parent=container[i].child=-1;
277 container[i].degree=0;
278 container[i].in=true;
279 container[i].marked=false;
283 container[container[minimum].right_neighbor].left_neighbor=i;
284 container[i].right_neighbor=container[minimum].right_neighbor;
285 container[minimum].right_neighbor=i;
286 container[i].left_neighbor=minimum;
287 if ( comp( value, container[minimum].prio) ) minimum=i;
289 container[i].right_neighbor=container[i].left_neighbor=i;
292 container[i].prio=value;
296 template <typename Item, typename Prio, typename ItemIntMap,
298 void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
299 /*The first case is that there are only one root.*/
300 if ( container[minimum].left_neighbor==minimum ) {
301 container[minimum].in=false;
302 if ( container[minimum].degree!=0 ) {
303 makeroot(container[minimum].child);
304 minimum=container[minimum].child;
308 int right=container[minimum].right_neighbor;
310 container[minimum].in=false;
311 if ( container[minimum].degree > 0 ) {
312 int left=container[minimum].left_neighbor;
313 int child=container[minimum].child;
314 int last_child=container[child].left_neighbor;
318 container[left].right_neighbor=child;
319 container[child].left_neighbor=left;
320 container[right].left_neighbor=last_child;
321 container[last_child].right_neighbor=right;
325 } // the case where there are more roots
330 template <typename Item, typename Prio, typename ItemIntMap,
332 void FibHeap<Item, Prio, ItemIntMap, Compare>::erase
336 if ( i >= 0 && container[i].in ) {
337 if ( container[i].parent!=-1 ) {
338 int p=container[i].parent;
342 minimum=i; //As if its prio would be -infinity
347 template <typename Item, typename Prio, typename ItemIntMap,
349 void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease
350 (Item item, PrioType const value) {
352 container[i].prio=value;
353 int p=container[i].parent;
355 if ( p!=-1 && comp(value, container[p].prio) ) {
359 if ( comp(value, container[minimum].prio) ) minimum=i;
363 template <typename Item, typename Prio, typename ItemIntMap,
365 void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {
367 int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
369 std::vector<int> A(maxdeg,-1);
372 *Recall that now minimum does not point to the minimum prio element.
373 *We set minimum to this during balance().
375 int anchor=container[minimum].left_neighbor;
381 if ( anchor==active ) end=true;
382 int d=container[active].degree;
383 next=container[active].right_neighbor;
386 if( comp(container[active].prio, container[A[d]].prio) ) {
399 while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
403 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
404 s=container[s].right_neighbor;
408 template <typename Item, typename Prio, typename ItemIntMap,
410 void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot
414 container[s].parent=-1;
415 s=container[s].right_neighbor;
420 template <typename Item, typename Prio, typename ItemIntMap,
422 void FibHeap<Item, Prio, ItemIntMap, Compare>::cut
425 *Replacing a from the children of b.
427 --container[b].degree;
429 if ( container[b].degree !=0 ) {
430 int child=container[b].child;
432 container[b].child=container[child].right_neighbor;
437 /*Lacing a to the roots.*/
438 int right=container[minimum].right_neighbor;
439 container[minimum].right_neighbor=a;
440 container[a].left_neighbor=minimum;
441 container[a].right_neighbor=right;
442 container[right].left_neighbor=a;
444 container[a].parent=-1;
445 container[a].marked=false;
449 template <typename Item, typename Prio, typename ItemIntMap,
451 void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade
454 if ( container[a].parent!=-1 ) {
455 int p=container[a].parent;
457 if ( container[a].marked==false ) container[a].marked=true;
466 template <typename Item, typename Prio, typename ItemIntMap,
468 void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse
472 /*Lacing b under a.*/
473 container[b].parent=a;
475 if (container[a].degree==0) {
476 container[b].left_neighbor=b;
477 container[b].right_neighbor=b;
478 container[a].child=b;
480 int child=container[a].child;
481 int last_child=container[child].left_neighbor;
482 container[child].left_neighbor=b;
483 container[b].right_neighbor=child;
484 container[last_child].right_neighbor=b;
485 container[b].left_neighbor=last_child;
488 ++container[a].degree;
490 container[b].marked=false;
495 *It is invoked only if a has siblings.
497 template <typename Item, typename Prio, typename ItemIntMap,
499 void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace
501 int leftn=container[a].left_neighbor;
502 int rightn=container[a].right_neighbor;
503 container[leftn].right_neighbor=rightn;
504 container[rightn].left_neighbor=leftn;
511 #endif //LEMON_FIB_HEAP_H