edu.berkeley.guir.lib.graphs
Class PathTree

java.lang.Object
  |
  +--edu.berkeley.guir.lib.graphs.BinaryTree
        |
        +--edu.berkeley.guir.lib.graphs.PathTree

All Implemented Interfaces:

Cloneable, Serializable

public class PathTree

extends BinaryTree

implements Serializable, Cloneable

A Path Tree that represents a hierarchy of siblings and children. You throw Paths into this Tree, and it builds the appropriate hierarchy tree.

The left subtree represents a sibling, and the right subtree represents a child.

This software is distributed under the Berkeley Software License.

 Revisions:  - GUIRLib-v1.0-1.0.0, Dec 01 1997, JH
               Created class
             - GUIRLib-v1.0-1.1.0, Feb 24 2000, JH
               Updated for JDK1.3RC1 to use the Collections
             - GUIRLib-v1.2-1.0.0, Jun 22 2000, JH
               Touched for GUIRLib release
             - GUIRLib-v1.3-1.0.0, Aug 11 2000, JH
               Touched for GUIRLib release
             - GUIRLib-v1.4-1.0.0, Aug 31 2000, JH
               Touched for GUIRLib release
 

Since:

1.1.4

Version:

GUIRLib-v1.4-1.0.0, Aug 31 2000

Author:

Jason Hong ( jasonh@cs.berkeley.edu)

See Also:

Serialized Form

Fields inherited from class edu.berkeley.guir.lib.graphs.BinaryTree

data, left, right

Constructor Summary

	PathTree() Creates a new and empty PathTree.
protected	PathTree(Node node) Creates a new PathTree.

Method Summary

void	addPath(Path p) Adds a path into this hierarchy tree.
protected PathTree	child() Get the child subtree of the current tree.
Object	clone() Clones this PathTree.
protected Node	data() Get the value at the root of this tree.
boolean	equals(Object obj)
int	getNumOfHits() Get the number of hits currently in this PathTree.
int	getNumOfLeaves() Get the number of leaves currently in this PathTree.
int	getNumOfNodes() Get the number of unique nodes currently in this PathTree.
protected PathTree	hasChild(PathTree ptree) Sees if the specified PathTree is a child of the current node.
protected PathTree	hasSibling(PathTree ptree) Sees if the specified PathTree is a sibling of the current node (or the same as the current node).
Enumeration	inOrderTraversal() Perform an inorder traversal on this tree.
Enumeration	postOrderTraversal() Perform a postorder traversal on this tree.
Enumeration	preOrderTraversal() Perform a preorder traversal on this tree.
void	printReverseOrderTraversal() Print out the traversal in reverse pre-order to the default System.out stream in a formatted order.
void	printReverseOrderTraversal(PrintWriter pwriter) Print out the traversal in reverse pre-order to the specified PrintWriter in a formatted order.
void	printTraversal() Print out the tree in a hierarchy to System.out, using the default layout formatter for the PathTree.
void	printTraversal(PathTreeFormatter f) Print out the tree in a hierarchy to System.out, using the specified layout formatter for the PathTree.
void	printTraversal(PrintWriter pwriter) Print out the tree in a hierarchy to the specified Writer, using the default PathTreeFormatter layout.
void	printTraversal(PrintWriter pwriter, PathTreeFormatter f) Print out the tree in a hierarchy to the specified Writer, using the PathTreeFormatter passed in.
protected void	setChild(PathTree ptree) Set the child subtree of the current tree.
protected void	setData(Node node) Set the value at the root of this tree.
void	setDefaultFormatter(PathTreeFormatter f)
protected void	setSibling(PathTree ptree) Set the sibling subtree of the current tree.
protected PathTree	sibling() Get the sibling subtree of the current tree.

Methods inherited from class edu.berkeley.guir.lib.graphs.BinaryTree

_data, _left, _right, _setData, _setLeft, _setRight, add, exists, getNumberOfElements, remove, toString

Methods inherited from class java.lang.Object

finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

PathTree

public PathTree()

Creates a new and empty PathTree.

PathTree

protected PathTree(Node node)

Creates a new PathTree. Used internally only.

Method Detail

setDefaultFormatter

public void setDefaultFormatter(PathTreeFormatter f)

addPath

public void addPath(Path p)

Adds a path into this hierarchy tree.

