StaticMinHeap.hpp

Go to the documentation of this file.

 
#pragma once
 
#include <array>
#include <cassert>
#include <cstddef>
#include <functional>
#include <utility>
 
namespace corium::internal {
 
template <
    typename T,
    std::size_t Capacity,
    typename Compare = std::greater<T>
>
class StaticMinHeap {
public:
    constexpr StaticMinHeap() = default;
 
    template <typename U>
    bool push(U&& value) {
        if (_size >= Capacity) {
            return false;
        }
 
        _data[_size] = std::forward<U>(value);
        siftUp(_size);
        _size++;
        return true;
    }
 
    bool pop() noexcept {
        if (_size == 0) {
            return false;
        }
 
        _size--;
        if (_size > 0) {
            _data[0] = std::move(_data[_size]);
            siftDown(0);
        }
        return true;
    }
 
    [[nodiscard]] const T& top() const noexcept {
        assert(_size > 0 && "Accessing top of empty StaticMinHeap");
        return _data[0];
    }
 
    [[nodiscard]] T& top() noexcept {
        assert(_size > 0 && "Accessing top of empty StaticMinHeap");
        return _data[0];
    }
 
    [[nodiscard]] constexpr std::size_t size() const noexcept {
        return _size;
    }
 
    [[nodiscard]] static constexpr std::size_t capacity() noexcept {
        return Capacity;
    }
 
    [[nodiscard]] constexpr bool empty() const noexcept {
        return _size == 0;
    }
 
    [[nodiscard]] constexpr bool full() const noexcept {
        return _size >= Capacity;
    }
 
    void clear() noexcept {
        _size = 0;
    }
 
    [[nodiscard]] T* data() noexcept {
        return _data.data();
    }
 
    [[nodiscard]] const T* data() const noexcept {
        return _data.data();
    }
 
    void siftDown(std::size_t index) noexcept {
        Compare comp;
        std::size_t current = index;
 
        while (true) {
            std::size_t left = 2 * current + 1;
            std::size_t right = 2 * current + 2;
            std::size_t smallest = current;
 
            if (left < _size && comp(_data[smallest], _data[left])) {
                smallest = left;
            }
            if (right < _size && comp(_data[smallest], _data[right])) {
                smallest = right;
            }
 
            if (smallest != current) {
                using std::swap;
                swap(_data[current], _data[smallest]);
                current = smallest;
            } else {
                break;
            }
        }
    }
 
    void siftUp(std::size_t index) noexcept {
        Compare comp;
        std::size_t current = index;
 
        while (current > 0) {
            std::size_t parent = (current - 1) / 2;
            if (comp(_data[parent], _data[current])) {
                using std::swap;
                swap(_data[parent], _data[current]);
                current = parent;
            } else {
                break;
            }
        }
    }
 
private:
    std::array<T, Capacity> _data{};
    std::size_t _size{0};
};
 
} // namespace corium::internal