In computer programming, a rope, or cord, is a data structure composed of smaller strings that is used to efficiently store and manipulate a very long string. For example, a text editing program may use a rope to represent the text being edited, so that operations such as insertion, deletion, and random access can be done efficiently.
Description
A rope is a type of binary tree where each leaf (end node) holds a string and a length (also known as a "weight"), and each node further up the tree holds the sum of the lengths of all the leaves in its left subtree. A node with two children thus divides the whole string into two parts: the left subtree stores the first part of the string, the right subtree stores the second part of the string, and a node's weight is the length of the first part.
For rope operations, the strings stored in nodes are assumed to be constant immutable objects in the typical nondestructive case, allowing for some copy-on-write behavior. Leaf nodes are usually implemented as basic fixed-length strings with a reference count attached for deallocation when no longer needed, although other garbage collection methods can be used as well.
Operations
In the following definitions, N is the length of the rope.
Collect leaves
Definition: Create a stack S and a list L. Traverse down the left-most spine of the tree until you reach a leaf l', adding each node N to S. Add l' to L. The parent of l' (p) is at the top of the stack. Repeat the procedure for p's right subtree.
final class InOrderRopeIterator implements Iterator<RopeLike> {
private final Deque<RopeLike> stack;
InOrderRopeIterator(@NonNull RopeLike root) {
stack = new ArrayDeque<>(); var c = root; while (c != null) { stack.push(c); c = c.getLeft(); } }
@Override
public boolean hasNext() {
return stack.size() > 0; }
@Override
public RopeLike next() {
val result = stack.pop();
if (!stack.isEmpty()) {
val parent = stack.pop(); val right = parent.getRight(); if (right != null) { stack.push(right); var cleft = right.getLeft(); while (cleft != null) { stack.push(cleft); cleft = cleft.getLeft(); } } }
return result; } }
Rebalance
Definition: Collect the set of leaves L and rebuild the tree from the bottom-up.
static boolean isBalanced(RopeLike r) {
val depth = r.depth(); if (depth >= FIBONACCI_SEQUENCE.length - 2) { return false; } return FIBONACCI_SEQUENCE[depth + 2] <= r.weight(); }
static RopeLike rebalance(RopeLike r) {
if (!isBalanced(r)) {
val leaves = Ropes.collectLeaves(r); return merge(leaves, 0, leaves.size()); } return r; }
static RopeLike merge(List<RopeLike> leaves) {
return merge(leaves, 0, leaves.size()); }
static RopeLike merge(List<RopeLike> leaves, int start, int end) {
int range = end - start; if (range == 1) { return leaves.get(start); } if (range == 2) { return new RopeLikeTree(leaves.get(start), leaves.get(start + 1)); } int mid = start + (range / 2); return new RopeLikeTree(merge(leaves, start, mid), merge(leaves, mid, end)); }
Insert
Definition: Insert(i, S’): insert the string S’ beginning at position i in the string s, to form a new string { { math|C1, ..., Ci, S''', Ci + 1, ..., Cm}}. Time complexity: .
This operation can be done by a Split() and two Concat() operations. The cost is the sum of the three. public Rope insert(int idx, CharSequence sequence) { if (idx == 0) { return prepend(sequence); } if (idx == length()) { return append(sequence); } val lhs = base.split(idx); return new Rope(Ropes.concat(lhs.fst.append(sequence), lhs.snd)); } Index
Definition: Index(i): return the character at position i Time complexity:
To retrieve the i-th character, we begin a recursive search from the root node:
@Override
public int indexOf(char ch, int startIndex) {
if (startIndex > left.weight()) {
return right.indexOf(ch, startIndex - left.weight()); } return left.indexOf(ch, startIndex); }
For example, to find the character at in Figure 2.1 shown on the right, start at the root node (A), find that 22 is greater than 10 and there is a left child, so go to the left child (B). 9 is less than 10, so subtract 9 from 10 (leaving ) and go to the right child (D). Then because 6 is greater than 1 and there's a left child, go to the left child (G). 2 is greater than 1 and there's a left child, so go to the left child again (J). Finally 2 is greater than 1 but there is no left child, so the character at index 1 of the short string "na" (ie "n") is the answer. (1-based index)