Immutable, structurally-shared rope over a sequence of Char. More...

#include <tpl_rope.H>

Collaboration diagram for Aleph::Rope< Char, LeafSize >:

Classes
struct	Node

Public Types
using	View = std::basic_string_view< Char >
	View type accepted by the constructor and compared against.

Public Member Functions
	Rope () noexcept=default
	Construct the empty rope.

	Rope (const View v)
	Construct a rope holding a copy of `v`'s characters.

	Rope (const Rope &other)=default
	Copy constructor: O(1), shares the entire tree (immutable, so sharing is always safe).

Rope &	operator= (const Rope &other)=default
	Copy assignment operator: O(1), shares the entire tree.

	Rope (Rope &&other) noexcept=default
	Move constructor.

Rope &	operator= (Rope &&other) noexcept=default
	Move assignment operator.

	~Rope ()=default
	Destructor: releases this rope's reference to its tree; nodes are only actually freed once no rope shares them anymore.

size_t	size () const noexcept
	Return the number of characters in this rope.

bool	is_empty () const noexcept
	Check whether this rope holds no characters.

Char	at (const size_t pos) const
	Return the character at `pos`.

Rope	concat (const Rope &other) const
	Return a new rope that is `*this` followed by `other`.

Rope	substr (const size_t pos, const size_t len) const
	Return a new rope holding `[pos, pos+len)` of `*this`.

Rope	insert (const size_t pos, const Rope &other) const
	Return a new rope with `other` inserted at `pos`.

Rope	erase (const size_t pos, const size_t len) const
	Return a new rope with `[pos, pos+len)` removed.

Array< Char >	flatten () const
	Return every character of this rope as an independent Array.

std::basic_string< Char >	to_string () const
	Return every character of this rope as a `std::basic_string`.

bool	operator== (const Rope &other) const
	Equality: `true` iff both ropes have the same length and the same characters in the same order (structural/identity sharing is irrelevant to this comparison).

bool	verify () const noexcept
	Check this rope's internal structural invariants.

Private Types
using	NodePtr = std::shared_ptr< const Node >

Private Member Functions
	Rope (NodePtr root) noexcept

Static Private Member Functions
static NodePtr	make_leaf (SmallVector< Char, LeafSize > data)

static NodePtr	make_internal_node (NodePtr left, NodePtr right)
	Raw construction of an internal node from two already-built, non-null subtrees: no rebalancing, just `length`/`depth` bookkeeping.

static NodePtr	make_internal (NodePtr left, NodePtr right)
	Wrap two non-null subtrees in a new internal node, then rebalance if the result is deeper than `is_balanced()` allows.

static NodePtr	try_absorb_right (const NodePtr &node, const SmallVector< Char, LeafSize > &extra)
	Try to merge `extra` into the rightmost leaf of `node`, sharing every other node unchanged.

static NodePtr	try_absorb_left (const NodePtr &node, const SmallVector< Char, LeafSize > &extra)
	Mirror of `try_absorb_right`: merge `extra` into the leftmost leaf of `node`, for the "prepend one small piece at a time" pattern.

static NodePtr	concat_nodes (NodePtr left, NodePtr right)
	Concatenate two (possibly null/empty) subtrees.

static bool	is_balanced (const Node *node) noexcept
	Generous upper bound on the depth a subtree of the given `length` should have if reasonably balanced – see the file-level "Rebalancing" note for why this (rather than the classical Fibonacci-threshold test) was chosen for this first version.

static void	collect_leaves (const NodePtr &node, Array< NodePtr > &out)

static void	collect_leaf_pointers (const Node node, Array< const Node > &out)
	Read-only counterpart of `collect_leaves`: collects raw, non-owning `const Node *` instead of `NodePtr` (`shared_ptr<const Node>`).

static NodePtr	build_balanced_from_leaves (const Array< NodePtr > &leaves, const size_t lo, const size_t hi)

static NodePtr	maybe_rebalance (NodePtr node)

static NodePtr	build_from_view (const View v)
	Build a balanced tree of leaves directly from a flat view, splitting at the midpoint recursively.

static const Char &	char_at (const Node *node, size_t pos) noexcept

static NodePtr	slice (const NodePtr &node, size_t pos, size_t len)
	Extract `[pos, pos+len)` from `node` (whose own length is assumed to be `>= pos+len`) as a new, independently-rooted subtree.

static void	flatten_into (const Node *node, Array< Char > &out)

