com.faunos.util.tree
Class AbstractTraverser<T>

java.lang.Object
  com.faunos.util.tree.AbstractTraverser<T>

All Implemented Interfaces:

Runnable

Direct Known Subclasses:

FileSystemTraverser

public abstract class AbstractTraverser<T>
extends Object
implements Runnable

A depth-first, tree structure traverser. The traverser implements an Euler traversal over the tree structure (generalized for tree nodes with arbitrary number of children). As it traverses the tree, an instance fires pre-order and post-order events along the way.

The tree structure does not have to be defined by the parametric type <T> itself (although it typically is); rather, it is the implementation (a subclass of this class) that decides the structure. This is done by implementing the following abstract methods:

• hasChildren(Object) hasChildren(T node)
• getChildren(T node)

Note we could had collapsed all the requirements into the single method getChildren(T node), but then would have had to specify whether return value can be null, zero-length, etc. So hopefully this is clearer.

Thread safety

This class is not safe under concurrent access. We'd have to make the fields volatile for that to work.

Author:

Babak Farhang

See Also:

TraverseListener, Euler Traversal

Constructor Summary

protected

AbstractTraverser(T root) Creates a new instance with the given root node.

Method Summary

protected abstract T[]	getChildren(T node) Returns the child nodes for the specified node.
TraverseListener<T>	getListener() Returns the listener set for traversal.
Comparator<T>	getSiblingOrder() Returns the comparator used to determine the order in which sibling nodes are visited.
protected abstract boolean	hasChildren(T node) Determines whether the given node has child nodes.
void	run() Performs the traversal over the tree structure.
void	setListener(TraverseListener<T> listener) Sets the listener for the traversal.
void	setSiblingOrder(Comparator<T> siblingOrder) Sets the comparator used to determine the order in which sibling nodes are visited.
void	visitPostorder(Visitor<T> visitor) Traverses the tree and visits the tree nodes in post-order.
void	visitPreorder(Visitor<T> visitor) Traverses the tree and visits the tree nodes in pre-order.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

AbstractTraverser

protected AbstractTraverser(T root)

Creates a new instance with the given root node.

Method Detail

setListener

public void setListener(TraverseListener<T> listener)

Sets the listener for the traversal. May be null.

getListener

public TraverseListener<T> getListener()

Returns the listener set for traversal. May be null.

setSiblingOrder

public void setSiblingOrder(Comparator<T> siblingOrder)

Sets the comparator used to determine the order in which sibling nodes are visited.

getSiblingOrder

public Comparator<T> getSiblingOrder()

Returns the comparator used to determine the order in which sibling nodes are visited.

visitPreorder

public void visitPreorder(Visitor<T> visitor)

Traverses the tree and visits the tree nodes in pre-order. This is done by setting the listener to be a pre-order adapter on the specified visitor.

Throws:

IllegalStateException - if the tree has already been traversed

visitPostorder

public void visitPostorder(Visitor<T> visitor)

Traverses the tree and visits the tree nodes in post-order. This is done by setting the listener to be a post-order adapter on the specified visitor.

Throws:

IllegalStateException - if the tree has already been traversed

run

public void run()

Performs the traversal over the tree structure. Pre- and post-order events are fired to the listener, if any.

This method may only be invoked once. Otherwise, an exception is thrown.

Specified by:

run in interface Runnable

Throws:

IllegalStateException - if the tree has already been traversed

hasChildren

protected abstract boolean hasChildren(T node)

Determines whether the given node has child nodes. Note, it's okay if an implementation returns true for a given node and returns an empty array on invoking getChildren(node). I.e. a subclass may treat the semantics of this method as if it were named canHaveChildren.

getChildren

protected abstract T[] getChildren(T node)

Returns the child nodes for the specified node. This method is invoked only if hasChildren(node) returns true.

Returns:

an array of child nodes, possibly empty; never null.