// NodeUtils.java
//
// (c) 1999-2001 PAL Development Core Team
//
// This package may be distributed under the
// terms of the Lesser GNU General Public License (LGPL)


package de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree;


import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.Identifier;


/**
 * Helper routines for dealing with nodes.
 *
 * @version $Id: NodeUtils.java,v 1.19 2002/01/08 02:09:53 alexi Exp $
 *
 * @author Alexei Drummond
 * @author Korbinian Strimmer
 */
public class NodeUtils {

	/**
	 * Converts lengths to heights, *without* assuming contemporaneous
	 * tips.
	 */
	public static void lengths2Heights(Node root) {

		lengths2Heights(root, getGreatestDistance(root));
	}

	/**
	 * Converts lengths to heights, but maintains tip heights.
	 */
	public static void lengths2HeightsKeepTips(Node node, boolean useMax) {

		if (!node.isLeaf()) {
			for (int i = 0; i < node.getChildCount(); i++) {
				lengths2HeightsKeepTips(node.getChild(i), useMax);
			}

			double totalHL = 0.0;
			double maxHL = 0.0;
			double hl = 0.0;
			double maxH = 0.0;
			double h = 0.0;
			for (int i = 0; i < node.getChildCount(); i++) {
				h = node.getChild(i).getNodeHeight();
				hl = node.getChild(i).getBranchLength() + h;
				if (hl > maxHL) maxHL = hl;
				if (h > maxH) maxH = h;
				totalHL += hl;
			}
			if (useMax) {
				hl = maxHL; // set parent height to maximum parent height implied by children
			} else {
				hl = totalHL /  node.getChildCount(); // get mean parent height
				if (hl < maxH) hl = maxHL; // if mean parent height is not greater than all children height, fall back on max parent height.
			}
			node.setNodeHeight(hl); // set new parent height

			// change lengths in children to reflect changes.
			for (int i = 0; i < node.getChildCount(); i++) {
				h = node.getChild(i).getNodeHeight();
				node.getChild(i).setBranchLength(hl - h);
			}
		}
	}


	/**
	 * sets this nodes height value to newHeight and all children's
	 * height values based on length of branches.
	 */
	private static void lengths2Heights(Node node, double newHeight) {

		if (!node.isRoot()) {
			newHeight -= node.getBranchLength();
			node.setNodeHeight(newHeight);
		} else {
			node.setNodeHeight(newHeight);
		}

		for (int i = 0; i < node.getChildCount(); i++) {
			lengths2Heights(node.getChild(i), newHeight);
		}
	}

	/**
	 * Exchange field info between two nodes. Specifically
	 * identifiers, branch lengths, node heights and branch length
	 * SEs.
	 */
	public static void exchangeInfo(Node node1, Node node2) {

		Identifier swaps;
		double swapd;

		swaps = node1.getIdentifier();
		node1.setIdentifier(node2.getIdentifier());
		node2.setIdentifier(swaps);

		swapd = node1.getBranchLength();
		node1.setBranchLength(node2.getBranchLength());
		node2.setBranchLength(swapd);

		swapd = node1.getNodeHeight();
		node1.setNodeHeight(node2.getNodeHeight());
		node2.setNodeHeight(swapd);

		swapd = node1.getBranchLengthSE();
		node1.setBranchLengthSE(node2.getBranchLengthSE());
		node2.setBranchLengthSE(swapd);
	}




	/**
	 * Get the distance to furthest leaf from this nodes parent.
	 */
	private static double getGreatestDistance(Node node) {

		double distance = 0.0;
		if (!node.isLeaf()) {
			if (!node.isRoot()) {
				distance = node.getBranchLength();
			}
			double max = getGreatestDistance(node.getChild(0));
			double posmax = 0.0;
			for (int i = 1; i < node.getChildCount(); i++) {
				posmax = getGreatestDistance(node.getChild(i));
				if (posmax > max) max = posmax;
			}
			distance += max;

					return distance;
		} else {
					return node.getBranchLength();
		}
	}

	/**
	 * Finds the largest child (in terms of node height).
	 */
	public static double findLargestChild(Node node) {
		// find child with largest height
		double max = node.getChild(0).getNodeHeight();
		for (int j = 1; j < node.getChildCount(); j++)
		{
			if (node.getChild(j).getNodeHeight() > max)
			{
				max = node.getChild(j).getNodeHeight();
			}
		}
		return max;
	}

	/**
	 * remove child
	 *
	 * @param node child node to be removed
	 */
	public static void removeChild(Node parent, Node child)
	{
		int rm = -1;
		for (int i = 0; i < parent.getChildCount(); i++)
		{
			if (child == parent.getChild(i))
			{
				rm = i;
				break;
			}
		}

		parent.removeChild(rm);
	}

