A rope is a [data structure] used to represent [string]s. Ropes are typically implemented with B-trees [http://en.wikipedia.org/wiki/B-tree] of (possibly [immutable]) strings. The potential immutability of source strings makes rope a good candidate for a [mutable] string structure on systems where the native string representation is immutable, such as [Java]. Also, ropes can be used to mix data from disjoint sources, e.g. stack, heap, memory-mapped files, on-demand content, etc.
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 [http://tip.tcl.tk/169] (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.
Each substring node could have metadata attached. For example, the string representation of a proc body could point to the original sourced string, with metadata giving the file name. This could be used to generate meaningful stack traces with line numbers and file names. See also [Tcl9 and annotated strings].
See [http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol25/issue12/spe986.pdf] for a real-world implementation of ropes in C ("C Cords").
SGI provides a rope template class in its STL implementation [http://www.sgi.com/tech/stl/Rope.html].
See also http://en.wikipedia.org/wiki/Rope_%28computer_science%29
<
>(''[escargo] 25 Jan 2008'' - There is a limitation in the rendering code that ignores the closing paren, so the [URL] ''if presented with literal opening and closing parens'' is right, but the generated [HTML] is wrong). <
>(''[DKF]'': You need to percent-encode the parenthesis.)
----
The [Scheme] people at http://schemers.org had this sort of discussion a while back regarding string representations; this can give some insight on what to do for [Cloverfield], given the similarities between Tcl and [Scheme] on many points.
[http://srfi.schemers.org/srfi-50/mail-archive/msg00428.html]
[http://srfi.schemers.org/srfi-75/mail-archive/msg00257.html]
----
[RS] 2008-01-25: Could someone give an example of a string rep for a rope - i.e. demonstrate how the internals can be turned outside? I roughly assume it to be a relation like of [text] widget's ''get'' method (text content only) vs. ''dump'' method ("including the text and information about marks, tags, and embedded windows")... Even if metadata is kept hidden at runtime, it has to be serialized for channel transport (files, sockets, pipes, etc.)
[FB]: Let's imagine that our rope object type uses 2-3 B-trees [http://en.wikipedia.org/wiki/2-3_tree].
======
# Create a rope by concatenating words.
% set s [rope create The Quick Brown Fox]
TheQuickBrownFox
# Display the 2-3 tree structure as Tcl lists.
% rope dump $s
Quick {The {Brown Fox}}
# Append more words. This will rebalance the tree.
% set s [rope append $s Over The Lazy Dog]
TheQuickBrownFoxOverTheLazyDog
% rope dump $s
Fox {Quick {The Brown} The {Over {Lazy Dog}}}
# Insert word in the middle of the rope.
% set s [rope insert $s 16 Jumps]
TheQuickBrownFoxJumpsOverTheLazyDog
% rope dump $s
Fox {Quick {The Brown} The {{Jumps Over} {Lazy Dog}}}
======
----
[LV] So it looks like the rope's display version isn't all that useful. That's fine - neither is the display version of
the output from open, etc.
Is there, however, a way to at least simulate [serializing], so that one can dump the contents of ropes into a flat file and load them back up again without having to somehow know what commands initially were issued?
----
This nice Java applet demonstrates basic operations on several tree structures with step-by-step animations:
http://people.ksp.sk/~kuko/bak/index.html
----
[DKF] 2008-01-25: The [text] widget B-tree is only partially decoupled from the text widget, and it's not as widely tested as it should be (it had major changes in 8.5 to support smooth-scrolling and other related changes [http://tip.tcl.tk/155]). It's not at all clear to me that it's the best place to start from for your own implementation either; it's very focussed on being a model for 2-D strings (it's a collection of paragraphs containing rich text).
----
See also [Abstract Data Types].
----
!!!!!!
%| [Category Data Structure] |%
!!!!!!