Update of /project/climacs/cvsroot/papers/ilc2005/syntax In directory common-lisp.net:/tmp/cvs-serv10331

Modified Files: climacssyntax.tex Log Message: Update the section about the proposed sequence-of-lines structure

Date: Tue May 24 17:01:49 2005 Author: bmastenbrook

Index: papers/ilc2005/syntax/climacssyntax.tex diff -u papers/ilc2005/syntax/climacssyntax.tex:1.28 papers/ilc2005/syntax/climacssyntax.tex:1.29 --- papers/ilc2005/syntax/climacssyntax.tex:1.28 Tue May 24 16:23:44 2005 +++ papers/ilc2005/syntax/climacssyntax.tex Tue May 24 17:01:49 2005 @@ -196,30 +196,34 @@ is alleviated by sharing significant portions of older buffer versions with newer versions.

-There is scope for provision of further buffer implementations in -Climacs, one of which will use a sequence of lines organised into a -tree for quick access. In this structure, a line can be considered -opened or closed. When a line is opened, it is represented as a -Flexichain {\tt cursorchain}. All editing operations are performed on -open lines, and a fixed number of lines are kept opened according to a -least-recently-used scheme. When a line is closed it is converted to -a vector for efficient storage and access. If the line contains only -{\tt base-char} objects this vector is a {\tt base-string}; otherwise, -it is unspecialised. +It is anticipated that Climacs will provide several other buffer +implementations, one of which will use a sequence of lines organised +into a tree for quick access. In this structure, a line can be +considered opened or closed. When a line is opened, it is represented +as a Flexichain {\tt cursorchain}. All editing operations are +performed on open lines, and a fixed number of lines are kept opened +according to a least-recently-used scheme. When a line is closed it +is converted to a vector for efficient storage and access. If the +line contains only {\tt base-char} objects this vector is a {\tt + base-string}; otherwise, it is unspecialised.

This structure has the advantage of efficient line-based access in the -buffer. It also provides much better behaviour than that of a single -gap buffer when a user is editing two disparate sections in a large -file. With a single gap buffer, the gap must be moved to the point of -edit before an edit operation is allowed; when the buffer is large and -edit operations occur frequently at multiple locations in the buffer, -this requires a substantial amount of copying between edits. In this -situation single-gap-buffer editors such as GNU Emacs will noticeably -pause between edits to move the gap. A structure which contains a -sequence of lines and keeps the most recently used lines open as gap -buffers can operate as a multi-gap buffer with automatic gap -placement, while not suffering poor performance when accessing a -specific line in the buffer. +buffer, in contrast to a single gap buffer implementation, where +determining the line number of a mark or placing a mark at a specific +line is $O(n)$, as the entire buffer must be scanned to determine how +many newlines precede the mark. The proposed structure also provides +much better behaviour than that of a single gap buffer when a user is +editing two disparate sections in a large file. With a single gap +buffer, the gap must be moved to the point of edit before an edit +operation is allowed; when the buffer is large and edit operations +occur frequently at multiple locations in the buffer, this requires a +substantial amount of copying between edits. In this situation +single-gap-buffer editors such as GNU Emacs will noticeably pause +between edits to move the gap. A structure which contains a sequence +of lines and keeps the most recently used lines open as gap buffers +can operate as a multi-gap buffer with automatic gap placement, while +not suffering poor performance when accessing a specific line in the +buffer.

The efficiency of Climacs buffers depends of course on the implementation of the buffer protocol that is used. Space efficiency