Подкиньте пожалуйста доку о том как написать редактор

Boyus drugoi doki krome golovy net i ne budet...

2anonymous: если что найдешь плиз кинь мне на eugene@enerpred.ru. Кинь туда же мессагу сразу чтоб я твой адрес поймал, может у меня что есть или найду.

Читал неплохую статью Андрея Зубинского про это в "Компьютерном
обозрении" за прошлый год. Ищи на www.itc.kiev.ua...

2stormbringer: Пишите сюда лучше оба, если что найдёте, мне тоже интересно :-)
Насчёт структуры для представления текста: часто используется "буфер с дыркой", описание можно найти например на http://www.cs.cmu.edu/~wjh/papers/byte.html

Народ привет это я задал вопрос. Очень спасибо Андрею Зубинскому за его статью : http://itc-ua.com/article.phtml?ID=5264 и за ссылку justme будем пробовать и втыкать, хоть и сесия на носу. С Николсом Виртом знаком, конкретного ничего нет, делал по нему лабы :) а вот про Д. Кнута(он сортировки анализировал), А. Ахо не знаю. Одно понял, что за один день редактор не соштопаеш, и нужно подходить с разных сторон. Кто заинтересован пишите stanv@mailru.com

Есть ещё такая вещь (правда, сильно продвинутая, и скорее для IDE, чем для редакторов):
Tim A. Wagner. Practical Algorithms for Incremental Software Development Environments. PhD thesis (http://www.cs.berkeley.edu/~harmonia/papers/twagner-thesis.ps.gz)

Народ, умираю!
Не могу найти в интернете описание таких структур как
таблицы кусочков
буфер фиксированого размера
пропасть

G> Hello out there. I'm currently writing a UN*X text editor. I

I'm kind of thinking about doing that myself. It's a bit of a
rite-of-passage. But I would recommend looking at other sources, in
particular those for the editor "joe", and possibly the text system
described by Wirth in his book on the Oberon system, for alternative
ways of doing this.

G> in one file). So after all this, I've basically got one idea
G> for a basic routine. ee uses a linked list to hold the text,
G> with structures looking something like this:

G> structure text { char *line; int length; int max_length; int
G> line_number; struct text *previous; struct text *next; };

Oops, supercite mangled your code. Anyway, there are other data
structures than a linked list of lines. Your first stop should be
Deja News and Alta Vista; I recommend searching for "buffer gap", for
reasons that will become clear. Note that my discussion of methods
used in particular editors is based on rumours (mostly here) rather than
on reading the sources, since I find it painful to extract algorithms
from actual code.

