First Draft of Undoable Threaded Binary Trees Finished (Finally!)

I've got a final draft of undoable threaded binary trees in the Umeta Sourceforge package of the JUndo Runtime project. Now I can actually use it for something...

Undoable Threaded Binary Trees Almost Completed

The latest draft of the umeta package of the JUndo Runtime Sourceforge project is now up (version 0.0.12). This update moves the binary tree classes much closer to completion. Hopefully I'm close to wrapping up umeta (at least in an initial draft).

New Umeta Update-- 071021 (Undoable Threaded Binary Trees)

I finished more code for undoable threaded binary trees. Hopefully, I'm getting close to wrapping this up. It seems like I've been working on nothing but trees for a while now. At the same time, the code does show how general a language JUndo is becoming (assuming anybody is reading it).

Binary Tree Traversals in Umeta

I just finished a draft version of the traversal code for the LowLevelBinTree class in the Umeta Sourceforge package of the Jundo Runtime, although I may revise it later.

One change I made in Umeta is that the Callback class from Meta isn't in Umeta and never will be. Umeta uses a different (Jundo-specific) design pattern for traversals. Here is the reasoning. In typical procedural code, a routine traverses a data structure such as a tree, and performs a "visit" on each traversed node. Hence, the logical thing to do is to provide a callback for each visit.

Hence, the typical Java code for using the traversal would be as follows:

Callback x = [Your callback here];
myDataStructure.someTraversal( x );

with the presumption that x would be called on each visit. JUndo provides a select expression syntax that doesn't exist in Java. In JUndo, it makes more sense to take advantage of the selection functionality rather than use a callback. The JUndo equivalent would be as follows (in a seq block):

IteratorFactory fac = myDataStructure.someTraversal();
IteratorFactory fac2 = select [Your callback here] from a : fac where true fi;
Iterator itf = ( fac2.iterator() ).cobj;
IteratorUtils.getLastItem( itf );

The advantage is that more possibilities are available. For instance, the select expression can be changed to:

IteratorFactory fac2 = select [Your callback here] from a : fac where [your condition here] fi;

One can apply arbitrary filters to the traversal, and this provides the ability to traverse a subset of a structure's elements. It's also possible to quantify over more than one IteratorFactory. For instance, one could perform a join between two different traversals. Imagine having a callback that gets invoked when items from two different structures match respective conditions as follows:

IteratorFactory fac2 = select [Your callback here] from a : faca , b : facb where [your condition here] fi;

Your callback and condition code gets access to both "a" and "b" in the select! This has a potentially limitless set of creative uses.

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.