1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
5 * Copyright (C) 2016 Red Hat Inc.
23 using IndIntruHeapData = size_t;
25 /* T is the ultimate data that's being stored in the heap, although
26 * through indirection.
28 * I is the indirect type that will actually be stored in the heap
29 * and that must allow dereferencing (via operator*) to yield a
32 * C is a functor when given two T&'s will return true if the first
33 * must precede the second.
35 * heap_info is a data member pointer as to where the heap data in T
38 * K is the branching factor of the heap, default is 2 (binary heap).
42 IndIntruHeapData T::*heap_info,
48 using HeapIndex = IndIntruHeapData;
51 std::is_same<T,typename std::pointer_traits<I>::element_type>::value,
52 "class I must resolve to class T by indirection (pointer dereference)");
56 typename std::result_of<C(const T&,const T&)>::type>::value,
57 "class C must define operator() to take two const T& and return a bool");
59 static_assert(K >= 2, "K (degree of branching) must be at least 2");
62 friend IndIntruHeap<I, T, heap_info, C, K>;
64 IndIntruHeap<I, T, heap_info, C, K>& heap;
67 Iterator(IndIntruHeap<I, T, heap_info, C, K>& _heap, HeapIndex _index) :
76 Iterator(Iterator&& other) :
83 Iterator(const Iterator& other) :
90 Iterator& operator=(Iterator&& other) {
91 std::swap(heap, other.heap);
92 std::swap(index, other.index);
96 Iterator& operator=(const Iterator& other) {
101 Iterator& operator++() {
102 if (index <= heap.count) {
108 bool operator==(const Iterator& other) const {
109 return &heap == &other.heap && index == other.index;
112 bool operator!=(const Iterator& other) const {
113 return !(*this == other);
117 return *heap.data[index];
121 return &(*heap.data[index]);
125 // the item this iterator refers to
133 class ConstIterator {
134 friend IndIntruHeap<I, T, heap_info, C, K>;
136 const IndIntruHeap<I, T, heap_info, C, K>& heap;
139 ConstIterator(const IndIntruHeap<I, T, heap_info, C, K>& _heap,
149 ConstIterator(ConstIterator&& other) :
156 ConstIterator(const ConstIterator& other) :
163 ConstIterator& operator=(ConstIterator&& other) {
164 std::swap(heap, other.heap);
165 std::swap(index, other.index);
169 ConstIterator& operator=(const ConstIterator& other) {
174 ConstIterator& operator++() {
175 if (index <= heap.count) {
181 bool operator==(const ConstIterator& other) const {
182 return &heap == &other.heap && index == other.index;
185 bool operator!=(const ConstIterator& other) const {
186 return !(*this == other);
189 const T& operator*() {
190 return *heap.data[index];
193 const T* operator->() {
194 return &(*heap.data[index]);
196 }; // class ConstIterator
213 IndIntruHeap(const IndIntruHeap<I,T,heap_info,C,K>& other) :
216 for (HeapIndex i = 0; i < other.count; ++i) {
217 data.push_back(other.data[i]);
221 bool empty() const { return 0 == count; }
223 size_t size() const { return (size_t) count; }
225 T& top() { return *data[0]; }
227 const T& top() const { return *data[0]; }
229 I& top_ind() { return data[0]; }
231 const I& top_ind() const { return data[0]; }
233 void push(I&& item) {
234 HeapIndex i = count++;
235 intru_data_of(item) = i;
236 data.emplace_back(std::move(item));
240 void push(const I& item) {
242 push(std::move(copy));
246 remove(HeapIndex(0));
249 void remove(Iterator& i) {
254 Iterator find(const I& ind_item) {
255 for (HeapIndex i = 0; i < count; ++i) {
256 if (data[i] == ind_item) {
257 return Iterator(*this, i);
263 // when passing in value we do a comparison via operator==
264 Iterator find(const T& item) {
265 for (HeapIndex i = 0; i < count; ++i) {
266 if (*data[i] == item) {
267 return Iterator(*this, i);
273 // reverse find -- start looking from bottom of heap
274 Iterator rfind(const I& ind_item) {
275 // HeapIndex is unsigned, so we can't allow to go negative; so
276 // we'll keep it one more than actual index
277 for (HeapIndex i = count; i > 0; --i) {
278 if (data[i-1] == ind_item) {
279 return Iterator(*this, i-1);
285 // reverse find -- start looking from bottom of heap
286 Iterator rfind(const T& item) {
287 // HeapIndex is unsigned, so we can't allow to go negative; so
288 // we'll keep it one more than actual index
289 for (HeapIndex i = count; i > 0; --i) {
290 if (*data[i-1] == item) {
291 return Iterator(*this, i-1);
297 ConstIterator find(const I& ind_item) const {
298 for (HeapIndex i = 0; i < count; ++i) {
299 if (data[i] == ind_item) {
300 return ConstIterator(*this, i);
306 // when passing in value we do a comparison via operator==
307 ConstIterator find(const T& item) const {
308 for (HeapIndex i = 0; i < count; ++i) {
309 if (*data[i] == item) {
310 return ConstIterator(*this, i);
316 // reverse find -- start looking from bottom of heap
317 ConstIterator rfind(const I& ind_item) const {
318 // HeapIndex is unsigned, so we can't allow to go negative; so
319 // we'll keep it one more than actual index
320 for (HeapIndex i = count; i > 0; --i) {
321 if (data[i-1] == ind_item) {
322 return ConstIterator(*this, i-1);
328 // reverse find -- start looking from bottom of heap
329 ConstIterator rfind(const T& item) const {
330 // HeapIndex is unsigned, so we can't allow to go negative; so
331 // we'll keep it one more than actual index
332 for (HeapIndex i = count; i > 0; --i) {
333 if (*data[i-1] == item) {
334 return ConstIterator(*this, i-1);
340 void promote(T& item) {
341 sift_up(item.*heap_info);
344 void demote(T& item) {
345 sift_down(item.*heap_info);
348 void adjust(T& item) {
349 sift(item.*heap_info);
353 return Iterator(*this, 0);
357 return Iterator(*this, count);
360 ConstIterator cbegin() const {
361 return ConstIterator(*this, 0);
364 ConstIterator cend() const {
365 return ConstIterator(*this, count);
368 friend std::ostream& operator<<(std::ostream& out, const IndIntruHeap& h) {
369 auto i = h.data.cbegin();
370 if (i != h.data.cend()) {
373 while (i != h.data.cend()) {
380 // can only be called if I is copyable; copies heap into a vector
381 // and sorts it before displaying it
383 display_sorted(std::ostream& out,
384 std::function<bool(const T&)> filter = all_filter) const {
385 static_assert(std::is_copy_constructible<I>::value,
386 "cannot call display_sorted when class I is not copy"
388 auto compare = [this] (const I first, const I second) -> bool {
389 return this->comparator(*first, *second);
391 std::vector<I> copy(data);
392 std::sort(copy.begin(), copy.end(), compare);
395 for (auto c = copy.begin(); c != copy.end(); ++c) {
412 static IndIntruHeapData& intru_data_of(I& item) {
413 return (*item).*heap_info;
416 void remove(HeapIndex i) {
417 std::swap(data[i], data[--count]);
418 intru_data_of(data[i]) = i;
421 // the following needs to be sift (and not sift_down) as it can
422 // go up or down the heap; imagine the heap vector contains 0,
423 // 10, 100, 20, 30, 200, 300, 40; then 200 is removed, and 40
424 // would have to be sifted upwards
429 // default value of filter parameter to display_sorted
430 static bool all_filter(const T& data) { return true; }
432 // when i is negative?
433 static inline HeapIndex parent(HeapIndex i) {
438 // index of left child when K==2, index of left-most child when K>2
439 static inline HeapIndex lhs(HeapIndex i) { return K*i + 1; }
441 // index of right child when K==2, index of right-most child when K>2
442 static inline HeapIndex rhs(HeapIndex i) { return K*i + K; }
444 void sift_up(HeapIndex i) {
446 HeapIndex pi = parent(i);
447 if (!comparator(*data[i], *data[pi])) {
451 std::swap(data[i], data[pi]);
452 intru_data_of(data[i]) = i;
453 intru_data_of(data[pi]) = pi;
458 // use this sift_down definition when K>2; it's more general and
459 // uses a loop; EnableBool insures template uses a template
461 template<bool EnableBool=true>
462 typename std::enable_if<(K>2)&&EnableBool,void>::type sift_down(HeapIndex i) {
463 if (i >= count) return;
465 HeapIndex li = lhs(i);
468 HeapIndex ri = std::min(rhs(i), count - 1);
470 // find the index of min. child
471 HeapIndex min_i = li;
472 for (HeapIndex k = li + 1; k <= ri; ++k) {
473 if (comparator(*data[k], *data[min_i])) {
478 if (comparator(*data[min_i], *data[i])) {
479 std::swap(data[i], data[min_i]);
480 intru_data_of(data[i]) = i;
481 intru_data_of(data[min_i]) = min_i;
484 // no child is smaller
494 // use this sift_down definition when K==2; EnableBool insures
495 // template uses a template parameter
496 template<bool EnableBool=true>
497 typename std::enable_if<K==2&&EnableBool,void>::type sift_down(HeapIndex i) {
498 if (i >= count) return;
500 const HeapIndex li = lhs(i);
501 const HeapIndex ri = 1 + li;
504 if (comparator(*data[li], *data[i])) {
505 if (ri < count && comparator(*data[ri], *data[li])) {
506 std::swap(data[i], data[ri]);
507 intru_data_of(data[i]) = i;
508 intru_data_of(data[ri]) = ri;
511 std::swap(data[i], data[li]);
512 intru_data_of(data[i]) = i;
513 intru_data_of(data[li]) = li;
516 } else if (ri < count && comparator(*data[ri], *data[i])) {
517 std::swap(data[i], data[ri]);
518 intru_data_of(data[i]) = i;
519 intru_data_of(data[ri]) = ri;
522 // no child is smaller
532 void sift(HeapIndex i) {
534 // if we're at top, can only go down
537 HeapIndex pi = parent(i);
538 if (comparator(*data[i], *data[pi])) {
539 // if we can go up, we will
542 // otherwise we'll try to go down
547 }; // class IndIntruHeap
549 } // namespace crimson