static void	string_append_into (const Node *node, std::basic_string< Char > &out)
	Like `flatten_into`, but appends directly into a `std::basic_string` (one bulk `append` per leaf) instead of an `Array<Char>`, so `to_string()` does not need a separate `Array<Char>` -> `string` copy pass.

static bool	verify_rec (const Node *node) noexcept
	Recursive structural-invariant check backing the public `verify()`.

Private Attributes
NodePtr	root_

Detailed Description

template<typename Char = char, size_t LeafSize = 256>
class Aleph::Rope< Char, LeafSize >

Immutable, structurally-shared rope over a sequence of Char.

See the file-level documentation in tpl_rope.H for the full design rationale, structure, and rebalancing contract.

Template Parameters

Char Character type stored (default char). Treated as an opaque fixed-width code unit; no Unicode awareness. Must be a trivial, standard-layout type: View is std::basic_string_view<Char>, which the standard library itself requires this of (see <string_view>'s own static_assert). One consequence: Char's copy can never throw (a trivial copy constructor cannot run user code), so Rope's only real exception source is allocation failure (std::bad_alloc), not anything Char-related.

LeafSize Maximum number of characters per leaf node (default 256). Larger values mean fewer, bigger leaves (cheaper to build, costlier to slice at a boundary inside one); smaller values mean more structural sharing granularity at the cost of more nodes.

Definition at line 175 of file tpl_rope.H.

Member Typedef Documentation

◆ NodePtr

template<typename Char = char, size_t LeafSize = 256>

using Aleph::Rope< Char, LeafSize >::NodePtr = std::shared_ptr<const Node>

private

Definition at line 213 of file tpl_rope.H.

◆ View

template<typename Char = char, size_t LeafSize = 256>

using Aleph::Rope< Char, LeafSize >::View = std::basic_string_view<Char>

View type accepted by the constructor and compared against.

Definition at line 181 of file tpl_rope.H.

Constructor & Destructor Documentation

◆ Rope() [1/5]

template<typename Char = char, size_t LeafSize = 256>

Aleph::Rope< Char, LeafSize >::Rope ( NodePtr root )

inlineexplicitprivatenoexcept

Definition at line 616 of file tpl_rope.H.

◆ Rope() [2/5]

template<typename Char = char, size_t LeafSize = 256>

Aleph::Rope< Char, LeafSize >::Rope ( )

defaultnoexcept

Construct the empty rope.

Exceptions

Nothing.

Referenced by Aleph::Rope< Char, LeafSize >::concat(), and Aleph::Rope< Char, LeafSize >::substr().

◆ Rope() [3/5]

template<typename Char = char, size_t LeafSize = 256>

Aleph::Rope< Char, LeafSize >::Rope ( const View v )

inlineexplicit

Construct a rope holding a copy of v's characters.

Parameters

[in] v Characters to copy in.

Exceptions

std::bad_alloc.

Definition at line 628 of file tpl_rope.H.

◆ Rope() [4/5]

template<typename Char = char, size_t LeafSize = 256>

Aleph::Rope< Char, LeafSize >::Rope ( const Rope< Char, LeafSize > & other )

default

Copy constructor: O(1), shares the entire tree (immutable, so sharing is always safe).

Parameters

[in] other Rope to copy.

Exceptions

Nothing.

◆ Rope() [5/5]

template<typename Char = char, size_t LeafSize = 256>

Aleph::Rope< Char, LeafSize >::Rope ( Rope< Char, LeafSize > && other )

defaultnoexcept

Move constructor.

Parameters

[in] other Rope to move from; left empty afterwards.

Exceptions

Nothing.

◆ ~Rope()

template<typename Char = char, size_t LeafSize = 256>

Aleph::Rope< Char, LeafSize >::~Rope ( )

default

Destructor: releases this rope's reference to its tree; nodes are only actually freed once no rope shares them anymore.

Member Function Documentation

◆ at()

template<typename Char = char, size_t LeafSize = 256>

Char Aleph::Rope< Char, LeafSize >::at ( const size_t pos ) const

inline

Return the character at pos.

Parameters

[in] pos Zero-based index.

Returns: The character at pos.

Precondition: pos < size().

Exceptions

std::out_of_range if pos >= size().

Note: O(depth), and depth is O(log size()) per the rebalancing contract.

Definition at line 683 of file tpl_rope.H.

References ah_out_of_range_error_if, Aleph::Rope< Char, LeafSize >::char_at(), Aleph::Rope< Char, LeafSize >::root_, and Aleph::Rope< Char, LeafSize >::size().

Referenced by TEST().

◆ build_balanced_from_leaves()

template<typename Char = char, size_t LeafSize = 256>

static NodePtr Aleph::Rope< Char, LeafSize >::build_balanced_from_leaves	(	const Array< NodePtr > &	leaves,
		const size_t	lo,
		const size_t	hi
	)

inlinestaticprivate

Definition at line 414 of file tpl_rope.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Rope< Char, LeafSize >::build_balanced_from_leaves(), and Aleph::Rope< Char, LeafSize >::make_internal_node().

Referenced by Aleph::Rope< Char, LeafSize >::build_balanced_from_leaves(), and Aleph::Rope< Char, LeafSize >::maybe_rebalance().

◆ build_from_view()

template<typename Char = char, size_t LeafSize = 256>

static NodePtr Aleph::Rope< Char, LeafSize >::build_from_view ( const View v )

inlinestaticprivate

Build a balanced tree of leaves directly from a flat view, splitting at the midpoint recursively.

Used by the constructor: since it never produces an unbalanced intermediate node, no maybe_rebalance() call is needed here.

Definition at line 462 of file tpl_rope.H.

References Aleph::SmallVector< T, N >::append_range(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Rope< Char, LeafSize >::build_from_view(), Aleph::Rope< Char, LeafSize >::make_internal_node(), and Aleph::Rope< Char, LeafSize >::make_leaf().

Referenced by Aleph::Rope< Char, LeafSize >::build_from_view().

◆ char_at()

template<typename Char = char, size_t LeafSize = 256>

static const Char & Aleph::Rope< Char, LeafSize >::char_at	(	const Node *	node,
		size_t	pos
	)

inlinestaticprivatenoexcept

Definition at line 481 of file tpl_rope.H.

References Aleph::blossom_maximum_cardinality_matching().

Referenced by Aleph::Rope< Char, LeafSize >::at().

◆ collect_leaf_pointers()

template<typename Char = char, size_t LeafSize = 256>

static void Aleph::Rope< Char, LeafSize >::collect_leaf_pointers	(	const Node *	node,
		Array< const Node * > &	out
	)

inlinestaticprivate

Read-only counterpart of collect_leaves: collects raw, non-owning const Node * instead of NodePtr (shared_ptr<const Node>).

operator== is the only caller – it only ever reads leaf character data during the comparison, never needs to extend any node's lifetime beyond it (the two ropes' own root_/other.root_ already keep every visited node alive for the whole call), so collecting owning shared_ptrs there would pay for an atomic refcount increment and decrement per leaf for no benefit – real traffic for a rope with many leaves. maybe_rebalance still uses the owning collect_leaves above, since it genuinely needs the NodePtrs themselves as the rebuilt tree's new owning children.

Definition at line 403 of file tpl_rope.H.

References Aleph::Rope< Char, LeafSize >::collect_leaf_pointers(), Aleph::Rope< Char, LeafSize >::Node::is_leaf(), Aleph::Rope< Char, LeafSize >::Node::left, out, and Aleph::Rope< Char, LeafSize >::Node::right.

Referenced by Aleph::Rope< Char, LeafSize >::collect_leaf_pointers(), and Aleph::Rope< Char, LeafSize >::operator==().

◆ collect_leaves()

template<typename Char = char, size_t LeafSize = 256>

static void Aleph::Rope< Char, LeafSize >::collect_leaves	(	const NodePtr &	node,
		Array< NodePtr > &	out
	)

inlinestaticprivate

Definition at line 381 of file tpl_rope.H.

References Aleph::Rope< Char, LeafSize >::collect_leaves(), and out.

Referenced by Aleph::Rope< Char, LeafSize >::collect_leaves(), and Aleph::Rope< Char, LeafSize >::maybe_rebalance().

◆ concat()

template<typename Char = char, size_t LeafSize = 256>

Rope Aleph::Rope< Char, LeafSize >::concat ( const Rope< Char, LeafSize > & other ) const

inline

Return a new rope that is *this followed by other.

Parameters

[in] other Rope to append.

Returns: The concatenated rope. Neither *this nor other is modified.

Exceptions

std::bad_alloc.
std::overflow_error	if `size() + other.size()` would exceed `std::numeric_limits<size_t>::max()`. Not just a theoretical concern: structural sharing makes this reachable with very little real memory, e.g. `r = r.concat(r)` doubles `size()` each call at O(1) real cost, so ~64 such calls reach the limit. Checked before the addition, never wraps silently.

Note: O(1) when neither side is a lone leaf. Otherwise O(depth + LeafSize) for the leaf-absorption fast path – the O(depth) spine walk plus an O(LeafSize) copy of the leaf being grown, so a larger LeafSize makes each such concat proportionally more expensive, not cheaper – plus the (amortized, occasional) cost of rebalancing; see the file-level "Rebalancing" and "Leaf absorption" notes.

Definition at line 708 of file tpl_rope.H.

References Aleph::Rope< Char, LeafSize >::Rope(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Rope< Char, LeafSize >::concat_nodes(), and Aleph::Rope< Char, LeafSize >::root_.

Referenced by Aleph::Rope< Char, LeafSize >::erase(), Aleph::Rope< Char, LeafSize >::insert(), TEST(), TEST(), and TEST().

◆ concat_nodes()

template<typename Char = char, size_t LeafSize = 256>

static NodePtr Aleph::Rope< Char, LeafSize >::concat_nodes	(	NodePtr	left,
		NodePtr	right
	)

inlinestaticprivate

Concatenate two (possibly null/empty) subtrees.

Definition at line 343 of file tpl_rope.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Rope< Char, LeafSize >::make_internal(), Aleph::Rope< Char, LeafSize >::try_absorb_left(), and Aleph::Rope< Char, LeafSize >::try_absorb_right().

Referenced by Aleph::Rope< Char, LeafSize >::concat(), and Aleph::Rope< Char, LeafSize >::slice().

◆ erase()

template<typename Char = char, size_t LeafSize = 256>

Rope Aleph::Rope< Char, LeafSize >::erase	(	const size_t	pos,
		const size_t	len
	)		const

inline

Return a new rope with [pos, pos+len) removed.

Parameters

[in]	pos	Start index.
[in]	len	Number of characters to remove.

Returns: substr(0, pos) + substr(pos+len, size()-pos-len).

Precondition: pos <= size() and len <= size() - pos.

Exceptions

std::out_of_range if pos + len > size().

Note: O(1) when len == 0: the current rope is returned by sharing its root. Otherwise this is two substr calls plus one concat: see each method's own @note for their individual costs – typically O(log size()) overall, subject to the same rebalance-triggered worst case substr documents. Same strong exception-safety argument as insert(): a failure partway through leaves *this untouched.

Definition at line 775 of file tpl_rope.H.

References ah_out_of_range_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Rope< Char, LeafSize >::concat(), Aleph::Rope< Char, LeafSize >::size(), and Aleph::Rope< Char, LeafSize >::substr().

Referenced by TEST().

◆ flatten()

template<typename Char = char, size_t LeafSize = 256>

Array< Char > Aleph::Rope< Char, LeafSize >::flatten ( ) const

inline

Return every character of this rope as an independent Array.

Returns: Array<Char> holding a copy of all characters, in order.

Exceptions

std::bad_alloc or std::overflow_error (from Array::reserve() when size() is extremely large).

Note: O(size()). Works for any Char, unlike to_string().

Definition at line 790 of file tpl_rope.H.

References Aleph::Rope< Char, LeafSize >::flatten_into(), Aleph::Array< T >::reserve(), Aleph::Rope< Char, LeafSize >::root_, and Aleph::Rope< Char, LeafSize >::size().

Referenced by TEST().

◆ flatten_into()

template<typename Char = char, size_t LeafSize = 256>

static void Aleph::Rope< Char, LeafSize >::flatten_into	(	const Node *	node,
		Array< Char > &	out
	)

inlinestaticprivate

Definition at line 558 of file tpl_rope.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Rope< Char, LeafSize >::flatten_into(), Aleph::Rope< Char, LeafSize >::Node::is_leaf(), Aleph::Rope< Char, LeafSize >::Node::leaf_data, Aleph::Rope< Char, LeafSize >::Node::left, out, and Aleph::Rope< Char, LeafSize >::Node::right.

Referenced by Aleph::Rope< Char, LeafSize >::flatten(), and Aleph::Rope< Char, LeafSize >::flatten_into().

◆ insert()

template<typename Char = char, size_t LeafSize = 256>

Rope Aleph::Rope< Char, LeafSize >::insert	(	const size_t	pos,
		const Rope< Char, LeafSize > &	other
	)		const

inline

Return a new rope with other inserted at pos.

Parameters

[in]	pos	Insertion index.
[in]	other	Rope to insert.

Returns: substr(0, pos) + other + substr(pos, size() - pos).

Precondition: pos <= size().

Exceptions

std::out_of_range if pos > size().

Note: O(1) when other is empty: the current rope is returned by sharing its root. Otherwise this is two substr calls plus two concat calls: see each method's own @note for their individual costs – typically O(log size()) overall, subject to the same rebalance-triggered worst case substr documents. If this throws (std::bad_alloc from any component call), *this and other are left completely unchanged: every intermediate result here is a new, independent Rope value, so a failure partway through never touches the receiver or the argument.

Definition at line 753 of file tpl_rope.H.

References ah_out_of_range_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Rope< Char, LeafSize >::concat(), Aleph::Rope< Char, LeafSize >::size(), and Aleph::Rope< Char, LeafSize >::substr().

Referenced by TEST(), and TEST().

◆ is_balanced()

template<typename Char = char, size_t LeafSize = 256>

static bool Aleph::Rope< Char, LeafSize >::is_balanced ( const Node * node )

inlinestaticprivatenoexcept

Generous upper bound on the depth a subtree of the given length should have if reasonably balanced – see the file-level "Rebalancing" note for why this (rather than the classical Fibonacci-threshold test) was chosen for this first version.

Definition at line 372 of file tpl_rope.H.

Referenced by Aleph::Rope< Char, LeafSize >::maybe_rebalance().

◆ is_empty()

template<typename Char = char, size_t LeafSize = 256>

bool Aleph::Rope< Char, LeafSize >::is_empty ( ) const

inlinenoexcept

Check whether this rope holds no characters.

Returns: true if size() == 0.

Exceptions

Nothing.

Definition at line 670 of file tpl_rope.H.

References Aleph::Rope< Char, LeafSize >::root_.

◆ make_internal()

template<typename Char = char, size_t LeafSize = 256>

static NodePtr Aleph::Rope< Char, LeafSize >::make_internal	(	NodePtr	left,
		NodePtr	right
	)

inlinestaticprivate

Wrap two non-null subtrees in a new internal node, then rebalance if the result is deeper than is_balanced() allows.

Never called with a null left/right – callers (concat_nodes) handle the "one side is the empty rope" case by returning the other side directly.

Definition at line 257 of file tpl_rope.H.

References Aleph::Rope< Char, LeafSize >::make_internal_node(), and Aleph::Rope< Char, LeafSize >::maybe_rebalance().

Referenced by Aleph::Rope< Char, LeafSize >::concat_nodes().

◆ make_internal_node()

template<typename Char = char, size_t LeafSize = 256>

static NodePtr Aleph::Rope< Char, LeafSize >::make_internal_node	(	NodePtr	left,
		NodePtr	right
	)

inlinestaticprivate

Raw construction of an internal node from two already-built, non-null subtrees: no rebalancing, just length/depth bookkeeping.

Shared by every call site that assembles an internal node from scratch (make_internal, build_balanced_from_leaves, build_from_view) so the bookkeeping can't drift between them.

Definition at line 232 of file tpl_rope.H.

References ah_overflow_error_if.

Referenced by Aleph::Rope< Char, LeafSize >::build_balanced_from_leaves(), Aleph::Rope< Char, LeafSize >::build_from_view(), and Aleph::Rope< Char, LeafSize >::make_internal().

◆ make_leaf()

template<typename Char = char, size_t LeafSize = 256>

static NodePtr Aleph::Rope< Char, LeafSize >::make_leaf ( SmallVector< Char, LeafSize > data )

inlinestaticprivate

Definition at line 217 of file tpl_rope.H.

References Aleph::SmallVector< T, N >::size().

Referenced by Aleph::Rope< Char, LeafSize >::build_from_view(), Aleph::Rope< Char, LeafSize >::slice(), Aleph::Rope< Char, LeafSize >::try_absorb_left(), and Aleph::Rope< Char, LeafSize >::try_absorb_right().

◆ maybe_rebalance()

template<typename Char = char, size_t LeafSize = 256>

static NodePtr Aleph::Rope< Char, LeafSize >::maybe_rebalance ( NodePtr node )

inlinestaticprivate

Definition at line 425 of file tpl_rope.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Rope< Char, LeafSize >::build_balanced_from_leaves(), Aleph::Rope< Char, LeafSize >::collect_leaves(), Aleph::Rope< Char, LeafSize >::is_balanced(), and FunctionalMethods< Container, T >::length().

Referenced by Aleph::Rope< Char, LeafSize >::make_internal().

◆ operator=() [1/2]

template<typename Char = char, size_t LeafSize = 256>

Rope & Aleph::Rope< Char, LeafSize >::operator= ( const Rope< Char, LeafSize > & other )

default

Copy assignment operator: O(1), shares the entire tree.

Parameters

[in] other Rope to copy.

Returns: *this, now sharing other's tree.

Exceptions

Nothing.

◆ operator=() [2/2]

template<typename Char = char, size_t LeafSize = 256>

Rope & Aleph::Rope< Char, LeafSize >::operator= ( Rope< Char, LeafSize > && other )

defaultnoexcept

Move assignment operator.

Parameters

[in] other Rope to move from; left empty afterwards.

Returns: *this, now holding other's former tree.

Exceptions

Nothing.

◆ operator==()

template<typename Char = char, size_t LeafSize = 256>

bool Aleph::Rope< Char, LeafSize >::operator== ( const Rope< Char, LeafSize > & other ) const

inline

Equality: true iff both ropes have the same length and the same characters in the same order (structural/identity sharing is irrelevant to this comparison).

Parameters

[in] other Rope to compare against.

Returns: true if the two ropes hold identical character sequences.

Exceptions

std::bad_alloc or std::overflow_error (from reserving temporary leaf arrays), and anything Char::operator== may throw.

Note: O(size()): collects each side's leaves once (O(number of leaves) extra space) and then walks both leaf sequences in lock-step, comparing each pair of overlapping ranges directly – never re-descending from the root the way per-index at() calls would. A leaf pair that is the very same shared node (structural sharing, aligned leaf boundaries) is skipped without touching its characters at all.

Definition at line 840 of file tpl_rope.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::Rope< Char, LeafSize >::collect_leaf_pointers(), Aleph::Rope< Char, LeafSize >::Node::leaf_data, Aleph::Rope< Char, LeafSize >::Node::length, Aleph::Array< T >::reserve(), Aleph::Rope< Char, LeafSize >::root_, and Aleph::Rope< Char, LeafSize >::size().

◆ size()

template<typename Char = char, size_t LeafSize = 256>

size_t Aleph::Rope< Char, LeafSize >::size ( ) const

inlinenoexcept

Return the number of characters in this rope.

Returns: Character count.

Exceptions

Nothing.

Definition at line 661 of file tpl_rope.H.

References Aleph::Rope< Char, LeafSize >::root_.

Referenced by Aleph::Rope< Char, LeafSize >::at(), Aleph::Rope< Char, LeafSize >::erase(), Aleph::Rope< Char, LeafSize >::flatten(), Aleph::Rope< Char, LeafSize >::insert(), Aleph::Rope< Char, LeafSize >::operator==(), Aleph::Rope< Char, LeafSize >::substr(), TEST(), and Aleph::Rope< Char, LeafSize >::to_string().

◆ slice()

template<typename Char = char, size_t LeafSize = 256>

static NodePtr Aleph::Rope< Char, LeafSize >::slice	(	const NodePtr &	node,
		size_t	pos,
		size_t	len
	)

inlinestaticprivate

Extract [pos, pos+len) from node (whose own length is assumed to be >= pos+len) as a new, independently-rooted subtree.

Whole children are returned by shared_ptr copy (O(1), no data touched); only children straddling the [pos, pos+len) boundary are recursed into.

Definition at line 505 of file tpl_rope.H.

References Aleph::and, Aleph::SmallVector< T, N >::append_range(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Rope< Char, LeafSize >::concat_nodes(), Aleph::Rope< Char, LeafSize >::make_leaf(), and Aleph::Rope< Char, LeafSize >::slice().

Referenced by Aleph::Rope< Char, LeafSize >::slice(), and Aleph::Rope< Char, LeafSize >::substr().

◆ string_append_into()

template<typename Char = char, size_t LeafSize = 256>

static void Aleph::Rope< Char, LeafSize >::string_append_into	(	const Node *	node,
		std::basic_string< Char > &	out
	)

inlinestaticprivate

Like flatten_into, but appends directly into a std::basic_string (one bulk append per leaf) instead of an Array<Char>, so to_string() does not need a separate Array<Char> -> string copy pass.

Definition at line 576 of file tpl_rope.H.

References out, and Aleph::Rope< Char, LeafSize >::string_append_into().

Referenced by Aleph::Rope< Char, LeafSize >::string_append_into(), and Aleph::Rope< Char, LeafSize >::to_string().

◆ substr()

template<typename Char = char, size_t LeafSize = 256>

Rope Aleph::Rope< Char, LeafSize >::substr	(	const size_t	pos,
		const size_t	len
	)		const

inline

Return a new rope holding [pos, pos+len) of *this.

Parameters

[in]	pos	Start index.
[in]	len	Number of characters to extract.

Returns: The extracted subrope.

Precondition: pos <= size() and len <= size() - pos.

Exceptions

std::out_of_range if pos + len > size() (or pos > size()).

Note: O(log size()) typical case: whole shared subtrees are reused, only the boundary leaves are copied/sliced. A range that straddles a node's children is rejoined via concat_nodes, which – like any other concat – can trigger a rebalance if the rejoined result exceeds the depth threshold; when that happens the affected rejoin costs up to O(number of leaves in the extracted range) instead of O(1), so the true worst case is closer to O(len / LeafSize) than O(log size()). Still far cheaper than copying the whole rope, but not a hard O(log n) guarantee for every possible range.

Definition at line 730 of file tpl_rope.H.

References Aleph::Rope< Char, LeafSize >::Rope(), ah_out_of_range_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Rope< Char, LeafSize >::root_, Aleph::Rope< Char, LeafSize >::size(), and Aleph::Rope< Char, LeafSize >::slice().

Referenced by Aleph::Rope< Char, LeafSize >::erase(), and Aleph::Rope< Char, LeafSize >::insert().

◆ to_string()

template<typename Char = char, size_t LeafSize = 256>

std::basic_string< Char > Aleph::Rope< Char, LeafSize >::to_string ( ) const

inline

Return every character of this rope as a std::basic_string.

Returns: std::basic_string<Char> holding a copy of all characters.

Exceptions

std::bad_alloc.
std::length_error	if `size()` exceeds `std::basic_string<Char>::max_size()`. Unlike a `std::string` built the ordinary way, a `Rope` can reach a `size()` far beyond what any real string could hold while using very little actual memory (structural sharing – see the overflow guard in `make_internal_node`), so this is reachable in practice, not just a theoretical bound.

Note: O(size()). Only available when Char has a std::char_traits specialization (char, wchar_t, char8_t, char16_t, char32_t); use flatten() for other Char types.

Definition at line 813 of file tpl_rope.H.

References ah_length_error_if, Aleph::Rope< Char, LeafSize >::root_, Aleph::Rope< Char, LeafSize >::size(), and Aleph::Rope< Char, LeafSize >::string_append_into().

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ try_absorb_left()

template<typename Char = char, size_t LeafSize = 256>

static NodePtr Aleph::Rope< Char, LeafSize >::try_absorb_left	(	const NodePtr &	node,
		const SmallVector< Char, LeafSize > &	extra
	)

inlinestaticprivate

Mirror of try_absorb_right: merge extra into the leftmost leaf of node, for the "prepend one small piece at a time" pattern.

The same depth-preservation argument applies, symmetrically on left.

Definition at line 313 of file tpl_rope.H.

References ah_overflow_error_if, Aleph::SmallVector< T, N >::append_range(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Rope< Char, LeafSize >::make_leaf(), and Aleph::Rope< Char, LeafSize >::try_absorb_left().

Referenced by Aleph::Rope< Char, LeafSize >::concat_nodes(), and Aleph::Rope< Char, LeafSize >::try_absorb_left().

◆ try_absorb_right()

template<typename Char = char, size_t LeafSize = 256>

static NodePtr Aleph::Rope< Char, LeafSize >::try_absorb_right	(	const NodePtr &	node,
		const SmallVector< Char, LeafSize > &	extra
	)

inlinestaticprivate

Try to merge extra into the rightmost leaf of node, sharing every other node unchanged.

Returns an empty NodePtr if node is null or its rightmost leaf has no spare room for extra (the caller then falls back to a normal concat). This never changes any node's depth: by induction on the recursion, node->right is replaced by a new_right of the exact same depth (base case: leaf -> leaf, depth 0; inductive case: new_right's own recursive call already preserved its depth) while node->left is shared verbatim – so 1 + max(depth(left), depth(new_right)) equals node->depth exactly, regardless of which side held the max (see concat_nodes for why this means absorption never needs maybe_rebalance).

Definition at line 273 of file tpl_rope.H.

References ah_overflow_error_if, Aleph::SmallVector< T, N >::append_range(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Rope< Char, LeafSize >::make_leaf(), and Aleph::Rope< Char, LeafSize >::try_absorb_right().

Referenced by Aleph::Rope< Char, LeafSize >::concat_nodes(), and Aleph::Rope< Char, LeafSize >::try_absorb_right().

◆ verify()

template<typename Char = char, size_t LeafSize = 256>

bool Aleph::Rope< Char, LeafSize >::verify ( ) const

inlinenoexcept

Check this rope's internal structural invariants.

Debug/test helper, not part of the regular contract – mirrors the verify()/check_invariants() self-checks other Aleph-w tree types expose (tpl_radix_tree.H, tpl_patricia_trie.H, tpl_rb_tree.H, tpl_avl.H). Content-only tests (comparing to_string() against a reference) cannot detect a violation of these invariants, since none of them are individually observable through the public API; calling verify() after mutating operations in a test gives that coverage directly.

Returns: true if every leaf's length matches its stored data and is in [1, LeafSize]; every internal node has two non-null children; every internal node's length equals the sum of its children's; and every internal node's depth equals 1 + max(child depths).

Exceptions

Nothing.

Note: O(number of distinct nodes) for an ordinarily-built rope. Does not deduplicate shared subtrees while recursing, so for a rope built by extreme self-sharing (e.g. repeated r = r.concat(r)) it walks every root-to-leaf path rather than every distinct node – up to O(2^depth) instead of O(depth) for that specific construction pattern. Not a concern for ordinary usage (sharing between otherwise-independent ropes, the common case) – only for a rope that shares itself with itself many levels deep.

Definition at line 927 of file tpl_rope.H.

References Aleph::Rope< Char, LeafSize >::root_, and Aleph::Rope< Char, LeafSize >::verify_rec().

Referenced by TEST(), TEST(), TEST(), and TEST().

◆ verify_rec()

template<typename Char = char, size_t LeafSize = 256>

static bool Aleph::Rope< Char, LeafSize >::verify_rec ( const Node * node )

inlinestaticprivatenoexcept

Recursive structural-invariant check backing the public verify().

Checks, at every node: a leaf has a non-null leaf_data whose length matches its stored data and is in [1, LeafSize] (leaves are never empty – no code path ever builds one); an internal node holds no leaf_data (see the Node::leaf_data comment: only leaves ever pay for a buffer) and has two non-null children, length equal to the sum of its children's, and depth equal to 1 + max(child depths).

Definition at line 598 of file tpl_rope.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), and Aleph::Rope< Char, LeafSize >::verify_rec().

Referenced by Aleph::Rope< Char, LeafSize >::verify(), and Aleph::Rope< Char, LeafSize >::verify_rec().

Member Data Documentation

◆ root_

template<typename Char = char, size_t LeafSize = 256>

NodePtr Aleph::Rope< Char, LeafSize >::root_

private

Definition at line 215 of file tpl_rope.H.

Referenced by Aleph::Rope< Char, LeafSize >::at(), Aleph::Rope< Char, LeafSize >::concat(), Aleph::Rope< Char, LeafSize >::flatten(), Aleph::Rope< Char, LeafSize >::is_empty(), Aleph::Rope< Char, LeafSize >::operator==(), Aleph::Rope< Char, LeafSize >::size(), Aleph::Rope< Char, LeafSize >::substr(), Aleph::Rope< Char, LeafSize >::to_string(), and Aleph::Rope< Char, LeafSize >::verify().

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

tpl_rope.H

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ NodePtr

◆ View

Constructor & Destructor Documentation

◆ Rope() [1/5]

◆ Rope() [2/5]

◆ Rope() [3/5]

◆ Rope() [4/5]

◆ Rope() [5/5]

◆ ~Rope()

Member Function Documentation

◆ at()

◆ build_balanced_from_leaves()

◆ build_from_view()

◆ char_at()

◆ collect_leaf_pointers()

◆ collect_leaves()

◆ concat()

◆ concat_nodes()

◆ erase()

◆ flatten()

◆ flatten_into()

◆ insert()

◆ is_balanced()

◆ is_empty()

◆ make_internal()

◆ make_internal_node()

◆ make_leaf()

◆ maybe_rebalance()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ size()

◆ slice()

◆ string_append_into()

◆ substr()

◆ to_string()

◆ try_absorb_left()

◆ try_absorb_right()

◆ verify()

◆ verify_rec()

Member Data Documentation

◆ root_