rmq.h

Go to the documentation of this file.

#pragma once

 
#include <concepts>
#include <cstddef>
#include <limits>
 
namespace pixie::rmq {

template <class Impl, class Value>
class RmqBase {
 public:
  static constexpr std::size_t npos = std::numeric_limits<std::size_t>::max();

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

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

  std::size_t arg_min(std::size_t left, std::size_t right) const {
    return impl().arg_min_impl(left, right);
  }

  Value range_min(std::size_t left, std::size_t right) const {
    const std::size_t position = arg_min(left, right);
    if (position == npos) {
      return Value{};
    }
    return impl().value_at_impl(position);
  }

  std::size_t memory_usage_bytes() const
    requires requires(const Impl& concrete) {
      {
        concrete.memory_usage_bytes_impl()
      } -> std::convertible_to<std::size_t>;
    }
  {
    return impl().memory_usage_bytes_impl();
  }
 
 private:
  const Impl& impl() const { return static_cast<const Impl&>(*this); }
};
 
}  // namespace pixie::rmq