Liking cljdoc? Tell your friends :D

ordered-collections.kernel.root

No vars found in this namespace.

ordered-collections.kernel.rope

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
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
raw docstring

ordered-collections.kernel.tree

cljdoc builds & hosts documentation for Clojure/Script libraries

Keyboard shortcuts
Ctrl+kJump to recent docs
Move to previous article
Move to next article
Ctrl+/Jump to the search field
× close