X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=srcjar%2Ffr%2Forsay%2Flri%2Fvarna%2Fmodels%2Ftreealign%2FTree.java;fp=srcjar%2Ffr%2Forsay%2Flri%2Fvarna%2Fmodels%2Ftreealign%2FTree.java;h=ff00e710b762f132f665e29aff675f36061dd130;hb=65740880573a48adc758bec3939ece9d9ae104dd;hp=0000000000000000000000000000000000000000;hpb=71aa78b8a7d54e5aeb6b278310dfd735efb77477;p=jalview.git

diff --git a/srcjar/fr/orsay/lri/varna/models/treealign/Tree.java b/srcjar/fr/orsay/lri/varna/models/treealign/Tree.java
new file mode 100644
index 0000000..ff00e71
--- /dev/null
+++ b/srcjar/fr/orsay/lri/varna/models/treealign/Tree.java
@@ -0,0 +1,157 @@
+package fr.orsay.lri.varna.models.treealign;
+import java.util.*;
+
+
+/**
+ * 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.
+ * 
+ * @param <T> The type of values on nodes.
+ * @author Raphael Champeimont
+ */
+public class Tree<T> implements Iterable<Tree<T>> {
+	private List<Tree<T>> children;
+	private T value;
+	private Tree<T> tree = this;
+	
+	public T getValue() {
+		return value;
+	}
+
+	public void setValue(T value) {
+		this.value = value;
+	}
+
+	/**
+	 * 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)
+	 */
+	public List<Tree<T>> getChildren() {
+		return 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.
+	 * @param children the new list of children
+	 */
+	public void replaceChildrenListBy(List<Tree<T>> children) {
+		this.children = children;
+	}
+
+	/**
+	 * Creates a tree, with the given set of children.
+	 * The given set is any collection that implements Iterable<Tree>.
+	 * The set is iterated on and its elements are copied (as references).
+	 */
+	public Tree(Iterable<Tree<T>> children) {
+		this();
+		for (Tree<T> child: children) {
+			this.children.add(child);
+		}
+	}
+	
+	/**
+	 * Creates a tree, with an empty list of children.
+	 */
+	public Tree() {
+		children = new ArrayList<Tree<T>>();
+	}
+	
+	/**
+	 * Returns the number of children of the root node.
+	 */
+	public int rootDegree() {
+		return children.size();
+	}
+	
+	
+	/**
+	 * Count the nodes in the tree.
+	 * Time: O(n)
+	 * @return the number of nodes in the tree
+	 */
+	public int countNodes() {
+		int count = 1;
+		for (Tree<T> child: children) {
+			count += child.countNodes();
+		}
+		return count;
+	}
+	
+	/**
+	 * Compute the tree degree, ie. the max over nodes of the node degree.
+	 * Time: O(n)
+	 * @return the maximum node degree
+	 */
+	public int computeDegree() {
+		int max = children.size();
+		for (Tree<T> child: children) {
+			int maxCandidate = child.computeDegree();
+			if (maxCandidate > max) {
+				max = maxCandidate;
+			}
+		}
+		return max;
+	}
+	
+	/**
+	 * Returns a string unique to this node.
+	 */
+	public String toGraphvizNodeId() {
+		return super.toString();
+	}
+	
+	
+	public Iterator<Tree<T>> iterator() {
+		return (new DFSPrefixIterator());
+	}
+	
+	/**
+	 * An iterator that returns the nodes in prefix (fathers before
+	 * children) DFS (go deep first) order.
+	 */
+	public class DFSPrefixIterator implements Iterator<Tree<T>> {
+		private LinkedList<Tree<T>> remainingNodes = new LinkedList<Tree<T>>();
+		
+		public boolean hasNext() {
+			return !remainingNodes.isEmpty();
+		}
+		
+		public Tree<T> next() {
+			if (remainingNodes.isEmpty()) {
+				throw (new NoSuchElementException());
+			}
+			Tree<T> currentNode = remainingNodes.getLast();
+			remainingNodes.removeLast();
+			List<Tree<T>> children = currentNode.getChildren();
+			int n = children.size();
+			// The children access is in O(1) so this loop is O(n)
+			for (int i=n-1; i>=0; i--) {
+				// We add the children is their reverse order so they
+				// are given in the original order by the iterator
+				remainingNodes.add(children.get(i));
+			}
+			return currentNode;
+		}
+		
+		public DFSPrefixIterator() {
+			remainingNodes.add(tree);
+		}
+
+		public void remove() {
+			throw (new UnsupportedOperationException());
+		}
+	}
+}