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(chunk-count root)Number of chunk nodes in the tree.
Number of chunk nodes in the tree.
(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).
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).
(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)Check that a rope root satisfies the Chunk Size Invariant:
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.
(normalize-root root)Full O(n) rechunk of a rope tree so every chunk satisfies CSI.
Full O(n) rechunk of a rope tree so every chunk satisfies CSI.
(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-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-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. The right-subtree continuation uses recur for zero stack growth on that branch; left-subtree recursion depth is bounded by tree height (O(log n)).
For IReduceInit chunks (PersistentVector), delegates to the vector's native reduce for tight array iteration. A single volatile + wrapper closure is allocated once per reduce call (not per chunk) to detect early termination from reduced.
Direct in-order tree walk: left subtree, chunk, right subtree. Bypasses the enumerator infrastructure to eliminate EnumFrame allocation and per-chunk lambda overhead. The right-subtree continuation uses recur for zero stack growth on that branch; left-subtree recursion depth is bounded by tree height (O(log n)). For IReduceInit chunks (PersistentVector), delegates to the vector's native reduce for tight array iteration. A single volatile + wrapper closure is allocated once per reduce call (not per chunk) to detect early termination from reduced.
(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-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.
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 |