Re: Overlays as an AA-tree

[Andreas Politz]

Joakim Jalap <address@hidden> writes:

> I thought I might chime in since I've been bashing my head againt this
> for a while now :)

Much appreciated.

> There is also the case of a replace, [...]
>
>> [...] occasionally we may have B > E.  How does this happen ?
>
> I think it happens in case 2 above [...] See also the comments at
> adjust_markers_for_insert in [...]

That's useful information.    

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

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.

> 
> [...] but then almost all the buffer text is deleted
> so that every overlay ends up being from 6 to 6!

No problem. Simply write a NEWS entry and declare it a new feature.

>> This suggests using two trees [...]
>
> 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.

>  [...] it only affects those overlays with an endpoint exactly at the
> point of insertion... [...]

Whether it'll mess with the order depends on the comparison function ;-) .

-ap