sequence.h

#pragma once
 
#include <pixie/permutable_sequence.h>
#include <pixie/permutations/detail/element_storage.h>
#include <pixie/permutations/detail/packed_value_block.h>
#include <pixie/permutations/detail/payload_chunks.h>
#include <pixie/permutations/detail/pointer_block.h>
#include <pixie/permutations/detail/sequence_tree.h>
 
#include <algorithm>
#include <array>
#include <climits>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <limits>
#include <memory>
#include <new>
#include <ranges>
#include <span>
#include <type_traits>
#include <utility>
 
namespace pixie {

template <class T = std::uint64_t,
          ElementStorage Storage = ElementStorage::automatic,
          std::size_t StorageBits = 2048,
          std::size_t Fanout = 8,
          LengthLayout Layout = LengthLayout::cumulative,
          std::size_t ChunkBytes = 4096>
class PermutableSequence
    : public PermutableSequenceBase<
          PermutableSequence<T,
                             Storage,
                             StorageBits,
                             Fanout,
                             Layout,
                             ChunkBytes>,
          T,
          typename permutations::detail::ElementStorageTraits<T, Storage>::
              const_reference> {
  using Traits = permutations::detail::ElementStorageTraits<T, Storage>;
  friend class PermutableSequenceBase<PermutableSequence,
                                      T,
                                      typename Traits::const_reference>;
  static constexpr bool packed = Traits::packed;
  using Block =
      std::conditional_t<packed,
                         permutations::detail::PackedValueBlock<T, StorageBits>,
                         permutations::detail::PointerBlock<T, StorageBits>>;
  static_assert(sizeof(Block) * CHAR_BIT == StorageBits);
  using Tree = permutations::detail::SequenceTree<Block, Fanout, Layout>;
  using Chunks = permutations::detail::PayloadChunks<T>;
  using Chunk = typename Chunks::Chunk;
  using Slot = typename Chunks::Slot;
  static constexpr std::size_t chunk_capacity =
      std::max(std::size_t{1}, ChunkBytes / sizeof(T));
  struct NoChunks {};
 
 public:
  using value_type = T;
  static constexpr ElementStorage storage = Traits::storage;
  using const_reference = typename Traits::const_reference;
  PermutableSequence() noexcept = default;
  PermutableSequence(const PermutableSequence&) = delete;
  PermutableSequence& operator=(const PermutableSequence&) = delete;
  PermutableSequence(PermutableSequence&& other) noexcept = default;
  PermutableSequence& operator=(PermutableSequence&& other) noexcept {
    if (this != &other) {
      tree_ = std::move(other.tree_);
      chunks_ = std::move(other.chunks_);
    }
    return *this;
  }

  ~PermutableSequence() = default;
  template <class Pred>
  std::size_t lower_bound(Pred pred) const {
    if constexpr (packed) {
      return tree_.lower_bound(pred);
    } else {
      return tree_.lower_bound([&](const T* p) { return pred(*p); });
    }
  }

  struct MemoryUsage {
    std::size_t facade_bytes = sizeof(PermutableSequence);
    std::size_t blocks = 0;
    std::size_t nodes = 0;
    std::size_t tree_block_bytes = 0;
    std::size_t tree_node_bytes = 0;
    std::size_t order_bytes = 0;
    std::size_t packed_capacity_bits = 0;
    std::size_t chunks = 0;
    std::size_t chunk_header_bytes = 0;
    std::size_t vector_capacity_bytes = 0;
    std::size_t vector_live_bytes = 0;
    std::size_t vector_slack_bytes = 0;
    std::size_t total_bytes = sizeof(PermutableSequence);
  };

  MemoryUsage memory_usage() const noexcept {
    MemoryUsage result;
    const auto tree = tree_.memory_usage();
    result.blocks = tree.blocks;
    result.nodes = tree.nodes;
    result.tree_block_bytes = tree.block_bytes;
    result.tree_node_bytes = tree.node_bytes;
    const auto tree_bytes = add(tree.block_bytes, tree.node_bytes);
    if constexpr (packed) {
      result.packed_capacity_bits =
          multiply(multiply(tree.blocks, Block::capacity),
                   std::numeric_limits<T>::digits);
    } else {
      result.order_bytes = tree_bytes;
      for (auto* chunk = chunks_.head; chunk; chunk = chunk->next) {
        ++result.chunks;
        result.chunk_header_bytes =
            add(result.chunk_header_bytes, sizeof(Chunk));
        result.vector_capacity_bytes =
            add(result.vector_capacity_bytes,
                multiply(chunk->values.capacity(), sizeof(Slot)));
        result.vector_live_bytes =
            add(result.vector_live_bytes,
                multiply(chunk->values.size(), sizeof(Slot)));
        result.vector_slack_bytes =
            add(result.vector_slack_bytes,
                multiply(chunk->values.capacity() - chunk->values.size(),
                         sizeof(Slot)));
      }
    }
    result.total_bytes =
        add(sizeof(*this), add(tree_bytes, add(result.chunk_header_bytes,
                                               result.vector_capacity_bytes)));
    return result;
  }
#ifdef PIXIE_SEQUENCE_TREE_TESTING
  using test_tree_type = Tree;
  const Tree& test_tree() const noexcept { return tree_; }
  static void test_fail_payload_after(std::ptrdiff_t n) noexcept {
    payload_failure_ = n;
  }
#endif
 
 private:
#ifdef PIXIE_SEQUENCE_TREE_TESTING
  inline static thread_local std::ptrdiff_t payload_failure_ = -1;
#endif
  static void payload_allocation() {
#ifdef PIXIE_SEQUENCE_TREE_TESTING
    if (payload_failure_ == 0) {
      throw std::bad_alloc();
    }
    if (payload_failure_ > 0) {
      --payload_failure_;
    }
#endif
  }
  static std::size_t add(std::size_t a, std::size_t b) noexcept {
    const auto max = std::numeric_limits<std::size_t>::max();
    return b > max - a ? max : a + b;
  }
  static std::size_t multiply(std::size_t a, std::size_t b) noexcept {
    const auto max = std::numeric_limits<std::size_t>::max();
    return b && a > max / b ? max : a * b;
  }
  // Stream blocks with bounded scratch and at most one unpublished chunk.
  // Reserve each payload vector before publishing addresses; never grow it.
  template <std::ranges::input_range Range>
    requires std::
        constructible_from<T, std::ranges::range_rvalue_reference_t<Range>>
      static PermutableSequence from_range_impl(Range&& range) {
    PermutableSequence result;
    auto it = std::ranges::begin(range);
    const auto end = std::ranges::end(range);
    Chunk* current = nullptr;
    std::size_t offset = 0;
    auto has_input = [&] {
      if constexpr (packed) {
        return it != end;
      } else {
        return (current && offset < current->values.size()) || it != end;
      }
    };
    auto next_block = [&] {
      std::array<typename Block::value_type, Block::capacity> scratch;
      std::size_t count = 0;
      while (count < Block::capacity && has_input()) {
        if constexpr (packed) {
          scratch[count++] = T(std::ranges::iter_move(it));
          ++it;
        } else {
          if (!current || offset == current->values.size()) {
            payload_allocation();
            auto chunk = std::make_unique<Chunk>();
            payload_allocation();
            chunk->values.reserve(chunk_capacity);
            while (chunk->values.size() < chunk_capacity && it != end) {
              if constexpr (std::same_as<T, bool>) {
                chunk->values.emplace_back(bool(std::ranges::iter_move(it)));
              } else {
                chunk->values.emplace_back(std::ranges::iter_move(it));
              }
              ++it;
            }
            current = chunk.get();
            result.chunks_.append(chunk.release());
            offset = 0;
          }
          if constexpr (std::same_as<T, bool>) {
            scratch[count++] = std::addressof(current->values[offset++].value);
          } else {
            scratch[count++] = std::addressof(current->values[offset++]);
          }
        }
      }
      return Block(
          std::span<const typename Block::value_type>(scratch.data(), count));
    };
    // A genuine single-pass cursor: dereferencing never advances the input.
    // A transform_view would incorrectly promise an equality-preserving map.
    struct Blocks {
      decltype(next_block)& next;
      Block current;
      struct Iterator {
        using value_type [[maybe_unused]] = Block;
        using difference_type [[maybe_unused]] = std::ptrdiff_t;
        using iterator_concept [[maybe_unused]] = std::input_iterator_tag;
        Blocks* source;
        Block& operator*() const noexcept { return source->current; }
        Iterator& operator++() {
          source->current = source->next();
          return *this;
        }
        void operator++(int) { ++*this; }
        bool operator==(std::default_sentinel_t) const noexcept {
          return source->current.size() == 0;
        }
      };
      Iterator begin() {
        current = next();
        return {this};
      }
      std::default_sentinel_t end() const noexcept { return {}; }
    } blocks{next_block, {}};
    result.tree_ = Tree::from_blocks(blocks);
    return result;
  }
  std::size_t size_impl() const noexcept { return tree_.size(); }
  const_reference value_at_impl(std::size_t i) const {
    if constexpr (packed) {
      return tree_[i];
    } else {
      return *tree_[i];
    }
  }
  // Stage a payload slot before inserting its pointer. Roll back the slot
  // if tree insertion fails; publish a new chunk only after tree commit.
  void insert_at_impl(std::size_t position, T value) {
    if (position > tree_.size()) {
      throw std::out_of_range("PermutableSequence: insert position");
    }
    if constexpr (packed) {
      tree_.insert_at(position, std::move(value));
    } else {
      std::unique_ptr<Chunk> staged;
      if (!chunks_.tail || chunks_.tail->values.size() >= chunk_capacity) {
        payload_allocation();
        staged = std::make_unique<Chunk>();
        payload_allocation();
        staged->values.reserve(chunk_capacity);
      }
      auto& slots = staged ? staged->values : chunks_.tail->values;
      if constexpr (std::same_as<T, bool>) {
        slots.emplace_back(bool(std::move(value)));
      } else {
        slots.emplace_back(std::move(value));
      }
      const T* ptr;
      if constexpr (std::same_as<T, bool>) {
        ptr = std::addressof(slots.back().value);
      } else {
        ptr = std::addressof(slots.back());
      }
      try {
        tree_.insert_at(position, ptr);
      } catch (...) {
        slots.pop_back();
        throw;
      }
      if (staged) {
        chunks_.append(staged.release());
      }
    }
  }
  void rotate_left_impl(std::size_t left,
                        std::size_t right,
                        std::size_t distance) {
    tree_.rotate_left(left, right, distance);
  }
  // Commit the order tree before the nonthrowing payload-chain splice.
  void merge_impl(PermutableSequence& donor) {
    if (this == &donor) {
      return;
    }
    tree_.merge(donor.tree_);
    if constexpr (!packed) {
      chunks_.splice(donor.chunks_);
    }
  }
  std::size_t memory_usage_bytes_impl() const noexcept {
    return memory_usage().total_bytes;
  }
 
  // Declaration order destroys the pointer tree before the pointed-to objects.
  [[no_unique_address]] std::conditional_t<packed, NoChunks, Chunks> chunks_;
  Tree tree_;
};
 
}  // namespace pixie