Re: Overlay tree. Stuck again

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

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Joakim Jalap <joakim.jalap@fastmail.com>
>> Date: Thu, 12 Jan 2017 22:10:44 +0100
>> 
>> However the nodes can be updated "externally" from the trees point of
>> view. For example if there is a delete in the buffer those overlays
>> which were in the deleted portion of the buffer will now be crowded at
>> the from_char of the delete. But those could have any address, so they
>> will probably be out of order. The problem is how to get them in order
>> again.
>> 
>> As far as I've gotten is to gather all the affected nodes (which I think
>> are only those of length zero which start (and end) at from_char) into
>> an array and sort that. But I can't figure out how to get them into the
>> tree again while keeping all the pointers correct.
>
> This might be a silly idea, but did you try removing them from the
> tree, and then re-adding them?  (I assume that adding a node will
> produce an ordered tree.)

Yes, that is the "big hammer" approach :) I hae thought about it, but I
think the problem is that it will be too expensive. When I traverse the
tree to adjust the overlays for a delete I traverse the whole tree at
once (and gather the problematic overlays in an array). If I would
remove the problematic overlays instead, I would have to do so with the
first one detected (because that's the only time we know the tree is in
OK shape). But then the tree might change because of rebalancing, so
then I think I would have to restart the adjusting traversal from the
root.

After all of this I would then have to insert each of the problematic
overlays one by one, which is of course also possibly expensive. So I
think this approach will be too slow, unfortunately.

However, I just had another idea about how to do this (about the 43rd I
guess), so I will try that and report back in a few weeks :)

Thanks,

-- Joakim