+++ /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 <memory>
-#include <vector>
-#include <string>
-#include <iostream>
-#include <functional>
-#include <algorithm>
-
-#include "assert.h"
-
-
-namespace crimson {
- using IndIntruHeapData = size_t;
-
- /* T is the ultimate data that's being stored in the heap, although
- * through indirection.
- *
- * I is the indirect type that will actually be stored in the heap
- * and that must allow dereferencing (via operator*) to yield a
- * T&.
- *
- * C is a functor when given two T&'s will return true if the first
- * must precede the second.
- *
- * heap_info is a data member pointer as to where the heap data in T
- * is stored.
- *
- * K is the branching factor of the heap, default is 2 (binary heap).
- */
- template<typename I,
- typename T,
- IndIntruHeapData T::*heap_info,
- typename C,
- uint K = 2>
- class IndIntruHeap {
-
- // shorthand
- using HeapIndex = IndIntruHeapData;
-
- static_assert(
- std::is_same<T,typename std::pointer_traits<I>::element_type>::value,
- "class I must resolve to class T by indirection (pointer dereference)");
-
- static_assert(
- std::is_same<bool,
- typename std::result_of<C(const T&,const T&)>::type>::value,
- "class C must define operator() to take two const T& and return a bool");
-
- static_assert(K >= 2, "K (degree of branching) must be at least 2");
-
- class Iterator {
- friend IndIntruHeap<I, T, heap_info, C, K>;
-
- IndIntruHeap<I, T, heap_info, C, K>& heap;
- HeapIndex index;
-
- Iterator(IndIntruHeap<I, T, heap_info, C, K>& _heap, HeapIndex _index) :
- heap(_heap),
- index(_index)
- {
- // empty
- }
-
- public:
-
- Iterator(Iterator&& other) :
- heap(other.heap),
- index(other.index)
- {
- // empty
- }
-
- Iterator(const Iterator& other) :
- heap(other.heap),
- index(other.index)
- {
- // empty
- }
-
- Iterator& operator=(Iterator&& other) {
- std::swap(heap, other.heap);
- std::swap(index, other.index);
- return *this;
- }
-
- Iterator& operator=(const Iterator& other) {
- heap = other.heap;
- index = other.index;
- }
-
- Iterator& operator++() {
- if (index <= heap.count) {
- ++index;
- }
- return *this;
- }
-
- bool operator==(const Iterator& other) const {
- return &heap == &other.heap && index == other.index;
- }
-
- bool operator!=(const Iterator& other) const {
- return !(*this == other);
- }
-
- T& operator*() {
- return *heap.data[index];
- }
-
- T* operator->() {
- return &(*heap.data[index]);
- }
-
-#if 0
- // the item this iterator refers to
- void increase() {
- heap.sift_up(index);
- }
-#endif
- }; // class Iterator
-
-
- class ConstIterator {
- friend IndIntruHeap<I, T, heap_info, C, K>;
-
- const IndIntruHeap<I, T, heap_info, C, K>& heap;
- HeapIndex index;
-
- ConstIterator(const IndIntruHeap<I, T, heap_info, C, K>& _heap,
- HeapIndex _index) :
- heap(_heap),
- index(_index)
- {
- // empty
- }
-
- public:
-
- ConstIterator(ConstIterator&& other) :
- heap(other.heap),
- index(other.index)
- {
- // empty
- }
-
- ConstIterator(const ConstIterator& other) :
- heap(other.heap),
- index(other.index)
- {
- // empty
- }
-
- ConstIterator& operator=(ConstIterator&& other) {
- std::swap(heap, other.heap);
- std::swap(index, other.index);
- return *this;
- }
-
- ConstIterator& operator=(const ConstIterator& other) {
- heap = other.heap;
- index = other.index;
- }
-
- ConstIterator& operator++() {
- if (index <= heap.count) {
- ++index;
- }
- return *this;
- }
-
- bool operator==(const ConstIterator& other) const {
- return &heap == &other.heap && index == other.index;
- }
-
- bool operator!=(const ConstIterator& other) const {
- return !(*this == other);
- }
-
- const T& operator*() {
- return *heap.data[index];
- }
-
- const T* operator->() {
- return &(*heap.data[index]);
- }
- }; // class ConstIterator
-
-
- protected:
-
- std::vector<I> data;
- HeapIndex count;
- C comparator;
-
- public:
-
- IndIntruHeap() :
- count(0)
- {
- // empty
- }
-
- IndIntruHeap(const IndIntruHeap<I,T,heap_info,C,K>& other) :
- count(other.count)
- {
- for (HeapIndex i = 0; i < other.count; ++i) {
- data.push_back(other.data[i]);
- }
- }
-
- bool empty() const { return 0 == count; }
-
- size_t size() const { return (size_t) count; }
-
- T& top() { return *data[0]; }
-
- const T& top() const { return *data[0]; }
-
- I& top_ind() { return data[0]; }
-
- const I& top_ind() const { return data[0]; }
-
- void push(I&& item) {
- HeapIndex i = count++;
- intru_data_of(item) = i;
- data.emplace_back(std::move(item));
- sift_up(i);
- }
-
- void push(const I& item) {
- I copy(item);
- push(std::move(copy));
- }
-
- void pop() {
- remove(HeapIndex(0));
- }
-
- void remove(Iterator& i) {
- remove(i.index);
- i = end();
- }
-
- Iterator find(const I& ind_item) {
- for (HeapIndex i = 0; i < count; ++i) {
- if (data[i] == ind_item) {
- return Iterator(*this, i);
- }
- }
- return end();
- }
-
- // when passing in value we do a comparison via operator==
- Iterator find(const T& item) {
- for (HeapIndex i = 0; i < count; ++i) {
- if (*data[i] == item) {
- return Iterator(*this, i);
- }
- }
- return end();
- }
-
- // reverse find -- start looking from bottom of heap
- Iterator rfind(const I& ind_item) {
- // HeapIndex is unsigned, so we can't allow to go negative; so
- // we'll keep it one more than actual index
- for (HeapIndex i = count; i > 0; --i) {
- if (data[i-1] == ind_item) {
- return Iterator(*this, i-1);
- }
- }
- return end();
- }
-
- // reverse find -- start looking from bottom of heap
- Iterator rfind(const T& item) {
- // HeapIndex is unsigned, so we can't allow to go negative; so
- // we'll keep it one more than actual index
- for (HeapIndex i = count; i > 0; --i) {
- if (*data[i-1] == item) {
- return Iterator(*this, i-1);
- }
- }
- return end();
- }
-
- ConstIterator find(const I& ind_item) const {
- for (HeapIndex i = 0; i < count; ++i) {
- if (data[i] == ind_item) {
- return ConstIterator(*this, i);
- }
- }
- return cend();
- }
-
- // when passing in value we do a comparison via operator==
- ConstIterator find(const T& item) const {
- for (HeapIndex i = 0; i < count; ++i) {
- if (*data[i] == item) {
- return ConstIterator(*this, i);
- }
- }
- return cend();
- }
-
- // reverse find -- start looking from bottom of heap
- ConstIterator rfind(const I& ind_item) const {
- // HeapIndex is unsigned, so we can't allow to go negative; so
- // we'll keep it one more than actual index
- for (HeapIndex i = count; i > 0; --i) {
- if (data[i-1] == ind_item) {
- return ConstIterator(*this, i-1);
- }
- }
- return cend();
- }
-
- // reverse find -- start looking from bottom of heap
- ConstIterator rfind(const T& item) const {
- // HeapIndex is unsigned, so we can't allow to go negative; so
- // we'll keep it one more than actual index
- for (HeapIndex i = count; i > 0; --i) {
- if (*data[i-1] == item) {
- return ConstIterator(*this, i-1);
- }
- }
- return cend();
- }
-
- void promote(T& item) {
- sift_up(item.*heap_info);
- }
-
- void demote(T& item) {
- sift_down(item.*heap_info);
- }
-
- void adjust(T& item) {
- sift(item.*heap_info);
- }
-
- Iterator begin() {
- return Iterator(*this, 0);
- }
-
- Iterator end() {
- return Iterator(*this, count);
- }
-
- ConstIterator cbegin() const {
- return ConstIterator(*this, 0);
- }
-
- ConstIterator cend() const {
- return ConstIterator(*this, count);
- }
-
- friend std::ostream& operator<<(std::ostream& out, const IndIntruHeap& h) {
- auto i = h.data.cbegin();
- if (i != h.data.cend()) {
- out << **i;
- ++i;
- while (i != h.data.cend()) {
- out << ", " << **i;
- }
- }
- return out;
- }
-
- // can only be called if I is copyable; copies heap into a vector
- // and sorts it before displaying it
- std::ostream&
- display_sorted(std::ostream& out,
- std::function<bool(const T&)> filter = all_filter) const {
- static_assert(std::is_copy_constructible<I>::value,
- "cannot call display_sorted when class I is not copy"
- " constructible");
- auto compare = [this] (const I first, const I second) -> bool {
- return this->comparator(*first, *second);
- };
- std::vector<I> copy(data);
- std::sort(copy.begin(), copy.end(), compare);
-
- bool first = true;
- for (auto c = copy.begin(); c != copy.end(); ++c) {
- if (filter(**c)) {
- if (!first) {
- out << ", ";
- } else {
- first = false;
- }
- out << **c;
- }
- }
-
- return out;
- }
-
-
- protected:
-
- static IndIntruHeapData& intru_data_of(I& item) {
- return (*item).*heap_info;
- }
-
- void remove(HeapIndex i) {
- std::swap(data[i], data[--count]);
- intru_data_of(data[i]) = i;
- data.pop_back();
-
- // the following needs to be sift (and not sift_down) as it can
- // go up or down the heap; imagine the heap vector contains 0,
- // 10, 100, 20, 30, 200, 300, 40; then 200 is removed, and 40
- // would have to be sifted upwards
- // sift(i);
- sift(i);
- }
-
- // default value of filter parameter to display_sorted
- static bool all_filter(const T& data) { return true; }
-
- // when i is negative?
- static inline HeapIndex parent(HeapIndex i) {
- assert(0 != i);
- return (i - 1) / K;
- }
-
- // index of left child when K==2, index of left-most child when K>2
- static inline HeapIndex lhs(HeapIndex i) { return K*i + 1; }
-
- // index of right child when K==2, index of right-most child when K>2
- static inline HeapIndex rhs(HeapIndex i) { return K*i + K; }
-
- void sift_up(HeapIndex i) {
- while (i > 0) {
- HeapIndex pi = parent(i);
- if (!comparator(*data[i], *data[pi])) {
- break;
- }
-
- std::swap(data[i], data[pi]);
- intru_data_of(data[i]) = i;
- intru_data_of(data[pi]) = pi;
- i = pi;
- }
- } // sift_up
-
- // use this sift_down definition when K>2; it's more general and
- // uses a loop; EnableBool insures template uses a template
- // parameter
- template<bool EnableBool=true>
- typename std::enable_if<(K>2)&&EnableBool,void>::type sift_down(HeapIndex i) {
- if (i >= count) return;
- while (true) {
- HeapIndex li = lhs(i);
-
- if (li < count) {
- HeapIndex ri = std::min(rhs(i), count - 1);
-
- // find the index of min. child
- HeapIndex min_i = li;
- for (HeapIndex k = li + 1; k <= ri; ++k) {
- if (comparator(*data[k], *data[min_i])) {
- min_i = k;
- }
- }
-
- if (comparator(*data[min_i], *data[i])) {
- std::swap(data[i], data[min_i]);
- intru_data_of(data[i]) = i;
- intru_data_of(data[min_i]) = min_i;
- i = min_i;
- } else {
- // no child is smaller
- break;
- }
- } else {
- // no children
- break;
- }
- }
- } // sift_down
-
- // use this sift_down definition when K==2; EnableBool insures
- // template uses a template parameter
- template<bool EnableBool=true>
- typename std::enable_if<K==2&&EnableBool,void>::type sift_down(HeapIndex i) {
- if (i >= count) return;
- while (true) {
- const HeapIndex li = lhs(i);
- const HeapIndex ri = 1 + li;
-
- if (li < count) {
- if (comparator(*data[li], *data[i])) {
- if (ri < count && comparator(*data[ri], *data[li])) {
- std::swap(data[i], data[ri]);
- intru_data_of(data[i]) = i;
- intru_data_of(data[ri]) = ri;
- i = ri;
- } else {
- std::swap(data[i], data[li]);
- intru_data_of(data[i]) = i;
- intru_data_of(data[li]) = li;
- i = li;
- }
- } else if (ri < count && comparator(*data[ri], *data[i])) {
- std::swap(data[i], data[ri]);
- intru_data_of(data[i]) = i;
- intru_data_of(data[ri]) = ri;
- i = ri;
- } else {
- // no child is smaller
- break;
- }
- } else {
- // no children
- break;
- }
- } // while
- } // sift_down
-
- void sift(HeapIndex i) {
- if (i == 0) {
- // if we're at top, can only go down
- sift_down(i);
- } else {
- HeapIndex pi = parent(i);
- if (comparator(*data[i], *data[pi])) {
- // if we can go up, we will
- sift_up(i);
- } else {
- // otherwise we'll try to go down
- sift_down(i);
- }
- }
- } // sift
- }; // class IndIntruHeap
-
-} // namespace crimson
Code Review / stor4nfv.git / blobdiff