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.
21 using IntruHeapData = size_t;
23 // T = type of data in heap; I = functor that returns a non-const
24 // reference to IntruHeapData; C = functor that compares two const
25 // refs and return true if the first precedes the second
26 template<typename T, typename I, typename C>
30 std::is_same<IntruHeapData&,typename std::result_of<I(T&)>::type>::value,
31 "class I must define operator() to take T& and return a IntruHeapData&.");
34 std::is_same<bool,typename std::result_of<C(const T&,const T&)>::type>::value,
35 "class C must define operator() to take two const T& and return a bool.");
39 using index_t = IntruHeapData;
54 IntruHeap(const IntruHeap<T,I,C>& other) :
57 for (uint i = 0; i < other.count; ++i) {
58 data.push_back(other.data[i]);
62 bool empty() const { return 0 == count; }
64 T& top() { return data[0]; }
68 intru_data_of(item) = i;
69 data.emplace_back(item);
73 void push(const T& item) {
75 push(std::move(copy));
79 std::swap(data[0], data[--count]);
80 intru_data_of(data[0]) = 0;
85 void adjust_up(T& item) {
86 sift_up(intru_data_of(item));
89 void adjust_down(T& item) {
90 sift_down(intru_data_of(item));
93 void adjust(T& item) {
94 sift(intru_data_of(item));
97 friend std::ostream& operator<<(std::ostream& out, const IntruHeap& h) {
98 for (uint i = 0; i < h.count; ++i) {
99 out << h.data[i] << ", ";
105 display_sorted(std::ostream& out,
106 bool insert_line_breaks = true,
107 std::function<bool(const T&)> filter = all_filter) const {
108 IntruHeap<T,I,C> copy = *this;
113 while(!copy.empty()) {
114 const T& top = copy.top();
119 if (insert_line_breaks) {
120 out << std::endl << " ";
129 if (insert_line_breaks) {
139 // default value of filter parameter to display_sorted
140 static bool all_filter(const T& data) { return true; }
142 // when i is negative?
143 static inline index_t parent(index_t i) {
148 static inline index_t lhs(index_t i) { return 2*i + 1; }
150 static inline index_t rhs(index_t i) { return 2*i + 2; }
152 void sift_up(index_t i) {
154 index_t pi = parent(i);
155 if (!comparator(data[i], data[pi])) {
159 std::swap(data[i], data[pi]);
160 intru_data_of(data[i]) = i;
161 intru_data_of(data[pi]) = pi;
166 void sift_down(index_t i) {
172 if (comparator(data[li], data[i])) {
173 if (ri < count && comparator(data[ri], data[li])) {
174 std::swap(data[i], data[ri]);
175 intru_data_of(data[i]) = i;
176 intru_data_of(data[ri]) = ri;
179 std::swap(data[i], data[li]);
180 intru_data_of(data[i]) = i;
181 intru_data_of(data[li]) = li;
184 } else if (ri < count && comparator(data[ri], data[i])) {
185 std::swap(data[i], data[ri]);
186 intru_data_of(data[i]) = i;
187 intru_data_of(data[ri]) = ri;
198 void sift(index_t i) {
200 // if we're at top, can only go down
203 index_t pi = parent(i);
204 if (comparator(data[i], data[pi])) {
205 // if we can go up, we will
208 // otherwise we'll try to go down
213 }; // class IntruHeap
214 } // namespace crimson