integer_vector.h

Go to the documentation of this file.

#pragma once

 
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <span>
#include <stdexcept>
#include <type_traits>
 
namespace pixie {

template <class Value>
concept IntegerVectorValue =
    std::unsigned_integral<Value> &&
    std::same_as<Value, std::remove_cv_t<Value>> &&
    !std::same_as<Value, bool> && (std::numeric_limits<Value>::digits <= 64);

template <class Impl, IntegerVectorValue Value = std::uint64_t>
class IntegerVectorBase {
 public:
  using value_type = Value;

  using size_type = std::size_t;

  size_type size() const { return impl().size_impl(); }

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

  value_type operator[](size_type position) const {
    return impl().value_at_impl(position);
  }

  value_type at(size_type position) const {
    if (position >= size()) {
      throw std::out_of_range("Integer-vector position is out of range");
    }
    return (*this)[position];
  }

  void copy_to(size_type begin, std::span<value_type> output) const {
    const size_type vector_size = size();
    if (begin > vector_size || output.size() > vector_size - begin) {
      throw std::out_of_range("Integer-vector copy range is out of bounds");
    }
    impl().copy_to_impl(begin, output);
  }

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

template <class Impl, IntegerVectorValue Value = std::uint64_t>
class MonotoneIntegerVectorBase : public IntegerVectorBase<Impl, Value> {
 public:
  using typename IntegerVectorBase<Impl, Value>::size_type;
  using typename IntegerVectorBase<Impl, Value>::value_type;

  size_type lower_bound_index(value_type x) const {
    return impl().lower_bound_index_impl(x);
  }

  size_type upper_bound_index(value_type x) const {
    return impl().upper_bound_index_impl(x);
  }

  bool contains(value_type x) const {
    const size_type position = lower_bound_index(x);
    return position != this->size() && (*this)[position] == x;
  }

  size_type count(value_type x) const {
    return upper_bound_index(x) - lower_bound_index(x);
  }
 
 private:
  const Impl& impl() const { return static_cast<const Impl&>(*this); }
};
 
}  // namespace pixie