86 PRE_HEAP = -1, |
86 PRE_HEAP = -1, |
87 ///The node was in the heap but it got out of it |
87 ///The node was in the heap but it got out of it |
88 POST_HEAP = -2 |
88 POST_HEAP = -2 |
89 }; |
89 }; |
90 |
90 |
91 ///The constructor |
91 /// \brief The constructor |
92 |
92 /// |
93 /** |
93 /// \c _iimap should be given to the constructor, since it is |
94 \c _iimap should be given to the constructor, since it is |
94 /// used internally to handle the cross references. |
95 used internally to handle the cross references. |
|
96 */ |
|
97 explicit FibHeap(ItemIntMap &_iimap) |
95 explicit FibHeap(ItemIntMap &_iimap) |
98 : minimum(0), iimap(_iimap), num_items() {} |
96 : minimum(0), iimap(_iimap), num_items() {} |
99 |
97 |
100 ///The constructor |
98 /// \brief The constructor |
101 |
99 /// |
102 /** |
100 /// \c _iimap should be given to the constructor, since it is used |
103 \c _iimap should be given to the constructor, since it is used |
101 /// internally to handle the cross references. \c _comp is an |
104 internally to handle the cross references. \c _comp is an |
102 /// object for ordering of the priorities. |
105 object for ordering of the priorities. |
|
106 */ |
|
107 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), |
103 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), |
108 iimap(_iimap), comp(_comp), num_items() {} |
104 iimap(_iimap), comp(_comp), num_items() {} |
109 |
105 |
110 ///The number of items stored in the heap. |
106 /// \brief The number of items stored in the heap. |
111 |
107 /// |
112 /** |
108 /// Returns the number of items stored in the heap. |
113 Returns the number of items stored in the heap. |
|
114 */ |
|
115 int size() const { return num_items; } |
109 int size() const { return num_items; } |
116 |
110 |
117 ///Checks if the heap stores no items. |
111 /// \brief Checks if the heap stores no items. |
118 |
112 /// |
119 /** |
113 /// Returns \c true if and only if the heap stores no items. |
120 Returns \c true if and only if the heap stores no items. |
|
121 */ |
|
122 bool empty() const { return num_items==0; } |
114 bool empty() const { return num_items==0; } |
123 |
115 |
124 ///\c item gets to the heap with priority \c value independently if \c item was already there. |
116 /// \brief Make empty this heap. |
125 |
117 /// |
126 /** |
118 /// Make empty this heap. |
127 This method calls \ref push(\c item, \c value) if \c item is not |
119 void clear() { |
128 stored in the heap and it calls \ref decrease(\c item, \c value) or |
120 for (int i = 0; i < (int)container.size(); ++i) { |
129 \ref increase(\c item, \c value) otherwise. |
121 iimap[container[i].name] = -2; |
130 */ |
122 } |
|
123 container.clear(); minimum = 0; num_items = 0; |
|
124 } |
|
125 |
|
126 /// \brief \c item gets to the heap with priority \c value independently |
|
127 /// if \c item was already there. |
|
128 /// |
|
129 /// This method calls \ref push(\c item, \c value) if \c item is not |
|
130 /// stored in the heap and it calls \ref decrease(\c item, \c value) or |
|
131 /// \ref increase(\c item, \c value) otherwise. |
131 void set (Item const item, PrioType const value); |
132 void set (Item const item, PrioType const value); |
132 |
133 |
133 ///Adds \c item to the heap with priority \c value. |
134 /// \brief Adds \c item to the heap with priority \c value. |
134 |
135 /// |
135 /** |
136 /// Adds \c item to the heap with priority \c value. |
136 Adds \c item to the heap with priority \c value. |
137 /// \pre \c item must not be stored in the heap. |
137 \pre \c item must not be stored in the heap. |
|
138 */ |
|
139 void push (Item const item, PrioType const value); |
138 void push (Item const item, PrioType const value); |
140 |
139 |
141 ///Returns the item with minimum priority relative to \c Compare. |
140 /// \brief Returns the item with minimum priority relative to \c Compare. |
142 |
141 /// |
143 /** |
142 /// This method returns the item with minimum priority relative to \c |
144 This method returns the item with minimum priority relative to \c |
143 /// Compare. |
145 Compare. |
144 /// \pre The heap must be nonempty. |
146 \pre The heap must be nonempty. |
|
147 */ |
|
148 Item top() const { return container[minimum].name; } |
145 Item top() const { return container[minimum].name; } |
149 |
146 |
150 ///Returns the minimum priority relative to \c Compare. |
147 /// \brief Returns the minimum priority relative to \c Compare. |
151 |
148 /// |
152 /** |
149 /// It returns the minimum priority relative to \c Compare. |
153 It returns the minimum priority relative to \c Compare. |
150 /// \pre The heap must be nonempty. |
154 \pre The heap must be nonempty. |
|
155 */ |
|
156 PrioType prio() const { return container[minimum].prio; } |
151 PrioType prio() const { return container[minimum].prio; } |
157 |
152 |
158 ///Returns the priority of \c item. |
153 /// \brief Returns the priority of \c item. |
159 |
154 /// |
160 /** |
155 /// This function returns the priority of \c item. |
161 This function returns the priority of \c item. |
156 /// \pre \c item must be in the heap. |
162 \pre \c item must be in the heap. |
|
163 */ |
|
164 PrioType& operator[](const Item& item) { |
157 PrioType& operator[](const Item& item) { |
165 return container[iimap[item]].prio; |
158 return container[iimap[item]].prio; |
166 } |
159 } |
167 |
160 |
168 ///Returns the priority of \c item. |
161 /// \brief Returns the priority of \c item. |
169 |
162 /// |
170 /** |
163 /// It returns the priority of \c item. |
171 It returns the priority of \c item. |
164 /// \pre \c item must be in the heap. |
172 \pre \c item must be in the heap. |
|
173 */ |
|
174 const PrioType& operator[](const Item& item) const { |
165 const PrioType& operator[](const Item& item) const { |
175 return container[iimap[item]].prio; |
166 return container[iimap[item]].prio; |
176 } |
167 } |
177 |
168 |
178 |
169 |
179 ///Deletes the item with minimum priority relative to \c Compare. |
170 /// \brief Deletes the item with minimum priority relative to \c Compare. |
180 |
171 /// |
181 /** |
172 /// This method deletes the item with minimum priority relative to \c |
182 This method deletes the item with minimum priority relative to \c |
173 /// Compare from the heap. |
183 Compare from the heap. |
174 /// \pre The heap must be non-empty. |
184 \pre The heap must be non-empty. |
|
185 */ |
|
186 void pop(); |
175 void pop(); |
187 |
176 |
188 ///Deletes \c item from the heap. |
177 /// \brief Deletes \c item from the heap. |
189 |
178 /// |
190 /** |
179 /// This method deletes \c item from the heap, if \c item was already |
191 This method deletes \c item from the heap, if \c item was already |
180 /// stored in the heap. It is quite inefficient in Fibonacci heaps. |
192 stored in the heap. It is quite inefficient in Fibonacci heaps. |
|
193 */ |
|
194 void erase (const Item& item); |
181 void erase (const Item& item); |
195 |
182 |
196 ///Decreases the priority of \c item to \c value. |
183 /// \brief Decreases the priority of \c item to \c value. |
197 |
184 /// |
198 /** |
185 /// This method decreases the priority of \c item to \c value. |
199 This method decreases the priority of \c item to \c value. |
186 /// \pre \c item must be stored in the heap with priority at least \c |
200 \pre \c item must be stored in the heap with priority at least \c |
187 /// value relative to \c Compare. |
201 value relative to \c Compare. |
|
202 */ |
|
203 void decrease (Item item, PrioType const value); |
188 void decrease (Item item, PrioType const value); |
204 |
189 |
205 ///Increases the priority of \c item to \c value. |
190 /// \brief Increases the priority of \c item to \c value. |
206 |
191 /// |
207 /** |
192 /// This method sets the priority of \c item to \c value. Though |
208 This method sets the priority of \c item to \c value. Though |
193 /// there is no precondition on the priority of \c item, this |
209 there is no precondition on the priority of \c item, this |
194 /// method should be used only if it is indeed necessary to increase |
210 method should be used only if it is indeed necessary to increase |
195 /// (relative to \c Compare) the priority of \c item, because this |
211 (relative to \c Compare) the priority of \c item, because this |
196 /// method is inefficient. |
212 method is inefficient. |
|
213 */ |
|
214 void increase (Item item, PrioType const value) { |
197 void increase (Item item, PrioType const value) { |
215 erase(item); |
198 erase(item); |
216 push(item, value); |
199 push(item, value); |
217 } |
200 } |
218 |
201 |
219 |
202 |
220 ///Returns if \c item is in, has already been in, or has never been in the heap. |
203 /// \brief Returns if \c item is in, has already been in, or has never |
221 |
204 /// been in the heap. |
222 /** |
205 /// |
223 This method returns PRE_HEAP if \c item has never been in the |
206 /// This method returns PRE_HEAP if \c item has never been in the |
224 heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
207 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
225 otherwise. In the latter case it is possible that \c item will |
208 /// otherwise. In the latter case it is possible that \c item will |
226 get back to the heap again. |
209 /// get back to the heap again. |
227 */ |
|
228 state_enum state(const Item &item) const { |
210 state_enum state(const Item &item) const { |
229 int i=iimap[item]; |
211 int i=iimap[item]; |
230 if( i>=0 ) { |
212 if( i>=0 ) { |
231 if ( container[i].in ) i=0; |
213 if ( container[i].in ) i=0; |
232 else i=-2; |
214 else i=-2; |