Version 2 of rope

Updated 2008-01-24 22:40:37 by FB

A rope is a data structure used to represent strings. Ropes are typically implemented with B-trees of (possibly immutable) strings.

The Tk text widget uses a B-tree to store textual data along with tags, so it's some sort of augmented rope, where each node has associated metadata. TIP #169 [L1 ] (Add Peer Text Widgets), implemented in Tk8.5, already involved uncoupling the B-Tree from the widget. A native rope object type could be used to push this idea even further, by allowing data sharing outside of text widgets. For example, a comment dated 24Jan2004 on the text page expresses the wish to share this structure with tdom.

The B-Tree code used in the text widget could serve as a basis for a rope object type, as the code is mature and widely tested.

Cloverfield suggests that ropes be used in place of flat strings as the primary string representation in Tcl.

See [L2 ] for a real-world implementation of ropes in C ("C Cords").

SGI provides a rope template class in its STL implementation [L3 ].


See also Abstract Data Types.