flow_binary_heap.h

Go to the documentation of this file.

#pragma once
#include "flow_polymorphic_allocator.h"
#include "flow_vector.h"
#include <cassert>
#include <concepts>
#include <memory>
#include <type_traits>
#include <utility>
 
namespace flow {

  template <typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<>>
  class BinaryHeap {
  public:
    using value_type = T;
    using reference = T&;
    using const_reference = const T&;
    using pointer = T*;
    using const_pointer = const T*;
    using iterator = T*;
    using const_iterator = const T*;
    using difference_type = std::ptrdiff_t;
    using allocator_type = std::allocator_traits<Allocator>::template rebind_alloc<T>;
 
  private:
    using container_type = Vector<T, Allocator>;
    container_type data_;
    Compare comparator_;
 
  public:
    constexpr BinaryHeap() 
      noexcept(noexcept(container_type()) && noexcept(Compare()))
      requires std::default_initializable<Compare>
      : data_(), comparator_() {
    }

    explicit constexpr BinaryHeap(const allocator_type& allocator)
      noexcept(noexcept(container_type(allocator)) && noexcept(Compare()))
      requires std::default_initializable<Compare>
      : data_(allocator), comparator_() {
    }

    explicit constexpr BinaryHeap(Compare comparator, const allocator_type& allocator = {})
      noexcept(noexcept(container_type(allocator)) && noexcept(Compare(std::move(comparator))))
      requires !std::default_initializable<Compare>
      : data_(allocator), comparator_(std::move(comparator)) {
    }
 
    constexpr BinaryHeap(const BinaryHeap&) = default;
    constexpr BinaryHeap(const BinaryHeap& rhs, const allocator_type& allocator)
      : data_(rhs.data_, allocator), comparator_(rhs.comparator_) {
    }
 
    constexpr BinaryHeap(BinaryHeap&&) = default;
    constexpr BinaryHeap(BinaryHeap&& rhs, const allocator_type& allocator)
      noexcept(noexcept(container_type(std::move(rhs.data_), allocator)) && noexcept(Compare(std::move(rhs.comparator_))))
      : data_(std::move(rhs.data_), allocator), comparator_(std::move(rhs.comparator_)) {
    }

    template <std::input_iterator It>
    constexpr BinaryHeap(It first, It last, const allocator_type& allocator = {})
      : data_(first, last, allocator), comparator_() {
      heapify();
    }

    template <std::input_iterator It>
    constexpr BinaryHeap(It first, It last, Compare comparator, const allocator_type& allocator = {})
      : data_(first, last, allocator), comparator_(std::move(comparator)) {
      heapify();
    }
 
    ~BinaryHeap() = default;
 
    // Allocator.
    allocator_type get_allocator() const noexcept {
      return data_.get_allocator();
    }
 
    // Accessor.

    constexpr std::size_t size() const noexcept {
      return data_.size();
    }

    constexpr std::size_t capacity() const noexcept {
      return data_.capacity();
    }

    constexpr bool empty() const noexcept {
      return data_.empty();
    }

    const T& top() const noexcept {
      assert(!data_.empty() && "call top on an empty heap");
      return data_.front();
    }

    void clear() noexcept {
      data_.clear();
    }

    void reserve(std::size_t capacity) {
      data_.reserve(capacity);
    }

    void push(const T& value) {
      emplace(value);
    }

    void push(T&& value) {
      emplace(std::move(value));
    }

    template <typename ...Args>
    void emplace(Args&&... args) {
      data_.emplaceBack(std::forward<Args>(args)...);
      T value = std::move(data_.back());
      fixUp(data_.size() - 1, 0, std::move(value));
    }

    void drop() 
      noexcept(std::is_nothrow_move_assignable_v<T>) {
      assert(!data_.empty() && "call drop on an empty heap");
      std::size_t index = fixDownWithHole(0);
      fixUp(index, 0, std::move(data_.back()));
      data_.popBack();
    }

    T pop() 
      noexcept(std::is_nothrow_move_constructible_v<T> && std::is_nothrow_move_assignable_v<T>) {
      assert(!data_.empty() && "call pop on an empty heap");
      T value = std::move(data_.front());
      drop();
      return value;
    }
 
  private:
    // Fix down by repeatedly choosing the less child.
    // Return the index of the hole at the bottom.
    std::size_t fixDownWithHole(std::size_t index)
      noexcept(std::is_nothrow_move_assignable_v<T>) {
      for (;;) {
        size_t child = getLeftChild(index);
        if (child >= data_.size()) {
          break;
        }
 
        // Select the less child.
        std::size_t rightChild = child + 1;
        if (rightChild < data_.size() && comparator_(data_[rightChild], data_[child])) {
          child = rightChild;
        }
        data_[index] = std::move(data_[child]);
        index = child;
      }
      return index;
    }
 
    // Fix up the value.
    void fixUp(std::size_t index, std::size_t top, T&& value) 
      noexcept(std::is_nothrow_move_assignable_v<T>) {
      while (index > top) {
        std::size_t parent = getParent(index);
        if (comparator_(value, data_[parent])) {
          data_[index] = std::move(data_[parent]);
          index = parent;
        } else {
          break;
        }
      }
      data_[index] = std::move(value);
    }
 
    void heapify() 
      noexcept(std::is_nothrow_move_constructible_v<T>&& std::is_nothrow_move_assignable_v<T>) {
      if (data_.size() < 2) {
        return;
      }
      for (std::size_t i = data_.size() / 2; i-- > 0 ;) {
        T value = std::move(data_[i]);
        std::size_t hole = fixDownWithHole(i);
        fixUp(hole, i, std::move(value));
      }
    }
 
    static constexpr bool hasParent(std::size_t i) noexcept {
      return i > 0;
    }
 
    static constexpr std::size_t getParent(std::size_t i) noexcept {
      assert(i > 0 && "calling parent on the root node");
      return (i - 1) / 2;
    }
 
    static constexpr std::size_t getLeftChild(std::size_t i) noexcept {
      return i * 2 + 1;
    }
  };
}