Thank you for this Edward. Very glad we got the deletepositionsinlist finally working =)
On Saturday, July 6, 2013 1:07:04 AM UTC+2, Edward K. Ream wrote: > > I have spent several hours recently writing unit tests for > p.deletePositionsInList. Today I realized that the failing unit tests have > been telling me something unexpected and important. > > There has been much discussion recently about deleting lists of > positions. I now see that all previous strategies are fatally flawed. > This is quite shocking. > > Here is the Aha: the positions passed to p.deletePositionsInList only > *specify* the desired changes; the only way to *make* those changes is to > operate on vnodes! > > The new view of the problem is relatively straightforward. Consider this > very simple outline, containing no clones: > > + ROOT > - A > - B > > The fundamental problem is *very* simple. If we delete node A, the index > of node B in ROOT.children will change. This problem has (almost) nothing > to do with clones or positions! > > To make this concrete, let's look at the *vnodes* that represent this > tree. It is the vnodes, and *not* the positions, that represent all of > Leo's data. Let ROOT, A and B be the vnodes corresponding to the nodes > ROOT, A and B. ROOT.children will look like this at first:: > > ROOT.children = [A,B] > > That is, the children array contains references (links) to both A and B. > After deleting A, we will have:: > > ROOT.children = [B] > > As you can see, the reference to B is at index 1 of ROOT.children before > deleting A, and at index 0 of ROOT.children after deleting A. Thus, *any* > position referring to B will become invalid after deleting A. > > Several people, including myself, have proposed an unsound solution--just > delete positions in reverse order, so that B will be deleted before A. > This idea has appeal, but it truly *is* unsound, as today's unit tests > finally convinced me. > > Here is an outline that at last explodes the notion that there is *any* > correct order for deleting positions. All A' nodes are clones of each > other:: > > + ROOT > + A' > - B # at position p1 > + A' > - B # at position p2 > > **Important**: B is *not* a clone. Also note that there is only *one* > node called A and *one* node called B. The children arrays will look like:: > > ROOT.children = [A,A] > A.children = [B] > B.children = [] > > It surely must be reasonable to pass either *or both* positions p1 and p2 > to p.deletePositionsInList. But after deleting the B corresponding to p1, > the children arrays will look like: > > ROOT.children = [A,A] > A.children = [] > B.children = [] # B is no longer referenced anywhere! > > So if p.deletePositionsInList attempts to delete position p2 (from A), B > will no longer appear in A.children! > > There are many other cases that we could discuss, but the conclusion in > all cases is that we must use the positions passed to > p.deletePositionsInList only as *hints* about what to do. > > Happily, there is a simple strategy that sidesteps all the difficulties: > > Step 1. Verify, *before* making any changes to the outline, that all the > positions passed to p.deletePositionsInList *initially* make sense. > > Step 2. Treat each position as a "request" to delete *some* vnode from the > children array in the *position's* parent vnode. > > This is just a bit subtle. Let me explain it in detail. > > First, recall that vnodes do not have unique parent vnodes. Because of > clones, a vnode may may have *many* parents. Happily, every position > *does* specify a unique parent (vnode) at that position. > > Second, as shown above, there is no way to order positions such that all > later positions remain valid. As the example above shows, deleting (the > vnode corresponding to) a position P may cause *all* later positions > referring to P.v to refer to *already deleted* vnodes. > > In other words, we simply *must* ignore the child indices in positions. > Given a position P, P.parent is well defined. So Step 2 above will simply > delete the *first* element in P.parent.children containing P.v. > > As we have seen, there may not even *be* any such element of > P.parent.children: a previous delete may have already deleted the last item > of P.parent.children equal to P.v. That should *not* be considered an > error--Step 1 has ensured that all positions *originally* did make sense. > > Summary > > Positions passed to p.deletePositionsInList specify *vnodes* to be deleted > from specific parents, but they do *not* specify at what index in the > parent.children array (if any!) those vnodes are to be found. The algorithm > will delete the *first* item in the children array that references the > vnode to be deleted. > > This will almost always be good enough. In the unlikely event that more > control is desired, p.deletePositionsInList can not possibly be used. > > The new emphasis on vnodes at last puts the problem an a completely solid > foundation. Moreover, the new algorithm should be considerably faster than > the old: there is no use in sorting positions into any kind of order. > > I'm afraid I have not succeeded in conveying the essential simplicity of > the idea. Feel free to ask questions! Your comments, please. > > Next, I'll rewrite the code and see what the unit tests make of it. > > Edward > -- You received this message because you are subscribed to the Google Groups "leo-editor" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/leo-editor. For more options, visit https://groups.google.com/groups/opt_out.
