 |
Pixie
|
|
Pixie
|
Owning, move-only tree sequence with immutable element reads. More...
#include <sequence.h>
Classes | |
| struct | MemoryUsage |
| Explicit live requested-memory breakdown, excluding allocator/RSS. More... | |
Public Types | |
| using | value_type = T |
| Stored element type. | |
| using | const_reference = typename Traits::const_reference |
| Immutable indexed result type. | |
 Public Types inherited from pixie::PermutableSequenceBase< PermutableSequence< std::uint64_t, ElementStorage::automatic, 2048, 8, LengthLayout::cumulative, 4096 >, std::uint64_t, permutations::detail::ElementStorageTraits< std::uint64_t, ElementStorage::automatic >::const_reference > | |
| using | value_type |
| Stored element type. | |
| using | const_reference |
| Immutable result type. | |
| using | size_type |
| Count and position type. | |
Public Member Functions | |
| PermutableSequence () noexcept=default | |
| Construct canonical empty. | |
| PermutableSequence (const PermutableSequence &)=delete | |
| Exclusive ownership disallows copying. | |
| PermutableSequence & | operator= (const PermutableSequence &)=delete |
| Exclusive ownership disallows copy assignment. | |
| PermutableSequence (PermutableSequence &&other) noexcept=default | |
| Transfer ownership without moving elements. | |
| PermutableSequence & | operator= (PermutableSequence &&other) noexcept |
| Replace ownership without moving elements; source becomes empty. | |
| ~PermutableSequence ()=default | |
| Destroy order nodes and iteratively reclaim all owned chunks. | |
| template<class Pred> | |
| std::size_t | lower_bound (Pred pred) const |
| Find the first position where pred(value) is true. | |
| MemoryUsage | memory_usage () const noexcept |
| Enumerate tree allocations and chunks in linear time, without writes. | |
| Public Member Functions inherited from pixie::PermutableSequenceBase< PermutableSequence< std::uint64_t, ElementStorage::automatic, 2048, 8, LengthLayout::cumulative, 4096 >, std::uint64_t, permutations::detail::ElementStorageTraits< std::uint64_t, ElementStorage::automatic >::const_reference > | |
| size_type | size () const noexcept |
| Return the logical element count. | |
| bool | empty () const noexcept |
| Test emptiness. | |
| const_reference | operator[] (size_type position) const |
| Read a checked zero-based element without exposing mutation. | |
| void | insert_at (size_type position, std::uint64_t value) |
| Insert one value at a zero-based position. | |
| void | rotate_left (size_type left, size_type right, size_type distance) |
| Rotate [left,right) left while preserving outside values. | |
| void | merge (PermutableSequence< std::uint64_t, ElementStorage::automatic, 2048, 8, LengthLayout::cumulative, 4096 > &donor) |
| Append unchanged donor values and consume donor ownership. | |
| size_type | memory_usage_bytes () const noexcept |
| Explicitly account for requested live storage. | |
Static Public Attributes | |
| static constexpr ElementStorage | storage = Traits::storage |
| Resolved compile-time storage strategy. | |
Friends | |
| class | PermutableSequenceBase< PermutableSequence, T, typename Traits::const_reference > |
Additional Inherited Members | |
| Static Public Member Functions inherited from pixie::PermutableSequenceBase< PermutableSequence< std::uint64_t, ElementStorage::automatic, 2048, 8, LengthLayout::cumulative, 4096 >, std::uint64_t, permutations::detail::ElementStorageTraits< std::uint64_t, ElementStorage::automatic >::const_reference > | |
| static PermutableSequence< std::uint64_t, ElementStorage::automatic, 2048, 8, LengthLayout::cumulative, 4096 > | from_range (Range &&range) |
| Consume a possibly single-pass input range into an owning sequence. | |
Owning, move-only tree sequence with immutable element reads.
Packed storage returns T by value. Indirect storage returns const T& and requires nonthrowing move construction and destruction, but neither default construction nor move assignment. Signed integers initially use indirect storage. Indirect rotations and concatenating merges never move payload objects after construction. References to indirect elements survive both, including references obtained from a consumed donor. They expire upon destruction of the eventual owner or replacement by move assignment.
Indirect payload lives in independent frozen vectors of actual object slots (including actual bool objects). A singly linked owning chain is spliced in O(1) after a successful order-tree merge and destroyed iteratively. Repeated small merges deliberately retain small chunks and their unused capacity; there is no compaction, contiguous-data promise, or reference rebasing. Access, rotation and merge use O(Fanout*height) tree work plus bounded local block operations. Construction, destruction and explicit accounting may be linear. Single-leaf and eligible complete-child rotations do not allocate; general rotations use transactional split/join with bounded leaf work. Default order blocks occupy 256 bytes with 1920 payload bits; untagged F8 nodes occupy 128 bytes on 64-bit hosts. Dynamic metadata is not promised strictly succinct. Internal detail types are unsupported. No public split, writable access, or serialization is provided.
| T | Unqualified object type; see storage requirements above. |
| Storage | Compile-time selection, never a runtime switch. |
| StorageBits | Complete local block budget, not whole-tree memory. |
| Fanout | Even tree fanout, at least four. |
| Layout | Representation of tree child lengths. |
| ChunkBytes | Indirect target bytes per vector, at least one T per chunk. |
| using pixie::PermutableSequence< T, Storage, StorageBits, Fanout, Layout, ChunkBytes >::const_reference = typename Traits::const_reference |
Immutable indexed result type.
T by value when packed; const T& with stable indirect ownership.
| using pixie::PermutableSequence< T, Storage, StorageBits, Fanout, Layout, ChunkBytes >::value_type = T |
Stored element type.
Identical to T, irrespective of physical representation.
|
defaultnoexcept |
Construct canonical empty.
Performs no allocation and owns no payload or tree nodes.
|
delete |
Exclusive ownership disallows copying.
This deleted operation cannot duplicate payload ownership.
|
defaultnoexcept |
Transfer ownership without moving elements.
The source becomes canonical empty, without allocation. Existing indirect references remain valid under the new owner's lifetime.
| other | Source whose ownership is consumed. |
|
default |
Destroy order nodes and iteratively reclaim all owned chunks.
Invalidates references to owned elements; does not throw.
|
inline |
Find the first position where pred(value) is true.
Uses the tree's guided descent with boundary-value pruning. The predicate receives the logical element (T by value when packed, const T& when indirect). Caller must guarantee monotonicity: all false results precede all true results.
| pred | Predicate on T returning true at or past the search target. |
|
inlinenoexcept |
Enumerate tree allocations and chunks in linear time, without writes.
Called only explicitly; merge and rotation never call accounting. Performs no allocation and does not throw. Byte arithmetic saturates at SIZE_MAX; see MemoryUsage for included and excluded allocation domains.
|
delete |
Exclusive ownership disallows copy assignment.
Transfer ownership with move assignment instead.
|
inlinenoexcept |
Replace ownership without moving elements; source becomes empty.
Self-move is a no-op. References to replaced elements expire. References to transferred indirect elements remain valid. Reclaims the old payload without recursive chunk-chain destruction; performs no allocation.
| other | Source whose ownership is consumed unless it is this object. |
|
staticconstexpr |
Resolved compile-time storage strategy.
Always packed or indirect; automatic is resolved from T.
1.13.2