[Top][All Lists]

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

Re: Overlays as an AA-tree

From: Stefan Monnier
Subject: Re: Overlays as an AA-tree
Date: Fri, 03 Feb 2017 08:55:15 -0500
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/26.0.50 (gnu/linux)

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

If so, this sounds good as well.


reply via email to

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