	/**
	 * remove internal branch (collapse node with its parent)
	 *
	 * @param node node associated with internal branch
	 */
	public static void removeBranch(Node node)
	{
		if (node.isRoot() || node.isLeaf())
		{
			throw new IllegalArgumentException("INTERNAL NODE REQUIRED (NOT ROOT)");
		}

		Node parent = node.getParent();

		// add childs of node to parent
		// (node still contains the link to childs
		// to allow later restoration)
		int numChilds = node.getChildCount();
		for (int i = 0; i < numChilds; i++)
		{
			parent.addChild(node.getChild(i));
		}

		// remove node from parent
		// (link to parent is restored and the
		// position is stored)
		int rm = -1;
		for (int i = 0; i < parent.getChildCount(); i++)
		{
			if (node == parent.getChild(i))
			{
				rm = i;
				break;
			}
		}
		parent.removeChild(rm);
		node.setParent(parent);
		node.setNumber(rm);
	}

	/**
	 * restore internal branch
	 *
	 * @param node node associated with internal branch
	 */
	public static void restoreBranch(Node node)
	{
		if (node.isRoot() || node.isLeaf())
		{
			throw new IllegalArgumentException("INTERNAL NODE REQUIRED (NOT ROOT)");
		}

		Node parent = node.getParent();

		// remove childs of node from parent and make node their parent
		int numChilds = node.getChildCount();
		for (int i = 0; i < numChilds; i++)
		{
			Node c = node.getChild(i);
			removeChild(parent, c);
			c.setParent(node);
		}

		// insert node into parent
		parent.insertChild(node, node.getNumber());
	}



	/**
	 * join two childs, introducing a new node/branch in the tree
	 * that replaces the first child
	 *
	 * @param n1 number of first child
	 * @param n2 number of second child
	 */
	public static void joinChilds(Node node, int n1, int n2) {

		if (n1 == n2) {
			throw new IllegalArgumentException("CHILDREN MUST BE DIFFERENT");
		}

		int c1, c2;
		if (n2 < n1)
		{
			c1 = n2;
			c2 = n1;
		}
		else
		{
			c1 = n1;
			c2 = n2;
		}

		Node newNode = NodeFactory.createNode();

		Node child1 = node.getChild(c1);
		Node child2 = node.getChild(c2);

		node.setChild(c1, newNode);
		newNode.setParent(node);
		node.removeChild(c2); // now parent of child2 = null

		newNode.addChild(child1);
		newNode.addChild(child2);
	}

	/**
	 * determine preorder successor of this node
	 *
	 * @return next node
	 */
	public static Node preorderSuccessor(Node node) {

		Node next = null;

		if (node.isLeaf()) {
			Node cn = node, ln = null; // Current and last node

			// Go up
			do
			{
				if (cn.isRoot())
				{
					next = cn;
					break;
				}
				ln = cn;
				cn = cn.getParent();
			}
			while (cn.getChild(cn.getChildCount()-1) == ln);

			// Determine next node
			if (next == null)
			{
				// Go down one node
				for (int i = 0; i < cn.getChildCount()-1; i++)
				{
					if (cn.getChild(i) == ln)
					{
						next = cn.getChild(i+1);
						break;
					}
				}
			}
		}
		else
		{
			next = node.getChild(0);
		}

		return next;
	}

	/**
	 * determine postorder successor of a node
	 *
	 * @return next node
	 */
	public static Node postorderSuccessor(Node node) {

		Node cn = null;
		Node parent = node.getParent();

		if (node.isRoot())
		{
			cn = node;
		}
		else
		{

			// Go up one node
			if (parent.getChild(parent.getChildCount()-1) == node) {
				return parent;
			}
			// Go down one node
			for (int i = 0; i < parent.getChildCount()-1; i++)
			{
				if (parent.getChild(i) == node)
				{
					cn = parent.getChild(i+1);
					break;
				}
			}
		}

		// Go down until leaf
		while (cn.getChildCount() > 0)
		{

			cn = cn.getChild(0);
		}

		return cn;
	}




	/**
	 * Returns the first nodes in this tree that has the
	 * required identifiers.
	 * @return null if none of the identifiers names match nodes in tree, else return array which may have
	 *  null "blanks" for corresponding identifiers that do not match any node in the tree
	 */
	public static final Node[] findByIdentifier(Node node, String[] identifierNames) {
		Node[] nodes = new Node[identifierNames.length];
		boolean foundSomething = false;
		for(int i = 0 ; i < nodes.length ; i++) {
			nodes[i] = findByIdentifier(node,identifierNames[i]);
			foundSomething = foundSomething||(nodes[i]!=null);
		}
		if(!foundSomething) {
			return null;
		}
		return nodes;
	}
	/**
	 * Returns the first nodes in this tree that has the
	 * required identifiers.
	 */
	public static final Node[] findByIdentifier(Node node, Identifier[] identifiers) {
		Node[] nodes = new Node[identifiers.length];
		for(int i = 0 ; i < nodes.length ; i++) {
			nodes[i] = findByIdentifier(node,identifiers[i]);
		}
		return nodes;
	}
	/**
	 * Returns the first node in this tree that has the
	 * required identifier.
	 */
	public static final Node findByIdentifier(Node node, Identifier identifier) {
		return findByIdentifier(node,identifier.getName());
	}
	/**
	 * Returns the first node in this tree that has the
	 * required identifier.
	 */
	public static final Node findByIdentifier(Node node, String identifierName) {


		if (node.getIdentifier().getName().equals(identifierName)) {
			return node;
		} else {
			Node pos = null;
			for (int i = 0; i < node.getChildCount(); i++) {
				pos = findByIdentifier(node.getChild(i), identifierName);
				if (pos != null) return pos;
			}
		
			return pos;
		}
	}

