[Top][All Lists]

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

Re: Overlays as an AA-tree

From: Stefan Monnier
Subject: Re: Overlays as an AA-tree
Date: Sun, 19 Feb 2017 18:10:29 -0500
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/26.0.50 (gnu/linux)

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


reply via email to

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