[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: |
Fri, 03 Feb 2017 12:33:27 +0100 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/26.0.50 (berkeley-unix) |
Andreas Politz <address@hidden> writes:
> Hi, I'm interested in this problem as well.
Great!
I thought I might chime in since I've been bashing my head againt this
for a while now :)
> 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.
There is also the case of a replace, conceptually I guess it's similar
to a delete or an insert, but in the code it is handled separately.
Interestingly, in the case of a replace, we don't look at the insertion type.
> Is this the correct model ? Someone mentioned in a different thread,
> that occasionally we may have B > E. How does this happen ?
I think it happens in case 2 above, when B = E = P, and we have
front-advance = t and read-advance = nil. Then B will move but E will
not, so we end up with a negative size overlay. See also the comments at
adjust_markers_for_insert in insdel.c and fix_start_end_in_overlays in
buffer.c.
> ---
>
> 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.
But if the tree is sorted by begin only we can have multiple overlays in
the same position, how does that work? A linked list of all overlays
starting at that position? I toyed with the idea, but I haven't actually
tried it.
For reference, the last case I got stuck on was byte compiling
lisp/semantic/cpp.el, where there are a bunch overlays (26 I believe) at
different positions, but then almost all the buffer text is deleted so
that every overlay ends up being from 6 to 6!
> This suggests using two trees or at least limits the amount of nodes
> having to be reinserted after a change.
Hm I don't understand this. How would we use two trees?
>
> 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.
I was going to do this too (but left that for later as I have bigger
problems right now :)). The problem here is that you have to take the
insertion_type into account, so an overlay may or may not change as the
result of an insertion. Actually maybe that isn't a problem since it
only affects those overlays with an endpoint exactly at the point of
insertion... This whole thing makes me dizzy...
> 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.
Sounds like a good idea. Let's hope you have better luck (or skill) than
me :)
> -ap
-- Joakim
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/03
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/04
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/04
- Re: Overlays as an AA-tree, Joakim Jalap, 2017/02/06
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/06
- Re: Overlays as an AA-tree, Joakim Jalap, 2017/02/06