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 * T : type of data held in the heap.
23 * C : class that implements operator() with two arguments and
24 * returns a boolean when the first argument is greater than (higher
25 * in priority than) the second.
27 template<typename T, typename C>
39 iterator(Heap<T,C>& _heap, int _index) :
48 iterator(iterator&& other) :
55 iterator& operator++() {
60 bool operator==(const iterator& other) const {
61 return index == other.index;
64 bool operator!=(const iterator& other) const {
65 return !(*this == other);
69 return heap.data[index];
72 // the item this iterator refers to
86 // parent(0) should be a negative value, which it is due to
87 // truncating towards negative infinity
88 static inline int parent(int i) { return (i - 1) / 2; }
90 static inline int lhs(int i) { return 2*i + 1; }
92 static inline int rhs(int i) { return 2*i + 2; }
99 if (!comparator(data[i], data[pi])) {
103 std::swap(data[i], data[pi]);
108 void siftDown(int i) {
114 if (comparator(data[li], data[i])) {
115 if (ri < count && comparator(data[ri], data[li])) {
116 std::swap(data[i], data[ri]);
119 std::swap(data[i], data[li]);
122 } else if (ri < count && comparator(data[ri], data[i])) {
123 std::swap(data[i], data[ri]);
143 Heap(const Heap<T,C>& other) {
144 data.resize(other.data.size());
145 for (int i = 0; i < other.count; ++i) {
146 data[i] = other.data[i];
151 const Heap<T,C>& operator=(const Heap<T,C>& other) {
152 data.resize(other.data.size());
153 for (int i = 0; i < other.count; ++i) {
154 data[i] = other.data[i];
160 bool empty() const { return 0 == count; }
162 T& top() { return data[0]; }
166 data.push_back(item);
171 data[0] = data[--count];
186 return iterator(*this, 0);
190 return iterator(*this, count);
193 std::ostream& displaySorted(std::ostream& out,
194 std::function<bool(const T&)> filter,
195 bool insert_line_breaks = true) const {
196 Heap<T,C> temp = *this;
201 while(!temp.empty()) {
202 const T& top = temp.top();
207 if (insert_line_breaks) {
208 out << std::endl << " ";
217 if (insert_line_breaks) {
223 template<typename T1, typename T2>
224 friend std::ostream& operator<<(std::ostream&, const Heap<T1,T2>&);
228 template<typename T1, typename T2>
229 std::ostream& operator<<(std::ostream& out, const Heap<T1,T2>& h) {
234 for (int i = 1; i < h.count; i++) {
235 out << ", " << h.data[i];