[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.
-ap
- Re: Overlays as an AA-tree, (continued)
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/09
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/12
- Re: Overlays as an AA-tree, Eli Zaretskii, 2017/02/13
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/13
- Re: Overlays as an AA-tree, Eli Zaretskii, 2017/02/13
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/14
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/16
- Re: Overlays as an AA-tree, Eli Zaretskii, 2017/02/17
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/19
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/19
- Re: Overlays as an AA-tree,
Andreas Politz <=
- Re: Overlays as an AA-tree, Eli Zaretskii, 2017/02/20
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/21
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/21
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/21
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/21
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/21
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/24
- Re: Overlays as an AA-tree, Richard Stallman, 2017/02/13
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/14
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/06