THE FOLD / LOOT / THE BOUNTY / THE ROPE
THE ROPE
a long string as a balanced tree of pieces
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A rope stores a long string as a balanced binary tree whose leaves hold small pieces and whose internal nodes cache the length of their left subtree. This makes concatenation and splitting O(log n) — just re-link a few nodes, no copying — and indexing a walk down the tree using the cached lengths. It is the structure behind fast text editors and immutable string libraries, where inserting into a huge document must not copy it whole.
LIT verified live: over 200 random strings, ropeIndex(i) returns the same character as the flat string at every position, and concatenating two ropes flattens to the exact concatenation (length and content) — window.__rope. FIG no framing; exact.
LIT verified live: over 200 random strings, ropeIndex(i) returns the same character as the flat string at every position, and concatenating two ropes flattens to the exact concatenation (length and content) — window.__rope. FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-bounty — the big reward of editing huge text cheaply: no whole-document copies. The rope is that reward. AVAN (AI) built the instrument: the balanced split into leaves, the left-length caches, the index walk, the O(1) concat, and the flatten cross-check.
Credit as content: Boehm, Atkinson & Plass (“Ropes: an Alternative to Strings”, 1995). The weave: David names the-bounty; I break a string into a tree of pieces, walk the length caches to index any position, and confirm the tree flattens back to the exact string.
Credit as content: Boehm, Atkinson & Plass (“Ropes: an Alternative to Strings”, 1995). The weave: David names the-bounty; I break a string into a tree of pieces, walk the length caches to index any position, and confirm the tree flattens back to the exact string.
3 ONE DIMENSION
Each internal node stores its left subtree’s length. To find character i: if i is less than the left length, go left; otherwise subtract it and go right. A few hops reach the leaf holding position i.
4 TWO DIMENSIONS · INTERACTIVE
A string as a rope tree; index any position by walking the length caches, and concatenate two ropes without copying.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a string as a tree of pieces.
AVAN’s addition (the inverse-companion): make concatenation and splitting O(log n) by storing a string as a balanced tree of pieces with cached subtree lengths — editing re-links nodes instead of copying characters. The inverse of ‘a string is one flat array you must copy to edit’ is ‘a string is a tree — concat and split by re-linking.’ Magenta is the whole-array copy you avoid; green is the piece tree. Editing text without copying it.
LIT Genuine rope data structure (Boehm, Atkinson & Plass 1995). Verified live: over 200 random strings, indexing a position via the cached left-lengths returns the same character as the flat string at every position, and concatenating two ropes flattens to the exact concatenation with the correct total length (window.__rope.index && .concat).
FIG No framing: the balanced split into leaves, the left-length caches, the index walk, the O(1) concat, and the flatten cross-check run in-browser and agree exactly. The AVAN inverse is honest — storing a string as a balanced tree of pieces with cached subtree lengths makes concat and split O(log n) by re-linking instead of copying; magenta is the whole-array copy you avoid, green the piece tree. Editing text without copying it.
FIG No framing: the balanced split into leaves, the left-length caches, the index walk, the O(1) concat, and the flatten cross-check run in-browser and agree exactly. The AVAN inverse is honest — storing a string as a balanced tree of pieces with cached subtree lengths makes concat and split O(log n) by re-linking instead of copying; magenta is the whole-array copy you avoid, green the piece tree. Editing text without copying it.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE BOUNTY · David Lee Wise (ROOT0), with AVAN