pixie::Permutation< Index, StorageBits, Fanout, Layout > Class Template Reference

Exclusively owned permutation of the integers in [0, size()). More...

#include <permutation.h>

Inheritance diagram for pixie::Permutation< Index, StorageBits, Fanout, Layout >:

Classes
struct	MemoryUsage
	Requested live storage breakdown, excluding allocator bookkeeping. More...

Public Member Functions
	Permutation () noexcept=default
	Construct empty.
	Permutation (const Permutation &)=delete
	Disallow copying.
Permutation &	operator= (const Permutation &)=delete
	Disallow copy assignment.
	Permutation (Permutation &&other) noexcept=default
	Transfer ownership without allocation.
Permutation &	operator= (Permutation &&other) noexcept=default
	Replace ownership without throwing.
template<class Pred>
std::size_t	lower_bound (Pred pred) const
	Find the first position where pred(logical_index) is true.
MemoryUsage	memory_usage () const noexcept
	Explicit linear-time live allocation accounting.
Public Member Functions inherited from pixie::PermutationBase< Permutation< std::uint64_t, 2048, 8, LengthLayout::cumulative >, std::uint64_t >
size_type	size () const noexcept
	Return the logical index count.
bool	empty () const noexcept
	Test emptiness.
const_reference	operator[] (size_type position) const
	Read a checked zero-based index by value.
void	insert_at (size_type position)
	Insert the next identity value at a zero-based position.
void	rotate_left (size_type left, size_type right, size_type distance)
	Rotate [left,right) left, preserving outside indices.
void	merge (Permutation< std::uint64_t, 2048, 8, LengthLayout::cumulative > &donor)
	Append donor indices plus the old receiver size and consume donor.
size_type	memory_usage_bytes () const noexcept
	Explicitly account for requested live storage.

Friends
class	PermutationBase< Permutation, Index >

Additional Inherited Members
Public Types inherited from pixie::PermutationBase< Permutation< std::uint64_t, 2048, 8, LengthLayout::cumulative >, std::uint64_t >
using	value_type
	Stored index type.
using	const_reference
	Immutable read result.
using	size_type
	Count and position type.
Static Public Member Functions inherited from pixie::PermutationBase< Permutation< std::uint64_t, 2048, 8, LengthLayout::cumulative >, std::uint64_t >
static Permutation< std::uint64_t, 2048, 8, LengthLayout::cumulative >	identity (size_type n)
	Construct an owning identity permutation.

Detailed Description

template<class Index = std::uint64_t, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative>
class pixie::Permutation< Index, StorageBits, Fanout, Layout >

Exclusively owned permutation of the integers in [0, size()).

Construction is identity-only. Rotations preserve the bijection; consuming merge appends donor entries plus the old receiver size. Fixed-width indices never widen. Reads return values, not references. Access, rotation, and merge use logarithmic tree work plus bounded local re-encoding; identity construction and explicit memory accounting are linear. No public arbitrary import, split, element assignment, or value addition is provided. Allocation failure leaves existing containers unchanged, including pending lazy index biases. Single-leaf and eligible complete-child rotations are nonallocating; general rotations use transactional split/join with bounded leaf work. Default leaves use 256-byte blocks with 1920 payload bits, wrapped to 320 bytes for lazy tags/alignment; F8 tagged nodes use 192 bytes on 64-bit hosts versus 128 untagged. Metadata is not promised strictly succinct. There is no whole-container contiguous buffer. Internal detail types are unsupported.

Template Parameters

Index	Unsigned integer, excluding bool, with at most 64 value bits.
StorageBits	Complete packed block budget, excluding tagged wrappers.
Fanout	Even tree fanout of at least four.
Layout	Cumulative or individual child measures.

Constructor & Destructor Documentation

Permutation() [1/3]

template<class Index = std::uint64_t, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative>

pixie::Permutation< Index, StorageBits, Fanout, Layout >::Permutation ( )

defaultnoexcept

Construct empty.

No allocation or implicit identity data.

Permutation() [2/3]

template<class Index = std::uint64_t, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative>

pixie::Permutation< Index, StorageBits, Fanout, Layout >::Permutation ( const Permutation< Index, StorageBits, Fanout, Layout > & )

delete

Disallow copying.

Ownership is exclusive.

Permutation() [3/3]

template<class Index = std::uint64_t, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative>

pixie::Permutation< Index, StorageBits, Fanout, Layout >::Permutation ( Permutation< Index, StorageBits, Fanout, Layout > && other )

defaultnoexcept

Transfer ownership without allocation.

Source becomes canonical empty; no stored index is rewritten.

Parameters

other

Source whose ownership is consumed.

Member Function Documentation

lower_bound()

template<class Index = std::uint64_t, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative>

template<class Pred>

std::size_t pixie::Permutation< Index, StorageBits, Fanout, Layout >::lower_bound ( Pred pred ) const

inline

Find the first position where pred(logical_index) is true.

Uses the tree's guided descent: at each node children are binary-searched by their rightmost stored index, then the search descends into the single child that can contain the first match. The predicate receives the decoded logical index (pending biases applied). Caller must guarantee monotonicity: all false results precede all true results.

Parameters

pred	Predicate on Index returning true at or past the search target.

Returns

Position in [0, size()]; size() means pred is false everywhere.

memory_usage()

template<class Index = std::uint64_t, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative>

MemoryUsage pixie::Permutation< Index, StorageBits, Fanout, Layout >::memory_usage ( ) const

inlinenoexcept

Explicit linear-time live allocation accounting.

Never called implicitly during queries or mutation; visits each allocation once, with no allocation of its own.

Returns

Disjoint storage categories and total requested live bytes.

operator=() [1/2]

template<class Index = std::uint64_t, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative>

Permutation & pixie::Permutation< Index, StorageBits, Fanout, Layout >::operator= ( const Permutation< Index, StorageBits, Fanout, Layout > & )

delete

Disallow copy assignment.

Ownership is exclusive.

operator=() [2/2]

template<class Index = std::uint64_t, std::size_t StorageBits = 2048, std::size_t Fanout = 8, LengthLayout Layout = LengthLayout::cumulative>

Permutation & pixie::Permutation< Index, StorageBits, Fanout, Layout >::operator= ( Permutation< Index, StorageBits, Fanout, Layout > && other )

defaultnoexcept

Replace ownership without throwing.

Source becomes canonical empty; self-move is a no-op.

Parameters

other

Source whose ownership replaces this owner's storage.

Returns

This owner after replacement.

---

The documentation for this class was generated from the following file:

• include/pixie/permutations/permutation.h