Re: Overlays as an AA-tree

[Andreas Politz]

Stefan Monnier <address@hidden> writes:

>> 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.

In this case all of them do.  I painted N=3 overlays only.

> 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.

Yes, that's a good point.

> 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.

Yes, but next-overlay-change (which is a function re-display heavily
depends on) does not need all overlays at some position, but just the
least of the next end or begin of them.  It is not *necessary*
to consider all overlays covering some position, its simply the best way
of doing it with the current implementations.

So, I guess I'm seeing to black then.

-ap