🪢 Rope
Balanced binary tree of strings for efficient text editing
Overview
A rope is a binary tree where leaves hold short strings and internal nodes cache the total length of their left subtree. This gives O(log n) concatenation, insertion, and deletion instead of the O(n) copies required by flat strings. Ropes are the backbone of modern text editors like VS Code, Xi, and Lapce.
This implementation includes automatic balancing (Fibonacci-based rebalancing), line-aware indexing, and a full functional API.
Concepts Demonstrated
- Algebraic data types — tree structure with Leaf / Node variants
- Persistent data structures — immutable tree with structural sharing
- Weight-balanced trees — cached subtree sizes for O(log n) indexing
- Fibonacci rebalancing — threshold-based tree restructuring
- Higher-order functions — fold, map, iter over character sequences
- Pattern matching — recursive tree traversal
How It Works
(* Tree structure *)
type t =
| Leaf of string (* up to max_leaf chars *)
| Node of { left; right;
weight; (* length of left subtree *)
len; depth }
(* Build a rope from a string *)
let r = Rope.of_string "Hello, world!"
(* O(1) concatenation — just creates a new root node *)
let r2 = Rope.concat r (Rope.of_string " Goodbye!")
(* O(log n) character access *)
let ch = Rope.index r2 7 (* → 'w' *)
(* O(log n) insert at position *)
let r3 = Rope.insert r2 5 " beautiful"
(* O(log n) delete range *)
let r4 = Rope.delete r3 0 6 (* remove "Hello," *)Key Functions
| Function | Complexity | Description |
|---|---|---|
of_string s | O(n) | Build balanced rope from string |
to_string r | O(n) | Flatten rope to string |
concat a b | O(1) | Concatenate two ropes |
length r | O(1) | Total character count |
index r i | O(log n) | Character at position i |
substring r i len | O(log n + len) | Extract substring |
insert r i s | O(log n) | Insert string at position |
delete r i len | O(log n) | Delete range |
split r i | O(log n) | Split into two ropes at position |
balance r | O(n) | Rebalance using Fibonacci thresholds |
is_balanced r | O(1) | Check balance invariant |
lines r | O(n) | Split into lines |
iter f r | O(n) | Apply f to each character |
fold f init r | O(n) | Left fold over characters |
map f r | O(n) | Map function over characters |
Why Not Just Use Strings?
| Operation | Flat String | Rope |
|---|---|---|
| Concatenation | O(n + m) — full copy | O(1) — new node |
| Insert at position | O(n) — shift + copy | O(log n) — split + concat |
| Delete range | O(n) — shift + copy | O(log n) — split + concat |
| Character access | O(1) — direct index | O(log n) — tree walk |
| Memory on edit | Full copy | Shared structure |
For documents longer than a few KB, ropes dramatically reduce the cost of editing operations. The O(log n) access trade-off is rarely noticeable since editors typically access characters sequentially.
When to Use
- Text editors — fast insert/delete anywhere in large documents
- Version control — efficient diff and patch with structural sharing
- Log aggregation — concatenating many small strings without copying
- Undo/redo — persistent structure enables cheap snapshots