Thursday, October 11, 2007

Started Adding Binary Tree Code to Umeta package of JUndo Runtime

I've found threaded binary trees to be a useful data structure on several occasions. That is one of the reasons why they exist in the Meta project. However, I have realized that there is a need for a binary tree that is undoable. That is to say, modifications to the tree can be reversed upon user request. To facilitate this, I have started adding undoable binary tree classes to the Umeta package of the JUndo Runtime Sourceforge project. The code is still in an incomplete state, and it will take some time to get the (non-undoable) Java fully converted to (undoable) JUndo. Once the tree classes are complete, I plan to use them in some Verdantium demo code.

One thing to notice is that the erasure patterns in methods pruneLeft() and eraseAll() differ from those in LowLevelBinTree in the Meta project. In the Java Meta code, pointers had to be assigned so that the identity of the next node would be picked up before the node was disconnected (disconnection deletes this information from the node by setting the node references to null). This creates some code that is tricky and hard to follow. It uses the temporary pointers in some rather complex ways. In addition, the technique for using the temporary pointers varies depending on the data structure. For instance, lists and trees require different temporary pointer techniques.

The new JUndo code for LowLevelBinTree uses a completely different paradigm in pruneLeft() and eraseAll(). The JUndo code traverses the structure in one time stream and disconnects the nodes in a different time stream. In the traversal time stream, the nodes aren't disconnected and hence there is no reason to build temporary traversal pointers such as delTemp. However, the nodes still get disconnected in the other time stream. The disconnection time stream's final milieu is the one that gets returned by the erasure method. This pattern for using multiple time streams makes deletions simpler and more consistent across data structures.

No comments: