+++ /dev/null
-// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
-// vim: ts=8 sw=2 smarttab
-
-/*
- * Copyright (C) 2016 Red Hat Inc.
- */
-
-
-#pragma once
-
-
-#include <vector>
-#include <ostream>
-
-#include "assert.h"
-
-
-namespace crimson {
-
- /*
- * T : type of data held in the heap.
- *
- * C : class that implements operator() with two arguments and
- * returns a boolean when the first argument is greater than (higher
- * in priority than) the second.
- */
- template<typename T, typename C>
- class Heap {
-
- public:
-
- class iterator {
-
- friend Heap<T,C>;
-
- Heap<T,C>& heap;
- int index;
-
- iterator(Heap<T,C>& _heap, int _index) :
- heap(_heap),
- index(_index)
- {
- // empty
- }
-
- public:
-
- iterator(iterator&& other) :
- heap(other.heap),
- index(other.index)
- {
- // empty
- }
-
- iterator& operator++() {
- ++index;
- return *this;
- }
-
- bool operator==(const iterator& other) const {
- return index == other.index;
- }
-
- bool operator!=(const iterator& other) const {
- return !(*this == other);
- }
-
- T& operator*() {
- return heap.data[index];
- }
-
- // the item this iterator refers to
- void increase() {
- heap.siftUp(index);
- }
- }; // class iterator
-
- friend iterator;
-
- protected:
-
- std::vector<T> data;
- int count;
- C comparator;
-
- // parent(0) should be a negative value, which it is due to
- // truncating towards negative infinity
- static inline int parent(int i) { return (i - 1) / 2; }
-
- static inline int lhs(int i) { return 2*i + 1; }
-
- static inline int rhs(int i) { return 2*i + 2; }
-
- void siftUp(int i) {
- assert(i < count);
-
- while (i > 0) {
- int pi = parent(i);
- if (!comparator(data[i], data[pi])) {
- break;
- }
-
- std::swap(data[i], data[pi]);
- i = pi;
- }
- }
-
- void siftDown(int i) {
- while (i < count) {
- int li = lhs(i);
- int ri = rhs(i);
-
- if (li < count) {
- if (comparator(data[li], data[i])) {
- if (ri < count && comparator(data[ri], data[li])) {
- std::swap(data[i], data[ri]);
- i = ri;
- } else {
- std::swap(data[i], data[li]);
- i = li;
- }
- } else if (ri < count && comparator(data[ri], data[i])) {
- std::swap(data[i], data[ri]);
- i = ri;
- } else {
- break;
- }
- } else {
- break;
- }
- }
- }
-
-
- public:
-
- Heap() :
- count(0)
- {
- // empty
- }
-
- Heap(const Heap<T,C>& other) {
- data.resize(other.data.size());
- for (int i = 0; i < other.count; ++i) {
- data[i] = other.data[i];
- }
- count = other.count;
- }
-
- const Heap<T,C>& operator=(const Heap<T,C>& other) {
- data.resize(other.data.size());
- for (int i = 0; i < other.count; ++i) {
- data[i] = other.data[i];
- }
- count = other.count;
- return *this;
- }
-
- bool empty() const { return 0 == count; }
-
- T& top() { return data[0]; }
-
- void push(T item) {
- int i = count++;
- data.push_back(item);
- siftUp(i);
- }
-
- void pop() {
- data[0] = data[--count];
- data.resize(count);
- siftDown(0);
- }
-
- void updateTop() {
- siftDown(0);
- }
-
- void clear() {
- count = 0;
- data.resize(0);
- }
-
- iterator begin() {
- return iterator(*this, 0);
- }
-
- iterator end() {
- return iterator(*this, count);
- }
-
- std::ostream& displaySorted(std::ostream& out,
- std::function<bool(const T&)> filter,
- bool insert_line_breaks = true) const {
- Heap<T,C> temp = *this;
-
- bool first = true;
- out << "[ ";
-
- while(!temp.empty()) {
- const T& top = temp.top();
- if (filter(top)) {
- if (!first) {
- out << ", ";
- }
- if (insert_line_breaks) {
- out << std::endl << " ";
- }
- out << temp.top();
- first = false;
- }
- temp.pop();
- }
-
- out << " ]";
- if (insert_line_breaks) {
- out << std::endl;
- }
- return out;
- }
-
- template<typename T1, typename T2>
- friend std::ostream& operator<<(std::ostream&, const Heap<T1,T2>&);
- }; // class Heap
-
-
- template<typename T1, typename T2>
- std::ostream& operator<<(std::ostream& out, const Heap<T1,T2>& h) {
- out << "[ ";
- if (h.count) {
- out << h.data[0];
- }
- for (int i = 1; i < h.count; i++) {
- out << ", " << h.data[i];
- }
- out << " ]";
- return out;
- }
-} // namespace