Re: line buffer as Red Black Trees instead of linear

[Alin Soare <as1789@gmail.com>]

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

>
>
> >
> > Emacs works bad with buffers with long lines. This would work well, and
> all
> > the others atomic operations, like random access, search, will preserve
> the
> > current speed.
>
> You cannot help redisplay with long lines by giving it random access
> to buffer text.
>


This is right. Redisplay is one, and computing the result of some functions
is another thing.

I did not check the flow of the calls that take place in that situation,
but I am sure that it happens at the level of buffer access, Some atomic
procedures of access to buffer are linear in time, instead of constant or
logarithmic in the worse case.

I provided a solution in which all atomic accesses to buffer are in good
time.


>
> Long lines slow down redisplay because it needs to scan the entire
> line to see how tall it will be on display.  For that, you must scan
> the line in its entirety, since Emacs supports variable-size fonts and
> images on the same line, so determining the height of a line requires
> to find the largest display element (character glyph or image)
> displayed on that line.
>


If we put at each node of a red-black tree an attribute which says how tall
the block of text at that node is  --  (for example, if there are 2K
characters at that block, all identical, we already computed 2K of all the
line, and pass to the next node, where there may be 5K or 0.5K characters,
and it is GUARANTEED that in the worse case we have log # of nodes ).

Then re-computing the glyph size will be logarithmic in the worse case,
because we need to check maximum a log # of nodes, to detect all the
properties of a line.

Each node must also have an attribute that says how many lines are at the
left of that node, another attrib that says how many chars are at the left,
and each node must also have a pointer to the next node, such that the
nondeterministic finite automata that use lazy search (for example in
search-forward) will take constant time on each change of state (as it is
now).



>
> How can random access to buffer text help here?
>

I repeat : it is very long since I read the code of emacs, so I cannot
remember the details of all the operations, but while I was working on the
tutorial in which I present the details how I deduced the formla of
red-black trees, I realized that these are the wonderful data structure to
work with in emacs buffers.

I knew that emacs loops in buffer data structure, hence the slow operations
in the cases that I said in my prev. message .

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