On Wed, Oct 5, 2011 at 11:13 AM, Edward K. Ream <[email protected]> wrote: > On Wed, Oct 5, 2011 at 10:58 AM, mdb <[email protected]> wrote: >> I got the crude code below to work in every case I tried > > Sorry, but the code is too important to be guessing.
Actually, it was I who could be said to be guessing :-) The more I think about the situation, the more I think your idea has merit, for at least the following reasons: 1. It's never a good idea to put a performance bug into code, even if the potential for it actually happening is remote. Creating an O(N**2) algorithm, when an O(N) algorithm is available, limits what Leo can do. 2. As I think about the situation, I think I was being too timid in rejecting "backwards" algorithms so quickly. Indeed, deleting a node (or moving a node to a "safe" spot, like the child of an unmoving root node), can *not* change the position of nodes that appear *earlier* in the (forward) tree traversal. True, the clone status of earlier nodes can change, but that does *not* change the positions of those nodes! 3. There is some chance that a backwards algorithm might actually simplify undo. In any event, undo is the acid test of these algorithms. As I considered the backwards algorithm, I saw that we want an undo/redo scheme based on *vnodes*, not positions. But this is sweet: a backward algorithm such as you propose will be exactly what we want for undo. It is this consideration that tipped the balance. I haven't explained myself very clearly, so let me try. Suppose we are deleting nodes "in reverse". We want to describe the deletion as follows: delete the n'th vnode of the some *parent* vnode. Because we are going in reverse, the *parent* vnode will not be affected by delete. Actually, because of clones, the parent.parents array may change, but that does not affect the traversal (positions). Now, to do the actual undo, we *reverse* the changes. That is, we undo the changes in the reverse order in which they were done. So at every stage of undo, the undo happens with *precisely* the same tree as existed when the original delete happened. In short, we can be confident that a backward algorithm will work by focusing on vnodes, not positions. Michael, I'm so glad you spoke up. The result should be significantly better move/delete-marked commands, and a bulletproof scheme for undo. Edward -- You received this message because you are subscribed to the Google Groups "leo-editor" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/leo-editor?hl=en.
