Re: Overlays as an AA-tree

[Joakim Jalap]

Andreas Politz <address@hidden> writes:

>> And here I thought it was rather an elegant solution :) (to the problem
>> of one overlay's beg going past another's because of an insert).
>
> I think the problem is that this would entail either having lots of ugly
> code at places where this double-tree is accessed, or having to create
> some kind of layer, hiding the fact that there are two trees.

I don't think it would be that ugly. Instead of:

adjust_overlays_for_insert (current_buffer->overlays);

it will be:

adjust_overlays_for_insert (current_buffer->front_insert_overlays);
adjust_overlays_for_insert (current_buffer->non_front_insert_overlays);

I don't think it's that big of a deal. But I guess that's a matter of
personal preference. (obviously the member names would be something...
better)

> I think its safe (in a RB-Tree anyway, AA probably as well) to remove
> the root node of the tree, given, that all other nodes are sorted.
>
> When recursively applied, it tells us that before we are attempting to
> remove an unsorted node, we need to make sure that its descendants are
> in-order.  In order to do that we just need to collect them
> appropriately while traversing the tree.
>
> BTW. I don't think this would change the complexity of the algorithm,
> since we're already in k*log(n) territory.

Maybe not... but it still sounds a bit expensive to me, spontaneously.

-- Joakim