Re: Immutable Ropes

It would be useful in decoding large files like iCalendars or .vcf
with many cards, because as you decode into objects, those objects
would hold reference to main Rope, memory would not have to be
duplicated.

I used <rope> from SGI STL lib when doing a RFC822 decoder in C++. It
made the claim about how a rope could actually be on disk... but didn't
implement it. Too bad, that too would be useful when decoding large
files on disk, to avoid brining them into memory except as needed.

Are there any implementation of Rope that actually do the disk cacheing?

Sam

Quoting [e-mail], on Tue, Mar 15, 2005 at 10:18:28PM +0900:
> Note how I didn't write "Immutable Strings" in the subject.
> 
> Boehm describes in [1] a data structure, called a _rope_, that can be
> used to represent very long strings efficiently.  The way they are
> implemented, where operations that modify the rope return a new rope
> that shares as much data as possible with the old one (i.e., a
> functional interface), also leads to the nice property that ropes may be
> heavily altered without wasting a lot of memory.  Another nice property
> is that as one abstracts away the pointer-to-char, ropes can be created
> lazily from IO or other generators of data.  As an example, say that we
> want a String of one million a's
> 
> s = "a" * 1000000
> 
> With a Rope, we could have written this as:
> 
> r = Rope.new("a", 1000000)
> 
> and that could be represented very efficiently.  A better example is if
> we would like to search the concatenation of two strings for a regular
> expression.  Using only Strings, we would have to write this as:
> 
> s1 + s2 =~ /.../
> 
> where the whole concatenation of s1 and s2 has to be created before the
> matching can take place, taking both O(max(s1.length, s2.length)) time
> and space, whereas with ropes this could be written as:
> 
> r1 + r2 =~ /.../
> 
> and the concatenation would simply be a O(1) time and space operation of
> creating a new concatenation node, representing the concatenation of the
> two ropes.
> 
> The implementation of ropes is rather straight-forward and fits well
> with the garbage-collection model of memory allocation, so I was
> wondering if there was any interest in seeing a Rope object in Ruby 2.0.
> It would give us that immutable string representation that everyone is
> always talking about as a plus for choosing Python.  Ropes are also a
> lot more memory-friendly than Strings for cases where the text sequence
> is long, or is to be heavily modified.
> 
> Comments?,
> 	nikolai
> 
> [1] Hans-J Boehm, "Ropes: an Alternative to Strings", Software--Practice
> and Experience, vol. 25(12), 1315--1330, Dec. 1995.
> 
> -- 
> ::: name: Nikolai Weibull    :: aliases: pcp / lone-star / aka :::
> ::: born: Chicago, IL USA    :: loc atm: Gothenburg, Sweden    :::
> ::: page: www.pcppopper.org  :: fun atm: gf,lps,ruby,lisp,war3 :::
> main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}
>