import beast.evolution.tree.Node; //导入依赖的package包/类
private Node findNode(final TreeParser tree, final String[] targetArray) {
    final Node[] treeNodes = tree.getNodesAsArray();
    final Set<String> targetSet = new HashSet<>();
    for (int i = 0; i < targetArray.length; i++) {
        targetSet.add(targetArray[i]);
    }

    for (Node node: treeNodes) {
        Set<String> nodeSet = new HashSet<>();

        if (node.isLeaf()) {
            nodeSet.add(node.getID());
        } else {
            final List<Node> leafNodes = node.getAllLeafNodes();
            for (Node leaf: leafNodes) {
                nodeSet.add(leaf.getID());
            }
        }

        if (targetSet.equals(nodeSet)) {
            return node;
        }
    }

    return null;
}
 

import beast.evolution.tree.Node; //导入依赖的package包/类
@SuppressWarnings("unchecked")
public List<Node>[] deepCopyLineagesAdded() {
   	List<Node>[] newList = new List[intervalCount];
   	for (int i = 0; i < intervalCount; i++) {
   		if (lineagesAdded[i] != null) {
   			List<Node> nodeList = new ArrayList<>();
   			int nodeCount = lineagesAdded[i].size();
   			for (int n = 0; n < nodeCount; n++) {
   				nodeList.add(lineagesAdded[i].get(n).copy());
   			}
   			newList[i] = nodeList;
   		}
   	}
   	return newList;
   	
   }
 

import beast.evolution.tree.Node; //导入依赖的package包/类
@SuppressWarnings("unchecked")
public List<Node>[] deepCopyLineagesRemoved() {    	
   	List<Node>[] newList = new List[intervals.length];
   	for (int i = 0; i < intervalCount; i++) {
   		if (lineagesRemoved[i] != null) {
    		List<Node> nodeList = new ArrayList<>();
    		int nodeCount = lineagesRemoved[i].size();
    		for (int n = 0; n < nodeCount; n++) {
    			nodeList.add(lineagesRemoved[i].get(n).copy());
    		}
    		newList[i] = nodeList;
    		}
   	}
   	return newList;
   	
   }
 

import beast.evolution.tree.Node; //导入依赖的package包/类
public List<Integer> getCoalescentIndices(STreeIntervals intervals, int interval) {
	List<Node> coalLines = intervals.getLineagesRemoved(interval);
	if (coalLines.size() > 2) return null;
 	
   	if (coalLines.size() > 2) {
		throw new RuntimeException("Unsupported coalescent at non-binary node");
	}
	int childIdx1 = extantIndex[coalLines.get(0).getNr()];
	int childIdx2 = extantIndex[coalLines.get(1).getNr()];
	
	if (childIdx1 == -1 || childIdx2 == -1){
    	intervals.swap();
    	coalLines = intervals.getLineagesRemoved(interval);
    	childIdx1 = extantIndex[coalLines.get(0).getNr()];
    	childIdx2 = extantIndex[coalLines.get(1).getNr()];
	}
	List<Integer> result = new ArrayList<Integer>();
	result.add(childIdx1);  result.add(childIdx2);
	return result;
}
 

import beast.evolution.tree.Node; //导入依赖的package包/类
public List<DoubleMatrix> getCoalescentVectors(STreeIntervals intervals, int interval) {
	List<Node> coalLines = intervals.getLineagesRemoved(interval);
	//if (coalLines.size() > 2) return null;
 	
   	if (coalLines.size() > 2) {
		throw new RuntimeException("Unsupported coalescent at non-binary node");
	}
	int childIdx1 = extantIndex[coalLines.get(0).getNr()];
	int childIdx2 = extantIndex[coalLines.get(1).getNr()];
	
	// if swap was already performed, this check is not needed
	if (childIdx1 == -1 || childIdx2 == -1){
    	intervals.swap();
    	coalLines = intervals.getLineagesRemoved(interval);
    	childIdx1 = extantIndex[coalLines.get(0).getNr()];
    	childIdx2 = extantIndex[coalLines.get(1).getNr()];
	}
	List<DoubleMatrix> result = new ArrayList<DoubleMatrix>();
	DoubleMatrix pvec1, pvec2;		
	pvec1 = this.getStateProbsFromIndex(childIdx1);
	pvec2 = this.getStateProbsFromIndex(childIdx2);
			
	result.add(pvec1);  result.add(pvec2);
	
	return result;		
}
 

import beast.evolution.tree.Node; //导入依赖的package包/类
/**
 * log this sample for current state to PrintStream,
 * e.g. value of a parameter, list of parameters or Newick tree
 *
 * @param nSample chain sample number
 * @param out     log stream
 */
