rank_select.h

Go to the documentation of this file.

#pragma once

 
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <string>
 
namespace pixie {

template <class Impl>
class RankSelectBase {
 public:
  std::size_t size() const { return impl().size_impl(); }

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

  int operator[](std::size_t position) const {
    return impl().bit_impl(position);
  }

  std::uint64_t rank(std::size_t end_position) const {
    return impl().rank_impl(end_position);
  }

  std::uint64_t rank0(std::size_t end_position) const {
    if constexpr (requires { impl().rank0_impl(end_position); }) {
      return impl().rank0_impl(end_position);
    } else {
      return end_position >= size() ? size() - rank(size())
                                    : end_position - rank(end_position);
    }
  }

  std::uint64_t select(std::size_t rank) const {
    return impl().select_impl(rank);
  }

  std::uint64_t select0(std::size_t rank) const {
    return impl().select0_impl(rank);
  }

  bool supports_select1() const { return impl().supports_select1_impl(); }

  bool supports_select0() const { return impl().supports_select0_impl(); }

  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();
  }

  std::string to_string() const {
    std::string result;
    result.reserve(size());
    for (std::size_t i = 0; i < size(); ++i) {
      result.push_back((*this)[i] ? '1' : '0');
    }
    return result;
  }
 
 private:
  const Impl& impl() const { return static_cast<const Impl&>(*this); }
};
 
}  // namespace pixie