Re: Overlays as an AA-tree

[Stefan Monnier]

> Anyway, my attempt is to use the RB-tree from alloc.c and add some
> node-attributes:

> 1. max_end :: Holds the maximum E value of this node's sub-tree and
> bounds the complexity of queries in terms of their result, i.e. number
> of intervals. (The so called ,,Augmented Tree'' approach to Interval
> Trees (which is actually just an example for how to augment a tree in
> the book).)

Sounds good.

> 2. offset :: The amount of shift of this node's sub-tree relative to
> its parent and applying to all position values (begin,end,max_end).
> This should limit the time it takes to modify the tree after an
> insertion/deletion in terms of intersecting intervals.

Sounds good.

> 3. modified_tick :: Essentially just a flag, indicating that all
> parent offsets have been applied to this node.  This would allow for
> constant time access on B/E for repeated accesses.

But that can't be a boolean, right (otherwise how do you plan to set it
to true on all overlays after the insertion point, without paying an
O(n) cost)?  So, by the "tick" name, I assume you keep a kind of MODIFF
counter at the root of the tree which is incremented every time an
insertion/deletion is performed, and you keep a copy of that MODIFF
value in the nodes, to remember the last time the start/end value
were recomputed, so the "flag" is really (modified_tick ==
root->modified_tick).

If so, this sounds good as well.


        Stefan