sparse_table.h

#pragma once
 
#include <pixie/memory_usage.h>
#include <pixie/rmq.h>
#include <pixie/storage/aligned.h>
 
#include <algorithm>
#include <bit>
#include <cstddef>
#include <functional>
#include <limits>
#include <memory>
#include <new>
#include <numeric>
#include <span>
#include <stdexcept>
#include <vector>
 
namespace pixie::rmq {

template <class T,
          class Compare = std::less<T>,
          class Index = std::size_t,
          std::size_t Alignment = pixie::kAlignedStorageLineBytes>
class SparseTable
    : public RmqBase<SparseTable<T, Compare, Index, Alignment>, T> {
 public:
  static constexpr std::size_t npos =
      RmqBase<SparseTable<T, Compare, Index, Alignment>, T>::npos;
  static constexpr Index invalid_index = std::numeric_limits<Index>::max();

  SparseTable() = default;

  explicit SparseTable(std::span<const T> values, Compare compare = Compare())
      : values_(values), compare_(compare) {
    build();
  }

  std::size_t size_impl() const { return values_.size(); }

  T value_at_impl(std::size_t position) const { return values_[position]; }

  std::size_t arg_min_impl(std::size_t left, std::size_t right) const {
    if (left >= right || right > values_.size()) {
      return npos;
    }
    const std::size_t length = right - left;
    const std::size_t level = std::bit_width(length) - 1;
    const std::size_t span = std::size_t{1} << level;
    const std::size_t first = table_[level][left];
    const std::size_t second = table_[level][right - span];
    return better(first, second);
  }

  std::size_t memory_usage_bytes_impl() const {
    std::size_t bytes = sizeof(*this);
    bytes += pixie::vector_capacity_bytes(table_);
    for (const TableLevel& level : table_) {
      bytes += pixie::vector_capacity_bytes(level);
    }
    return bytes;
  }
 
 private:
  std::size_t better(std::size_t left, std::size_t right) const {
    if (compare_(values_[right], values_[left])) {
      return right;
    }
    if (compare_(values_[left], values_[right])) {
      return left;
    }
    return std::min(left, right);
  }

  Index build_better(Index left, Index right) const {
    return compare_(values_[right], values_[left]) ? right : left;
  }

  void build() {
    table_.clear();
    if (values_.empty()) {
      return;
    }
    if (values_.size() > static_cast<std::size_t>(invalid_index)) {
      throw std::length_error("RMQ sparse table index type is too small");
    }
 
    table_.reserve(std::bit_width(values_.size()));
    table_.emplace_back(values_.size());
    std::iota(table_[0].begin(), table_[0].end(), Index{0});
 
    for (std::size_t span = 2, half = 1; span <= values_.size();
         half = span, span <<= 1) {
      const std::size_t level = table_.size();
      table_.emplace_back(values_.size() - span + 1);
      for (std::size_t i = 0; i < table_[level].size(); ++i) {
        table_[level][i] = static_cast<Index>(
            build_better(table_[level - 1][i], table_[level - 1][i + half]));
      }
    }
  }
 
  template <class Value, std::size_t AllocationAlignment>
  class AlignedAllocator {
   public:
    static_assert(AllocationAlignment >= alignof(Value));
    static_assert((AllocationAlignment & (AllocationAlignment - 1)) == 0);
 
    using value_type = Value;
 
    AlignedAllocator() = default;
 
    template <class Other>
    AlignedAllocator(
        const AlignedAllocator<Other, AllocationAlignment>&) noexcept {}
 
    [[nodiscard]] Value* allocate(std::size_t count) {
      if (count == 0) {
        return nullptr;
      }
      if (count > std::numeric_limits<std::size_t>::max() / sizeof(Value)) {
        throw std::bad_array_new_length();
      }
      return static_cast<Value*>(::operator new(
          count * sizeof(Value), std::align_val_t{AllocationAlignment}));
    }
 
    void deallocate(Value* pointer, std::size_t) noexcept {
      ::operator delete(pointer, std::align_val_t{AllocationAlignment});
    }
 
    template <class Other>
    bool operator==(
        const AlignedAllocator<Other, AllocationAlignment>&) const noexcept {
      return true;
    }
 
    template <class Other>
    bool operator!=(
        const AlignedAllocator<Other, AllocationAlignment>&) const noexcept {
      return false;
    }
 
    template <class Other>
    struct rebind {
      using other = AlignedAllocator<Other, AllocationAlignment>;
    };
  };
 
  template <class Value, std::size_t AllocationAlignment>
  struct LevelAllocator {
    using type = AlignedAllocator<Value, AllocationAlignment>;
  };
 
  template <class Value>
  struct LevelAllocator<Value, 0> {
    using type = std::allocator<Value>;
  };
 
  using TableLevel =
      std::vector<Index, typename LevelAllocator<Index, Alignment>::type>;
 
  std::span<const T> values_;
  Compare compare_;
  std::vector<TableLevel> table_;
};
 
}  // namespace pixie::rmq