monotone.h

Go to the documentation of this file.

#pragma once

 
#include <pixie/detail/serialization.h>
#include <pixie/integer_vector.h>
#include <pixie/memory_usage.h>
#include <pixie/serialization.h>
 
#include <array>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <span>
#include <stdexcept>
#include <utility>
 
namespace pixie {

template <class Vector>
  requires requires { typename Vector::value_type; } &&
               IntegerVectorValue<typename Vector::value_type> &&
               std::derived_from<
                   Vector,
                   IntegerVectorBase<Vector, typename Vector::value_type>>
class MonotoneIntegerVector
    : public MonotoneIntegerVectorBase<MonotoneIntegerVector<Vector>,
                                       typename Vector::value_type>,
      public SerializationBase<MonotoneIntegerVector<Vector>> {
 public:
  using value_type = typename Vector::value_type;

  using size_type = std::size_t;

  explicit MonotoneIntegerVector(Vector vector) : vector_(std::move(vector)) {
    validate_monotone();
  }

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

  value_type value_at_impl(size_type position) const {
    return vector_[position];
  }

  void copy_to_impl(size_type begin, std::span<value_type> output) const {
    vector_.copy_to(begin, output);
  }

  size_type memory_usage_bytes_impl() const
    requires requires(const Vector& vector) {
      { vector.memory_usage_bytes() } -> std::convertible_to<size_type>;
    }
  {
    return sizeof(*this) + nested_owned_memory_bytes(vector_);
  }

  size_type lower_bound_index_impl(value_type x) const {
    return partition_point_index([x](value_type value) { return value < x; });
  }

  size_type upper_bound_index_impl(value_type x) const {
    return partition_point_index([x](value_type value) { return value <= x; });
  }

  void serialize_impl(BinaryWriter& writer) const
    requires Serializable<Vector>
  {
    if (writer.size_bytes() % alignof(std::uint64_t) != 0) {
      throw std::invalid_argument(
          "Monotone integer-vector serialization requires an aligned offset");
    }
    const std::size_t artifact_begin = writer.size_bytes();
    detail::write_magic(writer, kSerializationMagic);
    writer.write_u32(kSerializationVersion);
    writer.write_u32(0);
    const std::size_t size_position = writer.write_u64_placeholder();
    vector_.serialize(writer);
    writer.patch_u64(size_position, static_cast<std::uint64_t>(
                                        writer.size_bytes() - artifact_begin));
  }

  static MonotoneIntegerVector deserialize_impl(
      BinaryReader& reader,
      DeserializationValidation validation = DeserializationValidation::kQuick)
    requires Deserializable<Vector, DeserializationValidation>
  {
    BinaryReader candidate = reader;
    const std::size_t available_size = candidate.remaining();
    detail::require_magic(candidate, kSerializationMagic);
    if (candidate.read_u32() != kSerializationVersion ||
        candidate.read_u32() != 0) {
      throw std::invalid_argument(
          "Incompatible serialized monotone integer vector");
    }
    const std::size_t artifact_size = detail::checked_artifact_size(
        candidate.read_u64(), kSerializationHeaderBytes, available_size);
    BinaryReader payload =
        candidate.read_subreader(artifact_size - kSerializationHeaderBytes);
    Vector vector = Vector::deserialize(payload, validation);
    payload.require_zero_padding(0);
 
    MonotoneIntegerVector result(std::move(vector), TrustedTag{});
    if (validation == DeserializationValidation::kFull) {
      result.validate_monotone();
    }
    reader = candidate;
    return result;
  }
 
 private:
  struct TrustedTag {};
 
  inline static constexpr std::array<std::uint8_t, 8> kSerializationMagic = {
      'P', 'X', 'M', 'O', 'N', 'O', 'V', '1'};
  static constexpr std::uint32_t kSerializationVersion = 1;
  static constexpr std::size_t kSerializationHeaderBytes = 24;
 
  MonotoneIntegerVector(Vector vector, TrustedTag)
      : vector_(std::move(vector)) {}
 
  template <class GoesBefore>
  size_type partition_point_index(GoesBefore goes_before) const {
    size_type first = 0;
    size_type count = vector_.size();
    while (count != 0) {
      const size_type step = count / 2;
      const size_type middle = first + step;
      if (goes_before(vector_[middle])) {
        first = middle + 1;
        count -= step + 1;
      } else {
        count = step;
      }
    }
    return first;
  }
 
  void validate_monotone() const {
    const size_type size = vector_.size();
    if (size == 0) {
      return;
    }
    value_type previous = vector_[0];
    for (size_type i = 1; i < size; ++i) {
      const value_type value = vector_[i];
      if (value < previous) {
        throw std::invalid_argument(
            "Monotone integer vector contains a decreasing pair");
      }
      previous = value;
    }
  }
 
  Vector vector_;
};
 
}  // namespace pixie