Introducing the Rope data structure 2 – Arrays, collections and data structures

Implementing concat(Node node1, Node node2)

Concatenating two Ropes (node1 and node2) is a straightforward step-by-step algorithm:

Create a new root node having the weight of the leaf nodes in node1

The new root node has node1 as its left child and node2 as is right child

Optional rebalancing (not implemented here, but is a classic binary tree rebalancing)

The following diagram represents the concatenation of two Ropes:

Figure 5.15 – Concatenating two ropes

In code lines, we have:

public static Node concat(Node node1, Node node2) {
  return new Node(node1, node2, getLength(node1));
}
private static int getLength(Node node) {
  if (node.str != null) {
    return node.weight;
  } else {
    return getLength(node.left) + (node.right == null ?
      0 : getLength(node.right));
  }
}

Next, let’s insert a new node.

Implementing insert(Node node, int index, String str)

In order to insert a piece of string at a certain index in the original string we have to split the original string and perform two concatenations. The algorithm has three steps as follows:

Split the original string at index in two strings, s1, and s2
Concatenate s1 and the given str into s3
Concatenate s1 with the new s3

In code lines, we have the following implementation:

public static Node insert(Node node, int index, String str) {
  List<Node> splitRopes = Rope.split(node, index);
  Node insertNode = new Node(null, null, str.length(), str);
  Node resultNode;
  if (splitRopes.size() == 1) {
    if (index == 0) {
      resultNode = Rope.concat(insertNode, splitRopes.get(0));
    } else {
      resultNode = Rope.concat(splitRopes.get(0), insertNode);
    }
  } else {                        
   resultNode = Rope.concat(splitRopes.get(0), insertNode);
   resultNode = Rope.concat(resultNode, splitRopes.get(1));
  }
  return resultNode;
}

Next, let’s see how to delete a substring.

Implementing delete(Node node, int start, int end)

Deleting a substring from the original string between start and end requires two splits and one concatenation. The algorithm consists of three steps as follows:

Split the original string at start into s1 and s2

Split s2 at end into s3 and s4

Concatenate s1 and s4

In code lines, we have the following implementation:

public static Node delete(Node node, int start, int end) {
  Node beforeNode = null;
  Node afterNode;
  List<Node> splitRopes1 = Rope.split(node, start);
  if (splitRopes1.size() == 1) {
    afterNode = splitRopes1.get(0);
  } else {
    beforeNode = splitRopes1.get(0);
    afterNode = splitRopes1.get(1);
  }
  List<Node> splitRopes2 = Rope.split(afterNode, end – start);
  if (splitRopes2.size() == 1) {
    return beforeNode;
  }
  return beforeNode == null ? splitRopes2.get(1) :
    Rope.concat(beforeNode, splitRopes2.get(1));
}

Finally, let’s talk about splitting a Rope.

Implementing split(Node node, int index)

Splitting a Rope into two Ropes is an operation that should consider two cases of splitting a leaf node:

Split should take place at the last character (index)

Split should take place at the middle character (index)

Both of these cases are considered in the implementation listed in the bundled code. Since this code is simple but quite large, we skipped it here for brevity reasons.