source: project/wiki/eggref/4/gap-buffer @ 26319

Last change on this file since 26319 was 26319, checked in by Ivan Raikov, 8 years ago

initial documentation for gap-buffer

File size: 5.4 KB
Line 
1[[tags: eggs]]
2
3== gap-buffer
4
5Gap buffer implementation.
6
7
8[[toc:]]
9
10=== Description
11
12A gap buffer is a structure that models a string but allows relatively
13efficient insertion of text somewhere in the middle.  The insertion
14location is called `point' with minimum value 1, and a maximum value of the
15length of the string (which is not fixed).
16
17Specifically, we allocate a continuous buffer of characters that is
18composed of the BEFORE, the GAP and the AFTER (reading L->R), like so:
19
20                          +--- POINT
21                          v
22    +--------------------+--------------------+--------------------+
23    |       BEFORE       |        GAP         |       AFTER        |
24    +--------------------+--------------------+--------------------+
25
26     <----- bef-sz ----->|<----- gap-sz ----->|<----- aft-sz ----->
27
28     <-------------------|       usr-sz       |------------------->
29
30     <-------------------------- all-sz -------------------------->
31
32This diagram also shows how the different sizes are computed, and the
33location of POINT.  Note that the user-visible buffer size `usr-sz'
34does NOT include the GAP, while the allocation `all-sz' DOES.
35
36The consequence of this arrangement is that "moving point" is simply a
37matter of kicking characters across the GAP, while insertion can be
38viewed as filling up the gap, increasing `bef-sz' and decreasing
39`gap-sz'.  When `gap-sz' falls below some threshold, we reallocate
40with a larger `all-sz'.
41
42In the implementation, we actually keep track of the AFTER start
43offset `aft-ofs' since it is used more often than `gap-sz'.  In fact,
44most of the variables in the diagram are for conceptualization only.
45
46(The term and concept of "gap buffer" are borrowed from Emacs.  We
47 will gladly return them when libemacs.so is available. ;-)
48
49=== Library Procedures
50
51<procedure>gb? :: OBJECT -> BOOL</procedure>
52
53Returns {{#t}} if the given object is a gap buffer object, {{#f}} otherwise.
54
55<procedure>make-gap-buffer :: [INIT] -> GAP-BUFFER</procedure>
56
57Returns a new gap buffer. Optional argument {{INIT}} is either a port
58to read from; a string, used to initialize the buffer contents; or an
59integer specifying the memory allocation (in bytes) requested. Point
60is left at the maximum position.
61
62==== Querying
63
64<procedure>gb-point :: GAP-BUFFER -> INTEGER</procedure>
65
66Returns the position of point in the given gap buffer. This is an
67integer starting with 1.
68
69<procedure>gb-point-min :: GAP-BUFFER -> INTEGER</procedure>
70
71Return the minimum position possible for point in the gap buffer. In
72the current implementation, this value is always 1 (one).
73
74<procedure>gb-point-max :: GAP-BUFFER -> INTEGER</procedure>
75
76Returns the maximum position possible for point in the given gap
77buffer. This value can be changed by inserting text into the buffer.
78
79==== Munging
80
81<procedure>gb-insert-string! :: GAP-BUFFER * STRING -> VOID</procedure>
82
83Inserts the given string into the given gap buffer, moving point
84forward as well as increasing the value that would be returned by
85{{gb-point-max}}.
86
87<procedure>gb-insert-char! :: GAP-BUFFER * CHAR -> VOID</procedure>
88
89Inserts the given character into, moving point forward as well as
90increasing the value that would be returned by {{gb-point-max}}.
91
92<procedure>gb-delete-char! :: GAP-BUFFER * INTEGER -> VOID</procedure>
93
94Deletes the given number of characters from point, forward if the
95integer argument is positive, backward if it is negative. (If zero, do
96nothing.) Deleting backwards moves point backwards. Deleting forwards
97or backwards decreases the value that would be returned by
98{{gb-point-max}}.
99
100<procedure>gb-erase! :: GAP-BUFFER -> VOID</procedure>
101
102Completely erases the gap buffer. Point is left at the minimum
103position possible.
104
105==== Moving
106
107<procedure>gb-goto-char :: GAP-BUFFER * INTEGER -> INTEGER</procedure>
108
109Moves point to the given point and returns it. If the new point is
110outside the minimum and maximum positions possible, it is adjusted to
111the the nearest boundary (however, the return value is unchanged).
112
113==== Transforming
114
115<procedure>gb->string :: GAP-BUFFER -> STRING</procedure>
116
117Return a new string representing the text of the gap buffer. Point does not move.
118
119<procedure>gb-filter! :: GAP-BUFFER * PROCEDURE -> VOID</procedure>
120
121Passes the string representing the contents of the gap buffer to the
122given procedure, and uses its return value to replace the contents of
123the gap buffer. Point is set to the maximum position.
124
125<procedure>gb->lines :: GAP-BUFFER -> LIST</procedure>
126
127Returns a list of strings representing the lines of text of the gap
128buffer. Newlines are automatically removed. A buffer with N newlines
129results in a list of length N+1. Point does not move.
130
131
132=== Examples
133
134
135=== Version History
136
137* 1.0 Initial Release
138
139=== License
140
141The {{gap-buffer}} library was written by Thien-Thi Nguyen for Guile Scheme.
142
143{{gap-buffer}} was ported to Chicken Scheme by Ivan Raikov.
144
145 Copyright (C) 2002, 2003, 2006 Free Software Foundation,
146 Inc.
147 
148 This program is free software: you can redistribute it and/or
149 modify it under the terms of the GNU Lesser General Public License
150 as published by the Free Software Foundation, either version 3 of
151 the License, or (at your option) any later version.
152 
153 This program is distributed in the hope that it will be useful, but
154 WITHOUT ANY WARRANTY; without even the implied warranty of
155 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
156 General Public License for more details.
157 
158 A full copy of the Lesser GPL license can be found at
159 <http://www.gnu.org/licenses/>.
160
Note: See TracBrowser for help on using the repository browser.