Friday, October 12, 2007

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.

No comments: