1 // -*- C++ -*- |
1 // -*- C++ -*- |
2 /* |
2 |
3 *template <typename Item, |
3 #ifndef HUGO_FIB_HEAP_H |
4 * typename Prio, |
4 #define HUGO_FIB_HEAP_H |
5 * typename ItemIntMap, |
|
6 * typename Compare = std::less<Prio> > |
|
7 * |
|
8 *constructors: |
|
9 * |
|
10 *FibHeap(ItemIntMap), FibHeap(ItemIntMap, Compare) |
|
11 * |
|
12 *Member functions: |
|
13 * |
|
14 *int size() : returns the number of elements in the heap |
|
15 * |
|
16 *bool empty() : true iff size()=0 |
|
17 * |
|
18 *void set(Item, Prio) : calls push(Item, Prio) if Item is not |
|
19 * in the heap, and calls decrease/increase(Item, Prio) otherwise |
|
20 * |
|
21 *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item |
|
22 * mustn't be in the heap. |
|
23 * |
|
24 *Item top() : returns the Item with least Prio. |
|
25 * Must be called only if heap is nonempty. |
|
26 * |
|
27 *Prio prio() : returns the least Prio |
|
28 * Must be called only if heap is nonempty. |
|
29 * |
|
30 *Prio get(Item) : returns Prio of Item |
|
31 * Must be called only if Item is in heap. |
|
32 * |
|
33 *void pop() : deletes the Item with least Prio |
|
34 * |
|
35 *void erase(Item) : deletes Item from the heap if it was already there |
|
36 * |
|
37 *void decrease(Item, P) : decreases prio of Item to P. |
|
38 * Item must be in the heap with prio at least P. |
|
39 * |
|
40 *void increase(Item, P) : sets prio of Item to P. |
|
41 * |
|
42 *state_enum state(Item) : returns PRE_HEAP if Item has not been in the |
|
43 * heap until now, IN_HEAP if it is in the heap at the moment, and |
|
44 * POST_HEAP otherwise. In the latter case it is possible that Item |
|
45 * will get back to the heap again. |
|
46 * |
|
47 *In Fibonacci heaps, increase and erase are not efficient, in case of |
|
48 *many calls to these operations, it is better to use bin_heap. |
|
49 */ |
|
50 |
|
51 #ifndef FIB_HEAP_H |
|
52 #define FIB_HEAP_H |
|
53 |
5 |
54 ///\file |
6 ///\file |
55 ///\brief Fibonacci Heap implementation. |
7 ///\brief Fibonacci Heap implementation. |
56 |
8 |
57 #include <vector> |
9 #include <vector> |
58 #include <functional> |
10 #include <functional> |
59 #include <math.h> |
11 #include <math.h> |
60 |
12 |
61 namespace hugo { |
13 namespace hugo { |
62 |
14 |
63 /// A Fibonacci Heap implementation. |
15 /// An implementation of the Fibonacci Heap. |
64 template <typename Item, typename Prio, typename ItemIntMap, |
16 |
|
17 /** |
|
18 This class implements the \e Fibonacci \e heap data structure. A \e |
|
19 heap is a data structure for storing items with specified priorities, |
|
20 such that finding the item with minimum priority is efficient. In a |
|
21 heap one can change the priority of an item, and to add or erase an |
|
22 item. |
|
23 |
|
24 The methods \ref increase and \ref erase are not efficient, in |
|
25 case of many calls to these operations, it is better to use |
|
26 a binary heap. |
|
27 |
|
28 /param Item The type of the items to be stored. |
|
29 /param Prio The type of the priority of the items. |
|
30 /param ItemIntMap A read and writable Item int map, for the usage of |
|
31 the heap. |
|
32 /param Compare A class for the comparison of the priorities. The |
|
33 default is \c std::less<Prio>. |
|
34 |
|
35 */ |
|
36 |
|
37 #ifdef DOXYGEN |
|
38 template <typename Item, |
|
39 typename Prio, |
|
40 typename ItemIntMap, |
|
41 typename Compare> |
|
42 #else |
|
43 template <typename Item, |
|
44 typename Prio, |
|
45 typename ItemIntMap, |
65 typename Compare = std::less<Prio> > |
46 typename Compare = std::less<Prio> > |
|
47 #endif |
66 class FibHeap { |
48 class FibHeap { |
67 |
49 public: |
68 typedef Prio PrioType; |
50 typedef Prio PrioType; |
69 |
51 |
|
52 private: |
70 class store; |
53 class store; |
71 |
54 |
72 std::vector<store> container; |
55 std::vector<store> container; |
73 int minimum; |
56 int minimum; |
74 ItemIntMap &iimap; |
57 ItemIntMap &iimap; |
75 Compare comp; |
58 Compare comp; |
76 int num_items; |
59 int num_items; |
77 |
60 |
78 ///\todo It is use nowhere |
61 ///\todo It is use nowhere |
79 ///\todo It doesn't conform to the naming conventions. |
62 ///\todo It doesn't conform to the naming conventions. |
80 public: |
63 public: |
81 enum state_enum { |
64 enum state_enum { |
82 IN_HEAP = 0, |
65 IN_HEAP = 0, |
84 POST_HEAP = -2 |
67 POST_HEAP = -2 |
85 }; |
68 }; |
86 |
69 |
87 public : |
70 public : |
88 |
71 |
89 FibHeap(ItemIntMap &_iimap) : minimum(), iimap(_iimap), num_items() {} |
72 FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {} |
90 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(), |
73 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), |
91 iimap(_iimap), comp(_comp), num_items() {} |
74 iimap(_iimap), comp(_comp), num_items() {} |
92 |
75 |
93 |
76 ///The number of items stored in the heap. |
94 int size() const { |
77 |
95 return num_items; |
78 /** |
96 } |
79 Returns the number of items stored in the heap. |
97 |
80 */ |
98 |
81 int size() const { return num_items; } |
|
82 |
|
83 ///Checks if the heap stores no items. |
|
84 |
|
85 /** |
|
86 Returns true iff the heap stores no items. |
|
87 */ |
99 bool empty() const { return num_items==0; } |
88 bool empty() const { return num_items==0; } |
100 |
89 |
|
90 ///Item \c item gets to the heap with priority \c value independently if \c item was already there. |
|
91 |
|
92 /** |
|
93 This method calls \ref push(item, value) if \c item is not |
|
94 stored in the heap, and it calls \ref decrease(it, \c value) or |
|
95 \ref increase(it, \c value) otherwise. |
|
96 */ |
|
97 void set (Item const item, PrioType const value); //vigyazat: az implementacioban it van |
|
98 |
|
99 ///Adds \c item to the heap with priority \c value. |
|
100 |
|
101 /** |
|
102 Adds \c item to the heap with priority \c value. |
|
103 \pre \c item must not be stored in the heap. |
|
104 */ |
|
105 void push (Item const it, PrioType const value); /*vigyazat: az implementacioban it van*/ |
|
106 |
|
107 |
|
108 ///Returns the item having the minimum priority w.r.t. Compare. |
|
109 |
|
110 /** |
|
111 This method returns the item having the minimum priority w.r.t. Compare. |
|
112 \pre The heap must be nonempty. |
|
113 */ |
|
114 Item top() const { return container[minimum].name; } |
|
115 |
|
116 |
|
117 ///Returns the minimum priority w.r.t. Compare. |
|
118 |
|
119 /** |
|
120 It returns the minimum priority w.r.t. Compare. |
|
121 \pre The heap must be nonempty. |
|
122 */ |
|
123 PrioType prio() const { return container[minimum].prio; } |
|
124 |
|
125 |
|
126 ///Returns the priority of \c item. |
|
127 |
|
128 /** |
|
129 It returns the priority of \c item. |
|
130 \pre \c item must be in the heap. |
|
131 */ |
|
132 PrioType& operator[](const Item& it) { return container[iimap[it]].prio; } |
|
133 |
|
134 ///Returns the priority of \c item. |
|
135 |
|
136 /** |
|
137 It returns the priority of \c item. |
|
138 \pre \c item must be in the heap. |
|
139 */ |
|
140 const PrioType& operator[](const Item& it) const { |
|
141 return container[iimap[it]].prio; |
|
142 } |
|
143 |
|
144 |
|
145 ///Deletes the item with minimum priority w.r.t. Compare. |
|
146 |
|
147 /** |
|
148 This method deletes the item with minimum priority w.r.t. |
|
149 Compare from the heap. |
|
150 \pre The heap must be non-empty. |
|
151 */ |
|
152 void pop(); |
|
153 |
|
154 ///Deletes \c item from the heap. |
|
155 |
|
156 /** |
|
157 This method deletes \c item from the heap, if \c item was already |
|
158 stored in the heap. It is quite inefficient in Fibonacci heaps. |
|
159 */ |
|
160 void erase (const Item& item); /*vigyazat: az implementacioban it van*/ |
|
161 |
|
162 ///Decreases the priority of \c item to \c value. |
|
163 |
|
164 /** |
|
165 This method decreases the priority of \c item to \c value. |
|
166 \pre \c item must be stored in the heap with priority at least \c |
|
167 value w.r.t. Compare. |
|
168 */ |
|
169 void decrease (Item item, PrioType const value); /*vigyazat: az implementacioban it van*/ |
|
170 |
|
171 |
|
172 ///Increases the priority of \c item to \c value. |
|
173 |
|
174 /** |
|
175 This method sets the priority of \c item to \c value. Though |
|
176 there is no precondition on the priority of \c item, this |
|
177 method should be used only if one wants to \e increase |
|
178 (w.r.t. Compare) the priority of \c item, because this |
|
179 method is inefficient. |
|
180 */ |
|
181 void increase (Item it, PrioType const value) { |
|
182 erase(it); |
|
183 push(it, value); |
|
184 } |
|
185 |
|
186 |
|
187 ///Tells if \c item is in, was in, or has not been in the heap. |
|
188 |
|
189 /** |
|
190 This method returns PRE_HEAP if \c item has never been in the |
|
191 heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
|
192 otherwise. In the latter case it is possible that \c item will |
|
193 get back to the heap again. |
|
194 */ |
|
195 state_enum state(const Item &it); /*vigyazat: az implementacioban it van*/ |
|
196 |
|
197 |
|
198 |
|
199 // ********************************************************************** |
|
200 // IMPLEMENTATIONS |
|
201 // ********************************************************************** |
|
202 |
101 |
203 |
102 void set (Item const it, PrioType const value) { |
204 void set (Item const it, PrioType const value) { |
103 int i=iimap[it]; |
205 int i=iimap[it]; |
104 if ( i >= 0 && container[i].in ) { |
206 if ( i >= 0 && container[i].in ) { |
105 if ( comp(value, container[i].prio) ) decrease(it, value); |
207 if ( comp(value, container[i].prio) ) decrease(it, value); |