sdsl.h

#pragma once
 
#ifndef SDSL_SUPPORT
#error "SdslRankSelectSupport requires PIXIE_THIRD_PARTY_BACKENDS"
#endif
 
#include <pixie/rank_select.h>
 
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <limits>
// SDSL undefines ALIGNMENT; preserve the optional 3-star configuration.
#pragma push_macro("ALIGNMENT")
#include <sdsl/int_vector.hpp>
#include <sdsl/rank_support_v.hpp>
#include <sdsl/select_support_mcl.hpp>
#pragma pop_macro("ALIGNMENT")
#include <span>
 
namespace pixie {

class SdslRankSelectSupport : public RankSelectBase<SdslRankSelectSupport> {
 public:
  explicit SdslRankSelectSupport(std::span<const std::uint64_t> source_words,
                                 std::size_t num_bits)
      : bits_(copy_source(source_words, num_bits)),
        rank_(&bits_),
        select1_(&bits_),
        select0_(&bits_),
        one_count_(bits_.empty() ? 0 : rank_(bits_.size())) {}
 
  SdslRankSelectSupport(const SdslRankSelectSupport&) = delete;
  SdslRankSelectSupport& operator=(const SdslRankSelectSupport&) = delete;
  SdslRankSelectSupport(SdslRankSelectSupport&&) = delete;
  SdslRankSelectSupport& operator=(SdslRankSelectSupport&&) = delete;

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

  int bit_impl(std::size_t position) const { return bits_[position]; }

  std::uint64_t rank_impl(std::size_t end) const {
    return end >= size() ? one_count_ : rank_(end);
  }

  std::uint64_t select_impl(std::size_t occurrence) const {
    return occurrence == 0           ? 0
           : occurrence > one_count_ ? size()
                                     : select1_(occurrence);
  }

  std::uint64_t select0_impl(std::size_t occurrence) const {
    return occurrence == 0                    ? 0
           : occurrence > size() - one_count_ ? size()
                                              : select0_(occurrence);
  }

  bool supports_select1_impl() const { return true; }

  bool supports_select0_impl() const { return true; }

  std::size_t source_copy_bytes() const { return bits_.bit_capacity() / 8; }

  std::size_t index_logical_bytes() const {
    return sizeof(*this) + sdsl::size_in_bytes(rank_) +
           sdsl::size_in_bytes(select1_) + sdsl::size_in_bytes(select0_);
  }

  std::size_t memory_usage_bytes_impl() const {
    return source_copy_bytes() + index_logical_bytes();
  }
 
 private:
  static sdsl::bit_vector copy_source(
      std::span<const std::uint64_t> source_words,
      std::size_t num_bits) {
    if (source_words.size() <= std::numeric_limits<std::size_t>::max() / 64) {
      num_bits = std::min(num_bits, source_words.size() * 64);
    }
    sdsl::bit_vector result(num_bits, 0);
    const std::size_t words = num_bits / 64 + (num_bits % 64 != 0);
    std::copy_n(source_words.begin(), words, result.data());
    if (num_bits % 64 != 0) {
      result.data()[words - 1] &= (std::uint64_t{1} << (num_bits % 64)) - 1;
    }
    return result;
  }
 
  sdsl::bit_vector bits_;
  sdsl::rank_support_v<> rank_;
  sdsl::select_support_mcl<1> select1_;
  sdsl::select_support_mcl<0> select0_;
  std::size_t one_count_;
};
 
}  // namespace pixie