Click
Loading...
Searching...
No Matches
heap.hh
1#ifndef CLICK_HEAP_HH
2#define CLICK_HEAP_HH
3#include <click/algorithm.hh>
4CLICK_DECLS
5
30template <typename iterator_type, typename compare_type, typename place_type>
31inline 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
47template <typename iterator_type, typename compare_type>
48inline 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
78template <typename iterator_type, typename compare_type, typename place_type>
79iterator_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
111template <typename iterator_type, typename compare_type>
112inline 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
144template <typename iterator_type, typename compare_type, typename place_type>
145inline 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
158template <typename iterator_type, typename compare_type>
159inline 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
191template <typename iterator_type, typename compare_type, typename place_type>
192inline 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
199template <typename iterator_type, typename compare_type>
200inline 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
234template <int arity,
235 typename iterator_type, typename compare_type, typename place_type>
236inline 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
253template <int arity, typename iterator_type, typename compare_type>
254inline 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
286template <int arity,
287 typename iterator_type, typename compare_type, typename place_type>
288iterator_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
323template <int arity,
324 typename iterator_type, typename compare_type>
325inline 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
357template <int arity,
358 typename iterator_type, typename compare_type, typename place_type>
359inline 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
372template <int arity,
373 typename iterator_type, typename compare_type>
374inline 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
407template <int arity,
408 typename iterator_type, typename compare_type, typename place_type>
409inline 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
416template <int arity,
417 typename iterator_type, typename compare_type>
418inline 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
424CLICK_ENDDECLS
425#endif
do_nothing
Binary function object that does nothing when called.
Definition algorithm.hh:88
Generated on Mon Nov 2 2026 11:59:47 for Click by doxygen 1.9.8