[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Overlays as an AA-tree
From: |
Joakim Jalap |
Subject: |
Re: Overlays as an AA-tree |
Date: |
Fri, 03 Feb 2017 15:11:49 +0100 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/26.0.50 (berkeley-unix) |
Andreas Politz <address@hidden> writes:
>
>>> I think if a tree is sorted by begin only [...] the tree can't possibly
>>> become
>>> disordered [...]
>>
>> But if the tree is sorted by begin only we can have multiple overlays in
>> the same position, how does that work? [...]
>
> Why should that be a problem ? A search-tree may contain some key
> multiple times. The question is whether this is useful. I don't think
> it is in this case, because including end in the comparison does not
> help with finding all overlays intersecting some position or interval
> (i.e. it does not allow pruning some sub-trees).
Hm, that is true... I think I actually started like that, but then got
stuck in the mindset of having a total ordering. So, will there be a
linked list in each node for the overlays, or how will it work?
> It would be useful, e.g. if we were going to search for an overlay
> starting at B1 and ending at E1, but I don't see were we needed this.
I can confirm that we never need it :)
>> Hm I don't understand this. How would we use two trees?
>
> If I'm right, we *could* use one tree for front-advance overlays and one
> for non-front-advance ones, such that these tree won't ever become
> unordered by insertion/deletion of text.
Sounds like a good idea.
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/03
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/04
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/04
- Re: Overlays as an AA-tree, Joakim Jalap, 2017/02/06
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/06
- Re: Overlays as an AA-tree, Joakim Jalap, 2017/02/06
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/06
- Re: Overlays as an AA-tree, Joakim Jalap, 2017/02/06