Re: Looking for a design pattern
On Aug 11, 9:18 am, Michael Doubez <michael.dou...@free.fr> wrote:
On 10 ao=FBt, 23:52, Jerry Coffin <jerryvcof...@yahoo.com> wrote:
In article <4a808b83$0$426$426a7...@news.free.fr>,
michael.dou...@free.fr says...
[ ... ]
The idiomatic choice for those who have made some
editors from scratch (not just using an edit
control/widget).Look up "cursor gap" in Wikipedia or
wherever.
I had a look on wikipedia ... as clear as the bottom of my socks.
The idea is pretty simple, really. When you're editing a
text file, you separate the file into two pieces: everything
that's before the cursor, and everything that's after the
cursor.
That I understood but what do you gain except an amortized
copy ? I guess it is memory cost effective.
You don't get a large copy on inserting near the beginning of
the buffer. It was an important issue 30 or 40 years ago, when
using the equivalent of std::vector< char >, an insertion near
the beginning of a large body of text visibly slowed things
down. Measurements made by a collegue roughly 20 years ago
showed that it wasn't an issue then; unless machines have gotten
slower since then, it isn't an issue today.
Those two pieces are place into memory with the part that's
before the cursor at the very beginning of the buffer, and
the part that's after the cursor at the very end of the
buffer. In between the two, you have a "gap" of unused
memory space. When/if the user enters new text, you add the
characters into that memory space (for overwrite mode, you
write at the end of the gap instead of the beginning).
That has the sake of simplicity but if you maintain a list of
modification (like rope or another list structure with
modifications stored in a scratch buffer) until next write to
file then insertion and deletion seems cheap to me.
Boehm designed Rope expressedly for this type of use. It also
handles spilling to disk gracefully, since you merge and spill
blocks, keeping the merged block header with the reference to
the disk image. (When spilling a gap buffer, it's usual to
maintain two separate spill zones, at each end, and maintain one
of them in reverse order.)
I'm not sure that spilling is an important issue today; if the
text doesn't fit in memory, it seems reasonable to require the
user to split it up into several files. Back when a process
could only have 64 KB of memory, however, efficient spilling was
an important design issue.
I have never tried to write a text editor but this approach
appeals me more than gap buffer.
When the user moves the cursor, you copy text from one side
of the gap to the other. Since the user usually only moves
the cursor in small increments (word, line, possibly page)
I don't know what you call small increment but, on a daily
basis, I move between marks, end/beginning of line,
next/previous char/word/ symbol ... I move much more than I
write; I expect the gap is created on the first modification.
The gap is always there. Of course, when the cursor is one end
of the file, the amount of text on the other side of the gap is
0. (When you start up the editor, most editors put the cursor
at the beginning of the file, which means all of the text is in
the end buffer, and the gap is at the start.)
Don't mistake me. I don't discuss the usefulness of the
technique but I try to understand the forces that apply to
such a design.
Today, nothing. Even in the older times, I think that the line
oriented approach used by vi was probably preferable (but then,
I've never cared much for emacs---and this really is an emacs
vs. vi argument). Today, just use std::vector< char > or
std::vector< std::vector< char > > until the profiler says
otherwise, wrapping it in a class which presents a minimal
interface to the rest of the code, to facilitate changing it if
that moment ever comes.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34