[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: |
Thu, 22 Sep 2016 22:11:07 +0200 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/25.1.50 (gnu/linux) |
Stefan Monnier <address@hidden> writes:
>>> which makes me suspect your design might not be quite right.
>> Well, I didn't think *too* hard about it. I didn't really think about
>> what to do when the intervals of two overlays are the same. Does it even
>> matter?
>
> Not much, no. Do note that in compare_overlays, we do need a total ordering
> (this is used for sort_overlays). Your sorting and that of
> compare_overlays can't be identical (compare_overlays has to obey the
> `priority` property, whereas yours shouldn't pay attention to it), but
> you can still use the same idea: i.e. when start and end are equal, just
> use the overlays's memory addresses to decide which comes first.
Do you mean when a->char_start == b->char_start && a->char_end ==
b->char_end?
Does it even matter what char_end is? I have a feeling it's ok to just
return true if a->char_start == b->char_end.
>>> Some tricky parts:
>>> - because of the insertion_type, two overlays may start with end1<end2
>>> and finish with end1>end2 without any call to move-overlay.
>> Hm, ok. I will have to look into this further.
Actually, this sounds like it could be quite complicated... I'm not sure
how to handle that in the tree.
> I think a more important aspect is that insertion/deletion of text has
> to update all char-positions of overlays after the point of
> insertion/deletion. I.e. it's an O(n) operation. In the intervals tree
> used for text-properties we avoid this by keeping track of distances
> rather than positions. and then positions get (re)computed when needed.
Hm, I don't really understand this. Do you mean how LENGTH(i) is
computed from TOTAL_LENGTH(i->left) and TOTAL_LENGTH(i->right)? Hm, how
could I do that in the AA-tree? Store the position in the root and then
an offset from the parent in every child node?
But doing it like I do it now (updating all the char-positions after the
modification) shouldn't be slower than updating the positions of all
markers, right?
>>> I wouldn't worry about merging (better yet: merge from master right away
>>> and then keep doing that on a regular basis, which should be easy since
>>> I don't think we've touched (nor will touch) this code very much).
>> I tried to do that yesterday. There were some conflicts in insdel.c
>> (which I think I fixed) but now I can't commit, because 'git commit'
>> complains about trailing whitespace in some regex test files. How do I
>> get around this?
>
> Just remove the trailing whitespace.
I just commited with --no-verify instead :)
- Re: Overlays as an AA-tree, (continued)
Re: Overlays as an AA-tree, Stefan Monnier, 2016/09/21
Re: Overlays as an AA-tree, Joakim Jalap, 2016/09/22
- Re: Overlays as an AA-tree, Stefan Monnier, 2016/09/22
- Re: Overlays as an AA-tree,
Joakim Jalap <=
- Re: Overlays as an AA-tree, Stefan Monnier, 2016/09/22
- Re: Overlays as an AA-tree, Joakim Jalap, 2016/09/27
- Re: Overlays as an AA-tree, Stefan Monnier, 2016/09/27
- Re: Overlays as an AA-tree, Eli Zaretskii, 2016/09/27
- Re: Overlays as an AA-tree, Joakim Jalap, 2016/09/28