GNU emacs (allegedly) uses what's called a buffer gap, which is a
(fairly) popular rival to the linked-list-of-lines approach you
describe. A buffer consists of a large chunk of chars with a `hole'
in it. Typically this hole coincides with the cursor, and it's
contents are garbage. The gap is represented by two pointers into the
text; one before (which I will call the "point") and one after the gap
(which I will call the "mark"). To insert a character at the cursor
the character is written to the array at point, and point is advanced
one place. To append a character after the cursor the char is written
at "mark", which is decremented by one. To move the cursor, each
charater it moves over is copied from the point side to the mark side
of the gap, and the pointers adjusted.

This method makes inserting and deleting characters easy, and
independent of the number of characters in a line; people occasionally
edit binary files, and they expect their editor not to break, or to
sulk. OTOH, moving the cursor from the beginning of the file to the
end (in one go) causes the entire buffer contents to be copied from
one side of the text area to the other, which can be painful for large
files or small memories. A recent flame war on easy editors (I think)
concluded that Emacs did indeed use this data structure for text
buffers, although (bizarrely) it uses an improved method for property
buffers, which hold colour coding, and other not-directly-textual
information.

"joe" uses a simple (and effective) improvement to this scheme: you
simply have a doubly linked list of "chunks", each with its own point
and mark. This maintains efficient long distance cursor movement,
without assuming that text must be newline delimited. It does,
however, increase the complexity of the code, and of auxilliary
operations like, say, regular expression search and replace. Joe's
author (Joseph H. Allen) posts here from time to time, and a DejaNews
search will acquaint you with his thoughts on these matters.

Wirth's Oberon text system handles different (simmultaneous) fonts, by
using what he calls a piece-chain structure, which simply uses a
linked list of chunks, each of one type of text, and a chunk header
which stores the type.

Given that the Unix world has already more editors than could possibly
be required, and a dearth of even modest word-processing type apps, I
would urge you at least to consider allowing mutliple fonts in one
document. You don't have to rewrite Word; we don't even have a
competitor for Notepad (simple wysiwyg-ish thing with RTF output).
And no, XEmacs does _not_ count.

G> books on writing editors, I wonder if any comp.editors readers

There was a book by Finseth (if memory serves), but it's out of print.
Wirth's book contains the full details of _all_ of his Oberon
operating system, including the text system. The Plan 9 (Plan 9 is
what the Bell Labs crowd -- Ken Thompson, Dennis Richie, and so on
-- developed to replace UNIX) text editors, Sam and Acme, have radical
models of text editing in a mouse enabled world, and Rob Pike (their
author) has written articles on them. Sam has a UNIX port (freely
available in source form, but I don't know what license) and Acme has
a Unix reimplementation called Wily. Wily's homepage is
http://www.cs.su.oz.au/~gary/wily/. Sam docs (user guide and
implementation details) are at
http://plan9.bell-labs.com/plan9/doc/sam.html. A literature search
of (gasp!) academic journals may well provide more leads.

G> have any ideas. I'm interested in alternatives to the
G> linked-list method, as well as any general methods for doing
G> all the things that an editor *must* do. I don't need anything
G> fancy, like syntax highlighting or a macro language.

Lots of people want these and more. I know I do. For non-power-users
who find pico a bit too limited joe is probably ideal. It has all the
things you seem to want (including pico emulation, when started as
"jpico", or with the appropriate resource file), it's simple to start
with, but without sacrificing full regexp support when it's needed,
and it can edit large binaries without pain. Try it, and even if you
don't want to use it, read the source code for a (GLP'ed)
implementation of the linked list of buffer gaps method I mentioned.
But unless you're just having fun I think you'll find it renders your
proposed editor unnecessary. Lest this sound too much like an advert,
I should mention that it lacks colour syntax highlighting, and that I
use Emacs myself, with occasional outbreaks of vi.

Should there be a FAQ on editor internals for this group, with all
this material in? These questions do crop up from time to time, and
piecing together the information from scratch can be a chore. I'd
offer to maintain one, but I'm shortly going to leave College and
collide with the Real World(tm). I'd certainly be willing to help
out.

<rant>
But I really, really think that this particular wheel has been
reinvented often enough. What _I_ want is a toy word
processor/editor, like wordpad on steroids, say, which could be used
for writing simple letters to Auntie (for the Windoze crowd), and to
make programming more pleasant (different faces for different bits of
syntax), and a nice HTML mode. XML (a sort of SGML-lite) is coming,
and its facilities for structured documents could make it a snap to
develop literate programming envronments, without locking you in to
one set of tools, or using (eek!) embedded TeX. You could have DTD's
for almost every application, and finally supercede the (admittedly
powerful) Unix "everything is stream of bytes" philosophy with a
universally understood set of conventions for _structured_ documents.
Word processors could use XML for storage! You could share files
across platforms! You could even still use Emacs or vi or joe, if you
wanted to!

I know XEmacs can (probably) do all this, but I want a small, fast,
cute version, that doesn't eat all my RAM. I want to use proportional
fonts to edit text (which Sam and Wily allow) without changing my
entire world-view (which they tend to insist on), and I don't care if
it won't run on a vt100. It's _1997_ for heaven's sake! I have a
windowing system! (Admittedly, it's only X, but it's still a window
system!) At the moment, my desktop has a bunch of terminal emulators,
and a couple of GNU emacs frames open. These are powerful tools, but
they hardly constitute a rich GUI environment that would make me the
envy of all my friends (they lust after the stability of my system,
but they run away screaming when confronted with the tools. And they
are neither stupid nor technophobic).

I don't want a ultra-heavy power tool, and I don't care about slow
serial lines: I already have tools for those jobs. I just want a
sprinkling of nice fonts, and an interface doesn't scare off Windows
or Mac users. Context sensitive pop-up menus might be nice, and a
reasonable (in terms of looks and functionality) menu bar, too.
Real-time spell-checking along the lines of Word is quite a nice idea,
too -- spellchecking email and Usenet posts is overkill if it takes
any effort at all. (Even M-x ispell-buffer is effort: I have to
remember to bother.) Notepad on steroids, is all I want, really. And
it has to be free (as in freedom-not-price, that is).

Does anyone have one, or do I really have to roll my own? And does
anyone have any info on (or pointers to) suitable data structures for
such a thing?

Standard Unix tools are very powerful, and for some things I find them
indispensible. But, for me at least, vt100 compatibility is a legacy
issue. Sometimes I use remote systems, and then I telnet in and use
vi, and I'm happy to do so. But most of the time I'm on my own Linux
box, with 16Mb and clock cycles to burn. I can afford some luxuries,
but I don't want a whole XEmacs. Is this really so weird, this late
in computing history? Or did I swear a vow of allegience to xterms
and proportional fonts when I signed on as a Unix user? Am I the only
person who finds the current situation imperfect? Do I have to wait
for GnuStep to combine the robustness and programmability of Unix
(which I love) with a halfway-sane GUI-fied environment for those
"I want to use a tool but I haven't got a month spare to master the
interface" moments?
</rant>

Sorry to rant on like that, but I feel strongly that the many things
Unix does well should not (and in the eyes of the Heathen do not)
excuse its barely-half-hearted embracing of the possibilities of the
new-fangled (ahem...) bit-mapped screen.

>I am writting (eventually / hopefully) an email client in C as programming
>practice. I have the address book completed and am now moving onto the
>difficult bits. I need to write a text editor to read/write the emails,
>but am not quite sure how to proceed.

The wisest thing is to let the user specify what his or her favorite editor is.
If the user does not know, fall back on something lame.

> My thoughts have led me to believe that it might be wisest to make
>each line an array, but then I have horific thoughts of adding a word to
>the first line and having to shift every subsequent array element.

You can make each line a structure like:

typedef struct {
char *data;
size_t len;
/* ... */
} line;

Then have an array of these. To insert a line into a 500 line file, you only
need to bump down up to 500 elements, you don't have to move the actual data.

Another possibility is to represent the whole buffer by a big array of
characters with a big ``gap'' at the insertion point. You amortize the cost of
inserting characters by opening the gap in big steps. When deleting characters,
you can simply create a gap which you will close in big increments.

> Any suggestions on how the wisest way to proceed? I doubt that a
>lot of you have writen text editos, given the number available, but any
>suggestions on pitfals to avoid would also be appreciated.

The biggest pitfall to avoid is to spend too much time on reinventing the
wheel. Even if you succeed in making a decent text editor, you will still have
to provide experienced and religious users access to their favorite. I won't
use a mail program that wont pop into the vi editor.

The 24ct platinum stack pointer has not yet been awarded to a suggested
name, but I am already pondering about my Forth editor╢s design and I
think I will start to implement it tomorrow... or on Sunday. Tomorrow, I
am dating - yeah, imagine, your average 16-year-old computer geek meets
a girl! Spawn me XTerms.

Since I am a newbie to Forth as well as to editor design but I consider
it a hackish virtue to do things one has never done before with tools
and languages one has never used before, I think I will need your
support now and then when attacking the problem.
Please comment on the following thoughts.

I think the basical structure will be based on a variable keeping a
pointer to an ALLOCATEd list of pointers to ALLOCATEd buffers. Every
buffer will have a unique number and an array of pointers to strings and
words operating on them will map these numbers to buffer names.

Do I need buffer names? I suppose so.

I will need to store point (and marks) for every buffer somewhere. Is it
OK to have separate array to keep pointers, names and marks or should I
attempt to pack this all into one big data structure? What╢s more
appropriate in Forth?
In C I would pack it all into a struct for sure.

Buffer memory will be allocated in steps (what do you think is a
sensible block size? 512 chars? 1024? 2048 [= Unix memory page]?).

Hey! I just realise that╢s where Forth *and* Emacs philosophy kick in:
keep it transparent and configurable. I think I will keep the block size
in a variable. BUFFER-ALLOC-BLOCK-SIZE (hey, is that hyphen-look okay or
to Emacsish?).

Characters before and after point will be flushed against the respective
ends of the buffers (some Emacs guru pointed me out how buffer-gap
editors really work, thanks). Thus I will need to keep track of the size
of the gap. I╢ll need to store pointers to where point physically is in
the buffer and to the last character in the gap and have some word
GAP-SIZE taking a buffer and computing the size of its gap. Or perhaps
it would be better to have this in a variable updated by every action
actually changing the gap╢s size.
(Opinions?)

New memory will be allocated to the buffer when the size of the gap
drops below MIN-GAP-SIZE (configurable). The buffer will be compacted
and memory freed if the gap size increases to more than MAX-GAP-SIZE.

The first character in the buffer will be character 0 and point will
store the number of the character point is in front of. Trivial.
Regions are stored as two variables, the number of the first char and
the number of the last char + 1.

Is that reasonable or should I use that Emacs system I loathe where one
border of the region is always point? Does that give me an advantage?

I will need a data structure keeping track of windows (unique number,
start and end X and Y coordinates) and words creating, resizing and
destroying windows while keeping the structure up to date.

The buffer data structure must store which window a buffer is displayed
in if any.

Display will be done by a wrapper word that controls all the other words
needed to display text. It will probably just take a buffer number and a
window number and display text in it. That way I should be able to
implement plain terminal, curses (if possible) and MINOS display below a
layer of abstraction.

Editing commands will be words. I╢ll store a list of keybindings,
basically one entry for every keycode. When initialising the editor, all
the codes will be bound to no-op or just scream at the user in Reverse
Polish.

Hey! That╢s an idea! What about having a sentence or two in Reverse
Polish on the splash screen? I╢d need someone translating me a cool
saying into Polish. I just know that the currency of Reverse Poland (or
is that Dnapol?) is the Ytolz.

The editor will read a list of keybindings when starting up. Then it
enters a main loop polling for keys and executing their bindings.

The first commands I will implement will be moving point around,
inserting, deleting and EVALUATE-BUFFER resp. EVALUATE-REGION. I can
evaluate a string with EVALUATE, can╢t I?

As soon as I can enter Forth code into my editor and execute it from a
buffer, I think I will drink a pot of tea, eat a kilo of After Eight
mints and look forward to a brighter future :)

I hope for as many comments, suggestions and criticism as possible. If I
screw up my design now, I may never be able to correct it. Just look at
what has happened to MS-DOS :->>>

> I'm working on a graphical editor for a master's project and am looking
> for a means to implement UNDO functionality in it. If anyone knows of
> of any information on how UNDO algorithms have been implemented for
> graphical editors, I'd be much obliged to know where such information
> may be.
>
> Thanks!

I saved this news article back in 1995. It's by Joseph H. Allen who wrote
the ``Joe'' editor and it contains lots of good knowledge about writing
a text editor, like how to implement ``undo''. I think that some similar
scheme could be applied to implement undo in a graphical editor as well.

/Enjoy,
Fredrik

In article 1L9@world.std.com, jhallen@world.std.com (Joseph H Allen) writes:
> In article <1995Jan10.215600.2519@dg-rtp.dg.com>,
> Mike P. Wagner <wagnermp@dg-rtp.dg.com> wrote:
> >Stefan Olson (stefan@dogbox.manawatu.planet.co.nz) wrote:
> >: brett@iit.com (Brett Coon) writes:
> >: > k920699@kingston.ac.uk (Sean Batten) writes:
> >: > >What's the best may to go about managing a text file when developing
> >: > >an editor? I had planned to use a linked list with each item in the
> >: > >list being one line from the file. Is this the best approach?
> >: > Keeping a linked list of lines would have a very large overhead (link
> >: > pointers for each line), and it might be slow to insert or delete text
> >: > if each line wrapped onto the following line.
> >You might learn a lot by looking at the source of nvi, elvis, etc. Most
> >of them do *not* use linked lists, but use arrays (I think that often the
> >value of the array entry is a pointer into a text file, or a cache).
>
> I've done some repackaging of the "Editech"/"Editor 101" files which I and
> others had written six years ago (wow! _six_ years ago):
>
> From: jhallen@wpi.wpi.edu (Joseph H Allen)
> Subject: Editor 101
>
> >I like many others have been writing my own editor based what I like.
> >The code is not as well laid out as I would like but then that is
> >careless designing on my part. It would be nice if there was some
> >sort of reference that suggests how to implement all the basic
> >structures and operations necessary for an editor.
>
> As far as I know there isn't any text-book for editors [Actually there now
> is]. I have seen various articles about text editors and also a few books
> on related issues: There are lots of things about string searches and a few
> theory books about the snobol language (which encounters similer issues).
>
> I've made several text editors and I'm in the process of making another one.
> This most recent one is my emacs replacement so I've been doing quite a bit
> of thinking and researching (if its going to replace emacs, it had better be
> pretty good :). I'm in the mood today so I'll try to show some of the
> thought processes and research I've made. Perhaps if I start, others will
> expand/correct what I say.
>
> > editor buffer data structures - multiple file buffers
>
> JOE'S FIRST ATTEMPT
>
> Originally, I had a large array to hold the file in and a small array which
> held a small piece of the large array in which the inserting and deleting
> occured. Moving the point involved saveing (and possibly making space in
> the large array for) the small array and loading a new one. When I found
> out about the gap method I rewrote the buffer manager. Both my method and
> the gap method work on a similer method but the gap method is much more
> refined. If anyone knows, I'd be interested in hearing who invented the gap
> buffer. Gnu-emacs uses a gap buffer.
>
> GAP METHOD
>
> One of the simplest and most effecient ways of storing a file in memory is
> with a gap buffer. The file is broken into three parts in one big array:
> The beginning, the gap and the end. The beginning and end parts are just
> normal text stored in an array: if the size of the gap is zero, then the
> buffer looks like a file loaded simply into an array. The gap lets you
> insert and delete characters without moving any large amount of data. All
> you have to do is change the size of the gap. You do have to move the gap
> if it's not at the spot you want to insert or delete, however. If you can
> get away with it, it's a good idea to always keep the gap at the cursor.
> (I.E., so moving the cursor right means to move one character from the end
> part to the beginning part.)
>
> Here's the buffer manager from an editor I wrote (and which I'm using right
> now) and an explanation of the functions/macros provided. Like emacs, it does
> not force the gap to be at the point.
>
> [See Appendix A for listing]
>
> The gap buffer has the best performance if you can insure that the gap is
> always at the cursor. If this is guarenteed, then the only time that there is
> ever a delay is when the gap gets completely filled- on unix systems, you have
> to realloc the block the buffer is in and make a new gap. On systems where
> you can access the far ends of the memory, you can prolong this as much as
> possible by starting out with the largest possible gap. This is what I've
> seen done on machines without memory management (micros) and on machines with
> really good memory management (the DEC 20, where to allocate memory you just
> access it).
>
> If the editor has multiple windows at different positions in the same file
> it may not be possible to insure that the gap is always at the cursor.
> There is a tradeoff to think about here. You can do two things: move the
> gap with the cursor when you change windows. Then there is a delay, but the
> gap is always with the cursor. The second way is to move the gap only when
> you are about to insert or delete something. This is not a bad idea since
> you usually only edit in one window and only look at the others. You can
> have more than one pointer to the buffer but you can't have more than one
> gap (well, you could have more than one gap but it would be very, very messy
> to manage).
>
> I don't like the gap buffer for editors with multiple windows because of the
> gap motion delays. In particular, if you're on a virtual memory system, much
> of the buffer might be swapped out to the disk. Then if you have to move the
> gap there has to be a lot of disk accesses. Still, the gap editor does use
> the least amount of cycles (remember the things you do most often in an editor
> is type single characters and move the cursor short distances), so if you're
> most interested in not loading down the system...
>
> From: trier@shasta.scl.cwru.edu (Stephen Trier)
>
> Gap Buffer Explained Again
>
> The buffer gap method for storing data in an editor is not very
> complicated. The idea is to divide the file into two sections at the cursor
> point, the location at which the next change will take place. These sections
> are placed at opposite ends of the buffer, with the "gap" in between them
> representing the cursor point. For example, here's a sixteen-character
> buffer containing the words "The net", with the cursor on the letter 'n'.:
>
> The ---------net
>
> (I'm using the '-' character to represent the spaces making up the gap.)
>
> Now, if you wanted to insert a character, all you must do is to add it
> into one end or the other of the gap. Conventional editors that move the
> cursor left as you type would insert at the top edge of the gap. For example,
> if I wanted to change the word "net" to "Usenet", I would start by typing the
> letter 'U', and the editor would change the buffer to look like this:
>
> The U--------net
>
> This represents the string "The Unet", with the cursor still on the 'n'.
> Typing an 's' character would bring us to the following:
>
> The Us-------net
>
> And finally, the 'e' character brings us to this:
>
> The Use------net
>
> But now we decide that we want to completely change tack and change the
> phrase from "The Usenet" to "The Usenix". To do this, we will first have to
> move our cursor to the right one spot, so we don't waste time retyping an
> 'n'. To move the cursor point up and down through the file, we must move
> letters "across" the gap. In this case, we're moving the cursor toward the
> end of the phrase, so we move the 'n' across the gap, to the top end.
>
> The Usen------et
>
> Now we're ready to delete the 'e' and the 't'. To do this, we just
> widen the gap at the bottom edge, wiping out the appropriate character.
> After deleting the 'e', the buffer looks like this:
>
> The Usen-------t
>
> And after deleting the 't', the buffer looks like this:
>
> The Usen--------
>
> (Note that the gap now extends all the way to the edge of the buffer.
> This means that the file now reads "The Usen", with the cursor at the very
> end.)
>
> Backspacing works out to be something very similar to delete, with the
> gap is widening at the top instead of the bottom.
>
> Now we add the letters 'i' and 'x', giving us the following buffer
> snapshots after each key is pressed:
>
> The Useni-------
>
> The Usenix------
>
> Now we've made our changes. Moving the cursor back to the top of the
> file means moving the characters across the buffer in the other direction,
> starting with the 'x', like this:
>
> The Useni------x
>
> Finally, after doing this once for each of the letters in the buffer,
> we're at the top of the file, and the buffer looks like this:
>
> ------The Usenix
>
> Of course, there are many details yet to consider. Real buffers will be
> much larger than this, probably starting at 64K and stopping at whatever size
> is appropriate for the machine at hand. In a real implementation, line breaks
> have to be marked in some way. My editor does this by simply inserting line
> feed ('\n') characters into the buffer, but other approaches might be useful.
> Moving the cursor up and down between lines can get complicated. What about
> virtual memory, so that we can fit the 21-letter phrase "The Usenix
> Conference" in our 16-letter buffer? Then, of course, there's the question of
> making the screen reflect the contents of the buffer, which is what my
> original "Editor 102" post discussed.
>
> Hope this clears up the question of what a buffer gap is, and why it's
> a convenient data structure to use in an editor. There are, of course,
> other ways to structure an editor's memory, with no clear victor. All have
> their strong points and weak points, so I picked the buffer gap for my
> editor because of its simplicity and efficient use of memory.
>
> LINKED LIST OF LINES BUFFER
>
> The next most common buffer data structure I've seen is the doubly linked list
> of lines buffer. In this case you store each line in a structure:
>
> struct line
> {
> struct line *next; /* Link to other lines */
> struct line *prev;
> unsigned char size; /* Size of 'text' */
> unsigned char bksize; /* Size of malloc block this is in */
> char text[];
> };
>
> Each line contains only a small amount of text so you can insert and delete
> using brute force without any noticable delays (although this will use 20
> times as many cycles as the gap buffer).
>
> This buffer scheme eliminates the large delays of the gap method and also
> eliminates some of the delays at higher levels in the editor (you don't have
> to search for ends of lines any more), but it also has a rather large
> overhead (~50% for program source).
>
> ARRAY OF POINTERS TO LINES
>
> From: aarons@syma.sussex.ac.uk (Aaron Sloman)
> Subject: How it's done in VED
>
> In the recent discussion of editor buffer management I don't think
> anyone mentioned the sort of technique used in VED, the Poplog editor.
> It's a bit like a linked list of records, but more compact, and less
> flexible. On the other hand, for some patterns of use it seems to work
> very well, although it was originally implemented a long time ago as
> a temporary measure, to be replaced by something cleaner and more
> general eventually!
>
> VED is implemented in Pop-11, the core Poplog language, with Lisp-like
> facilities but a Pascal-like syntax. In fact VED uses the "Syspop"
> dialect of Pop-11 which also includes C-like pointer manipulation for
> efficiency, and which is used for building and porting Poplog.
>
> From the point of view of a programmer, VED is just an extendable,
> collection of Pop-11 procedures that operate on a collection of Pop-11
> data-structures (something like Emacs and its Lisp?). Because Poplog
> provides a very fast garbage collector VED simply uses it to reclaim
> space when necessary. Garbage collecting a process around 2MB, on a
> Sun360 with 8Meg takes just over a second, and doesn't happen often
> while editing. VED's strategy would not be tolerable in those AI systems
> where a garbage collection takes up time for a coffee break. In VED most
> users are never aware of garbage collection.
>
> VED reads in complete files on the assumption that it would always
> be used on machines with virtual memory, and we could not hope to
> improve on the performance of the pager.
>
> The text buffer is a vector of strings in memory, where the strings are
> represented by pointers. Each string corresponds to one line of text. So
> shifting N lines of K characters to insert or delete a line requires
> shifting only N pointers, not NxK bytes. In general that's very fast,
> though not as fast as manipulating a linked list. The vector is allowed
> to have spare space at the end, but occasionally it overflows. Then a
> new larger one is created and the string pointers copied to it. How much
> new space that has to be allocated and how much has to be copied depends
> on the number of lines of text, not the number of characters in the
> buffer, so in general it is MUCH faster than copying a complete
> character buffer would be, and turns over much less store.
>
> Two integer variables, vedline and vedcolumn record cursor position,
> and there is no data movement during browsing through a file, once
> it has been read in.
>
> Editing uses the concept of the "current" line, which is the string
> of characters returned by vedbuffer(vedline). On every (non-static)
> insertion or deletion the characters to the right of the cursor are
> shifted left or right. This is generally very quick, because lines
> are not very long, and most of the work is done near the end of a
> line anyway (except for things like global substitions and text
> justificiation).
>
> Whenever there's not enough space in the string, it is replaced with
> a copy that has 20 extra spaces on the right, then when you are
> about to move off that line the line has to be trimmed. (A point
> that people who extend VED by programming it at a very low level
> sometimes forget). The number 20 was a guess made around 1982 and
> has never been reconsidered. Perhaps it should be context sensitive.
> (However increments to fixed sizes would simplify the use of a set
> of free lists for strings, which we probably should implement to
> reduce garbage collection even further, but haven't bothered.)
>
> VED is one of those dirty hacks, that works. In order to avoid the
> problem of working out what has changed whenever it is time to refresh
> the screen, which a clean implementation with separate buffer manager
> and screen manager would do, VED provides a collection of procedures for

а что здесь написано ?

http://www.cs.unm.edu/~crowley/papers/sds/sds.html - посмотри сюда, может понятнее будет, хотя это тоже на английском.