src2/fr/orsay/lri/varna/models/treealign/Tree.java

   1 package fr.orsay.lri.varna.models.treealign;
   2 import java.util.*;
   3
   4
   5 /**
   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.
   9  *
  10  * @param <T> The type of values on nodes.
  11  * @author Raphael Champeimont
  12  */
  13 public class Tree<T> implements Iterable<Tree<T>> {
  14         private List<Tree<T>> children;
  15         private T value;
  16         private Tree<T> tree = this;
  17
  18         public T getValue() {
  19                 return value;
  20         }
  21
  22         public void setValue(T value) {
  23                 this.value = value;
  24         }
  25
  26         /**
  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)
  30          */
  31         public List<Tree<T>> getChildren() {
  32                 return children;
  33         }
  34
  35         /**
  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
  48          */
  49         public void replaceChildrenListBy(List<Tree<T>> children) {
  50                 this.children = children;
  51         }
  52
  53         /**
  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).
  57          */
  58         public Tree(Iterable<Tree<T>> children) {
  59                 this();
  60                 for (Tree<T> child: children) {
  61                         this.children.add(child);
  62                 }
  63         }
  64
  65         /**
  66          * Creates a tree, with an empty list of children.
  67          */
  68         public Tree() {
  69                 children = new ArrayList<Tree<T>>();
  70         }
  71
  72         /**
  73          * Returns the number of children of the root node.
  74          */
  75         public int rootDegree() {
  76                 return children.size();
  77         }
  78
  79
  80         /**
  81          * Count the nodes in the tree.
  82          * Time: O(n)
  83          * @return the number of nodes in the tree
  84          */
  85         public int countNodes() {
  86                 int count = 1;
  87                 for (Tree<T> child: children) {
  88                         count += child.countNodes();
  89                 }
  90                 return count;
  91         }
  92
  93         /**
  94          * Compute the tree degree, ie. the max over nodes of the node degree.
  95          * Time: O(n)
  96          * @return the maximum node degree
  97          */
  98         public int computeDegree() {
  99                 int max = children.size();
 100                 for (Tree<T> child: children) {
 101                         int maxCandidate = child.computeDegree();
 102                         if (maxCandidate > max) {
 103                                 max = maxCandidate;
 104                         }
 105                 }
 106                 return max;
 107         }
 108
 109         /**
 110          * Returns a string unique to this node.
 111          */
 112         public String toGraphvizNodeId() {
 113                 return super.toString();
 114         }
 115
 116
 117         public Iterator<Tree<T>> iterator() {
 118                 return (new DFSPrefixIterator());
 119         }
 120
 121         /**
 122          * An iterator that returns the nodes in prefix (fathers before
 123          * children) DFS (go deep first) order.
 124          */
 125         public class DFSPrefixIterator implements Iterator<Tree<T>> {
 126                 private LinkedList<Tree<T>> remainingNodes = new LinkedList<Tree<T>>();
 127
 128                 public boolean hasNext() {
 129                         return !remainingNodes.isEmpty();
 130                 }
 131
 132                 public Tree<T> next() {
 133                         if (remainingNodes.isEmpty()) {
 134                                 throw (new NoSuchElementException());
 135                         }
 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));
 145                         }
 146                         return currentNode;
 147                 }
 148
 149                 public DFSPrefixIterator() {
 150                         remainingNodes.add(tree);
 151                 }
 152
 153                 public void remove() {
 154                         throw (new UnsupportedOperationException());
 155                 }
 156         }
 157 }