Rope (computer science)

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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • String (computer science) — In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet. In computer programming, a string is traditionally a sequence of… …   Wikipedia

  • Rope (disambiguation) — Rope may refer to:* Rope, a length of non metallic fibers twisted or braided together * Wire rope, a length of metallic fibers twisted or braided together * Rope (unit), a unit of length * Rope (play), a play by Patrick Hamilton ** Rope (film), a …   Wikipedia

  • Computer data storage — 1 GB of SDRAM mounted in a personal computer. An example of primary storage …   Wikipedia

  • Rope and Skin — Theatrical poster for Rope and Skin (1979) Directed by Shōgorō Nishimura[1] …   Wikipedia

  • Rope Hell — Theatrical poster for Rope Hell (1978) Directed by Kōyū Ohara[1] …   Wikipedia

  • Rope Cosmetology — Theatrical poster for Rope Cosmetology (1978) Directed by Shōgorō Nishimura[1] …   Wikipedia

  • Core rope memory — test sample from the Apollo Program. Core rope memory is a form of read only memory (ROM) for computers, first used by early NASA Mars probes and then in the Apollo Guidance Computer (AGC) designed and programmed by the MIT Instrumentation La …   Wikipedia

  • Apollo Guidance Computer — and DSKY Invented by MIT Instrumentation Laboratory Manufacturer Raytheon Introduced August 1966 …   Wikipedia

  • Coral Academy of Science — is a public charter school located on East 9th Street in Reno, Nevada. It was founded in 2000 with grades 7 10, over the years it has grown, now CAS serves grades K 12 in northern Nevada. The school is accredited by NAAS and it has been a high… …   Wikipedia

  • materials science — the study of the characteristics and uses of various materials, as glass, plastics, and metals. [1960 65] * * * Study of the properties of solid materials and how those properties are determined by the material s composition and structure, both… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”