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 C₁, ..., C_i, S', C_{i + 1}, ..., C_m.

Time complexity: ${\displaystyle O(\log N)}$.

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

Figure 2.1: Example of index lookup on a rope.

Definition: Index(i): return the character at position i

Time complexity: ${\displaystyle O(\log N)}$

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 > weight) {
      return right.indexOf(ch, startIndex - weight);
    }
    return left.indexOf(ch, startIndex);
  }

For example, to find the character at i=10 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 i=1) 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)

Concat

Figure 2.2: Concatenating two child ropes into a single rope.

Definition: Concat(S1, S2): concatenate two ropes, S₁ and S₂, into a single rope.

Time complexity: ${\displaystyle O(1)}$ (or ${\displaystyle O(\log N)}$ time to compute the root weight)

A concatenation can be performed simply by creating a new root node with left = S1 and right = S2, which is constant time. The weight of the parent node is set to the length of the left child S₁, which would take ${\displaystyle O(\log N)}$ time, if the tree is balanced.

As most rope operations require balanced trees, the tree may need to be re-balanced after concatenation.

Split

Figure 2.3: Splitting a rope in half.

Definition: Split (i, S): split the string S into two new strings S₁ and S₂, S₁ = C₁, ..., C_i and S₂ = C_{i + 1}, ..., C_m.

Time complexity: ${\displaystyle O(\log N)}$

There are two cases that must be dealt with:

1. The split point is at the end of a string (i.e. after the last character of a leaf node)
2. The split point is in the middle of a string.

The second case reduces to the first by splitting the string at the split point to create two new leaf nodes, then creating a new node that is the parent of the two component strings.

For example, to split the 22-character rope pictured in Figure 2.3 into two equal component ropes of length 11, query the 12th character to locate the node K at the bottom level. Remove the link between K and G. Go to the parent of G and subtract the weight of K from the weight of D. Travel up the tree and remove any right links to subtrees covering characters past position 11, subtracting the weight of K from their parent nodes (only node D and A, in this case). Finally, build up the newly orphaned nodes K and H by concatenating them together and creating a new parent P with weight equal to the length of the left node K.

As most rope operations require balanced trees, the tree may need to be re-balanced after splitting.

  public Pair<RopeLike, RopeLike> split(int index) {
    if (index < weight) {
      val split = left.split(index);
      return Pair.of(rebalance(split.fst), rebalance(new RopeLikeTree(split.snd, right)));
    } else if (index > weight) {
      val split = right.split(index - weight);
      return Pair.of(rebalance(new RopeLikeTree(left, split.fst)), rebalance(split.snd));
    } else {
      return Pair.of(left, right);
    }
  }

Delete

Definition: Delete(i, j): delete the substring C_i, …, C_{i + j − 1}, from s to form a new string C₁, …, C_{i − 1}, C_{i + j}, …, C_m.

Time complexity: ${\displaystyle O(\log N)}$.

This operation can be done by two Split() and one Concat() operation. First, split the rope in three, divided by i-th and i+j-th character respectively, which extracts the string to delete in a separate node. Then concatenate the other two nodes.

  @Override
  public RopeLike delete(int start, int length) {
    val lhs = split(start);
    val rhs = split(start + length);
    return rebalance(new RopeLikeTree(lhs.fst, rhs.snd));
  }

Report

Definition: Report(i, j): output the string C_i, …, C_{i + j − 1}.

Time complexity: ${\displaystyle O(j+\log N)}$

To report the string C_i, …, C_{i + j − 1}, find the node u that contains C_i and weight(u) >= j, and then traverse T starting at node u. Output C_i, …, C_{i + j − 1} by doing an in-order traversal of T starting at node u.