Util.Structures
Class NimbleTree<E>

java.lang.Object
  extended by Util.Structures.NimbleTree<E>
Direct Known Subclasses:
DerivationTree

public class NimbleTree<E>
extends java.lang.Object

Lightweight tree n-arity structure

Version:
2006.1016
Author:
EHemberg, Eoin Murphy

Constructor Summary
NimbleTree()
          Creates a new instance of NimbleTree
NimbleTree(E data)
          Creates a new Tree with data as the root nodes data
NimbleTree(NimbleTree<E> n)
          Copy constructor
 
Method Summary
 void addChild(E data)
          Add a child to the current node.
 java.util.ArrayList<TreeNode<E>> depthFirstTraversal(TreeNode<E> root)
          Do a depth-first traversal of the tree starting at a given node.
 java.util.ArrayList<TreeNode<E>> getAncestorChain(TreeNode<E> node, int n)
          Starting at a given node, get a chain of ancestors of length n or less.
 java.util.ArrayList<java.util.ArrayList<TreeNode<E>>> getAncestorChains(int n)
          Get all the chains of ancestors of length n in this tree.
 java.util.ArrayList<java.lang.Integer> getBranchLengths()
          Do a depth first traversal and return the list of branch depths
 java.util.ArrayList<java.lang.Integer> getBranchLengths(TreeNode<E> root)
           
 int getCurrentLevel()
          Get current level
 TreeNode<E> getCurrentNode()
          Get current node
 int getDepth()
          Get maximum depth of tree
 int getMaxStackSize()
          Get max stack size
 int getNodeCount()
          Get node count
 TreeNode<E> getRoot()
          Get root of tree
 java.util.ArrayList<java.util.ArrayList<TreeNode<E>>> getRootToLeafPaths()
          Find all the paths from root to leaves.
static NimbleTree<java.lang.String> makeTreeOverStringFromSExpression(java.lang.String input)
          A static constructor (is this the right term?)
protected  TreeNode<E> newNode()
           
 void populateStack()
          Create nodes and push to the stack
 void setCurrentLevel(int i)
          Set current level
 void setCurrentNode(TreeNode<E> tn)
          Set current node
 void setDepth(int i)
          Set depth of tree
 void setMaxStackSize(int i)
          Set max stack size
 void setNodeCount(int i)
          Set node count
 void setRoot(TreeNode<E> tn)
          Set tree root
 java.lang.String toString()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

NimbleTree

public NimbleTree()
Creates a new instance of NimbleTree


NimbleTree

public NimbleTree(E data)
Creates a new Tree with data as the root nodes data

Parameters:
data - The data/label for the root node

NimbleTree

public NimbleTree(NimbleTree<E> n)
Copy constructor

Parameters:
n - copied tree
Method Detail

newNode

protected TreeNode<E> newNode()

setMaxStackSize

public void setMaxStackSize(int i)
Set max stack size

Parameters:
i - max stack size

getMaxStackSize

public int getMaxStackSize()
Get max stack size

Returns:
max stack size

populateStack

public void populateStack()
Create nodes and push to the stack


getRoot

public TreeNode<E> getRoot()
Get root of tree

Returns:
tree root

setRoot

public void setRoot(TreeNode<E> tn)
Set tree root

Parameters:
tn - root of tree

getCurrentNode

public TreeNode<E> getCurrentNode()
Get current node

Returns:
current node

setCurrentNode

public void setCurrentNode(TreeNode<E> tn)
Set current node

Parameters:
tn - node to be current

getNodeCount

public int getNodeCount()
Get node count

Returns:
number of nodes in tree

setNodeCount

public void setNodeCount(int i)
Set node count

Parameters:
i - number to set

setDepth

public void setDepth(int i)
Set depth of tree

Parameters:
i - depth

getDepth

public int getDepth()
Get maximum depth of tree

Returns:
tree max depth

getCurrentLevel

public int getCurrentLevel()
Get current level

Returns:
current level

setCurrentLevel

public void setCurrentLevel(int i)
Set current level

Parameters:
i - level to set

makeTreeOverStringFromSExpression

public static NimbleTree<java.lang.String> makeTreeOverStringFromSExpression(java.lang.String input)
A static constructor (is this the right term?) where a lisp-style s-expression is passed in as a string. This can't be a true constructor because the result is a tree over String, not a generic tree.


getRootToLeafPaths

public java.util.ArrayList<java.util.ArrayList<TreeNode<E>>> getRootToLeafPaths()
Find all the paths from root to leaves. Used by NGramEDAReproductionOperation.

Returns:
list of list of TreeNode, each list starting at the root and ending at a leaf.

getAncestorChains

public java.util.ArrayList<java.util.ArrayList<TreeNode<E>>> getAncestorChains(int n)
Get all the chains of ancestors of length n in this tree. Used as sources for NGram model.


getAncestorChain

public java.util.ArrayList<TreeNode<E>> getAncestorChain(TreeNode<E> node,
                                                         int n)
Starting at a given node, get a chain of ancestors of length n or less.


depthFirstTraversal

public java.util.ArrayList<TreeNode<E>> depthFirstTraversal(TreeNode<E> root)
Do a depth-first traversal of the tree starting at a given node.

Returns:
a list of TreeNodes in depth-first order.

getBranchLengths

public java.util.ArrayList<java.lang.Integer> getBranchLengths()
Do a depth first traversal and return the list of branch depths


getBranchLengths

public java.util.ArrayList<java.lang.Integer> getBranchLengths(TreeNode<E> root)

addChild

public void addChild(E data)
Add a child to the current node. Take a node from the free nodes. INFINITE LOOP POSSIBILITY??!!

Parameters:
data - data contained in the child

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object