Russell Senior <seniorr@aracnet.com> wrote:
+---------------
| I have recently had need for a way of holding sequences longer than
| will fit in a particular implementation's array ... In response, I
| "invented" a buffer-list, a list of buffers with the wrinkle that
| the list is actually a list of lists, where the sublists are
| (buffer-length buffer)...
...
| Having developed these functions to a stage where they are useful to
| me, it has entered my consciousness that this problem has certainly
| presented itself to others before and I am curious how they might have
| solved the problem. I did a little googling around but didn't find
| anything relevant. Do my "buffer-lists" have another more typical name?
+---------------
The term I'm most familiar with for that general concept is "cords",
as described in the Boehm-Demers-Weiser conservative garbage collector
<URL:http://www.hpl.hp.com/personal/Hans_Boehm/gc/>:
The garbage collector distribution includes a C string
(cord [1]) package that provides for fast concatenation and
substring operations on long strings. A simple curses- and
win32-based editor that represents the entire file as a cord
is included as a sample application.
[1] <URL:http://www.hpl.hp.com/personal/Hans_Boehm/gc/gc_source/cordh.txt>
is the header file for the cord package, which says (with C comment chars
stripped):
Cords are immutable character strings. A number of operations
on long cords are much more efficient than their strings.h
counterpart. In particular, concatenation takes constant time
independent of the length of the arguments. (Cords are represented
as trees, with internal nodes representing concatenation and
leaves consisting of either C strings or a functional description of
the string.)
Note particularly that bit about allowing functional representations
for leaves. In the cords package, "functional" leaves are actually
implemented in C as closures(!!) which are (virtual) accessors for
the strings they represent. Again from "cordh.txt":
/* Cords may be represented by functions defining the ith character */
typedef char (* CORD_fn)(size_t i, void * client_data);
In CL you could do that, too. Or depending on your needs, maybe make the
closures be just thunks that when called return the data they represent
as strings or as further cords of strings and/or thunks. I've seen
several server-side dynamic HTML systems (mostly in Scheme, as it happens)
that do something similar when generating web pages -- that is, there's
a generation phase that produces a cord-like tree of strings and/or
closures, and an output phase that walks the tree outputting the strings
and calling the closures [usually thunks], which return strings. (Or more
trees, which...)
So you might want to consider adding these two features of "cords" --
trees [possibly (re)balanced] and closures -- to your "buffer-lists".
-Rob
-----
Rob Warnock, 30-3-510 <rpw3@sgi.com>
SGI Network Engineering <http://www.meer.net/~rpw3/>
1600 Amphitheatre Pkwy. Phone: 650-933-1673
Mountain View, CA 94043 PP-ASEL-IA
[Note: aaanalyst@sgi.com and zedwatch@sgi.com aren't for humans ]