Stefan Monnier wrote:
> (I've tried splay-trees for text-properties, and the performance was not
> noticeably different from the current mostly-balanced binary tree.
> In particular it seems that either we don't get to see the O(1) behavior
> because the locality is not as good as it seems, or the constant factor
> makes up for the difference).
>   

Thanks for the anecdote.

I was kind of thinking that, worst case, that was exactly
what to expect and so then, yes, is expected log N good
for these purposes?  (And I decided, "probably", so I'm
coding....)

It'll be interesting to see.

I think I have an elegant way to do properties and
markers but since I haven't coded that part yet I
can't swear there isn't a devil in the details. 

Years ago I did something very close to what I
have in mind while working on Guile.   (For a while,
Guile had an (unreleased) buffer type, with text properties
and markers, and a redisplay engine for X11.  It was
doing OK and might have matured to what I'm thinking
of now but that work got interrupted and then bit-rotted
away.




>   
>> It *should* (in theory) be just fine for each undo-elt
>> to contain both string snapshot(s) and markers that
>> track the region effected.   That's easy to code and in
>> turn it makes undo-elt-in-region very easy to code.
>>     
>
> But that would significantly increase the size of the undo log, I expect
> (maybe not algorithmically, but by a non-negligible factor).
>   

I guess the way I would say it is that it will *noticably* increase
the size of the undo log (yes, by a constant factor).    And I would
guess that that's *noticably* not *significantly*.   We'll see.
The library is useful, either way.



> It's too bad, because of we ignore the undo-in-region, we don't need
> undo info for each modification, we could just grab a snapshot in
> undo-boundary.  That would be elegant (tho it's not like it matters:
> changing the implementation of the undo data is trying to solve
> a non-problem, really).
>   

The real problems are a desire for a *nice* unicode-and-text-properties-
capable string library with buffer-like capabilities.   I want that as a
library, first and foremost, not tied to just one program.


Thanks,
-t



>
>         Stefan
>
>