14 namespace hugo { |
14 namespace hugo { |
15 |
15 |
16 /// \addtogroup auxdat |
16 /// \addtogroup auxdat |
17 /// @{ |
17 /// @{ |
18 |
18 |
19 /// An implementation of the Fibonacci Heap. |
19 /// Fibonacci Heap. |
20 |
20 |
21 /** |
21 ///This class implements the \e Fibonacci \e heap data structure. A \e heap |
22 This class implements the \e Fibonacci \e heap data structure. A \e heap |
22 ///is a data structure for storing items with specified values called \e |
23 is a data structure for storing items with specified values called \e |
23 ///priorities in such a way that finding the item with minimum priority is |
24 priorities, such that finding the item with minimum priority with respect |
24 ///efficient. \ref Compare specifies the ordering of the priorities. In a heap |
25 to \e Compare is efficient. In a heap one can change the priority of an |
25 ///one can change the priority of an item, add or erase an item, etc. |
26 item, add or erase an item, etc. |
26 /// |
27 |
27 ///The methods \ref increase and \ref erase are not efficient in a Fibonacci |
28 The methods \ref increase and \ref erase are not efficient in a Fibonacci |
28 ///heap. In case of many calls to these operations, it is better to use a |
29 heap. In case of many calls to these operations, it is better to use a |
29 ///\e binary \e heap. |
30 \e binary \e heap. |
30 /// |
31 |
31 ///\param Item Type of the items to be stored. |
32 \param Item The type of the items to be stored. |
32 ///\param Prio Type of the priority of the items. |
33 \param Prio The type of the priority of the items. |
33 ///\param ItemIntMap A read and writable Item int map, for the usage of |
34 \param ItemIntMap A read and writable Item int map, for the usage of |
34 ///the heap. |
35 the heap. |
35 ///\param Compare A class for the ordering of the priorities. The |
36 \param Compare A class for the comparison of the priorities. The |
36 ///default is \c std::less<Prio>. |
37 default is \c std::less<Prio>. |
37 /// |
38 |
38 ///\author Jacint Szabo |
39 */ |
39 |
40 |
|
41 #ifdef DOXYGEN |
40 #ifdef DOXYGEN |
42 template <typename Item, |
41 template <typename Item, |
43 typename Prio, |
42 typename Prio, |
44 typename ItemIntMap, |
43 typename ItemIntMap, |
45 typename Compare> |
44 typename Compare> |
81 int size() const { return num_items; } |
80 int size() const { return num_items; } |
82 |
81 |
83 ///Checks if the heap stores no items. |
82 ///Checks if the heap stores no items. |
84 |
83 |
85 /** |
84 /** |
86 Returns \c true iff the heap stores no items. |
85 Returns \c true if and only if the heap stores no items. |
87 */ |
86 */ |
88 bool empty() const { return num_items==0; } |
87 bool empty() const { return num_items==0; } |
89 |
88 |
90 ///\c item gets to the heap with priority \c value independently if \c item was already there. |
89 ///\c item gets to the heap with priority \c value independently if \c item was already there. |
91 |
90 |
102 Adds \c item to the heap with priority \c value. |
101 Adds \c item to the heap with priority \c value. |
103 \pre \c item must not be stored in the heap. |
102 \pre \c item must not be stored in the heap. |
104 */ |
103 */ |
105 void push (Item const item, PrioType const value); |
104 void push (Item const item, PrioType const value); |
106 |
105 |
107 |
106 ///Returns the item with minimum priority relative to \ref Compare. |
108 ///Returns the item having the minimum priority w.r.t. Compare. |
107 |
109 |
108 /** |
110 /** |
109 This method returns the item with minimum priority relative to \ref |
111 This method returns the item having the minimum priority w.r.t. Compare. |
110 Compare. |
|
111 \pre The heap must be nonempty. |
|
112 */ |
|
113 Item top() const { return container[minimum].name; } |
|
114 |
|
115 ///Returns the minimum priority relative to \ref Compare. |
|
116 |
|
117 /** |
|
118 It returns the minimum priority relative to \ref Compare. |
112 \pre The heap must be nonempty. |
119 \pre The heap must be nonempty. |
113 */ |
120 */ |
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; } |
121 PrioType prio() const { return container[minimum].prio; } |
124 |
122 |
125 |
|
126 ///Returns the priority of \c item. |
123 ///Returns the priority of \c item. |
127 |
124 |
|
125 /** |
|
126 This function returns the priority of \c item. |
|
127 \pre \c item must be in the heap. |
|
128 */ |
|
129 PrioType& operator[](const Item& item) { |
|
130 return container[iimap[item]].prio; |
|
131 } |
|
132 |
|
133 ///Returns the priority of \c item. |
|
134 |
128 /** |
135 /** |
129 It returns the priority of \c item. |
136 It returns the priority of \c item. |
130 \pre \c item must be in the heap. |
137 \pre \c item must be in the heap. |
131 */ |
138 */ |
132 PrioType& operator[](const Item& item) { |
|
133 return container[iimap[item]].prio; |
|
134 } |
|
135 |
|
136 ///Returns the priority of \c item. |
|
137 |
|
138 /** |
|
139 It returns the priority of \c item. |
|
140 \pre \c item must be in the heap. |
|
141 */ |
|
142 const PrioType& operator[](const Item& item) const { |
139 const PrioType& operator[](const Item& item) const { |
143 return container[iimap[item]].prio; |
140 return container[iimap[item]].prio; |
144 } |
141 } |
145 |
142 |
146 |
143 |
147 ///Deletes the item with minimum priority w.r.t. Compare. |
144 ///Deletes the item with minimum priority relative to \ref Compare. |
148 |
145 |
149 /** |
146 /** |
150 This method deletes the item with minimum priority w.r.t. |
147 This method deletes the item with minimum priority relative to \ref |
151 Compare from the heap. |
148 Compare from the heap. |
152 \pre The heap must be non-empty. |
149 \pre The heap must be non-empty. |
153 */ |
150 */ |
154 void pop(); |
151 void pop(); |
155 |
152 |
156 ///Deletes \c item from the heap. |
153 ///Deletes \c item from the heap. |
157 |
154 |
164 ///Decreases the priority of \c item to \c value. |
161 ///Decreases the priority of \c item to \c value. |
165 |
162 |
166 /** |
163 /** |
167 This method decreases the priority of \c item to \c value. |
164 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 |
165 \pre \c item must be stored in the heap with priority at least \c |
169 value w.r.t. Compare. |
166 value relative to \ref Compare. |
170 */ |
167 */ |
171 void decrease (Item item, PrioType const value); |
168 void decrease (Item item, PrioType const value); |
172 |
|
173 |
169 |
174 ///Increases the priority of \c item to \c value. |
170 ///Increases the priority of \c item to \c value. |
175 |
171 |
176 /** |
172 /** |
177 This method sets the priority of \c item to \c value. Though |
173 This method sets the priority of \c item to \c value. Though |
178 there is no precondition on the priority of \c item, this |
174 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 |
175 method should be used only if it is indeed necessary to increase |
180 (w.r.t. Compare) the priority of \c item, because this |
176 (relative to \ref Compare) the priority of \c item, because this |
181 method is inefficient. |
177 method is inefficient. |
182 */ |
178 */ |
183 void increase (Item item, PrioType const value) { |
179 void increase (Item item, PrioType const value) { |
184 erase(item); |
180 erase(item); |
185 push(item, value); |
181 push(item, value); |
186 } |
182 } |
187 |
183 |
188 |
184 |
189 ///Tells if \c item is in, was already in, or has never been in the heap. |
185 ///Returns if \c item is in, has already been in, or has never been in the heap. |
190 |
186 |
191 /** |
187 /** |
192 This method returns PRE_HEAP if \c item has never been in the |
188 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 |
189 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 |
190 otherwise. In the latter case it is possible that \c item will |