Stefan Monnier wrote:
>> I don't think we would want to implement undo by making a snapshot,
>> even if the data makes snapshots possible, because this would take up
>> a lot more space than the current undo data.
>>     
>
> I don't think it would necessarily take up significantly more memory.
> In some cases it'll use up less memory.  OTOH it might make it difficult
> to implement undo-elt-in-region.
>   


Neat problem.  No, I hadn't thought about that case.

Is it the case that undo-elt-in-region exists for little or
nothing more than undo-in-region?    Because:

Markers are currently still stored in a list, right?
So inserts and deletes are linear in the number of
markers in a buffer, right?   (I thought I remembered
that changing long ago but looking at 22.1 source
I guess not.)

My plan is to keep markers in a tree in such a way that
inserts and deletes are log N in the number of markers,
and accessing a marker's position is log N in the number
of markers, but because this will be a self-adjusting tree
all those operations will be O(1) in the expected case where
changes display pretty good locality.

In other words: markers get a lot cheaper.

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.

That's an example of why I (so far) like this data
structure better than the current ones.   If markers get
significantly cheaper than they currently are, and
functional string edit operations get faster -- a lot of
code can be simpler.

-t





>
>         Stefan
>
>
>
>
>