cartesian_rmm.h

#pragma once

 
#include <pixie/memory_usage.h>
#include <pixie/rmm/btree.h>
#include <pixie/rmq.h>
#include <pixie/rmq/utils/succinct_monotone_stack.h>
 
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <optional>
#include <span>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <vector>
 
namespace pixie::rmq {
 
namespace detail {

template <class Index = std::size_t,
          std::size_t HighCacheLines = 4,
          std::size_t LowFanout = 32>
class RmMPlusMinusOne {
 public:
  static_assert(std::is_unsigned_v<Index>,
                "RmMPlusMinusOne index type must be unsigned");
 
  static constexpr std::size_t npos = std::numeric_limits<std::size_t>::max();
  static constexpr Index invalid_index = std::numeric_limits<Index>::max();
  static constexpr std::size_t kBlockSize =
      pixie::experimental::RmMBTree<HighCacheLines, LowFanout>::kBlockBits;
 
  RmMPlusMinusOne() = default;

  RmMPlusMinusOne(std::span<const std::uint64_t> bits,
                  std::size_t depth_count) {
    build(bits, depth_count);
  }

  RmMPlusMinusOne(std::span<const std::uint64_t> bits,
                  std::size_t depth_count,
                  std::size_t one_count) {
    build(bits, depth_count, one_count);
  }

  void build(std::span<const std::uint64_t> bits, std::size_t depth_count) {
    build(bits, depth_count, std::nullopt);
  }

  void build(std::span<const std::uint64_t> bits,
             std::size_t depth_count,
             std::optional<std::size_t> one_count) {
    words_ = bits;
    depth_count_ = depth_count;
    rmm_ = RmM();
 
    if (depth_count_ == 0) {
      return;
    }
    if (depth_count_ > static_cast<std::size_t>(invalid_index)) {
      throw std::length_error("RMQ rmM btree index type is too small");
    }
    rmm_ = RmM(words_, depth_count_ - 1,
               RankSelectSupport<>::SelectSupport::kSelect0, one_count);
  }

  std::size_t size() const { return depth_count_; }

  bool empty() const { return depth_count_ == 0; }

  std::size_t arg_min(std::size_t left, std::size_t right) const {
    if (left >= right || right > depth_count_) {
      return npos;
    }
    if (right == left + 1) {
      return left;
    }
 
    const std::size_t bit_left = left;
    const std::size_t bit_right = right - 2;
    const auto minimum_after_left =
        rmm_.range_min_query_result(bit_left, bit_right);
    if (minimum_after_left.value >= 0) {
      return left;
    }
 
    const std::size_t bit_position = minimum_after_left.position;
    return bit_position == RmM::npos ? npos : bit_position + 1;
  }

  std::size_t select0(std::size_t rank) const { return rmm_.select0(rank); }

  std::size_t rank0(std::size_t end_position) const {
    return rmm_.rank0(end_position);
  }

  std::size_t memory_usage_bytes() const {
    return sizeof(*this) + pixie::nested_owned_memory_bytes(rmm_);
  }
 
 private:
  using RmM = pixie::experimental::RmMBTree<HighCacheLines, LowFanout>;
 
