122 } |
122 } |
123 |
123 |
124 private: |
124 private: |
125 static int parent(int i) { return (i-1)/2; } |
125 static int parent(int i) { return (i-1)/2; } |
126 |
126 |
127 static int second_child(int i) { return 2*i+2; } |
127 static int secondChild(int i) { return 2*i+2; } |
128 bool less(const Pair &p1, const Pair &p2) const { |
128 bool less(const Pair &p1, const Pair &p2) const { |
129 return _comp(p1.second, p2.second); |
129 return _comp(p1.second, p2.second); |
130 } |
130 } |
131 |
131 |
132 int bubble_up(int hole, Pair p) { |
132 int bubbleUp(int hole, Pair p) { |
133 int par = parent(hole); |
133 int par = parent(hole); |
134 while( hole>0 && less(p,_data[par]) ) { |
134 while( hole>0 && less(p,_data[par]) ) { |
135 move(_data[par],hole); |
135 move(_data[par],hole); |
136 hole = par; |
136 hole = par; |
137 par = parent(hole); |
137 par = parent(hole); |
138 } |
138 } |
139 move(p, hole); |
139 move(p, hole); |
140 return hole; |
140 return hole; |
141 } |
141 } |
142 |
142 |
143 int bubble_down(int hole, Pair p, int length) { |
143 int bubbleDown(int hole, Pair p, int length) { |
144 int child = second_child(hole); |
144 int child = secondChild(hole); |
145 while(child < length) { |
145 while(child < length) { |
146 if( less(_data[child-1], _data[child]) ) { |
146 if( less(_data[child-1], _data[child]) ) { |
147 --child; |
147 --child; |
148 } |
148 } |
149 if( !less(_data[child], p) ) |
149 if( !less(_data[child], p) ) |
150 goto ok; |
150 goto ok; |
151 move(_data[child], hole); |
151 move(_data[child], hole); |
152 hole = child; |
152 hole = child; |
153 child = second_child(hole); |
153 child = secondChild(hole); |
154 } |
154 } |
155 child--; |
155 child--; |
156 if( child<length && less(_data[child], p) ) { |
156 if( child<length && less(_data[child], p) ) { |
157 move(_data[child], hole); |
157 move(_data[child], hole); |
158 hole=child; |
158 hole=child; |
176 /// \param p The pair to insert. |
176 /// \param p The pair to insert. |
177 /// \pre \c p.first must not be stored in the heap. |
177 /// \pre \c p.first must not be stored in the heap. |
178 void push(const Pair &p) { |
178 void push(const Pair &p) { |
179 int n = _data.size(); |
179 int n = _data.size(); |
180 _data.resize(n+1); |
180 _data.resize(n+1); |
181 bubble_up(n, p); |
181 bubbleUp(n, p); |
182 } |
182 } |
183 |
183 |
184 /// \brief Insert an item into the heap with the given priority. |
184 /// \brief Insert an item into the heap with the given priority. |
185 /// |
185 /// |
186 /// This function inserts the given item into the heap with the |
186 /// This function inserts the given item into the heap with the |
212 /// \pre The heap must be non-empty. |
212 /// \pre The heap must be non-empty. |
213 void pop() { |
213 void pop() { |
214 int n = _data.size()-1; |
214 int n = _data.size()-1; |
215 _iim.set(_data[0].first, POST_HEAP); |
215 _iim.set(_data[0].first, POST_HEAP); |
216 if (n > 0) { |
216 if (n > 0) { |
217 bubble_down(0, _data[n], n); |
217 bubbleDown(0, _data[n], n); |
218 } |
218 } |
219 _data.pop_back(); |
219 _data.pop_back(); |
220 } |
220 } |
221 |
221 |
222 /// \brief Remove the given item from the heap. |
222 /// \brief Remove the given item from the heap. |
228 void erase(const Item &i) { |
228 void erase(const Item &i) { |
229 int h = _iim[i]; |
229 int h = _iim[i]; |
230 int n = _data.size()-1; |
230 int n = _data.size()-1; |
231 _iim.set(_data[h].first, POST_HEAP); |
231 _iim.set(_data[h].first, POST_HEAP); |
232 if( h < n ) { |
232 if( h < n ) { |
233 if ( bubble_up(h, _data[n]) == h) { |
233 if ( bubbleUp(h, _data[n]) == h) { |
234 bubble_down(h, _data[n], n); |
234 bubbleDown(h, _data[n], n); |
235 } |
235 } |
236 } |
236 } |
237 _data.pop_back(); |
237 _data.pop_back(); |
238 } |
238 } |
239 |
239 |
259 int idx = _iim[i]; |
259 int idx = _iim[i]; |
260 if( idx < 0 ) { |
260 if( idx < 0 ) { |
261 push(i,p); |
261 push(i,p); |
262 } |
262 } |
263 else if( _comp(p, _data[idx].second) ) { |
263 else if( _comp(p, _data[idx].second) ) { |
264 bubble_up(idx, Pair(i,p)); |
264 bubbleUp(idx, Pair(i,p)); |
265 } |
265 } |
266 else { |
266 else { |
267 bubble_down(idx, Pair(i,p), _data.size()); |
267 bubbleDown(idx, Pair(i,p), _data.size()); |
268 } |
268 } |
269 } |
269 } |
270 |
270 |
271 /// \brief Decrease the priority of an item to the given value. |
271 /// \brief Decrease the priority of an item to the given value. |
272 /// |
272 /// |
274 /// \param i The item. |
274 /// \param i The item. |
275 /// \param p The priority. |
275 /// \param p The priority. |
276 /// \pre \e i must be stored in the heap with priority at least \e p. |
276 /// \pre \e i must be stored in the heap with priority at least \e p. |
277 void decrease(const Item &i, const Prio &p) { |
277 void decrease(const Item &i, const Prio &p) { |
278 int idx = _iim[i]; |
278 int idx = _iim[i]; |
279 bubble_up(idx, Pair(i,p)); |
279 bubbleUp(idx, Pair(i,p)); |
280 } |
280 } |
281 |
281 |
282 /// \brief Increase the priority of an item to the given value. |
282 /// \brief Increase the priority of an item to the given value. |
283 /// |
283 /// |
284 /// This function increases the priority of an item to the given value. |
284 /// This function increases the priority of an item to the given value. |
285 /// \param i The item. |
285 /// \param i The item. |
286 /// \param p The priority. |
286 /// \param p The priority. |
287 /// \pre \e i must be stored in the heap with priority at most \e p. |
287 /// \pre \e i must be stored in the heap with priority at most \e p. |
288 void increase(const Item &i, const Prio &p) { |
288 void increase(const Item &i, const Prio &p) { |
289 int idx = _iim[i]; |
289 int idx = _iim[i]; |
290 bubble_down(idx, Pair(i,p), _data.size()); |
290 bubbleDown(idx, Pair(i,p), _data.size()); |
291 } |
291 } |
292 |
292 |
293 /// \brief Return the state of an item. |
293 /// \brief Return the state of an item. |
294 /// |
294 /// |
295 /// This method returns \c PRE_HEAP if the given item has never |
295 /// This method returns \c PRE_HEAP if the given item has never |