Re: Overlays as an AA-tree

[Stefan Monnier <monnier@iro.umontreal.ca>]

> Here is one such case were the tree is forced to search through all
> overlays in order to find the next change:

> |--------------------------|
>    |-------------------|
>       |-------------|
>       B      ^      E
>              P

> We are looking for the next change after P, which is E.  But E is the
> end of some overlay, and the tree knows nothing about the order of
> these, so it needs to consider all overlays.

Maybe I don't understand your example, but AFAICT it doesn't need to
consider all overlays: only those that cover P.

> A stateful folding mode using overlays to keep data about, possibly
> closed, folds.

Even if that results in thousands of overlays in the buffer, any
particular location in the buffer shouldn't have a "folding nesting" so
terribly high that it is covered by hundreds of overlays.

The complexity of overlays-in and overlays-at is necessarily of O(N) where
N is the number of overlays covering the area.  Even O(N log M) (where
M is the total number of overlays) should be fine.


        Stefan