Print Story Rope is made from String
Software
By codemonkey uk (Tue Oct 31, 2006 at 03:18:02 AM EST) (all tags)
In which I post some interesting and useful code.


http://www.hulver.com/scoop-files/18/Rope.zip

Contains a "string" class that scales very well for operations on large strings. For instance, concatenation operations happen independently of string length. Creating a 9k substring of a 10k source string only consumes a handful of extra bytes. Creating a reverse copy of a string of any size happens in constant time.

Iteration is amortised constant time, though slower than std::string/vector or pointer iteration.

On the down side, in place editing is very expensive (and therefore not explictly supported), and I currently only support forward const iteration. Furthermore, strings that are the result of thousands of concatination / substring operations become expensive to access / iterate over.

It's a fun little data structure to develop. Questions / comments, see below.

Enjoy.

< Note to self. | BBC White season: 'Rivers of Blood' >
Rope is made from String | 8 comments (8 topical, 0 hidden) | Trackback
i seem to vaguely remember by i (2.00 / 0) #1 Tue Oct 31, 2006 at 05:45:42 AM EST
the original sgi stl having a "rope" class which was the basis of their "string" class. your approach appears to be similar to theirs iirc.




rope vs string by fluffy (2.00 / 0) #2 Tue Oct 31, 2006 at 06:35:12 AM EST
Rope isn't the basis for string, it's an alternate implementation of it. STL's string class is basically a std::vector with more operators on it (operator+, substring, etc.). You're supposed to use string for shorter, immutable things, while you're supposed to use rope for longer things which are going to be concatenated and so on.
--
ceci n'est pas une signature
i like plaid
[ Parent ]

sgi rope by codemonkey uk (2.00 / 0) #3 Tue Oct 31, 2006 at 02:00:29 PM EST
The sgi version of stl has a rope implementation, though I was familiar with it's interface & design requirements, my implementation is independently developed, by me, for fun.

The sgi string class is a fairly normal string implementation, and is not based on the rope (the opposite is probably true, if my implementation is anything to go by). The performance characteristics of rope vs string are quite different, as fluffy pointed out, strings are more efficient for "small" amounts of data, or simple transformations.

One neat consequence of ropes is that, where you to create a text editor, the edit-history/undo buffer comes for "free", where as an implementation based on editing a string would require either more programming effort, or more memory, or both.

--- Thad ---
iPhone Game!
[ Parent ]

care to explain how it works? by martingale (2.00 / 0) #4 Tue Oct 31, 2006 at 02:16:32 PM EST
I mean the algorithm, in English? (*)

(*) I could read the C++, but then I'd have nothing to ask on husi.
--
$E(X_t|F_s) = X_s,\quad t > s$


it's a tree by codemonkey uk (4.00 / 1) #7 Wed Nov 01, 2006 at 10:23:16 AM EST
a rope is a reference counted pointer to a "rope rep" which can be one of: a string (which contains actual characters), a concatenation (which contains left/right pointers to rope reps), a sub string (which contains a rope rep and a start/end index), or perhaps other things which can do the things a rope rep needs to do.

The clever bits are in the details, which i leave as an exercises for the reader to discover. ;)

--- Thad ---
iPhone Game!
[ Parent ]

interesting by martingale (2.00 / 0) #8 Wed Nov 01, 2006 at 03:27:33 PM EST
Neat idea. Sounds not too far from a parse tree for a line editor.
--
$E(X_t|F_s) = X_s,\quad t > s$
[ Parent ]

Poh kai by theboz (2.00 / 0) #5 Tue Oct 31, 2006 at 05:20:17 PM EST
Cantonese for something like, "I tripped on a string", but in reality is used to mean something more like, "Oh fuck!"
- - - - -
That's what I always say about you, boz, you have a good memory for random facts about pussy. -- joh3n


hm by i (4.00 / 1) #6 Wed Nov 01, 2006 at 12:13:34 AM EST
so that's where the name of KAI C++ comes from.


[ Parent ]

Rope is made from String | 8 comments (8 topical, 0 hidden) | Trackback