+++ /dev/null
-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());
- }
- }
-}
git://source.jalview.org / jalview.git / blobdiff