NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
2 * lemon/fib_heap.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, 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 /// \brief The constructor
93 /// \c _iimap should be given to the constructor, since it is
94 /// used internally to handle the cross references.
95 explicit FibHeap(ItemIntMap &_iimap)
96 : minimum(0), iimap(_iimap), num_items() {}
98 /// \brief The constructor
100 /// \c _iimap should be given to the constructor, since it is used
101 /// internally to handle the cross references. \c _comp is an
102 /// object for ordering of the priorities.
103 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
104 iimap(_iimap), comp(_comp), num_items() {}
106 /// \brief The number of items stored in the heap.
108 /// Returns the number of items stored in the heap.
109 int size() const { return num_items; }
111 /// \brief Checks if the heap stores no items.
113 /// Returns \c true if and only if the heap stores no items.
114 bool empty() const { return num_items==0; }
116 /// \brief Make empty this heap.
118 /// Make empty this heap.
120 if (num_items != 0) {
121 for (int i = 0; i < (int)container.size(); ++i) {
122 iimap[container[i].name] = -2;
125 container.clear(); minimum = 0; num_items = 0;
128 /// \brief \c item gets to the heap with priority \c value independently
129 /// if \c item was already there.
131 /// This method calls \ref push(\c item, \c value) if \c item is not
132 /// stored in the heap and it calls \ref decrease(\c item, \c value) or
133 /// \ref increase(\c item, \c value) otherwise.
134 void set (Item const item, PrioType const value);
136 /// \brief Adds \c item to the heap with priority \c value.
138 /// Adds \c item to the heap with priority \c value.
139 /// \pre \c item must not be stored in the heap.
140 void push (Item const item, PrioType const value);
142 /// \brief Returns the item with minimum priority relative to \c Compare.
144 /// This method returns the item with minimum priority relative to \c
146 /// \pre The heap must be nonempty.
147 Item top() const { return container[minimum].name; }
149 /// \brief Returns the minimum priority relative to \c Compare.
151 /// It returns the minimum priority relative to \c Compare.
152 /// \pre The heap must be nonempty.
153 PrioType prio() const { return container[minimum].prio; }
155 /// \brief Returns the priority of \c item.
157 /// This function returns the priority of \c item.
158 /// \pre \c item must be in the heap.
159 PrioType& operator[](const Item& item) {
160 return container[iimap[item]].prio;
163 /// \brief Returns the priority of \c item.
165 /// It returns the priority of \c item.
166 /// \pre \c item must be in the heap.
167 const PrioType& operator[](const Item& item) const {
168 return container[iimap[item]].prio;
172 /// \brief Deletes the item with minimum priority relative to \c Compare.
174 /// This method deletes the item with minimum priority relative to \c
175 /// Compare from the heap.
176 /// \pre The heap must be non-empty.
179 /// \brief Deletes \c item from the heap.
181 /// This method deletes \c item from the heap, if \c item was already
182 /// stored in the heap. It is quite inefficient in Fibonacci heaps.
183 void erase (const Item& item);
185 /// \brief Decreases the priority of \c item to \c value.
187 /// This method decreases the priority of \c item to \c value.
188 /// \pre \c item must be stored in the heap with priority at least \c
189 /// value relative to \c Compare.
190 void decrease (Item item, PrioType const value);
192 /// \brief 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.
199 void increase (Item item, PrioType const value) {
205 /// \brief Returns if \c item is in, has already been in, or has never
206 /// been in the heap.
208 /// This method returns PRE_HEAP if \c item has never been in the
209 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
210 /// otherwise. In the latter case it is possible that \c item will
211 /// get back to the heap again.
212 state_enum state(const Item &item) const {
215 if ( container[i].in ) i=0;
218 return state_enum(i);
224 void makeroot(int c);
225 void cut(int a, int b);
227 void fuse(int a, int b);
232 friend class FibHeap;
244 store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
250 // **********************************************************************
252 // **********************************************************************
254 template <typename Item, typename Prio, typename ItemIntMap,
256 void FibHeap<Item, Prio, ItemIntMap, Compare>::set
257 (Item const item, PrioType const value)
260 if ( i >= 0 && container[i].in ) {
261 if ( comp(value, container[i].prio) ) decrease(item, value);
262 if ( comp(container[i].prio, value) ) increase(item, value);
263 } else push(item, value);
266 template <typename Item, typename Prio, typename ItemIntMap,
268 void FibHeap<Item, Prio, ItemIntMap, Compare>::push
269 (Item const item, PrioType const value) {
272 int s=container.size();
273 iimap.set( item, s );
276 container.push_back(st);
279 container[i].parent=container[i].child=-1;
280 container[i].degree=0;
281 container[i].in=true;
282 container[i].marked=false;
286 container[container[minimum].right_neighbor].left_neighbor=i;
287 container[i].right_neighbor=container[minimum].right_neighbor;
288 container[minimum].right_neighbor=i;
289 container[i].left_neighbor=minimum;
290 if ( comp( value, container[minimum].prio) ) minimum=i;
292 container[i].right_neighbor=container[i].left_neighbor=i;
295 container[i].prio=value;
299 template <typename Item, typename Prio, typename ItemIntMap,
301 void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
302 /*The first case is that there are only one root.*/
303 if ( container[minimum].left_neighbor==minimum ) {
304 container[minimum].in=false;
305 if ( container[minimum].degree!=0 ) {
306 makeroot(container[minimum].child);
307 minimum=container[minimum].child;
311 int right=container[minimum].right_neighbor;
313 container[minimum].in=false;
314 if ( container[minimum].degree > 0 ) {
315 int left=container[minimum].left_neighbor;
316 int child=container[minimum].child;
317 int last_child=container[child].left_neighbor;
321 container[left].right_neighbor=child;
322 container[child].left_neighbor=left;
323 container[right].left_neighbor=last_child;
324 container[last_child].right_neighbor=right;
328 } // the case where there are more roots
333 template <typename Item, typename Prio, typename ItemIntMap,
335 void FibHeap<Item, Prio, ItemIntMap, Compare>::erase
339 if ( i >= 0 && container[i].in ) {
340 if ( container[i].parent!=-1 ) {
341 int p=container[i].parent;
345 minimum=i; //As if its prio would be -infinity
350 template <typename Item, typename Prio, typename ItemIntMap,
352 void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease
353 (Item item, PrioType const value) {
355 container[i].prio=value;
356 int p=container[i].parent;
358 if ( p!=-1 && comp(value, container[p].prio) ) {
362 if ( comp(value, container[minimum].prio) ) minimum=i;
366 template <typename Item, typename Prio, typename ItemIntMap,
368 void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {
370 int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
372 std::vector<int> A(maxdeg,-1);
375 *Recall that now minimum does not point to the minimum prio element.
376 *We set minimum to this during balance().
378 int anchor=container[minimum].left_neighbor;
384 if ( anchor==active ) end=true;
385 int d=container[active].degree;
386 next=container[active].right_neighbor;
389 if( comp(container[active].prio, container[A[d]].prio) ) {
402 while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
406 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
407 s=container[s].right_neighbor;
411 template <typename Item, typename Prio, typename ItemIntMap,
413 void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot
417 container[s].parent=-1;
418 s=container[s].right_neighbor;
423 template <typename Item, typename Prio, typename ItemIntMap,
425 void FibHeap<Item, Prio, ItemIntMap, Compare>::cut
428 *Replacing a from the children of b.
430 --container[b].degree;
432 if ( container[b].degree !=0 ) {
433 int child=container[b].child;
435 container[b].child=container[child].right_neighbor;
440 /*Lacing a to the roots.*/
441 int right=container[minimum].right_neighbor;
442 container[minimum].right_neighbor=a;
443 container[a].left_neighbor=minimum;
444 container[a].right_neighbor=right;
445 container[right].left_neighbor=a;
447 container[a].parent=-1;
448 container[a].marked=false;
452 template <typename Item, typename Prio, typename ItemIntMap,
454 void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade
457 if ( container[a].parent!=-1 ) {
458 int p=container[a].parent;
460 if ( container[a].marked==false ) container[a].marked=true;
469 template <typename Item, typename Prio, typename ItemIntMap,
471 void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse
475 /*Lacing b under a.*/
476 container[b].parent=a;
478 if (container[a].degree==0) {
479 container[b].left_neighbor=b;
480 container[b].right_neighbor=b;
481 container[a].child=b;
483 int child=container[a].child;
484 int last_child=container[child].left_neighbor;
485 container[child].left_neighbor=b;
486 container[b].right_neighbor=child;
487 container[last_child].right_neighbor=b;
488 container[b].left_neighbor=last_child;
491 ++container[a].degree;
493 container[b].marked=false;
498 *It is invoked only if a has siblings.
500 template <typename Item, typename Prio, typename ItemIntMap,
502 void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace
504 int leftn=container[a].left_neighbor;
505 int rightn=container[a].right_neighbor;
506 container[leftn].right_neighbor=rightn;
507 container[rightn].left_neighbor=leftn;
514 #endif //LEMON_FIB_HEAP_H