Rope (data structure)

A simple rope built on the string of "Hello_my_name_is_Simon".

Incomputer programming,arope,orcord,is adata structurecomposed of smallerstringsthat is used to efficiently store and manipulate longer strings or entire texts. For example, atext editingprogram 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 ofbinary treewhere each leaf (end node) holds a string and a length (also known as aweight), and each node further up the tree holds the sum of the lengths of all the leaves in its leftsubtree.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 constantimmutable objectsin the typical nondestructive case, allowing for somecopy-on-writebehavior. Leaf nodes are usually implemented asbasic fixed-length stringswith areference countattached for deallocation when no longer needed, although othergarbage collectionmethods can be used as well.

Operations

In the following definitions,Nis the length of the rope, that is, the weight of the root node.

Collect leaves

Definition:Create a stackSand a listL.Traverse down the left-most spine of the tree until you reach a leaf l', adding each nodentoS.Add l' toL.The parent of l' (p) is at the top of the stack. Repeat the procedure for p's right subtree.

finalclassInOrderRopeIteratorimplementsIterator<RopeLike>{

privatefinalDeque<RopeLike>stack;

InOrderRopeIterator(@NonNullRopeLikeroot){
stack=newArrayDeque<>();
varc=root;
while(c!=null){
stack.push(c);
c=c.getLeft();
}
}

@Override
publicbooleanhasNext(){
returnstack.size()>0;
}

@Override
publicRopeLikenext(){
valresult=stack.pop();

if(!stack.isEmpty()){
varparent=stack.pop();
varright=parent.getRight();
if(right!=null){
stack.push(right);
varcleft=right.getLeft();
while(cleft!=null){
stack.push(cleft);
cleft=cleft.getLeft();
}
}
}

returnresult;
}
}

Rebalance

Definition:Collect the set of leavesLand rebuild the tree from the bottom-up.

staticbooleanisBalanced(RopeLiker){
valdepth=r.depth();
if(depth>=FIBONACCI_SEQUENCE.length-2){
returnfalse;
}
returnFIBONACCI_SEQUENCE[depth+2]<=r.weight();
}

staticRopeLikerebalance(RopeLiker){
if(!isBalanced(r)){
valleaves=Ropes.collectLeaves(r);
returnmerge(leaves,0,leaves.size());
}
returnr;
}

staticRopeLikemerge(List<RopeLike>leaves){
returnmerge(leaves,0,leaves.size());
}

staticRopeLikemerge(List<RopeLike>leaves,intstart,intend){
intrange=end-start;
if(range==1){
returnleaves.get(start);
}
if(range==2){
returnnewRopeLikeTree(leaves.get(start),leaves.get(start+1));
}
intmid=start+(range/2);
returnnewRopeLikeTree(merge(leaves,start,mid),merge(leaves,mid,end));
}

Insert

Definition:Insert(i, S’):insert the stringS’beginning at positioniin the strings,to form a new stringC₁,...,C_i,S',C_{i+ 1},...,C_m.

Time complexity:⁠$O(\log N)$⁠.

This operation can be done by aSplit()and twoConcat()operations. The cost is the sum of the three.

