Re: Overlay tree. Stuck again

[Joakim Jalap <joakim.jalap@fastmail.com>]

Andreas Politz <politza@hochschule-trier.de> writes:

> Joakim Jalap <joakim.jalap@fastmail.com> writes:
>
>> Eli Zaretskii <eliz@gnu.org> writes:
>>> [...] try removing them from the tree, and then re-adding them [...]
>>
>> Yes, that is the "big hammer" approach :) I hae thought about it, but I
>> think the problem is that it will be too expensive. [...]
>
> Joakim, I think that trying to somehow manually fix the disorder is at
> least as expensive as a deletion and reinsertion.  Because if it weren't
> you would have essentially discovered a better algorithm for balancing
> trees then the one you've got.

Well this case isn't really about rebalncing, since the tree was
balanced to begin with, and no nodes are deleted or inserted. The
problem is that a few overlays end up in the wrong place in the tree
since I sort by different criteria (memory address) than before for
those overlays which happened to end up with the same start/end.

> The trick is probably to gather the dirty nodes in post-order and delete
> them all at once. This way you're only removing a node, if its
> corresponding sub-tree is in order.  After that you're free to reinsert
> them again.

Yes, that should do it. But that would be many traversals of the tree,
so I'm afraid it would be too slow.

Anyway, I'm trying a new approach now, where the tree is separate from
the acual struct Lisp_Overlays, but each overlay is linked to a node in
the tree with a pointer (and vice versa). I think this might be easier
(that's my theory at least).

>
> -ap

-- Joakim