[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Overlays as an AA-tree

From: Stefan Monnier
Subject: Re: Overlays as an AA-tree
Date: Mon, 06 Feb 2017 12:34:38 -0500
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/26.0.50 (gnu/linux)

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


reply via email to

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