permutation.h

#pragma once
 
#include <pixie/permutation.h>
#include <pixie/permutations/detail/packed_value_block.h>
#include <pixie/permutations/detail/sequence_tree.h>
 
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <ranges>
#include <span>
#include <stdexcept>
#include <type_traits>
 
namespace pixie {

template <class Index = std::uint64_t,
          std::size_t StorageBits = 2048,
          std::size_t Fanout = 8,
          LengthLayout Layout = LengthLayout::cumulative>
class Permutation
    : public PermutationBase<Permutation<Index, StorageBits, Fanout, Layout>,
                             Index> {
  friend class PermutationBase<Permutation, Index>;
  using block_type = permutations::detail::PackedValueBlock<Index, StorageBits>;
  using tree_type =
      permutations::detail::SequenceTree<block_type, Fanout, Layout, true>;
  static_assert(std::is_integral_v<Index> && std::is_unsigned_v<Index> &&
                !std::is_same_v<Index, bool> &&
                std::numeric_limits<Index>::digits <= 64);
 
 public:
  Permutation() noexcept = default;
  Permutation(const Permutation&) = delete;
  Permutation& operator=(const Permutation&) = delete;
  Permutation(Permutation&& other) noexcept = default;
  Permutation& operator=(Permutation&& other) noexcept = default;
 
  // Stream identity blocks without a full temporary index vector.
  template <class Pred>
  std::size_t lower_bound(Pred pred) const {
    return tree_.lower_bound(pred);
  }

  struct MemoryUsage {
    std::size_t blocks = 0;
    std::size_t nodes = 0;
    std::size_t payload_capacity_bytes = 0;
    std::size_t block_metadata_bytes = 0;
    std::size_t ordering_tree_bytes = 0;
    std::size_t tag_padding_bytes = 0;
    std::size_t facade_bytes = sizeof(Permutation);
    std::size_t total_bytes = sizeof(Permutation);
  };

  MemoryUsage memory_usage() const noexcept {
    using Untagged =
        permutations::detail::SequenceTree<block_type, Fanout, Layout>;
    const auto tree = tree_.memory_usage();
    MemoryUsage result;
    result.blocks = tree.blocks;
    result.nodes = tree.nodes;
    result.payload_capacity_bytes = tree_type::saturated_multiply(
        tree.blocks, block_type{}.payload_capacity_bytes());
    result.block_metadata_bytes = tree_type::saturated_multiply(
        tree.blocks, block_type{}.metadata_bytes());
    result.ordering_tree_bytes =
        tree_type::saturated_multiply(tree.nodes, Untagged::node_storage_bytes);
    result.tag_padding_bytes = tree_type::saturated_add(
        tree_type::saturated_multiply(
            tree.blocks, tree_type::block_storage_bytes - sizeof(block_type)),
        tree_type::saturated_multiply(
            tree.nodes,
            tree_type::node_storage_bytes - Untagged::node_storage_bytes));
    result.total_bytes = tree_type::saturated_add(
        sizeof(*this),
        tree_type::saturated_add(tree.block_bytes, tree.node_bytes));
    return result;
  }
#ifdef PIXIE_SEQUENCE_TREE_TESTING
  const tree_type& test_tree() const noexcept { return tree_; }
#endif
 
 private:
  static Permutation identity_impl(std::size_t n) {
    check_domain(n);
    const auto count =
        n / block_type::capacity + (n % block_type::capacity != 0);
    auto blocks =
        std::views::iota(std::size_t{0}, count) |
        std::views::transform([n](std::size_t block) {
          std::array<Index, block_type::capacity> fields;
          const auto start = block * block_type::capacity;
          const auto length = std::min(block_type::capacity, n - start);
          for (std::size_t i = 0; i < length; ++i) {
            fields[i] = static_cast<Index>(start + i);
          }
          return block_type(std::span<const Index>(fields.data(), length));
        });
    Permutation result;
    result.tree_ = tree_type::from_blocks(blocks);
    return result;
  }
  std::size_t size_impl() const noexcept { return tree_.size(); }
  Index value_at_impl(std::size_t position) const { return tree_[position]; }
  void insert_at_impl(std::size_t position) {
    if (position > tree_.size()) {
      throw std::out_of_range("Permutation: insert position");
    }
    check_domain(tree_.size() + 1);
    tree_.insert_at(position, static_cast<Index>(tree_.size()));
  }
  void rotate_left_impl(std::size_t left,
                        std::size_t right,
                        std::size_t distance) {
    tree_.rotate_left(left, right, distance);
  }
  // Validate the resulting index domain before rebasing the donor.
  void merge_impl(Permutation& donor) {
    if (this == &donor || donor.empty()) {
      return;
    }
    if (donor.size() > std::numeric_limits<std::size_t>::max() - this->size()) {
      throw std::length_error("Permutation: concatenation size");
    }
    check_domain(this->size() + donor.size());
    tree_.merge_rebased(donor.tree_);
  }
  std::size_t memory_usage_bytes_impl() const noexcept {
    return memory_usage().total_bytes;
  }
  static void check_domain(std::size_t n) {
    if (n != 0 && n - 1 > std::numeric_limits<Index>::max()) {
      throw std::length_error("Permutation: index domain");
    }
  }
  tree_type tree_;
};
 
}  // namespace pixie