Parameters:

p - is the Path to add into this tree.

setChild

protected void setChild(PathTree ptree)

Set the child subtree of the current tree.

Parameters:

ptree - is a PathTree to set the child subtree to.

setSibling

protected void setSibling(PathTree ptree)

Set the sibling subtree of the current tree.

Parameters:

ptree - is a PathTree to set the sibling subtree to.

setData

protected void setData(Node node)

Set the value at the root of this tree.

Parameters:

str - is the value for the root of this tree.

getNumOfNodes

public int getNumOfNodes()

Get the number of unique nodes currently in this PathTree.

Returns:

the number of unique nodes currently in this PathTree.

getNumOfLeaves

public int getNumOfLeaves()

Get the number of leaves currently in this PathTree. Currently, does not return a useful value.

Returns:

an unuseful value.

getNumOfHits

public int getNumOfHits()

Get the number of hits currently in this PathTree.

Returns:

the number of hits currently in this PathTree.

hasChild

protected PathTree hasChild(PathTree ptree)

Sees if the specified PathTree is a child of the current node. Only checks the specified node itself, does not check the children or siblings of the specified node.

Parameters:

ptree - is the PathTree to check for.

Returns:

the actual child, or null if it is not a child.

hasSibling

protected PathTree hasSibling(PathTree ptree)

Sees if the specified PathTree is a sibling of the current node (or the same as the current node). Only checks the specified node itself, does not check the children or siblings of the specified node.

Parameters:

ptree - is the PathTree to check for.

Returns:

the actual sibling, or null if it is not a sibling.

data

protected Node data()

Get the value at the root of this tree.

Returns:

A Node containing the value at the root of this tree.

child

protected PathTree child()

Get the child subtree of the current tree.

Returns:

the child subtree.

sibling

protected PathTree sibling()

Get the sibling subtree of the current tree.

Returns:

the sibling subtree.

inOrderTraversal

public Enumeration inOrderTraversal()

Perform an inorder traversal on this tree.

Overrides:

inOrderTraversal in class BinaryTree

Returns:

an Enumeration containing the elements of this tree in order.

preOrderTraversal

public Enumeration preOrderTraversal()

Perform a preorder traversal on this tree.

Overrides:

preOrderTraversal in class BinaryTree

Returns:

an Enumeration containing the elements of this tree in order.

postOrderTraversal

public Enumeration postOrderTraversal()

Perform a postorder traversal on this tree.

Overrides:

postOrderTraversal in class BinaryTree

Returns:

an Enumeration containing the elements of this tree in preorder.

printReverseOrderTraversal

public void printReverseOrderTraversal()

Print out the traversal in reverse pre-order to the default System.out stream in a formatted order.

printReverseOrderTraversal

public void printReverseOrderTraversal(PrintWriter pwriter)

Print out the traversal in reverse pre-order to the specified PrintWriter in a formatted order.

Parameters:

pwriter - is the PrintWriter to print out to.

printTraversal

public void printTraversal()

Print out the tree in a hierarchy to System.out, using the default layout formatter for the PathTree.

printTraversal

public void printTraversal(PathTreeFormatter f)

Print out the tree in a hierarchy to System.out, using the specified layout formatter for the PathTree.

Parameters:

f - is an interface to a layout formatter for PathTrees.

printTraversal

public void printTraversal(PrintWriter pwriter)

Print out the tree in a hierarchy to the specified Writer, using the default PathTreeFormatter layout.

The order of events is:

• onStart() (once only)
• onStartOfNode()
• either onLeaf() or onNode()
• traverse all of the children
• onBacktrack()
• traverse all of the siblings
• onEndOfNode()
• onFinish() (once only)

Parameters:

pwriter - is the PrintWriter to print out to.

printTraversal

public void printTraversal(PrintWriter pwriter,
                           PathTreeFormatter f)

Print out the tree in a hierarchy to the specified Writer, using the PathTreeFormatter passed in.

Parameters:

pwriter - is the PrintWriter to print out to.

f - is the formatting object, that is, an interface to an object that contains methods that can format the layout of this PathTree.

clone

public Object clone()

Clones this PathTree.

Overrides:

clone in class Object

Returns:

a PathTree object that has the same values as this PathTree object.

equals

public boolean equals(Object obj)

Overrides:

equals in class BinaryTree