Chunked implicit-index rope helpers.
Rope trees are ordered by position, not by comparator. Each node stores a chunk vector in the key slot and the total element count of the subtree in the value slot. Weight balancing is still performed by node count, while the subtree element counts support indexed operations.
Chunk Size Invariant (CSI) ───────────────────────── Every chunk has size in [min, target] except:
No chunk may exceed target.
This is analogous to a B-tree minimum fill factor. The rightmost exception exists because conj (the most frequent growth operation) appends to the rightmost chunk, so a short rightmost chunk is naturally filled by subsequent appends.
CSI is maintained by:
Chunked implicit-index rope helpers.
Rope trees are ordered by position, not by comparator. Each node stores a
chunk vector in the key slot and the total element count of the subtree in
the value slot. Weight balancing is still performed by node count, while the
subtree element counts support indexed operations.
Chunk Size Invariant (CSI)
─────────────────────────
Every chunk has size in [min, target] except:
- If the rope has 0 chunks: the rope is empty (root is nil).
- If the rope has 1 chunk: the chunk may be any size in [1, target].
- If the rope has >= 2 chunks: only the rightmost chunk may be smaller
than min (the 'runt'). All other chunks must be in [min, target].
No chunk may exceed target.
This is analogous to a B-tree minimum fill factor. The rightmost exception
exists because conj (the most frequent growth operation) appends to the
rightmost chunk, so a short rightmost chunk is naturally filled by
subsequent appends.
CSI is maintained by:
- rope-concat: position-aware boundary check + merge-boundary
- rope-split-at: ensure-split-parts (fringe repair on both halves)
- rope-subvec-root: ensure-left-fringe + ensure-right-fringe
- rope-conj-right: fills rightmost chunk, overflows to new node
- rope-pop-right: shrinks rightmost chunk, removes if empty
- coll->root: partition-all target produces valid chunks(byte-rope->bytes root)Materialize a byte rope tree to a single byte array via bulk arraycopy. O(n).
Materialize a byte rope tree to a single byte array via bulk arraycopy. O(n).
(byte-rope-node-create chunk _ l r)Create a rope node for byte[] chunks. The node value stores subtree byte count. This is the t-join binding for ByteRope.
Create a rope node for byte[] chunks. The node value stores subtree byte count. This is the *t-join* binding for ByteRope.
(bytes->root data)Build a rope tree from a byte array, partitioned into target-sized byte[] chunks.
Always copies the input so the tree never shares mutable state with the caller.
Uses the currently bound *target-chunk-size*.
Build a rope tree from a byte array, partitioned into target-sized byte[] chunks. Always copies the input so the tree never shares mutable state with the caller. Uses the currently bound `*target-chunk-size*`.
(chunk-count root)Number of chunk nodes in the tree.
Number of chunk nodes in the tree.
(chunks->root chunks)Build a balanced rope tree from a sequence of chunks. Empty chunks are filtered out.
Build a balanced rope tree from a sequence of chunks. Empty chunks are filtered out.
(chunks->root-csi chunks)Build a rope tree from a sequence of chunks, ensuring CSI.
Scans left to right, accumulating a current chunk. When the current
chunk reaches [min, target] it is emitted; when it would exceed target
it is split evenly. The last chunk is emitted at any size (the runt).
Uses the currently bound *target-chunk-size* and *min-chunk-size*.
Build a rope tree from a sequence of chunks, ensuring CSI. Scans left to right, accumulating a current chunk. When the current chunk reaches [min, target] it is emitted; when it would exceed target it is split evenly. The last chunk is emitted at any size (the runt). Uses the currently bound `*target-chunk-size*` and `*min-chunk-size*`.
(coll->root coll)Build a rope tree from a sequential collection, partitioned into chunks.
Uses the currently bound *target-chunk-size*.
Build a rope tree from a sequential collection, partitioned into chunks. Uses the currently bound `*target-chunk-size*`.
(ensure-split-parts [l r])Restore CSI on both halves of a split. The left half may have an undersized right fringe; the right half may have an undersized left fringe.
Restore CSI on both halves of a split. The left half may have an undersized right fringe; the right half may have an undersized left fringe.
(invariant-valid? root)(invariant-valid? root target minsz)Check that a rope root satisfies the Chunk Size Invariant:
A flat-mode root (a raw PersistentVector that some rope variants use
as a single-chunk optimization) is trivially valid when its size fits
in [0, target].
Reads the currently bound *target-chunk-size* and *min-chunk-size*,
so callers testing a particular rope variant should invoke this from
inside that variant's with-tree binding (or the 3-arity form that
takes explicit sizes).
Check that a rope root satisfies the Chunk Size Invariant: - every chunk has size in [1, target] - every chunk except the rightmost has size >= min Returns true if CSI holds, false otherwise. A flat-mode root (a raw PersistentVector that some rope variants use as a single-chunk optimization) is trivially valid when its size fits in `[0, target]`. Reads the currently bound `*target-chunk-size*` and `*min-chunk-size*`, so callers testing a particular rope variant should invoke this from inside that variant's `with-tree` binding (or the 3-arity form that takes explicit sizes).
(normalize-root root)Full O(n) rechunk of a rope tree so every chunk satisfies CSI. Note: materializes all chunks to elements and reassembles as vectors. For string ropes, use chunks->root-csi on root->chunks instead.
Accepts a flat-mode vector root as well, in which case it is rebuilt
into a balanced tree via coll->root.
Full O(n) rechunk of a rope tree so every chunk satisfies CSI. Note: materializes all chunks to elements and reassembles as vectors. For string ropes, use chunks->root-csi on root->chunks instead. Accepts a flat-mode vector root as well, in which case it is rebuilt into a balanced tree via `coll->root`.
(root->chunks root)Extract all chunks from a rope tree in order.
Extract all chunks from a rope tree in order.
(rope->str root)Efficient rope-to-string via StringBuilder. Appends each chunk's elements directly, avoiding lazy seq overhead.
Efficient rope-to-string via StringBuilder. Appends each chunk's elements directly, avoiding lazy seq overhead.
(rope-chunk-at root i)Find the chunk containing index i and its global start offset. Returns [chunk chunk-start-offset]. Index must be in bounds.
Find the chunk containing index i and its global start offset. Returns [chunk chunk-start-offset]. Index must be in bounds.
(rope-chunks-reduce f root)(rope-chunks-reduce f init root)Reduce over chunks (not individual elements) of a rope tree.
Reduce over chunks (not individual elements) of a rope tree.
(rope-concat l r)Concatenate two rope trees, preserving left-before-right order. Ensures the Chunk Size Invariant holds on the result: every chunk is in [min, target] except possibly the rightmost.
Position-aware: l's rightmost becomes internal (must be >= min). r's leftmost becomes internal only if r has >= 2 chunks; if r has exactly 1 chunk it becomes the rightmost of the result and any size in [1, target] is valid.
Concatenate two rope trees, preserving left-before-right order. Ensures the Chunk Size Invariant holds on the result: every chunk is in [min, target] except possibly the rightmost. Position-aware: l's rightmost becomes internal (must be >= min). r's leftmost becomes internal only if r has >= 2 chunks; if r has exactly 1 chunk it becomes the rightmost of the result and any size in [1, target] is valid.
(rope-fold root n combinef reducef)Parallel fold over the rope's existing tree shape.
Unlike a split-based fold, this does not rebuild intermediate half-ropes. It recursively folds left subtree, current chunk, and right subtree in left-to-right order, using subtree sizes to decide when to stop splitting.
Parallel fold over the rope's existing tree shape. Unlike a split-based fold, this does not rebuild intermediate half-ropes. It recursively folds left subtree, current chunk, and right subtree in left-to-right order, using subtree sizes to decide when to stop splitting.
(rope-insert-root root start mid-root)Insert mid-root at start in root.
Insert mid-root at start in root.
(rope-node-create chunk _ l r)Create a rope node for generic (vector) chunks. The node value stores subtree element count; the balance metric remains ordinary node count. This is the t-join binding for the generic Rope type.
Create a rope node for generic (vector) chunks. The node value stores subtree element count; the balance metric remains ordinary node count. This is the *t-join* binding for the generic Rope type.
(rope-reduce f root)(rope-reduce f init root)Direct in-order tree walk: left subtree, chunk, right subtree. Bypasses the enumerator infrastructure to eliminate EnumFrame allocation and per-chunk lambda overhead.
Direct in-order tree walk: left subtree, chunk, right subtree. Bypasses the enumerator infrastructure to eliminate EnumFrame allocation and per-chunk lambda overhead.
(rope-remove-root root start end)Remove [start, end) from root.
Remove [start, end) from root.
(rope-size root)Total element count across all chunks.
Total element count across all chunks.
(rope-splice-inplace root start end replacement-chunk create)Fused single-chunk splice: replace [start, end) with replacement-chunk in a single tree traversal. Returns new root when [start, end) falls entirely within one chunk and the result chunk is in [1, target], or nil to signal fallback to the multi-traversal path.
replacement-chunk may be nil for pure removal. The chunk type must match the tree's chunk type (String for StringRope, vector for generic Rope).
Fused single-chunk splice: replace [start, end) with replacement-chunk in a single tree traversal. Returns new root when [start, end) falls entirely within one chunk and the result chunk is in [1, target], or nil to signal fallback to the multi-traversal path. replacement-chunk may be nil for pure removal. The chunk type must match the tree's chunk type (String for StringRope, vector for generic Rope).
(rope-splice-root root start end mid-root)Replace [start, end) in root with mid-root, where all arguments are rope roots. Uses raw positional splits and repairs only the fringes that remain exposed in the final result.
Replace [start, end) in root with mid-root, where all arguments are rope roots. Uses raw positional splits and repairs only the fringes that remain exposed in the final result.
(rope-split-at root i)Split rope tree at element index i, returning [left right]. Uses rope-join (concat3) during unwind so total cost is O(log n), matching the standard split-join pattern from Blelloch et al.
Split rope tree at element index i, returning [left right]. Uses rope-join (concat3) during unwind so total cost is O(log n), matching the standard split-join pattern from Blelloch et al.
(str->root s)Build a rope tree from a String, partitioned into substring chunks.
Uses the currently bound *target-chunk-size*. Split points are
adjusted to avoid breaking UTF-16 surrogate pairs at chunk boundaries.
Build a rope tree from a String, partitioned into substring chunks. Uses the currently bound `*target-chunk-size*`. Split points are adjusted to avoid breaking UTF-16 surrogate pairs at chunk boundaries.
(string-rope-node-create chunk _ l r)Create a rope node for String chunks. The node value stores subtree character count. This is the t-join binding for StringRope.
Create a rope node for String chunks. The node value stores subtree character count. This is the *t-join* binding for StringRope.
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |