Editing Rope (data structure) (section)

==Operations==
In the following definitions, ''N'' is the length of the rope, that is, the weight of the root node.

=== 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.

<syntaxhighlight lang="java">
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()) {
            var parent = stack.pop();
            var right = parent.getRight();
            if (right != null) {
                stack.push(right);
                var cleft = right.getLeft();
                while (cleft != null) {
                    stack.push(cleft);
                    cleft = cleft.getLeft();
                }
            }
        }

        return result;
    }
}
</syntaxhighlight>

=== Rebalance ===
: ''Definition:'' Collect the set of leaves ''L'' and rebuild the tree from the bottom-up.

<syntaxhighlight lang="java">
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));
}
</syntaxhighlight>

=== Insert ===
: ''Definition:'' <code>Insert(i, S’)</code>: insert the string ''S’'' beginning at position ''i'' in the string ''s'', to form a new string {{math|''C''<sub>1</sub>, ..., ''C<sub>i</sub>'', ''S''', ''C''<sub>''i'' + 1</sub>, ..., ''C<sub>m</sub>''}}.
: ''Time complexity:'' {{tmath|O(\log N)}}.

This operation can be done by a <code>Split()</code> and two <code>Concat()</code> operations. The cost is the sum of the three.
<syntaxhighlight lang="java">
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));
}
</syntaxhighlight>
=== Index ===

[[File:Vector Rope index.svg|right|x200px|thumb|Figure 2.1: Example of index lookup on a rope.]]

: ''Definition:'' <code>Index(i)</code>: return the character at position ''i''
: ''Time complexity:'' {{tmath|O(\log N)}}

To retrieve the ''i''-th character, we begin a [[Recursion|recursive]] search from the root node:

<syntaxhighlight lang="java">
@Override
public int indexOf(char ch, int startIndex) {
    if (startIndex > weight) {
        return right.indexOf(ch, startIndex - weight);
    }
    return left.indexOf(ch, startIndex);
}
</syntaxhighlight>

For example, to find the character at {{code|1=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 {{code|1=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 ===
[[File:Vector Rope concat.svg|right|x200px|thumb|Figure 2.2: Concatenating two child ropes into a single rope.]]
: ''Definition:'' <code>Concat(S1, S2)</code>: concatenate two ropes, ''S''<sub>1</sub> and ''S''<sub>2</sub>, into a single rope.
: ''Time complexity:'' {{tmath|O(1)}} (or {{tmath|O(\log N)}} time to compute the root weight)

A concatenation can be performed simply by creating a new root node with {{mono|1=left = S1}} and {{mono|1=right = S2}}, which is constant time. The weight of the parent node is set to the length of the left child ''S''<sub>1</sub>, which would take {{tmath|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 ===
[[File:Vector Rope split.svg|right|x600px|thumb|Figure 2.3: Splitting a rope in half.]]

: ''Definition:'' <code>Split (i, S)</code>: split the string ''S'' into two new strings ''S''<sub>1</sub> and ''S''<sub>2</sub>, {{math|1=''S''<sub>1</sub> = ''C''<sub>1</sub>, ..., ''C<sub>i</sub>''}} and {{math|1=''S''<sub>2</sub> = ''C''<sub>''i'' + 1</sub>, ..., ''C<sub>m</sub>''}}.
: ''Time complexity:'' {{tmath|O(\log N)}}

There are two cases that must be dealt with:
# The split point is at the end of a string (i.e. after the last character of a leaf node)
# 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.

<syntaxhighlight lang="java">
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);
    }
}
</syntaxhighlight>

=== Delete ===
: ''Definition:'' <code>Delete(i, j)</code>: delete the substring {{math|''C<sub>i</sub>'', …, ''C''<sub>''i'' + ''j'' − 1</sub>}}, from ''s'' to form a new string {{math|''C''<sub>1</sub>, …, ''C''<sub>''i'' − 1</sub>, ''C''<sub>''i'' + ''j''</sub>, …, ''C<sub>m</sub>''}}.
: ''Time complexity:'' {{tmath|O(\log N)}}.

This operation can be done by two <code>Split()</code> and one <code>Concat()</code> 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.

<syntaxhighlight lang="java">
@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));
}
</syntaxhighlight>

=== Report ===
: ''Definition:'' <code>Report(i, j)</code>: output the string {{math|''C<sub>i</sub>'', …, ''C''<sub>''i'' + ''j'' − 1</sub>}}.
: ''Time complexity:'' {{tmath|O(j + \log N)}}

To report the string {{math|''C<sub>i</sub>'', …, ''C''<sub>''i'' + ''j'' − 1</sub>}}, find the node ''u'' that contains ''C<sub>i</sub>'' and {{code|1=weight(u) >= j}}, and then traverse ''T'' starting at node ''u''. Output {{math|''C<sub>i</sub>'', …, ''C''<sub>''i'' + ''j'' − 1</sub>}} by doing an [[in-order traversal]] of ''T'' starting at node ''u''.