Re: Overlays as an AA-tree

[Stefan Monnier]

>> Not much, no.  Do note that in compare_overlays, we do need a total ordering
>> (this is used for sort_overlays).  Your sorting and that of
>> compare_overlays can't be identical (compare_overlays has to obey the
>> `priority` property, whereas yours shouldn't pay attention to it), but
>> you can still use the same idea: i.e. when start and end are equal, just
>> use the overlays's memory addresses to decide which comes first.

> Do you mean when a->char_start == b->char_start && a->char_end ==
> b-> char_end?

Yes.

> Does it even matter what char_end is? I have a feeling it's ok to just
> return true if a->char_start == b->char_end.

Things are easier if you make the comparison a total order, so o1==o2
only if o1 and o2 are actually one and the same overlay.

>>>> Some tricky parts:
>>>> - because of the insertion_type, two overlays may start with end1<end2
>>>> and finish with end1>end2 without any call to move-overlay.
>>> Hm, ok. I will have to look into this further.
> Actually, this sounds like it could be quite complicated... I'm not sure
> how to handle that in the tree.

After an insertion/deletion, you'll need to update the char positions.
While doing it should be fairly easy to check that the adjustments don't
break the tree's consistency.  When an inconsistency is detected, you
can either try to adjust things locally or just remove and re-insert the
overlay.

> Hm, I don't really understand this. Do you mean how LENGTH(i) is
> computed from TOTAL_LENGTH(i->left) and TOTAL_LENGTH(i->right)?

Not exactly, tho it's related.  I was referring to the `position` field
of `struct interval`.

> Hm, how could I do that in the AA-tree?

Haven't thought about it yet.

> Store the position in the root and then an offset from the parent in
> every child node?

Something like that, I guess, yes.

> But doing it like I do it now (updating all the char-positions after the
> modification) shouldn't be slower than updating the positions of all
> markers, right?

Indeed, it's no worse than what we have, but it reduces the algorithmic
benefit of the change.  IOW we can keep this for later.


        Stefan