chickadee » gap-buffer

Outdated egg!

This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for the CHICKEN 5 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

gap-buffer

Gap buffer implementation.

Description

A gap buffer is a structure that models a string but allows relatively efficient insertion of text somewhere in the middle. The insertion location is called `point' with minimum value 1, and a maximum value of the length of the string (which is not fixed).

Specifically, we allocate a continuous buffer of characters that is composed of the BEFORE, the GAP and the AFTER (reading L->R), like so:

                         +--- POINT
                         v
   +--------------------+--------------------+--------------------+
   |       BEFORE       |        GAP         |       AFTER        |
   +--------------------+--------------------+--------------------+
    <----- bef-sz ----->|<----- gap-sz ----->|<----- aft-sz ----->
    <-------------------|       usr-sz       |------------------->
    <-------------------------- all-sz -------------------------->

This diagram also shows how the different sizes are computed, and the location of POINT. Note that the user-visible buffer size `usr-sz' does NOT include the GAP, while the allocation `all-sz' DOES.

The consequence of this arrangement is that "moving point" is simply a matter of kicking characters across the GAP, while insertion can be viewed as filling up the gap, increasing `bef-sz' and decreasing `gap-sz'. When `gap-sz' falls below some threshold, we reallocate with a larger `all-sz'.

In the implementation, we actually keep track of the AFTER start offset `aft-ofs' since it is used more often than `gap-sz'. In fact, most of the variables in the diagram are for conceptualization only.

(The term and concept of "gap buffer" are borrowed from Emacs. We will gladly return them when libemacs.so is available. ;-)

Library Procedures

gb?procedure

Returns #t if the given object is a gap buffer object, #f otherwise.

make-gap-bufferprocedure

Returns a new gap buffer. Optional argument INIT is either a port to read from; a string, used to initialize the buffer contents; or an integer specifying the memory allocation (in bytes) requested. Point is left at the maximum position.

Querying

gb-pointprocedure

Returns the position of point in the given gap buffer. This is an integer starting with 1.

gb-point-minprocedure

Return the minimum position possible for point in the gap buffer. In the current implementation, this value is always 1 (one).

gb-point-maxprocedure

Returns the maximum position possible for point in the given gap buffer. This value can be changed by inserting text into the buffer.

Munging

gb-insert-string!procedure

Inserts the given string into the given gap buffer, moving point forward as well as increasing the value that would be returned by gb-point-max.

gb-insert-char!procedure

Inserts the given character into, moving point forward as well as increasing the value that would be returned by gb-point-max.

gb-delete-char!procedure

Deletes the given number of characters from point, forward if the integer argument is positive, backward if it is negative. (If zero, do nothing.) Deleting backwards moves point backwards. Deleting forwards or backwards decreases the value that would be returned by gb-point-max.

gb-erase!procedure

Completely erases the gap buffer. Point is left at the minimum position possible.

Moving

gb-goto-charprocedure

Moves point to the given point and returns it. If the new point is outside the minimum and maximum positions possible, it is adjusted to the the nearest boundary (however, the return value is unchanged).

Transforming

gb->stringprocedure

Return a new string representing the text of the gap buffer. Point does not move.

gb-filter!procedure

Passes the string representing the contents of the gap buffer to the given procedure, and uses its return value to replace the contents of the gap buffer. Point is set to the maximum position.

gb->linesprocedure

Returns a list of strings representing the lines of text of the gap buffer. Newlines are automatically removed. A buffer with N newlines results in a list of length N+1. Point does not move.

Examples

Version History

License

The gap-buffer library was written by Thien-Thi Nguyen for Guile Scheme.

gap-buffer was ported to Chicken Scheme by Ivan Raikov.

Copyright (C) 2002, 2003, 2006 Free Software Foundation,
Inc.

This program is free software: you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public License
as published by the Free Software Foundation, either version 3 of
the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

A full copy of the Lesser GPL license can be found at
<http://www.gnu.org/licenses/>.

Contents »