public void log(int nSample, PrintStream out) {
	out.print(nSample+"\t");
	Tree tree = (Tree)treeInput.get().getCurrent();
	Node root = tree.getRoot();
	StateProbabilities sp = densityInput.get().getStateProbabilities();
	DoubleMatrix probs = sp.getStateProbs(root.getNr());
	if (probs != null) {
		for(int i=0; i < numStates; i++)
			out.print(probs.get(i)+"\t");
	} else {
		for(int i=0; i < numStates; i++)
			out.print(0.00+"\t");
	}
	// out.println("");
}
 

import beast.evolution.tree.Node; //导入依赖的package包/类
public Tree mutateOverTree(Tree base) throws Exception {
	ArrayList<Node> currParents = new ArrayList<Node>();
	ArrayList<Node> newParents = new ArrayList<Node>();
	currParents.add(base.getRoot());
	while (currParents.size() > 0) {
		for (Node parent : currParents) {
			List<Node> children = parent.getChildren();
			for (Node child : children) {
				double T = Math.abs(child.getHeight() - parent.getHeight());
				Sequence parentLang = getSequence(parent);
				Sequence newLang = mutateLang(parentLang, T);
				child.setMetaData("lang", newLang);
				newParents.add(child);
				addEmptyTrait(base, child);
			}
		}
		currParents = new ArrayList<Node>(newParents);
		newParents = new ArrayList<Node>();
	}
	return base;
}
 

import beast.evolution.tree.Node; //导入依赖的package包/类
protected void addEmptyTrait(Tree t, Node newLangNode) throws Exception {
	// Get all nodes in two lists.
	List<Node> children = newLangNode.getAllChildNodes();
	// Find nodes that aren't children (or trait lang).
	List<Node> allNodes = t.getInternalNodes();
	allNodes.addAll(t.getExternalNodes());
	allNodes.removeAll(children);
	allNodes.remove(newLangNode);

	// Calculate number of [new] mutations in new language.
	Sequence newLang = getSequence(newLangNode);
	for (Node n : allNodes) {
		Sequence nLang = getSequence(n);
		String s = nLang.getData();
		Sequence newNodeLang = new Sequence("", s);
		while (newNodeLang.getData().length() < newLang.getData().length()) {
			String sNew = newNodeLang.getData() + '0';
			// System.out.println(newNodeLang);
			newNodeLang.dataInput.setValue(sNew, this);
		}
		n.setMetaData("lang", newNodeLang);
	}
}
 

import beast.evolution.tree.Node; //导入依赖的package包/类
protected boolean localDist(Node L1, Node L2) {
	// If z is 0, global borrowing is in effect.
	if (borrowZ == 0.0) {
		return true;
	}
	Node parent1, parent2;
	Double dist1 = 0.0, dist2 = 0.0;
	while (dist1 <= borrowZ && dist2 <= borrowZ) {
		parent1 = L1.getParent();
		parent2 = L1.getParent();

		// If it's the same ancestor, return true.
		if (parent1.equals(parent2)) {
			return true;
		}

		// Reduce height: leaves -> root.
		dist1 = Math.abs(L1.getHeight() - parent1.getHeight());
		dist2 = Math.abs(L2.getHeight() - parent2.getHeight());

		L1 = parent1;
		L2 = parent2;
	}
	return false;
}
 

import beast.evolution.tree.Node; //导入依赖的package包/类
protected Double[] getEvents(Tree tr) {
	Node[] nodes = tr.getNodesAsArray();
	Double[] events = new Double[nodes.length];
	for (int i = 0; i < nodes.length; i++) {
		events[i] = nodes[i].getHeight();
	}
	Arrays.sort(events, Collections.reverseOrder());
	return events;
}
 

import beast.evolution.tree.Node; //导入依赖的package包/类
public Tree mutateOverTree(Tree base) throws Exception {
	ArrayList<Node> currParents = new ArrayList<Node>();
	ArrayList<Node> newParents = new ArrayList<Node>();
	currParents.add(base.getRoot());
	while (currParents.size() > 0) {
		for (Node parent : currParents) {
			List<Node> children = parent.getChildren();
			for (Node child : children) {
				double T = Math.abs(child.getHeight() - parent.getHeight());
				Sequence parentLang = getSequence(parent);
				Sequence newLang = mutateLang(parentLang, T);
				child.setMetaData("lang", newLang);
				newParents.add(child);
			}
		}
		currParents = new ArrayList<Node>(newParents);
		newParents = new ArrayList<Node>();
	}
	return base;
}
 

