sorted_sequence.h

Go to the documentation of this file.

#pragma once

 
#include <pixie/permutations/sequence.h>
 
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <ranges>
#include <utility>
 
namespace pixie {

template <class T = std::uint64_t,
          class Compare = std::less<>,
          ElementStorage Storage = ElementStorage::automatic,
          std::size_t StorageBits = 2048,
          std::size_t Fanout = 8,
          LengthLayout Layout = LengthLayout::cumulative,
          std::size_t ChunkBytes = 4096>
class SortedPermutableSequence {
 public:
  using sequence_type =
      PermutableSequence<T, Storage, StorageBits, Fanout, Layout, ChunkBytes>;
  using value_type = T;
  using const_reference = typename sequence_type::const_reference;
  using size_type = std::size_t;

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

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

  template <std::ranges::input_range Range>
    requires std::
        constructible_from<T, std::ranges::range_rvalue_reference_t<Range>>
      static SortedPermutableSequence from_range(Range&& range,
                                                 Compare compare = {}) {
    SortedPermutableSequence 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 sequence_.size(); }
  bool empty() const noexcept { return sequence_.empty(); }
  const_reference operator[](size_type position) const {
    return sequence_[position];
  }

  template <class Key>
  size_type lower_bound_index(const Key& key) const {
    return sequence_.lower_bound([&](const T& v) { return !compare_(v, key); });
  }

  template <class Key>
  size_type upper_bound_index(const Key& key) const {
    return sequence_.lower_bound([&](const T& v) { return compare_(key, v); });
  }

  size_type insert(T value) {
    const size_type position = lower_bound_index(value);
    sequence_.insert_at(position, std::move(value));
    return position;
  }

  size_type memory_usage_bytes() const noexcept {
    const size_type nested = sequence_.memory_usage_bytes() - sizeof(sequence_);
    return nested > std::numeric_limits<size_type>::max() - sizeof(*this)
               ? std::numeric_limits<size_type>::max()
               : sizeof(*this) + nested;
  }
 
 private:
  sequence_type sequence_;
  [[no_unique_address]] Compare compare_;
};
 
}  // namespace pixie