[fa.editor-p] buffer structures

ARPAVAX:C70:editor-people (09/17/82)

>From EAK@MIT-MC Fri Sep 17 01:51:44 1982
No linked list of lines editor that I know of (including Multics
EMACS, ZWEI, CCA EMACS, Gossling EMACS, TORES etc.) has ever
implemented the EMACS buffer bounds concept.  This probably has
to do with a more basic limitation of the linked list of lines
approach; namely, you can't easily tell which of two buffer
positions is "first" efficiently.

It seems to me that other ways of implementing buffer bounds
should exist, but since no one has done so, and because I think
bounds are a real feature, I dislike the linked list of lines
approach.

Also, relocating marks efficiently in a buffer gap scheme is
easy.  I have code that anyone can look at if they care.
Marks a certainly NOT a reason for linked lists.

Another interesting possibility is a binary-tree of "text" (which
I prefer to lines for the reasons KLH gives).  It is possible to
compare buffer positions in log time using such structures.

ARPAVAX:C70:editor-people (09/20/82)

>From z@CCA-UNIX Mon Sep 20 01:54:22 1982
CCA EMACS uses an array of line pointers rather than a linked list of
lines; in such a scheme I don't see any problem in implementing
buffer bounds or in efficiently determining which of two buffer
positions is "first".

Actually, the only reason I haven't implemented buffer bounds in CCA
EMACS is that they're somewhat low in priority; they are definitely
on my list to be done, though, and their implementation is
straightforward.  If they had been designed-in from the start, they
would have been quite trivial to put in.  However, I started out with
Montgomery's EMACS and have had to retrofit a lot of stuff.  The same
goes for nondrifting marks; this is also a feature which has recently
been installed.

To determine the relative positions of two points may take two
comparisons in a line-oriented editor compared to one in a buffer gap
editor, but in terms of actual peformance this difference is
insignificant.  In actual execution, only one comparison is usually
needed anyway.  All in all, I am quite happy with the line oriented
approach, and I think it is a major reason why command execution
speed in CCA EMACS is generally quite fast.

	Steve Zimmerman

ARPAVAX:C70:editor-people (09/20/82)

>From GZ@MIT-MC Mon Sep 20 02:42:30 1982
I don't see what the difficulty is with implementing virtual bounds
in the linked list of lines scheme.  If you mean the fact that the break
can occur in the middle of the line, well, you split the line at the given
point, and merge it back when lifting the bounds. Of course you unlink the
out-of-bounds parts and keep 'em somewhere else, so the problem of verifying
relative positions only comes up when you are changing bounds, not all the
time.  Implementing virtual bounds would be no worse than any region operation.

I do agree though that the problem of comparing positions is one of the
major disadvantages of the linked list approach, making all region hacking
more expensive.

Also, a correction: Gosling's emacs uses the buffer+gap scheme.

ARPAVAX:C70:editor-people (09/20/82)

>From z@CCA-UNIX Mon Sep 20 02:46:18 1982
CCA EMACS uses an array of line pointers rather than a linked list of
lines; in such a scheme I don't see any problem in implementing
buffer bounds or in efficiently determining which of two buffer
positions is "first".

Actually, the only reason I haven't implemented buffer bounds in CCA
EMACS is that they're somewhat low in priority; they are definitely
on my list to be done, though, and their implementation is
straightforward.  If they had been designed-in from the start, they
would have been quite trivial to put in.  However, I started out with
Montgomery's EMACS and have had to retrofit a lot of stuff.  The same
goes for nondrifting marks; this is also a feature which has recently
been installed.

To determine the relative positions of two points may take two
comparisons in a line-oriented editor compared to one in a buffer gap
editor, but in terms of actual peformance this difference is
insignificant.  In actual execution, only one comparison is usually
needed anyway.  All in all, I am quite happy with the line oriented
approach, and I think it is a major reason why command execution
speed in CCA EMACS is generally quite fast.

	Steve Zimmerman