import beast.evolution.tree.Node; //导入依赖的package包/类
private static List<Node> getConstraintNodes (Tree tree, double minConstraintHeight) {
	List<Node> constraintNodes = new ArrayList<Node>();
	List<Node> possibleConstraintNodes = new ArrayList<Node>();
	for (Node n : tree.getNodesAsArray()) {
		if (n.getHeight() < minConstraintHeight) {
			continue;
		}
		List<Node> c2Children = n.getAllChildNodes();
		for (Node c1 : possibleConstraintNodes) {
			List<Node> c1Children = c1.getAllChildNodes();
			if (Collections.disjoint(c1Children, c2Children)) {
				constraintNodes.add(n);
				constraintNodes.add(c1);
				break;
			}
		}
		if (!constraintNodes.isEmpty()) {
			break;
		}
		possibleConstraintNodes.add(n);
	}
	return constraintNodes;
}
 

import beast.evolution.tree.Node; //导入依赖的package包/类
private static void TreeSDBorrowingTest(String seq) throws Exception {
	seq = "";
	for (int j = 0; j < 5; j++) {
		seq += '1';
	}
	Sequence l = new Sequence("", seq);

	ExplicitBinaryStochasticDollo sd_mod = new ExplicitBinaryStochasticDollo(0.1, 0.2, 0.0, 0.0,
			false);

	System.out.println("Tree SD Borrowing Test");
	Tree tree = randomYuleTree(2, 0.01);
	tree.getRoot().setMetaData("lang", l);
	sd_mod.mutateOverTreeBorrowing(tree);
	for (Node n : tree.getExternalNodes()) {
		Sequence l2 = (Sequence) n.getMetaData("lang");
		System.out.println(l2.getData());
	}
}
 

import beast.evolution.tree.Node; //导入依赖的package包/类
private static void NoEmptyTraitTest() throws Exception {
	for (int i = 0; i < 1; i++) {
		System.out.println(i);
		Sequence l = new Sequence("", "00000000000001");
		Tree tree = randomYuleTree(3, 0.06);
		tree.getRoot().setMetaData("lang", l);
		ExplicitBinaryStochasticDollo sd_mod = new ExplicitBinaryStochasticDollo(0.0, 0.5, 0.0, 0.0, true);
		tree = sd_mod.mutateOverTree(tree);

		for (Node n : tree.getExternalNodes()) {
			Sequence l2 = (Sequence) n.getMetaData("lang");
			System.out.println(l2.getData());
		}

	}
}
 

import beast.evolution.tree.Node; //导入依赖的package包/类
private static void GTRTreeValidation() throws Exception {
	ArrayList<Integer> births = new ArrayList<Integer>();
	for (int i = 0; i < 10000; i++) {
		System.out.println(i);
		ExplicitBinaryGTR gtr_mod = new ExplicitBinaryGTR(0.5, 0.0, 0.0, false);
		String seq = "";
		for (int j = 0; j < 20; j++) {
			seq += Integer.toString(Randomizer.nextInt(2));
		}
		Sequence l = new Sequence("", seq);
		Tree tree = randomYuleTree(8, 0.001);
		tree.getRoot().setMetaData("lang", l);
		tree = gtr_mod.mutateOverTree(tree);
		for (Node n : tree.getExternalNodes()) {
			Sequence l2 = (Sequence) n.getMetaData("lang");
			births.add(LanguageSubsitutionModel.getBirths(l2));
		}

	}
	listToCSV(births, "Utilities/Thesis Graph Generation/gtrtree.csv");
}
 

import beast.evolution.tree.Node; //导入依赖的package包/类
private static void SDTreeValidation() throws Exception {
	ArrayList<Integer> births = new ArrayList<Integer>();

	for (int i = 0; i < 10000; i++) {
		System.out.println(i);
		ExplicitBinaryStochasticDollo sd_mod = new ExplicitBinaryStochasticDollo(0.5, 0.5, 0.0, 0.0, false);
		String seq = "";
		Sequence l = new Sequence("", seq);
		Tree tree = randomYuleTree(8, 0.01);
		tree.getRoot().setMetaData("lang", l);
		tree = sd_mod.mutateOverTreeBorrowing(tree);
		for (Node n : tree.getExternalNodes()) {
			Sequence l2 = (Sequence) n.getMetaData("lang");
			births.add(LanguageSubsitutionModel.getBirths(l2));
		}
	}
	listToCSV(births, "Utilities/Thesis Graph Generation/sdtree.csv");
}
 

