sorted_vector.h

Go to the documentation of this file.

#pragma once

 
#include <pixie/permutations/permutation.h>
 
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <ranges>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <vector>
 
namespace pixie {

template <class T = std::uint64_t,
          class Compare = std::less<>,
          class Index = std::uint64_t,
          std::size_t StorageBits = 2048,
          std::size_t Fanout = 8,
          LengthLayout Layout = LengthLayout::cumulative>
class SortedPermutationVector {
  static_assert(std::is_object_v<T> && !std::is_array_v<T> &&
                    std::same_as<T, std::remove_cv_t<T>> &&
                    !std::same_as<T, bool>,
                "SortedPermutationVector requires a non-bool object type");
 
 public:
  using permutation_type = Permutation<Index, StorageBits, Fanout, Layout>;
  using value_type = T;
  using const_reference = const T&;
  using size_type = std::size_t;

  explicit SortedPermutationVector(Compare compare = {})
      : compare_(std::move(compare)) {}

  SortedPermutationVector(const SortedPermutationVector&) = delete;
  SortedPermutationVector& operator=(const SortedPermutationVector&) = delete;
  SortedPermutationVector(SortedPermutationVector&&) = default;
  SortedPermutationVector& operator=(SortedPermutationVector&&) = default;

  template <std::ranges::input_range Range>
    requires std::
        constructible_from<T, std::ranges::range_rvalue_reference_t<Range>>
      static SortedPermutationVector from_range(Range&& range,
                                                Compare compare = {}) {
    SortedPermutationVector result(std::move(compare));
    auto it = std::ranges::begin(range);
    const auto end = std::ranges::end(range);
    for (; it != end; ++it) {
      result.insert(T(std::ranges::iter_move(it)));
    }
    return result;
  }

  size_type size() const noexcept { return permutation_.size(); }
  bool empty() const noexcept { return permutation_.empty(); }
  const_reference operator[](size_type position) const {
    return values_[permutation_[position]];
  }

  void reserve(size_type count) { values_.reserve(count); }

  template <class Key>
  size_type lower_bound_index(const Key& key) const {
    return permutation_.lower_bound(
        [&](Index idx) { return !compare_(values_[idx], key); });
  }

  template <class Key>
  size_type upper_bound_index(const Key& key) const {
    return permutation_.lower_bound(
        [&](Index idx) { return compare_(key, values_[idx]); });
  }

  size_type insert(T value) {
    const size_type position = lower_bound_index(value);
    if (values_.size() > std::numeric_limits<Index>::max()) {
      throw std::length_error("SortedPermutationVector: index domain");
    }
    values_.push_back(std::move(value));
    try {
      permutation_.insert_at(position);
    } catch (...) {
      values_.pop_back();
      throw;
    }
    return position;
  }

  size_type memory_usage_bytes() const noexcept {
    const size_type maximum = std::numeric_limits<size_type>::max();
    const size_type payload = values_.capacity() > maximum / sizeof(T)
                                  ? maximum
                                  : values_.capacity() * sizeof(T);
    const size_type permutation =
        permutation_.memory_usage_bytes() - sizeof(permutation_);
    const size_type base =
        payload > maximum - sizeof(*this) ? maximum : sizeof(*this) + payload;
    return permutation > maximum - base ? maximum : base + permutation;
  }
 
 private:
  std::vector<T> values_;
  permutation_type permutation_;
  [[no_unique_address]] Compare compare_;
};
 
}  // namespace pixie