[Top][All Lists]

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

reply via email to

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