  std::span<const std::uint64_t> words_;
  std::size_t depth_count_ = 0;
  RmM rmm_;
};
 
}  // namespace detail

template <class T,
          class Compare = std::less<T>,
          class Index = std::size_t,
          std::size_t HighCacheLines = 4,
          std::size_t LowFanout = 32>
class CartesianRmM
    : public RmqBase<CartesianRmM<T, Compare, Index, HighCacheLines, LowFanout>,
                     T> {
 public:
  static_assert(std::is_unsigned_v<Index>,
                "CartesianRmM index type must be unsigned");
 
  static constexpr std::size_t npos =
      RmqBase<CartesianRmM<T, Compare, Index, HighCacheLines, LowFanout>,
              T>::npos;
  static constexpr Index invalid_index = std::numeric_limits<Index>::max();
 
  CartesianRmM() = default;

  explicit CartesianRmM(std::span<const T> values, Compare compare = Compare())
      : values_(values), compare_(compare) {
    build();
  }
 
  CartesianRmM(const CartesianRmM& other)
      : values_(other.values_),
        compare_(other.compare_),
        bp_bits_(other.bp_bits_),
        bp_bit_count_(other.bp_bit_count_) {
    reset_bp_index();
  }
 
  CartesianRmM& operator=(const CartesianRmM& other) {
    if (this == &other) {
      return *this;
    }
    values_ = other.values_;
    compare_ = other.compare_;
    bp_bits_ = other.bp_bits_;
    bp_bit_count_ = other.bp_bit_count_;
    reset_bp_index();
    return *this;
  }
 
  CartesianRmM(CartesianRmM&& other) noexcept
      : values_(other.values_),
        compare_(std::move(other.compare_)),
        bp_bits_(std::move(other.bp_bits_)),
        bp_bit_count_(other.bp_bit_count_) {
    other.values_ = std::span<const T>();
    other.bp_bit_count_ = 0;
    reset_bp_index();
  }
 
  CartesianRmM& operator=(CartesianRmM&& other) noexcept {
    if (this == &other) {
      return *this;
    }
    values_ = other.values_;
    compare_ = std::move(other.compare_);
    bp_bits_ = std::move(other.bp_bits_);
    bp_bit_count_ = other.bp_bit_count_;
    other.values_ = std::span<const T>();
    other.bp_bit_count_ = 0;
    reset_bp_index();
    return *this;
  }

  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 first_close = bp_support_.select0(left + 1);
    const std::size_t last_close = bp_support_.select0(right);
    if (first_close == BpSupport::npos || last_close == BpSupport::npos ||
        first_close > last_close) {
      return npos;
    }
 
    const std::size_t shifted_min =
        bp_support_.arg_min(first_close + 1, last_close + 2);
    if (shifted_min == npos || shifted_min == 0) {
      return npos;
    }
    const std::size_t answer = bp_support_.rank0(shifted_min) - 1;
    return answer < values_.size() ? answer : npos;
  }

  std::size_t bp_bit_count() const { return bp_bit_count_; }

  std::span<const std::uint64_t> bp_words() const { return bp_bits_; }

  std::size_t memory_usage_bytes_impl() const {
    return sizeof(*this) + pixie::vector_capacity_bytes(bp_bits_) +
           pixie::nested_owned_memory_bytes(bp_support_);
  }
 
 private:
  using BpSupport = detail::RmMPlusMinusOne<Index, HighCacheLines, LowFanout>;
 
  void build() {
    bp_bits_.clear();
    bp_bit_count_ = 0;
    bp_support_ = BpSupport();
 
    if (values_.empty()) {
      return;
    }
    if (values_.size() > (static_cast<std::size_t>(invalid_index) - 1) / 2) {
      throw std::length_error("Cartesian rmM RMQ index type is too small");
    }
 
    bp_bit_count_ = 2 * values_.size();
    bp_bits_.assign((bp_bit_count_ + 63) / 64, 0);
    build_bp_bits();
    reset_bp_index();
  }
 
  void build_bp_bits() {
    utils::SuccinctIncreasingStack stack(values_.size());
    std::size_t write_position = bp_bit_count_;
    std::vector<std::uint64_t>& words = bp_bits_;
    const auto prepend_open = [&]() {
      --write_position;
      words[write_position >> 6] |= std::uint64_t{1} << (write_position & 63);
    };
 
    for (std::size_t i = values_.size(); i-- > 0;) {
      while (!stack.empty() &&
             !compare_(values_[stack_index(stack.top())], values_[i])) {
        stack.pop();
        prepend_open();
      }
      stack.push(stack_key(i));
      --write_position;
    }
 
    while (write_position != 0) {
      prepend_open();
    }
  }

  std::size_t stack_key(std::size_t value_index) const {
    return values_.size() - 1 - value_index;
  }

  std::size_t stack_index(std::size_t key) const {
    return values_.size() - 1 - key;
  }
 
  void reset_bp_index() {
    bp_support_ = BpSupport();
    if (bp_bit_count_ == 0) {
      return;
    }
    bp_support_ = BpSupport(std::span<const std::uint64_t>(bp_bits_),
                            bp_bit_count_ + 1, values_.size());
  }
 
  std::span<const T> values_;
  Compare compare_;
  std::vector<std::uint64_t> bp_bits_;
  std::size_t bp_bit_count_ = 0;
  BpSupport bp_support_;
};
 
}  // namespace pixie::rmq