sdsl_sct.h

#pragma once
 
#ifndef SDSL_SUPPORT
#error "pixie/rmq/sdsl_sct.h requires SDSL_SUPPORT"
#endif
 
#include <pixie/rmq.h>
 
#include <cstddef>
#include <functional>
#include <sdsl/io.hpp>
#include <sdsl/rmq_succinct_sct.hpp>
#include <span>
#include <type_traits>
 
namespace pixie::rmq {

template <class T, class Compare = std::less<T>, class Index = std::size_t>
class SdslSct : public RmqBase<SdslSct<T, Compare, Index>, T> {
 public:
  static_assert(std::is_same_v<Compare, std::less<T>>,
                "SDSL SCT RMQ wrapper supports only std::less");
 
  static constexpr std::size_t npos =
      RmqBase<SdslSct<T, Compare, Index>, T>::npos;

  SdslSct() = default;

  explicit SdslSct(std::span<const T> values, Compare compare = Compare())
      : values_(values), rmq_(&values_) {
    (void)compare;
  }

  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;
    }
    return static_cast<std::size_t>(rmq_(left, right - 1));
  }

  std::size_t memory_usage_bytes_impl() const {
    sdsl::nullstream out;
    return sizeof(*this) + static_cast<std::size_t>(rmq_.serialize(out));
  }
 
 private:
  std::span<const T> values_;
  sdsl::rmq_succinct_sct<true> rmq_;
};
 
}  // namespace pixie::rmq