Welcome to the MedLibrary.org Wikipedia Supplement on Rope (computer science) -- Please Click to Return to Front Page

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".¹

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

Ropes extension is supported³ by the libstdc++ which is included with the GNU Compiler Collection.

For Java there is a Ropes for Java implementation licensed under the GPL.

References

1. ^ Boehm, Hans-J; Atkinson, Russ; and Plass, Michael (December 1995). "Ropes: an Alternative to Strings" (PDF). Software—Practice & Experience (New York, NY, USA: John Wiley & Sons, Inc.) 25 (12): 1315–1330. doi:10.1002/spe.4380251203, http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol25/issue12/spe986.pdf. 
2. ^ http://www.sgi.com/tech/stl/Rope.html provides the documentation for the rope class.
3. ^ __gnu_cxx::rope documentation for GCC 4.3

 This data structure-related article is a stub. You can help Wikipedia by expanding it.

Wikipedia content modification information:

• This page was last modified on 6 October 2008, at 00:45.

Wikipedia Authorship and Review

Wikipedia content provided here is not reviewed directly by MedLibrary.org. Wikipedia content is authored by an open community of volunteers and is not produced by or in any way affiliated with MedLibrary.org.

Wikipedia Usage Guidelines

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article on "Rope (computer science)".

The URL for this specific entry is:

• http://medlibrary.org/medwiki/Rope_(computer_science)

All Wikipedia text is available under the terms of the GNU Free Documentation License. (See Copyrights for details). Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc.