fr.orsay.lri.varna.models.treealign
Class Tree<T>

java.lang.Object
  extended by fr.orsay.lri.varna.models.treealign.Tree<T>
Type Parameters:
T - The type of values on nodes.
All Implemented Interfaces:
Iterable<Tree<T>>

public class Tree<T>
extends Object
implements Iterable<Tree<T>>

An object of this class is a rooted tree, where children are ordered. The tree is iterable, and the default iterator is DFS (depth-first search), with the fathers given before the children.

Author:
Raphael Champeimont

Nested Class Summary
 class Tree.DFSPrefixIterator
          An iterator that returns the nodes in prefix (fathers before children) DFS (go deep first) order.
 
Field Summary
private  List<Tree<T>> children
           
private  Tree<T> tree
           
private  T value
           
 
Constructor Summary
Tree()
          Creates a tree, with an empty list of children.
Tree(Iterable<Tree<T>> children)
          Creates a tree, with the given set of children.
 
Method Summary
 int computeDegree()
          Compute the tree degree, ie.
 int countNodes()
          Count the nodes in the tree.
 List<Tree<T>> getChildren()
          Returns the list of children.
 T getValue()
           
 Iterator<Tree<T>> iterator()
           
 void replaceChildrenListBy(List<Tree<T>> children)
          This method replaces the list of children of a tree with the list given as argument.
 int rootDegree()
          Returns the number of children of the root node.
 void setValue(T value)
           
 String toGraphvizNodeId()
          Returns a string unique to this node.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

children

private List<Tree<T>> children

value

private T value

tree

private Tree<T> tree
Constructor Detail

Tree

public Tree(Iterable<Tree<T>> children)
Creates a tree, with the given set of children. The given set is any collection that implements Iterable. The set is iterated on and its elements are copied (as references).


Tree

public Tree()
Creates a tree, with an empty list of children.

Method Detail

getValue

public T getValue()

setValue

public void setValue(T value)

getChildren

public List<Tree<T>> getChildren()
Returns the list of children. The return list has a O(1) access time to any of its elements (ie. it is like an array and unlike a linked list)


replaceChildrenListBy

public void replaceChildrenListBy(List<Tree<T>> children)
This method replaces the list of children of a tree with the list given as argument. Be careful, because it means the list will be kept as a reference (it will not be copied) so if you later modify the list you passed as an argument here, it will modify the list of children. Note that the List object you give must have a 0(1) access time to elements (because someone calling getChildren() can expect that property). This method may be useful if you have already built a list of children and you don't want to use this.getChildren.addAll() to avoid a O(n) copy. In that case you would simply call the constructor that takes no argument to create an empty tree and then call replaceChildrenListBy(children) where children is the list of children you have built.

Parameters:
children - the new list of children

rootDegree

public int rootDegree()
Returns the number of children of the root node.


countNodes

public int countNodes()
Count the nodes in the tree. Time: O(n)

Returns:
the number of nodes in the tree

computeDegree

public int computeDegree()
Compute the tree degree, ie. the max over nodes of the node degree. Time: O(n)

Returns:
the maximum node degree

toGraphvizNodeId

public String toGraphvizNodeId()
Returns a string unique to this node.


iterator

public Iterator<Tree<T>> iterator()
Specified by:
iterator in interface Iterable<Tree<T>>