Re: Overlays as an AA-tree

[Stefan Monnier]

> True. Even rarer I guess that they have differing front-advance types.
> Still I think finding those overlays, deleting them if they are there
> and then reinserting them requires quite a few traversals of the tree.

Should cost O(N * log M) where N is the number of overlays that you need
to remove&add and N is the total number of overlays.
IOW should be very fast.

> Maybe it's not a big deal perfomance wise, but I have a feeling the code
> could be a bit messy. (But my feelings are eusually not correct)

My assumption is that the code to remove&add would be easy to write, but
I've often been wrong in such assessments as well.  All I'm saying is
that remove&add should be plenty fast enough, so it should not be
dismissed on performance grounds.  But if another solution is simpler...


        Stefan