1 #ifndef CLICK_HEAP_HH
2 #define CLICK_HEAP_HH
3 #include <click/algorithm.hh>
4 CLICK_DECLS
5
6 /** @brief Add an element to a heap.
7 * @param begin begin random-access iterator
8 * @param end end random-access iterator
9 * @param comp compare function object, such as less<>
10 * @param place placement function object, defaults to do_nothing<>
11 * @pre @a begin \< @a end
12 * @pre [@a begin, @a end - 1) is a heap
13 * @post [@a begin, @a end) is a heap
14 *
15 * This function rearranges the elements in [@a begin, @a end) to be a heap.
16 * It assumes that most of the sequence is already a heap -- only the new
17 * element, @a end[-1], might not be in a valid place.
18 *
19 * The comparison function @a comp defines the heap order.
20 *
21 * The placement function @a place is called for each element that
22 * changes place within the heap order; its arguments are @a begin and
23 * an iterator for the element that switched place. @a place is always
24 * called once with an iterator pointing the new element in its final
25 * place. @a place is useful when elements need to keep track of
26 * their own positions in the heap order. @a place defaults to
27 * do_nothing<>().
28 *
29 * @sa change_heap, pop_heap, remove_heap */
30 template <typename iterator_type, typename compare_type, typename place_type>
push_heap(iterator_type begin,iterator_type end,compare_type comp,place_type place)31 inline void push_heap(iterator_type begin, iterator_type end,
32 compare_type comp, place_type place)
33 {
34 assert(begin < end);
35 size_t i = end - begin - 1, npos;
36
37 while (i > 0 && (npos = (i-1)/2, comp(begin[i], begin[npos]))) {
38 click_swap(begin[i], begin[npos]);
39 place(begin, begin + i);
40 i = npos;
41 }
42
43 place(begin, begin + i);
44 }
45
46 /** @overload */
47 template <typename iterator_type, typename compare_type>
push_heap(iterator_type begin,iterator_type end,compare_type comp)48 inline void push_heap(iterator_type begin, iterator_type end,
49 compare_type comp)
50 {
51 push_heap(begin, end, comp, do_nothing<iterator_type, iterator_type>());
52 }
53
54 /** @brief Change an element's position within a heap.
55 * @param begin begin random-access iterator
56 * @param end end random-access iterator
57 * @param element iterator pointing to element whose position may change
58 * @param comp compare function object, such as less<>
59 * @param place placement function object, defaults to do_nothing<>
60 * @pre @a begin \<= @a element < @a end
61 * @pre [@a begin, @a end) is a heap, perhaps excluding @a element
62 * @post [@a begin, @a end) is a heap
63 * @return iterator pointing to the new location of *@a element
64 *
65 * This function rearranges the elements in [@a begin, @a end) to be a heap.
66 * It assumes that most of the sequence is already a heap. Only the element
67 * pointed to by @a element might be out of place.
68 *
69 * The comparison function @a comp defines the heap order.
70 *
71 * The placement function @a place is called for each element that
72 * changes place within the heap order; its arguments are @a begin and
73 * an iterator for the element that switched place. @a place is
74 * useful when elements need to keep track of their own positions in
75 * the heap order. @a place defaults to do_nothing<>().
76 *
77 * @sa push_heap, pop_heap, remove_heap */
78 template <typename iterator_type, typename compare_type, typename place_type>
79 iterator_type change_heap(iterator_type begin, iterator_type end,
80 iterator_type element,
81 compare_type comp, place_type place)
82 {
83 assert(begin <= element && element < end);
84 size_t i = element - begin, size = end - begin, npos;
85
86 while (i > 0 && (npos = (i-1)/2, comp(begin[i], begin[npos]))) {
87 click_swap(begin[i], begin[npos]);
88 place(begin, begin + i);
89 i = npos;
90 }
91
92 while (1) {
93 size_t smallest = i, trial = i*2 + 1;
94 if (trial < size && comp(begin[trial], begin[smallest]))
95 smallest = trial;
96 if (trial + 1 < size && comp(begin[trial + 1], begin[smallest]))
97 smallest = trial + 1;
98 if (smallest == i)
99 break;
100 click_swap(begin[i], begin[smallest]);
101 place(begin, begin + i);
102 i = smallest;
103 }
104
105 if (begin + i != element)
106 place(begin, begin + i);
107 return begin + i;
108 }
109
110 /** @overload */
111 template <typename iterator_type, typename compare_type>
change_heap(iterator_type begin,iterator_type end,iterator_type element,compare_type comp)112 inline iterator_type change_heap(iterator_type begin, iterator_type end,
113 iterator_type element, compare_type comp)
114 {
115 return change_heap(begin, end, element, comp, do_nothing<iterator_type, iterator_type>());
116 }
117
118 /** @brief Remove an element from a heap.
119 * @param begin begin random-access iterator
120 * @param end end random-access iterator
121 * @param element iterator pointing to element to remove
122 * @param comp compare function object, such as less<>
123 * @param place placement function object, defaults to do_nothing<>
124 * @pre @a begin \<= @a element < @a end
125 * @pre [@a begin, @a end) is a heap, possibly excluding @a element
126 * @post [@a begin, @a end - 1) is a heap, and the element formerly at
127 * *@a element has shifted to *(@a end - 1)
128 *
129 * This function removes @a element from the heap in [@a begin, @a end) by
130 * shifting it to the end, preserving the heap property on the remaining
131 * elements.
132 *
133 * The comparison function @a comp defines the heap order.
134 *
135 * The placement function @a place is called for each actual element
136 * that changes place within the heap order; its arguments are @a
137 * begin and an iterator for the element that switched place. It is
138 * not called on @a element, which is no longer considered a member of
139 * the heap. @a place is useful when elements need to keep track of
140 * their own positions in the heap order. @a place defaults to
141 * do_nothing<>().
142 *
143 * @sa push_heap, change_heap, pop_heap */
144 template <typename iterator_type, typename compare_type, typename place_type>
remove_heap(iterator_type begin,iterator_type end,iterator_type element,compare_type comp,place_type place)145 inline void remove_heap(iterator_type begin, iterator_type end,
146 iterator_type element,
147 compare_type comp, place_type place)
148 {
149 assert(begin <= element && element < end);
150 if (element + 1 != end) {
151 click_swap(element[0], end[-1]);
152 place(begin, element);
153 change_heap(begin, end - 1, element, comp, place);
154 }
155 }
156
157 /** @overload */
158 template <typename iterator_type, typename compare_type>
remove_heap(iterator_type begin,iterator_type end,iterator_type element,compare_type comp)159 inline void remove_heap(iterator_type begin, iterator_type end,
160 iterator_type element,
161 compare_type comp)
162 {
163 remove_heap(begin, end, element, comp, do_nothing<iterator_type, iterator_type>());
164 }
165
166 /** @brief Remove the first element from a heap.
167 * @param begin begin random-access iterator
168 * @param end end random-access iterator
169 * @param comp compare function object, such as less<>
170 * @param place placement function object, defaults to do_nothing<>
171 * @pre @a begin \< @a end
172 * @pre [@a begin, @a end) is a heap
173 * @post [@a begin, @a end - 1) is a heap, and the element formerly at
174 * *@a begin has shifted to *(@a end - 1)
175 *
176 * This function removes the first element of [@a begin, @a end) from a heap
177 * by shifting it to the end, preserving the heap property on the remaining
178 * elements.
179 *
180 * The comparison function @a comp defines the heap order.
181 *
182 * The placement function @a place is called for each element that
183 * changes place within the heap order; its arguments are @a begin and
184 * an iterator for the element that switched place. It is not called
185 * on the first element, which is no longer considered a member of the
186 * heap. @a place is useful when elements need to keep track of their
187 * own positions in the heap order. @a place defaults to
188 * do_nothing<>().
189 *
190 * @sa push_heap, change_heap, remove_heap */
191 template <typename iterator_type, typename compare_type, typename place_type>
pop_heap(iterator_type begin,iterator_type end,compare_type comp,place_type place)192 inline void pop_heap(iterator_type begin, iterator_type end,
193 compare_type comp, place_type place)
194 {
195 remove_heap(begin, end, begin, comp, place);
196 }
197
198 /** @overload */
199 template <typename iterator_type, typename compare_type>
pop_heap(iterator_type begin,iterator_type end,compare_type comp)200 inline void pop_heap(iterator_type begin, iterator_type end,
201 compare_type comp)
202 {
203 pop_heap(begin, end, comp, do_nothing<iterator_type, iterator_type>());
204 }
205
206
207
208 /** @brief Add an element to a d-ary heap.
209 * @param begin begin random-access iterator
210 * @param end end random-access iterator
211 * @param comp compare function object, such as less<>
212 * @param place placement function object, defaults to do_nothing<>
213 * @pre @a begin \< @a end
214 * @pre [@a begin, @a end - 1) is a d-ary heap
215 * @post [@a begin, @a end) is a d-ary heap
216 *
217 * This function rearranges the elements in [@a begin, @a end) to be
218 * a d-ary heap. It assumes that most of the sequence is already a
219 * heap -- only the new element, @a end[-1], might not be in a valid
220 * place. The arity @a n is a template parameter, and must be greater
221 * than 2.
222 *
223 * The comparison function @a comp defines the heap order.
224 *
225 * The placement function @a place is called for each element that
226 * changes place within the heap order; its arguments are @a begin and
227 * an iterator for the element that switched place. @a place is always
228 * called once with an iterator pointing the new element in its final
229 * place. @a place is useful when elements need to keep track of
230 * their own positions in the heap order. @a place defaults to
231 * do_nothing<>().
232 *
233 * @sa change_heap, pop_heap, remove_heap */
234 template <int arity,
235 typename iterator_type, typename compare_type, typename place_type>
push_heap(iterator_type begin,iterator_type end,compare_type comp,place_type place)236 inline void push_heap(iterator_type begin, iterator_type end,
237 compare_type comp, place_type place)
238 {
239 static_assert(arity > 2, "For arity == 2, use push_heap(...), not push_heap<2>(...).");
240 assert(begin < end);
241 size_t i = end - begin - 1, npos;
242
243 while (i > 0 && (npos = i/arity, comp(begin[i], begin[npos]))) {
244 click_swap(begin[i], begin[npos]);
245 place(begin, begin + i);
246 i = npos;
247 }
248
249 place(begin, begin + i);
250 }
251
252 /** @overload */
253 template <int arity, typename iterator_type, typename compare_type>
push_heap(iterator_type begin,iterator_type end,compare_type comp)254 inline void push_heap(iterator_type begin, iterator_type end,
255 compare_type comp)
256 {
257 push_heap<arity>(begin, end, comp, do_nothing<iterator_type, iterator_type>());
258 }
259
260 /** @brief Change an element's position within a d-ary heap.
261 * @param begin begin random-access iterator
262 * @param end end random-access iterator
263 * @param element iterator pointing to element whose position may change
264 * @param comp compare function object, such as less<>
265 * @param place placement function object, defaults to do_nothing<>
266 * @pre @a begin \<= @a element < @a end
267 * @pre [@a begin, @a end) is a d-ary heap, perhaps excluding @a element
268 * @post [@a begin, @a end) is a d-ary heap
269 * @return iterator pointing to the new location of *@a element
270 *
271 * This function rearranges the elements in [@a begin, @a end) to be
272 * a d-ary heap. It assumes that most of the sequence is already a
273 * heap. Only the element pointed to by @a element might be out of
274 * place. The arity @a n is a template parameter, and must be greater
275 * than 2.
276 *
277 * The comparison function @a comp defines the heap order.
278 *
279 * The placement function @a place is called for each element that
280 * changes place within the heap order; its arguments are @a begin and
281 * an iterator for the element that switched place. @a place is
282 * useful when elements need to keep track of their own positions in
283 * the heap order. @a place defaults to do_nothing<>().
284 *
285 * @sa push_heap, pop_heap, remove_heap */
286 template <int arity,
287 typename iterator_type, typename compare_type, typename place_type>
288 iterator_type change_heap(iterator_type begin, iterator_type end,
289 iterator_type element,
290 compare_type comp, place_type place)
291 {
292 static_assert(arity > 2, "For arity == 2, use change_heap(...), not change_heap<2>(...).");
293 assert(begin <= element && element < end);
294 size_t i = element - begin, size = end - begin, npos;
295
296 while (i > 0 && (npos = i/arity, comp(begin[i], begin[npos]))) {
297 click_swap(begin[i], begin[npos]);
298 place(begin, begin + i);
299 i = npos;
300 }
301
302 while (1) {
303 size_t smallest = i,
304 trial = i ? i * arity : 1,
305 end_trial = i ? trial + arity : arity;
306 end_trial = end_trial < size ? end_trial : size;
307 for (; trial < end_trial; ++trial)
308 if (comp(begin[trial], begin[smallest]))
309 smallest = trial;
310 if (smallest == i)
311 break;
312 click_swap(begin[i], begin[smallest]);
313 place(begin, begin + i);
314 i = smallest;
315 }
316
317 if (begin + i != element)
318 place(begin, begin + i);
319 return begin + i;
320 }
321
322 /** @overload */
323 template <int arity,
324 typename iterator_type, typename compare_type>
change_heap(iterator_type begin,iterator_type end,iterator_type element,compare_type comp)325 inline iterator_type change_heap(iterator_type begin, iterator_type end,
326 iterator_type element, compare_type comp)
327 {
328 return change_heap<arity>(begin, end, element, comp, do_nothing<iterator_type, iterator_type>());
329 }
330
331 /** @brief Remove an element from a d-ary heap.
332 * @param begin begin random-access iterator
333 * @param end end random-access iterator
334 * @param element iterator pointing to element to remove
335 * @param comp compare function object, such as less<>
336 * @param place placement function object, defaults to do_nothing<>
337 * @pre @a begin \<= @a element < @a end
338 * @pre [@a begin, @a end) is a d-ary heap, possibly excluding @a element
339 * @post [@a begin, @a end - 1) is a d-ary heap, and the element formerly
340 * at *@a element has shifted to *(@a end - 1)
341 *
342 * This function removes @a element from the d-ary heap in [@a begin,
343 * @a end) by shifting it to the end, preserving the heap property on
344 * the remaining elements. The arity @a n is a template parameter.
345 *
346 * The comparison function @a comp defines the heap order.
347 *
348 * The placement function @a place is called for each actual element
349 * that changes place within the heap order; its arguments are @a
350 * begin and an iterator for the element that switched place. It is
351 * not called on @a element, which is no longer considered a member of
352 * the heap. @a place is useful when elements need to keep track of
353 * their own positions in the heap order. @a place defaults to
354 * do_nothing<>().
355 *
356 * @sa push_heap, change_heap, pop_heap */
357 template <int arity,
358 typename iterator_type, typename compare_type, typename place_type>
remove_heap(iterator_type begin,iterator_type end,iterator_type element,compare_type comp,place_type place)359 inline void remove_heap(iterator_type begin, iterator_type end,
360 iterator_type element,
361 compare_type comp, place_type place)
362 {
363 assert(begin <= element && element < end);
364 if (element + 1 != end) {
365 click_swap(element[0], end[-1]);
366 place(begin, element);
367 change_heap<arity>(begin, end - 1, element, comp, place);
368 }
369 }
370
371 /** @overload */
372 template <int arity,
373 typename iterator_type, typename compare_type>
remove_heap(iterator_type begin,iterator_type end,iterator_type element,compare_type comp)374 inline void remove_heap(iterator_type begin, iterator_type end,
375 iterator_type element,
376 compare_type comp)
377 {
378 remove_heap<arity>(begin, end, element, comp, do_nothing<iterator_type, iterator_type>());
379 }
380
381 /** @brief Remove the first element from a d-ary heap.
382 * @param begin begin random-access iterator
383 * @param end end random-access iterator
384 * @param comp compare function object, such as less<>
385 * @param place placement function object, defaults to do_nothing<>
386 * @pre @a begin \< @a end
387 * @pre [@a begin, @a end) is a d-ary heap
388 * @post [@a begin, @a end - 1) is a d-ary heap, and the element formerly
389 * at *@a begin has shifted to *(@a end - 1)
390 *
391 * This function removes the first element of [@a begin, @a end) from
392 * a d-ary heap by shifting it to the end, preserving the heap
393 * property on the remaining elements. The arity @a n is a template
394 * parameter.
395 *
396 * The comparison function @a comp defines the heap order.
397 *
398 * The placement function @a place is called for each element that
399 * changes place within the heap order; its arguments are @a begin and
400 * an iterator for the element that switched place. It is not called
401 * on the first element, which is no longer considered a member of the
402 * heap. @a place is useful when elements need to keep track of their
403 * own positions in the heap order. @a place defaults to
404 * do_nothing<>().
405 *
406 * @sa push_heap, change_heap, remove_heap */
407 template <int arity,
408 typename iterator_type, typename compare_type, typename place_type>
pop_heap(iterator_type begin,iterator_type end,compare_type comp,place_type place)409 inline void pop_heap(iterator_type begin, iterator_type end,
410 compare_type comp, place_type place)
411 {
412 remove_heap<arity>(begin, end, begin, comp, place);
413 }
414
415 /** @overload */
416 template <int arity,
417 typename iterator_type, typename compare_type>
pop_heap(iterator_type begin,iterator_type end,compare_type comp)418 inline void pop_heap(iterator_type begin, iterator_type end,
419 compare_type comp)
420 {
421 pop_heap<arity>(begin, end, comp, do_nothing<iterator_type, iterator_type>());
422 }
423
424 CLICK_ENDDECLS
425 #endif
426