line buffer as Red Black Trees instead of linear

[Alin Soare <as1789@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 2755 bytes --]

Hi,

I am writing a tutorial about red-black trees, in which I present an
recursive formula that I deduced for left leaning red-black trees . I
implemented it in java. In emacs the red-black trees are already used in
this moment for keeping the  memory segments of lisp symbols.

An application of red-black trees in emacs, which would drastically improve
the redisplay system, would be to keep the text of each line as a rbt.

I give a rough explanation of the basic operations, without having studied
recently the details of buffer implementation.

In emacs the buffers text contents is kept in memory linearly at the
address buffer_text->beg.

One could keep as well the text from each line of the buffer into a
red-black tree.

Each node will contain

* a buffer with a part of the text (for gap an empty text)
* a pointer to the next node, such that the search operation to be done in
constant time
* the number of characters of text are on the nodes at left of the current
node


The speed of the basic operations will be so:

1. search for text (remain the same)
   -- it will remain linear as it is now.

2. seach for a given offset into a line (almost no change)
   -- this will be logarithmic , logarithm of the length of the line
   -- in this moment I think it's constant time, so no visible change

3. insert a new gap (major improvement)
   -- this will be logarithmic in time, and no need to move memory
segments. To insert a new gap at offset X of a line, we start at the root,
if X > number of characters at the left of root we go to right, ifnot, we
either move to left or insert a new node and move the current node to the
left of the new node.

4. insert a new text into the buffer. (the same)
   -- This will insert into the gap from the point, and when the gap is
filled, a new gap is created.

5. remove text.
   -- this supposes a lot of things, like re-checking the values of all
values of properties at the left and right, so many changes, but it will
remain as fast as in this moment.

6. merging 2 lines means to combine the text from 2 red-black trees, and
this is done in constant time, with no need to move memory segments.

The text properties, overlays, markers, etc will remain almost the same as
now. Or they can be moved on the node of a corresponding text. In this
moment these are kept into lists, but one can move the given properties
into the node that keeps the corresponding text.

The whole buffer would be encoded as a list of lines, and each line is
encoded as a red-black tree, as I described.

This will make fast operations involving the gap, the red-black trees are
quite easy to implement, but I cannot see now the bad side effects involved
by such a change. The major improvement would be the redisplay.

[-- Attachment #2: Type: text/html, Size: 3502 bytes --]