[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Overlays as an AA-tree

From: Andreas Politz
Subject: Re: Overlays as an AA-tree
Date: Mon, 20 Feb 2017 00:44:00 +0100
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux)

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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]