import beast.evolution.tree.Node; //导入依赖的package包/类
@Override
public double branchLogP(int speciesTreeNodeNumber, Node speciesTreeNode, double ploidy, double[] branchCoalescentTimes, int branchLineageCount, int branchEventCount) {
    final RealParameter tipPopSizes = tipPopSizesInput.get();
    final RealParameter topPopSizes = topPopSizesInput.get();

    double branchTipPopSize;
    if (speciesTreeNode.isLeaf()) {
        branchTipPopSize = tipPopSizes.getValue(speciesTreeNodeNumber);
    } else {
        final int leftChildTopI = speciesTreeNode.getLeft().getNr();
        final int rightChildTopI = speciesTreeNode.getRight().getNr();
        branchTipPopSize = topPopSizes.getValue(leftChildTopI) + topPopSizes.getValue(rightChildTopI);
    }

    if (speciesTreeNode.isRoot()) {
        return ConstantPopulations.constantLogP(branchTipPopSize, ploidy, branchCoalescentTimes, branchLineageCount, branchEventCount);
    } else {
        final int speciesTopI = speciesTreeNodeNumber;
        final double branchTopPopSize = topPopSizes.getValue(speciesTopI);
        return linearLogP(branchTopPopSize, branchTipPopSize, ploidy, branchCoalescentTimes, branchLineageCount, branchEventCount);
    }
}
 

import beast.evolution.tree.Node; //导入依赖的package包/类
@Override
public void serialize(Node speciesTreeNode, StringBuffer buf, DecimalFormat df) {
    final RealParameter tipPopSizes = tipPopSizesInput.get();
    final RealParameter topPopSizes = topPopSizesInput.get();
    final int speciesTreeNodeNumber = speciesTreeNode.getNr();

    double branchTipPopSize;
    if (speciesTreeNode.isLeaf()) {
        branchTipPopSize = tipPopSizes.getValue(speciesTreeNodeNumber);
    } else {
        final int leftChildTopI = speciesTreeNode.getLeft().getNr();
        final int rightChildTopI = speciesTreeNode.getRight().getNr();
        branchTipPopSize = topPopSizes.getValue(leftChildTopI) + topPopSizes.getValue(rightChildTopI);
    }

    final double branchTopPopSize = (speciesTreeNode.isRoot()) ? branchTipPopSize : topPopSizes.getValue(speciesTreeNode.getNr());

    if (df == null) buf.append("dmv={" + branchTopPopSize + "," + branchTipPopSize + "}");
    else buf.append("dmv={" + df.format(branchTopPopSize) + "," + df.format(branchTipPopSize) + "}");
}
 

import beast.evolution.tree.Node; //导入依赖的package包/类
private SetMultimap<Integer, Node> getConnectingNodes(Node speciesTreeNode, MinimumDouble tipwardFreedom) {
    final Node leftChildNode = speciesTreeNode.getLeft();
    final Node rightChildNode = speciesTreeNode.getRight();
    final int leftChildNodeNumber = leftChildNode.getNr();
    final int rightChildNodeNumber = rightChildNode.getNr();
    final Set<String> leftChildDescendants = findDescendants(leftChildNode, leftChildNodeNumber);
    final Set<String> rightChildDescendants = findDescendants(rightChildNode, rightChildNodeNumber);

    final SetMultimap<Integer, Node> allConnectingNodes = HashMultimap.create();
    final List<Tree> geneTrees = geneTreeInput.get();
    for (int j = 0; j < nGeneTrees; j++) {
        final Tree geneTree = geneTrees.get(j);
        final Node geneTreeRootNode = geneTree.getRoot();
        final Set<Node> jConnectingNodes = new HashSet<Node>();
        findConnectingNodes(geneTreeRootNode, jConnectingNodes, leftChildDescendants, rightChildDescendants, tipwardFreedom);
        allConnectingNodes.putAll(j, jConnectingNodes);
        geneTree.startEditing(null); // hack to stop beast.core.State.Trie memory leak
    }

    return allConnectingNodes;
}
 

import beast.evolution.tree.Node; //导入依赖的package包/类
protected static boolean checkTreeSanity(Node node) {
    final double nodeHeight = node.getHeight();
    final List<Node> children = node.getChildren();
    assert children.size() == 2;

    for (Node childNode: children) {
        final double childHeight = childNode.getHeight();
        assert childNode.getParent() == node;

        if (childNode.isLeaf()) {
            // direct ancestor branches have zero height
            // so equal height allowed in this case
            assert childHeight <= nodeHeight;
        } else{
            if (childHeight >= nodeHeight) {
                System.out.println(node.toNewick());
            }
            assert childHeight < nodeHeight;
            checkTreeSanity(childNode);
        }
    }

    return true;
}