aud.example.expr.ExpressionTreeTraversal Class Reference

example: visualize expression tree traversal More...

Inheritance diagram for aud.example.expr.ExpressionTreeTraversal:

Collaboration diagram for aud.example.expr.ExpressionTreeTraversal:

Public Member Functions
	ExpressionTreeTraversal (ExpressionTree tree)
	create traversal application for tree More...
void	traverse (String type)
	start traversal More...
Public Member Functions inherited from aud.util.SingleStepper
	SingleStepper (JFrame parent)
	create new instance More...
	SingleStepper (String caption)
	create new instance More...
JFrame	parent ()
	get parent widget More...
void	halt (String text, int timeout)
	display text and wait for user or timeout More...
void	setTimeout (int timeout)
	Set global timeout. More...
SingleStepper	whereAmI ()
	print location of calling code More...
SingleStepper	showSource ()
	jmp to caller's location in editor (emacs only) More...
void	halt (String text)
	display text and wait for user (or global timeout) More...
void	halt ()
	wait for user More...

Static Public Member Functions
static void	main (String[] args)
static void	main (String[] args)

Protected Member Functions
void	onHalt ()
void	output (ExpressionTree node)
	output node during traversal More...
void	see (ExpressionTree node)
	arrived node for first time (for visualization) More...
void	preorder (ExpressionTree node)
	recursive preorder traversal More...
void	inorder (ExpressionTree node)
	recursive inorder traversal More...
void	postorder (ExpressionTree node)
	recursive postorder traversal More...
void	levelorder (ExpressionTree root)
	level order traversdal More...
Protected Member Functions inherited from aud.util.SingleStepper
JComponent	createComponents ()
void	onNext ()
	call on button pressed More...
void	println (String text)
	print to both, text area and stdout More...
void	onHalt ()

Protected Attributes
ExpressionTree	tree_ = null
DotViewer	viewer_
SimpleDecorator	decorator
Protected Attributes inherited from aud.util.SingleStepper
JFrame	frame
JTextArea	history
JButton	next
Object	monitor = new Object()
int	timeout = 0

Detailed Description

example: visualize expression tree traversal

Definition at line 7 of file ExpressionTreeTraversal.java.

Constructor & Destructor Documentation

ExpressionTreeTraversal()

aud.example.expr.ExpressionTreeTraversal.ExpressionTreeTraversal

(

ExpressionTree

tree

)

create traversal application for tree

Definition at line 15 of file ExpressionTreeTraversal.java.

                                                      {
    super("aud.example.expr.ExpressionTreeTraversal");
    tree_=tree;
    decorator=(SimpleDecorator) tree_.getDecorator(); // same per tree
  }

References aud.example.expr.ExpressionTreeTraversal.decorator, aud.example.expr.ExpressionTree.getDecorator(), and aud.example.expr.ExpressionTreeTraversal.tree_.

Here is the call graph for this function:

Member Function Documentation

inorder()

void aud.example.expr.ExpressionTreeTraversal.inorder ( ExpressionTree  node )

protected

recursive inorder traversal

Definition at line 83 of file ExpressionTreeTraversal.java.

                                              {
    if (node!=null) {
      see(node);
 
      inorder((ExpressionTree) node.getLeft());
      output(node);
      inorder((ExpressionTree) node.getRight());
    }
  }

References aud.BinaryTree< T >.getLeft(), aud.BinaryTree< T >.getRight(), aud.example.expr.ExpressionTreeTraversal.inorder(), aud.example.expr.ExpressionTreeTraversal.output(), and aud.example.expr.ExpressionTreeTraversal.see().

Referenced by aud.example.expr.ExpressionTreeTraversal.inorder(), and aud.example.expr.ExpressionTreeTraversal.traverse().

Here is the call graph for this function:

Here is the caller graph for this function:

levelorder()

void aud.example.expr.ExpressionTreeTraversal.levelorder ( ExpressionTree  root )

protected

level order traversdal

Definition at line 103 of file ExpressionTreeTraversal.java.

                                                 {
    Queue<ExpressionTree> queue=new Queue<ExpressionTree>();
    queue.enqueue(null);     // marker: next level
    queue.enqueue(root);
    int level=0;             // keep track of/count levels
    while (!queue.is_empty()) {
      ExpressionTree node=queue.dequeue();
 
      if (node==null) {
        decorator.highlightNode(null);
        halt("enter next level "+(level++));
        if (!queue.is_empty())
          queue.enqueue(null); // marker: next level
      }
      else {
        see(node);
 
        if (node.getLeft()!=null)
          queue.enqueue((ExpressionTree) node.getLeft());
        if (node.getRight()!=null)
          queue.enqueue((ExpressionTree) node.getRight());
        output(node);
      }
    }
  }

