Gseq/Lseq library (preliminary name)

Gseq/Lseq is a libraray that implements a very efficient editable sequence

The Gseq (for "generalized sequence"; we are open to better names) protocol allows the user to insert and delete elements at arbitrary points in a sequence of elements. The point of insertion and deletion is given as indexes (from 0 to the length of the vector inclusive)

The Lseq (for "locator sequence"; again, we need a better name) is an extension of the Gseq protocol, where the sequence can hold an arbitrary number "locators" which are similar to cursors. Editing operations use cursors to determine the point of insertion or deletion

Using the Gseq protocol on an Lseq object correctly preserves the position of the locators

The libraries are implemented in Common Lisp. The basic representation is similar to that of a gap-buffer used by popular editors such as Emacs, with the difference that the Gseq/Lseq can be created to hold objects of any Common Lisp type. Specializing to characters or bytes make for a very compact representation, whereas leaving the type unspecified allows the users to store any Common Lisp object.

We optimize the an important way compared to traditional gap-buffer implementations. Internally, the buffer is circular. There are two major advantages to this circularity. First, we never have to move more than half of the objects, whereas traditional implementations may have to move all objects. Second, our implementation can be used as a very efficient queue (insert at end, delete at beginning), whereas a sequence of such operations represents the worst-case performance for traditional implementation.

Potential clients

We know of one sure and two potential clients. Gsharp will use this library at many levels in the representation of a score buffer. We hope to convince Tim Moore to use it in the buffer representation of Goatee, the editor that is part of the McCLIM project. Finally, hope to convince Gilbert Baumann (or someone else working on portable Hemlock) to replace the representation of buffer lines by this library.

We would of course be delighted if others can use our library as well. The license is LGPL so has very few restrictions

We welcome comments to the documentation and the code. Notice, however, that the code is not quite finished yet. We hope to have a first official distribution very soon now (in the next couple weeks).

What exists now

We have some documentation that contains both a description of the protocols and of the implementation.

We also have some preliminary code. The code consists of four files: package.lisp (containing package definitions, utilities.lisp (containing a few utilities used in the rest of the code), gseq.lisp (containing the implementation of the Gseq protocol (mostly finished)), and finally lseq.lisp (containing a partial implementation of the Lseq protocol)