succinct_bitvec.h

#pragma once
 
#ifndef PIXIE_SUCCINCT_BITVEC_SUPPORT
#error "SuccinctFastRankSelectSupport requires PIXIE_THIRD_PARTY_BACKENDS"
#endif
 
#include <pixie/rank_select.h>
 
#include <algorithm>
#include <bitvec.hpp>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <span>
#include <stdexcept>
 
namespace pixie {

class SuccinctFastRankSelectSupport
    : public RankSelectBase<SuccinctFastRankSelectSupport> {
 public:
  static constexpr std::uint64_t kMaxBits = std::uint64_t{1} << 32;

  explicit SuccinctFastRankSelectSupport(
      std::span<const std::uint64_t> source_words,
      std::size_t num_bits)
      : bits_(checked_size(source_words, num_bits)),
        support_(copy_source(bits_, source_words)) {}
 
  SuccinctFastRankSelectSupport(const SuccinctFastRankSelectSupport&) = delete;
  SuccinctFastRankSelectSupport& operator=(
      const SuccinctFastRankSelectSupport&) = delete;
  SuccinctFastRankSelectSupport(SuccinctFastRankSelectSupport&&) = delete;
  SuccinctFastRankSelectSupport& operator=(SuccinctFastRankSelectSupport&&) =
      delete;

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

  int bit_impl(std::size_t position) const { return bits_.get(position); }

  std::uint64_t rank_impl(std::size_t end) const {
    if (end >= size()) {
      return support_.get_total_ones();
    }
    return end == 0 ? 0 : support_.rank1(end - 1);
  }

  std::uint64_t select_impl(std::size_t occurrence) const {
    if (occurrence == 0) {
      return 0;
    }
    if (occurrence > support_.get_total_ones()) {
      return size();
    }
    return static_cast<std::uint64_t>(support_.select1(occurrence - 1));
  }

  bool supports_select1_impl() const { return true; }
  bool supports_select0_impl() const { return false; }
  std::uint64_t select0_impl(std::size_t occurrence) const {
    return occurrence == 0 ? 0 : size();
  }

  std::size_t source_copy_bytes() const {
    return bits_.words.capacity() * sizeof(std::uint64_t);
  }

  std::size_t index_logical_bytes() const {
    return sizeof(*this) + support_.overhead_bytes();
  }

  std::size_t memory_usage_bytes_impl() const {
    return index_logical_bytes() + source_copy_bytes();
  }
 
 private:
  static std::size_t checked_size(std::span<const std::uint64_t> source,
                                  std::size_t num_bits) {
    if (source.size() <= std::numeric_limits<std::size_t>::max() / 64) {
      num_bits = std::min(num_bits, source.size() * 64);
    }
    if (num_bits > kMaxBits) {
      throw std::length_error(
          "FastBitVec select samples support at most 2^32 bits");
    }
    return num_bits;
  }
 
  static const succinct::RawBits& copy_source(
      succinct::RawBits& bits,
      std::span<const std::uint64_t> source) {
    const std::size_t word_count = std::min(bits.num_words, source.size());
    std::copy_n(source.begin(), word_count, bits.words.begin());
    if (bits.len % 64 != 0) {
      bits.words.back() &= (std::uint64_t{1} << (bits.len % 64)) - 1;
    }
    return bits;
  }
 
  succinct::RawBits bits_;
  succinct::FastBitVec support_;
};
 
}  // namespace pixie