|
From: | Thomas Lord |
Subject: | Re: Release plans |
Date: | Mon, 01 Sep 2008 13:17:52 -0700 |
User-agent: | Thunderbird 1.5.0.5 (X11/20060808) |
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 |
[Prev in Thread] | Current Thread | [Next in Thread] |