Rope (computer science)

: "This article is about the data structure. For other uses, see Rope (disambiguation)."

In computer programming, a rope is a heavyweight string, involving the use of a concatenation tree representation. The concept was introduced in a paper called "Ropes: an Alternative to Strings". [cite journal
last = Boehm
first = Hans-J
coauthors = Atkinson, Russ; and Plass, Michael
title = Ropes: an Alternative to Strings
journal = Software—Practice & Experience
volume = 25
issue = 12
pages = 1315–1330
publisher = John Wiley & Sons, Inc.
location = New York, NY, USA
date = December 1995
url = http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol25/issue12/spe986.pdf
format = PDF
doi = 10.1002/spe.4380251203]

A rope is essentially a binary tree whose leaves are arrays of characters. A node in the tree has a left child and a right child - the left child is the first part of the string, while the right child is the final part of the string. Concatenation of two ropes simply involves the creation of a new tree node with both ropes as children.

The main advantages of ropes as compared to storing strings as character arrays is that they enable much faster concatenation than ordinary strings, and don't require a large contiguous memory space to store a large string. The main disadvantage is greater space usage and slower indexing, both of which become more severe as the tree structure becomes larger and deeper. However, many practical applications of indexing involve only iteration over the string, which remains fast as long as the leaf nodes are large enough to benefit from cache effects.

Language Support

Ropes are a built-in data type in Cedar.

SGI's extension to the C++ Standard Template Library provides a "rope" class. [ [http://www.sgi.com/tech/stl/Rope.html http://www.sgi.com/tech/stl/Rope.html] provides the documentation for the rope class.]

Ropes extension is supported [ [http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.3/a00223.html __gnu_cxx::rope documentation for GCC 4.3] ] by the [http://gcc.gnu.org/libstdc++/ libstdc++] which is included with the GNU Compiler Collection.

For Java there is a [http://ahmadsoft.org/ropes/ Ropes for Java] implementation licensed under the GPL.

References