Re: Overlays as an AA-tree

[Andreas Politz <politza@hochschule-trier.de>]

Hi, I'm interested in this problem as well.

I want to clarify something:

Overlays have begin B and end E positions each with a flag (front-advance
resp. rear-advance).  These positions may change in one of 3 ways:

1. move-overlay is called
2. Text of length L is inserted at position P.
   Here the flags decide whether begin B resp. end E will move or not
   in the literal border-cases P = B resp. P = E .
3. Text of length L is deleted beginning at position P.

Is this the correct model ?  Someone mentioned in a different thread,
that occasionally we may have B > E.  How does this happen ?

---

I think if a tree is sorted by begin only and the front-advance of
every node is either true or false, the tree can't possibly become
disordered by insertion/deletion operations.  Further the disorder
exists at most for nodes having the same begin but different
front-advances after an insert at begin was performed.

This suggests using two trees or at least limits the amount of nodes
having to be reinserted after a change.

---

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

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.

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.

I'm essentially building an overlay model and if it works, will try to
plug it into the Editor.

-ap