[Top][All Lists]

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

Re: Overlays as an AA-tree

From: Joakim Jalap
Subject: Re: Overlays as an AA-tree
Date: Mon, 06 Feb 2017 16:33:22 +0100
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/26.0.50 (berkeley-unix)

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

> 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

reply via email to

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