	/**
	 * Root tree at this node.
	 */
	public static Node root(Node node) {

		if (!node.isRoot()) {

			Node myParent = node.getParent();
			removeChild(myParent, node);

			root(myParent);

			while (myParent.getChildCount() == 1) {
				myParent = myParent.getChild(0);
			}

			node.addChild(myParent);
			lengths2Heights(node);
		}
		return node;
	}

	/**
	 * Root the tree above the node with this identifier.
	 */
	public static Node rootAbove(Identifier id, Node root) {
		return rootAbove(findByIdentifier(root, id));
	}

	/**
	 * Root tree above this node;
	 */
	public static Node rootAbove(Node node) {

		if (!node.isRoot()) {

			Node root = NodeFactory.createNode();

			Node myParent = node.getParent();
			removeChild(myParent, node);

			root(myParent);
			
			while (myParent.getChildCount() == 1) {
				myParent = myParent.getChild(0);
			}

			root.addChild(myParent);
			root.addChild(node);

			lengths2Heights(root);

			return root;

		} else return node;
	}

	/**
	 * determine distance to root
	 *
	 * @return distance to root
	 */
	public static double getDistanceToRoot(Node node)
	{
		if (node.isRoot())
		{
			return 0.0;
		}
		else
		{
			return node.getBranchLength() + getDistanceToRoot(node.getParent());
		}
	}

	/**
	 * Return the number of terminal leaves below this node or 1 if this is
	 * a terminal leaf.
	 */
	public static int getLeafCount(Node node) {

		int count = 0;
		if (!node.isLeaf()) {
			for (int i = 0; i < node.getChildCount(); i++) {
				count += getLeafCount(node.getChild(i));
			}
		} else {
			count = 1;
		}
		return count;
	}
	/**
	 * For two nodes in the tree true if the first node is the ancestor of the second
	 *
	 * @param possibleAncestor the node that may be the ancestor of the other node
	 * @param node the node that may have the other node as it's ancestor
	 */
	public static boolean isAncestor(Node possibleAncestor, Node node) {
		if(node==possibleAncestor) {
			return true;
		}
		while(!node.isRoot()){
			node = node.getParent();
			if(node==possibleAncestor) {
				return true;
			}
		}
		return false;
	}

	/**
	 * For a set of nodes in the tree returns the common ancestor closest to all nodes (most recent common ancestor)
	 *
	 * @param nodes the nodes to check, is okay if array elements are null!
	 * @returns null if a at least one node is disjoint from the others nodes disjoint
	 */
	public static Node getFirstCommonAncestor(Node[] nodes) {
		Node currentCA = nodes[0];
		for(int i = 1; i < nodes.length ;i++) {
			if(currentCA!=null&&nodes[i]!=null) {
				currentCA = getFirstCommonAncestor(currentCA,nodes[i]);
				if(currentCA==null) {
					return null;
				}
			}
		}
		return currentCA;
	}
	/**
	 * For two nodes in the tree returns the common ancestor closest to both nodes (most recent common ancestor)
	 *
	 * @param nodeOne
	 * @param nodeTwo
	 * @returns null if two nodes disjoint (from different trees). May also return either nodeOne or nodeTwo if one node is an ancestor of the other
	 */
	public static Node getFirstCommonAncestor(Node nodeOne, Node nodeTwo) {
		if(isAncestor(nodeTwo, nodeOne)) {
			return nodeTwo;
		}
		if(isAncestor(nodeOne, nodeTwo)) {
			return nodeOne;
		}
		while(!nodeTwo.isRoot()) {
			nodeTwo = nodeTwo.getParent();
			if(isAncestor(nodeTwo, nodeOne)) {
				return nodeTwo;
			}
		}
		return null;
	}

		/** returns number of branches centered around an internal node in an unrooted tree */
	public static final int getUnrootedBranchCount(Node center) {
		if (center.isRoot()) 	{
			return center.getChildCount();
		}
		else {
			return center.getChildCount()+1;
		}
	}

	/** Attempts to remove the root of a tree by making it polyficating (as opposed to bificating).
	*/
	public static final Node getUnrooted(Node root) {
		if(!root.isRoot()) {
			return root; //Already unrooted
		}
		Node left = root.getChild(0);
		Node right = root.getChild(1);
		/*if(left.getChildCount()==1) {
			if(l
		} */
		if(left.getChildCount()>1) {
			return root(left);
		}
		if(right.getChildCount()>1) {
			return root(right);
		}
		return root; //Can't do much
	}
}