For the last several days I've been playing with ideas re reducing the work when redrawing the tree in the qt plugin. The shape of the problem is becoming clear. Here are some notes to myself:
- The general idea is to insert and delete the minimum number of tree (i.e., QTreeWidgitItem) nodes. At present, the redraw code calls w.clear, which deletes *all* nodes, and then redraws all *visible* nodes. We can do much better than this. - There are two main parts of the problem: 1) inserting, deleting and (maybe) moving tree nodes, and 2) updating descriptive data structures to reflect the changes made in 1). This second part has the potential to be trickier than the first. Conceivably 2) will be done by brute force by recomputing all the info. This is likely to be fast enough since no screen widgets will be involved. - The overall idea is to reduce the redraw to a series of redraws of siblings. Any change to an outline, regardless of how complex, will ultimately reduce to a series of insertions, deletions and moves of siblings. Moving an outline left or right will appear to be a deletion from one set of siblings and an insertion to another. Special case code might be used for this, but that is not essential. Even without the optimization, not redrawing the entire tree will be a huge improvement. - With the new code, no changes will be made *at all* to the tree when nodes are expanded and contracted. To make this work, the entire tree (including hidden nodes) must be drawn initially, and all nodes (including hidden nodes) must be created when inserting a tree. Now lets consider some particular cases: - This morning I realized that moving a sibling up is exactly the same as moving a sibling down. In either case, the effect is to interchange the two siblings. This "little" Aha was actually quite important. Let's look in detail at what this interchange entails. It's the simplest case in some sense, but it points the way to all the other complexities. 1. At the tree node level, it probably suffices to interchange the two sibling nodes. This can probably be done with just a few calls to QTreeWidget methods. 2. The real problem is updating the auxiliary information maintained by the qt plugin (not the QTreeWidget). In particular, when nodes move, their position changes, as does the position of all descendant nodes. Yes, it might be possible to compute the new positions, but it might be just as simple to recompute everything. We shall see. OTOH, we almost certainly do not want to call item.setData for every item of the tree whenever anything changes,so it would be good to have the data associated with each QTreeWidgetItem be position independent. I think this will be possible. We could, for example, interpose a Python dict: the keys would be item numbers, the values would be (mutable) data. Thus, item.data() doesn't change even when the contents of item.data() changes. Aside: now is the time to build in some sanity checks. The qt tree code will maintain a dictionary of all valid items. Before accessing any item, the qt plugin will ensure it still exists. The goal is to completely eliminate the possibility of hard crashes as the result of passing bad data to QTreeWidget. - Inserting and deleting siblings follows the same general form. To insert a sibling, all the sibling's descendants are created. Deleting a sibling deletes all the deleted siblings descendants. - As mentioned above, we might try to detect and optimize moving a (tree) node left or right. This morning I realized that moving a node left or right always puts that node at the beginning (or end, depending on preferences) of the nodes new siblings. So detecting moves is, in principle, relatively easy. Conclusions There is something very interesting about this approach. It is completely general. That is, it works without knowing anything about the operations that have been performed. **It doesn't need hints.** Indeed, it could not easily use hints even if they were available! And this general algorithm knows nothing about clones and will work no matter how many nodes are affected by clones. This is very good. The cost of this (relative) simplicity is the need to traverse the entire tree any time the tree has been changed. However, expanding and contracting nodes does *not* change the tree in this sense, so expanding and contracting nodes is as fast as possible. I plan to write the first draft of the new code in the next day or so. The first draft will not optimize moves left or right: they'll be in effect a pair of inserts and deletes. That will probably be good enough for a long time. All comments and suggestions welcome. 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 -~----------~----~----~----~------~----~------~--~---