References aud.example.expr.ExpressionTreeTraversal.decorator, aud.Queue< T >.dequeue(), aud.Queue< T >.enqueue(), aud.BinaryTree< T >.getLeft(), aud.BinaryTree< T >.getRight(), aud.util.SingleStepper.halt(), aud.util.SimpleDecorator.highlightNode(), aud.Queue< T >.is_empty(), aud.example.expr.ExpressionTreeTraversal.output(), and aud.example.expr.ExpressionTreeTraversal.see().

Referenced by aud.example.expr.ExpressionTreeTraversal.traverse().

Here is the call graph for this function:

Here is the caller graph for this function:

main()

static void aud.example.expr.ExpressionTreeTraversal.main ( String[]  args )

static

Reimplemented from aud.util.SingleStepper.

Definition at line 129 of file ExpressionTreeTraversal.java.

                                         {
 
    if (args.length<1 || args.length>2) {
      System.err.println
        ("usage: java aud.example.expr.ExpressionTreeTraversal expr [mode]\n"+
         "- expr: an expression, e.g., \"2*(3+4)\" "+
         "(use quotes \"...\" on command line!)\n"+
         "- mode: preorder | inorder | postorder | levelorder");
      System.exit(-1);
    }
 
    ExpressionTree tree=new ExpressionParser().parse(args[0]);
    ExpressionTreeTraversal app=new ExpressionTreeTraversal(tree);
 
    app.traverse(args.length>1 ? args[1] : "preorder");
 
    app.halt("QUIT");
    System.exit(0);
  }

References aud.util.SingleStepper.halt(), aud.example.expr.ExpressionParser.parse(), and aud.example.expr.ExpressionTreeTraversal.traverse().

Here is the call graph for this function:

onHalt()

void aud.example.expr.ExpressionTreeTraversal.onHalt ( )

protected

Reimplemented from aud.util.SingleStepper.

Definition at line 21 of file ExpressionTreeTraversal.java.

                                    {
    if (tree_!=null)
      viewer_.display(tree_);
  }

References aud.util.DotViewer.display(), aud.example.expr.ExpressionTreeTraversal.tree_, and aud.example.expr.ExpressionTreeTraversal.viewer_.

Here is the call graph for this function:

output()

void aud.example.expr.ExpressionTreeTraversal.output ( ExpressionTree  node )

protected

output node during traversal

See also

traverse

Definition at line 29 of file ExpressionTreeTraversal.java.

                                             {
    decorator.markNode(node);
    decorator.highlightNode(node);
    decorator.setGraphLabel(decorator.getGraphLabel()+node.getData()+" ");
    halt("output "+node.getData()+" ["+node+"]");
  }

References aud.example.expr.ExpressionTreeTraversal.decorator, aud.BinaryTree< T >.getData(), aud.util.CommonGraphvizDecorator.getGraphLabel(), aud.util.SingleStepper.halt(), aud.util.SimpleDecorator.highlightNode(), aud.util.SimpleDecorator.markNode(), and aud.util.CommonGraphvizDecorator.setGraphLabel().

Referenced by aud.example.expr.ExpressionTreeTraversal.inorder(), aud.example.expr.ExpressionTreeTraversal.levelorder(), aud.example.expr.ExpressionTreeTraversal.postorder(), and aud.example.expr.ExpressionTreeTraversal.preorder().

Here is the call graph for this function:

Here is the caller graph for this function:

postorder()

void aud.example.expr.ExpressionTreeTraversal.postorder ( ExpressionTree  node )

protected

recursive postorder traversal

Definition at line 93 of file ExpressionTreeTraversal.java.

                                                {
    if (node!=null) {
      see(node);
 
      postorder((ExpressionTree) node.getLeft());
      postorder((ExpressionTree) node.getRight());
      output(node);
    }
  }

References aud.BinaryTree< T >.getLeft(), aud.BinaryTree< T >.getRight(), aud.example.expr.ExpressionTreeTraversal.output(), aud.example.expr.ExpressionTreeTraversal.postorder(), and aud.example.expr.ExpressionTreeTraversal.see().

Referenced by aud.example.expr.ExpressionTreeTraversal.postorder(), and aud.example.expr.ExpressionTreeTraversal.traverse().

Here is the call graph for this function:

Here is the caller graph for this function:

preorder()

void aud.example.expr.ExpressionTreeTraversal.preorder ( ExpressionTree  node )

protected

recursive preorder traversal