publicRopeinsert(intidx,CharSequencesequence){
if(idx==0){
returnprepend(sequence);
}
if(idx==length()){
returnappend(sequence);
}
vallhs=base.split(idx);
returnnewRope(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 positioni

Time complexity:⁠$O(\log N)$⁠

To retrieve thei-th character, we begin arecursivesearch from the root node:

@Override
publicintindexOf(charch,intstartIndex){
if(startIndex>weight){
returnright.indexOf(ch,startIndex-weight);
}
returnleft.indexOf(ch,startIndex);
}

For example, to find the character ati=10in 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 (leavingi=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₁andS₂,into a single rope.

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

A concatenation can be performed simply by creating a new root node withleft = S1andright = S2,which is constant time. The weight of the parent node is set to the length of the left childS₁,which would take⁠$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 stringSinto two new stringsS₁andS₂,S₁=C₁,...,C_iandS₂=C_{i+ 1},...,C_m.

Time complexity:⁠$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 nodeKat the bottom level. Remove the link betweenKandG.Go to the parent ofGand subtract the weight ofKfrom the weight ofD.Travel up the tree and remove any right links to subtrees covering characters past position 11, subtracting the weight ofKfrom their parent nodes (only nodeDandA,in this case). Finally, build up the newly orphaned nodesKandHby concatenating them together and creating a new parentPwith weight equal to the length of the left nodeK.

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

publicPair<RopeLike,RopeLike>split(intindex){
if(index<weight){
valsplit=left.split(index);
returnPair.of(rebalance(split.fst),rebalance(newRopeLikeTree(split.snd,right)));
}elseif(index>weight){
valsplit=right.split(index-weight);
returnPair.of(rebalance(newRopeLikeTree(left,split.fst)),rebalance(split.snd));
}else{
returnPair.of(left,right);
}
}

Delete

Definition:Delete(i, j):delete the substringC_i,…,C_{i+j− 1},fromsto form a new stringC₁,…,C_{i− 1},C_i+j,…,C_m.

Time complexity:⁠$O(\log N)$⁠.

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

@Override
publicRopeLikedelete(intstart,intlength){
vallhs=split(start);
valrhs=split(start+length);
returnrebalance(newRopeLikeTree(lhs.fst,rhs.snd));
}

Report

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

Time complexity:⁠$O(j+\log N)$⁠

To report the stringC_i,…,C_{i+j− 1},find the nodeuthat containsC_iandweight(u) >= j,and then traverseTstarting at nodeu.OutputC_i,…,C_{i+j− 1}by doing anin-order traversalofTstarting at nodeu.

Comparison with monolithic arrays

Complexity

Operation	Rope	String
Index	O(log n)	O(1)
Split	O(log n)	O(1)
Concatenate	O(1) amortized, O(log n) worst case	O(n)
Iterate over each character	O(n)	O(n)
Insert	O(log n)	O(n)
Append	O(1) amortized, O(log n) worst case	O(1) amortized, O(n) worst case
Delete	O(log n)	O(n)
Report	O(j + log n)	O(j)
Build	O(n)	O(n)

Advantages:

• Ropes enable much faster insertion and deletion of text than monolithic string arrays, on which operations have time complexity O(n).
• Ropes do not require O(n) extra memory when operated upon (arrays need that for copying operations).
• Ropes do not require large contiguous memory spaces.
• If only nondestructive versions of operations are used, rope is apersistent data structure.For the text editing program example, this leads to an easy support for multipleundolevels.

Disadvantages:

• Greater overall space use when not being operated on, mainly to store parent nodes. There is a trade-off between how much of the total memory is such overhead and how long pieces of data are being processed as strings. The strings in example figures above are unrealistically short for modern architectures. The overhead is always O(n), but the constant can be made arbitrarily small.
• Increase in time to manage the extra storage
• Increased complexity of source code; greater risk of bugs

This table compares thealgorithmictraits of string and rope implementations, not theirraw speed.Array-based strings have smaller overhead, so (for example) concatenation and split operations are faster on small datasets. However, when array-based strings are used for longer strings, time complexity and memory use for inserting and deleting characters becomes unacceptably large. In contrast, a rope data structure has stable performance regardless of data size. Further, the space complexity for ropes and arrays are both O(n). In summary, ropes are preferable when the data is large and modified often.

See also

• TheCedarprogramming environment, which used ropes "almost since its inception"
• TheModel T enfilade,a similar data structure from the early 1970s
• Gap buffer,a data structure commonly used in text editors that allows efficient insertion and deletion operations clustered near the same location
• Piece table,another data structure commonly used in text editors

External links

• "absl::Cord" implementation of ropes within The Abseil library
• "C cords" implementation of ropes within the Boehm Garbage Collector library
• SGI C++ specification for ropes(supported by STLPort andlibstdc++)
• RopesforC#
• ropesforCommon Lisp
• Ropes for Java
• String-Like Ropes for Java
• Ropes for JavaScript
• RopesforLimbo
• ropesforNim
• RopesforOCaml
• pyropesforPython
• RopesforSmalltalk
• SwiftRopeforSwift
• "Ropey"forRust