[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.
Stefan
- Re: Overlays as an AA-tree, (continued)
- Re: Overlays as an AA-tree, Joakim Jalap, 2017/02/09
- 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 <=
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/19
- 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