Definition at line 73 of file ExpressionTreeTraversal.java.

                                               {
    if (node!=null) {
      see(node);
 
      output(node);
      preorder((ExpressionTree) node.getLeft());
      preorder((ExpressionTree) node.getRight());
    }
  }

References aud.BinaryTree< T >.getLeft(), aud.BinaryTree< T >.getRight(), aud.example.expr.ExpressionTreeTraversal.output(), aud.example.expr.ExpressionTreeTraversal.preorder(), and aud.example.expr.ExpressionTreeTraversal.see().

Referenced by aud.example.expr.ExpressionTreeTraversal.preorder(), and aud.example.expr.ExpressionTreeTraversal.traverse().

Here is the call graph for this function:

Here is the caller graph for this function:

see()

void aud.example.expr.ExpressionTreeTraversal.see ( ExpressionTree  node )

protected

arrived node for first time (for visualization)

Definition at line 36 of file ExpressionTreeTraversal.java.

                                          {
    decorator.markEdge(node);
  }

References aud.example.expr.ExpressionTreeTraversal.decorator, and aud.util.SimpleDecorator.markEdge().

Referenced by aud.example.expr.ExpressionTreeTraversal.inorder(), aud.example.expr.ExpressionTreeTraversal.levelorder(), aud.example.expr.ExpressionTreeTraversal.postorder(), and aud.example.expr.ExpressionTreeTraversal.preorder().

Here is the call graph for this function:

Here is the caller graph for this function:

traverse()

void aud.example.expr.ExpressionTreeTraversal.traverse

(

String

type

)

start traversal

Parameters

type	denotes the type of traversal "preorder", "inorder","postorder"

Exceptions

RuntimeException

for unknown type

Definition at line 45 of file ExpressionTreeTraversal.java.

                                    {
    decorator.clear();
    decorator.setGraphLabel("Traversal: ");
 
    if (type.toLowerCase().startsWith("pre")) {
      halt("START preorder traversal");
      preorder(tree_);
    }
    else if (type.toLowerCase().startsWith("in")) {
      halt("START inorder traversal");
      inorder(tree_);
    }
    else if (type.toLowerCase().startsWith("post")) {
      halt("START postorder traversal");
      postorder(tree_);
    }
    else if (type.toLowerCase().startsWith("level")) {
      halt("START level-order traversal");
      levelorder(tree_);
    }
    else
      throw new RuntimeException("unknown traversal '"+type+"'");
 
    decorator.highlightNode(null);
    halt("FINISHED");
  }

References aud.util.CommonGraphvizDecorator.clear(), aud.example.expr.ExpressionTreeTraversal.decorator, aud.util.SingleStepper.halt(), aud.util.SimpleDecorator.highlightNode(), aud.example.expr.ExpressionTreeTraversal.inorder(), aud.example.expr.ExpressionTreeTraversal.levelorder(), aud.example.expr.ExpressionTreeTraversal.postorder(), aud.example.expr.ExpressionTreeTraversal.preorder(), aud.util.CommonGraphvizDecorator.setGraphLabel(), and aud.example.expr.ExpressionTreeTraversal.tree_.

Referenced by aud.example.expr.ExpressionTreeTraversal.main().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

decorator

SimpleDecorator aud.example.expr.ExpressionTreeTraversal.decorator

protected

Definition at line 12 of file ExpressionTreeTraversal.java.

Referenced by aud.example.expr.ExpressionTreeTraversal.ExpressionTreeTraversal(), aud.example.expr.ExpressionTreeTraversal.levelorder(), aud.example.expr.ExpressionTreeTraversal.output(), aud.example.expr.ExpressionTreeTraversal.see(), and aud.example.expr.ExpressionTreeTraversal.traverse().

tree_

ExpressionTree aud.example.expr.ExpressionTreeTraversal.tree_ = null

protected

Definition at line 9 of file ExpressionTreeTraversal.java.

Referenced by aud.example.expr.ExpressionTreeTraversal.ExpressionTreeTraversal(), aud.example.expr.ExpressionTreeTraversal.onHalt(), and aud.example.expr.ExpressionTreeTraversal.traverse().

viewer_

DotViewer aud.example.expr.ExpressionTreeTraversal.viewer_

protected

Initial value:

= DotViewer.displayWindow
    ((String) null,"aud.example.expr.ExpressionTreeTraversal")

Definition at line 10 of file ExpressionTreeTraversal.java.

Referenced by aud.example.expr.ExpressionTreeTraversal.onHalt().

---

The documentation for this class was generated from the following file:

• ExpressionTreeTraversal.java