1 package fr.orsay.lri.varna.models.treealign;
6 * An object of this class is a rooted tree, where children are ordered.
7 * The tree is iterable, and the default iterator is DFS
8 * (depth-first search), with the fathers given before the children.
10 * @param <T> The type of values on nodes.
11 * @author Raphael Champeimont
13 public class Tree<T> implements Iterable<Tree<T>> {
14 private List<Tree<T>> children;
16 private Tree<T> tree = this;
22 public void setValue(T value) {
27 * Returns the list of children.
28 * The return list has a O(1) access time to any of its elements
29 * (ie. it is like an array and unlike a linked list)
31 public List<Tree<T>> getChildren() {
36 * This method replaces the list of children of a tree with the list given
37 * as argument. Be careful, because it means the list will be kept as a
38 * reference (it will not be copied) so if you later modify the list
39 * you passed as an argument here, it will modify the list of children.
40 * Note that the List object you give must have a 0(1) access time to
41 * elements (because someone calling getChildren() can expect that property).
42 * This method may be useful if you have already built a list of children
43 * and you don't want to use this.getChildren.addAll() to avoid a O(n) copy.
44 * In that case you would simply call the constructor that takes no argument
45 * to create an empty tree and then call replaceChildrenListBy(children)
46 * where children is the list of children you have built.
47 * @param children the new list of children
49 public void replaceChildrenListBy(List<Tree<T>> children) {
50 this.children = children;
54 * Creates a tree, with the given set of children.
55 * The given set is any collection that implements Iterable<Tree>.
56 * The set is iterated on and its elements are copied (as references).
58 public Tree(Iterable<Tree<T>> children) {
60 for (Tree<T> child: children) {
61 this.children.add(child);
66 * Creates a tree, with an empty list of children.
69 children = new ArrayList<Tree<T>>();
73 * Returns the number of children of the root node.
75 public int rootDegree() {
76 return children.size();
81 * Count the nodes in the tree.
83 * @return the number of nodes in the tree
85 public int countNodes() {
87 for (Tree<T> child: children) {
88 count += child.countNodes();
94 * Compute the tree degree, ie. the max over nodes of the node degree.
96 * @return the maximum node degree
98 public int computeDegree() {
99 int max = children.size();
100 for (Tree<T> child: children) {
101 int maxCandidate = child.computeDegree();
102 if (maxCandidate > max) {
110 * Returns a string unique to this node.
112 public String toGraphvizNodeId() {
113 return super.toString();
117 public Iterator<Tree<T>> iterator() {
118 return (new DFSPrefixIterator());
122 * An iterator that returns the nodes in prefix (fathers before
123 * children) DFS (go deep first) order.
125 public class DFSPrefixIterator implements Iterator<Tree<T>> {
126 private LinkedList<Tree<T>> remainingNodes = new LinkedList<Tree<T>>();
128 public boolean hasNext() {
129 return !remainingNodes.isEmpty();
132 public Tree<T> next() {
133 if (remainingNodes.isEmpty()) {
134 throw (new NoSuchElementException());
136 Tree<T> currentNode = remainingNodes.getLast();
137 remainingNodes.removeLast();
138 List<Tree<T>> children = currentNode.getChildren();
139 int n = children.size();
140 // The children access is in O(1) so this loop is O(n)
141 for (int i=n-1; i>=0; i--) {
142 // We add the children is their reverse order so they
143 // are given in the original order by the iterator
144 remainingNodes.add(children.get(i));
149 public DFSPrefixIterator() {
150 remainingNodes.add(tree);
153 public void remove() {
154 throw (new UnsupportedOperationException());