<commit_before>package beast.evolution.tree;

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import beast.core.Description;
import beast.core.Input;
import beast.core.Operator;
import beast.core.StateNode;
import beast.core.StateNodeInitialiser;
import beast.core.util.Log;
import beast.evolution.alignment.TaxonSet;
import beast.util.TreeParser;


@Description("Tree (the T in BEAST) representing gene beast.tree, species"
        + " beast.tree, language history, or other time-beast.tree"
        + " relationships among sequence data.")
public class Tree extends StateNode implements TreeInterface {
    final public Input<Tree> m_initial = new Input<>("initial", "tree to start with");
    final public Input<List<TraitSet>> m_traitList = new Input<>("trait",
            "trait information for initializing traits (like node dates) in the tree",
            new ArrayList<>());
    final public Input<TaxonSet> m_taxonset = new Input<>("taxonset",
            "set of taxa that correspond to the leafs in the tree");
    final public Input<String> nodeTypeInput = new Input<>("nodetype",
            "type of the nodes in the beast.tree", Node.class.getName());

    /**
     * state of dirtiness of a node in the tree
     * DIRTY means a property on the node has changed, but not the topology. "property" includes the node height
     *       and that branch length to its parent.
     * FILTHY means the nodes' parent or child has changed.
     */
    public static final int IS_CLEAN = 0, IS_DIRTY = 1, IS_FILTHY = 2;

    /**
     * counters of number of nodes, nodeCount = internalNodeCount + leafNodeCount *
     */
    protected int nodeCount = -1;
    protected int internalNodeCount = -1;
    protected int leafNodeCount = -1;

    /**
     * node representation of the beast.tree *
     */
    protected beast.evolution.tree.Node root;
    protected beast.evolution.tree.Node storedRoot;

    /**
     * array of all nodes in the tree *
     */
    protected Node[] m_nodes = null;

    protected Node[] m_storedNodes = null;

    /**
     * array of taxa names for the nodes in the tree
     * such that m_sTaxaNames[node.getNr()] == node.getID()*
     */
    String[] m_sTaxaNames = null;

    /**
     * Trait set which specifies leaf node times.
     */
    protected TraitSet timeTraitSet = null;

    /*
     * Whether or not TraitSets have been processed.
     */
    protected boolean traitsProcessed = false;

    @Override
    public void initAndValidate() {
        if (m_initial.get() != null && !(this instanceof StateNodeInitialiser)) {
        	throw new RuntimeException("initial-input should be specified for tree that is not a StateNodeInitialiser");
//            final Tree other = m_initial.get();
//            root = other.root.copy();
//            nodeCount = other.nodeCount;
//            internalNodeCount = other.internalNodeCount;
//            leafNodeCount = other.leafNodeCount;
        }

        if (nodeCount < 0) {
            if (m_taxonset.get() != null) {
                makeCaterpillar(0, 1, false);
            } else {
                // make dummy tree with a single root node
                root = newNode();
                root.labelNr = 0;
                root.height = 0;
                root.m_tree = this;
                nodeCount = 1;
                internalNodeCount = 0;
                leafNodeCount = 1;
            }
        }

        if (nodeCount >= 0) {
            initArrays();
        }

        processTraits(m_traitList.get());

        // Ensure tree is compatible with time trait.
        if (timeTraitSet != null)
            adjustTreeNodeHeights(root);
        
        // ensure all nodes have their taxon names set up
        String [] taxa = getTaxaNames();
        for (int i = 0; i < getNodeCount() && i < taxa.length; i++) {
        	if (taxa[i] != null)
        		m_nodes[i].setID(taxa[i]);
        }
    }

    public void makeCaterpillar(final double minInternalHeight, final double step, final boolean finalize) {
        // make a caterpillar
        final List<String> taxa = m_taxonset.get().asStringList();
        Node left = newNode();
        left.labelNr = 0;
        left.height = 0;
        left.setID(taxa.get(0));
        for (int i = 1; i < taxa.size(); i++) {
            final Node right = newNode();
            right.labelNr = i;
            right.height = 0;
            right.setID(taxa.get(i));
            final Node parent = newNode();
            parent.labelNr = taxa.size() + i - 1;
            parent.height = minInternalHeight + i * step;
            left.parent = parent;
            parent.setLeft(left);
            right.parent = parent;
            parent.setRight(right);
            left = parent;
        }
        root = left;
        leafNodeCount = taxa.size();
        nodeCount = leafNodeCount * 2 - 1;
        internalNodeCount = leafNodeCount - 1;

        if (finalize) {
            initArrays();
        }
    }

    /**
     * Process trait sets.
     *
     * @param traitList List of trait sets.
     */
    protected void processTraits(List<TraitSet> traitList) {
        for (TraitSet traitSet : traitList) {
            for (Node node : getExternalNodes()) {
            	String id = node.getID();
            	if (id != null) {
                    node.setMetaData(traitSet.getTraitName(), traitSet.getValue(id));
            	}
            }
            if (traitSet.isDateTrait())
                timeTraitSet = traitSet;
        }
        traitsProcessed = true;
    }

    /**
     * Overridable method to construct new node object of the specific type
     * defined by nodeTypeInput.
     *
     * @return new node object.
     */
    protected Node newNode() {
        try {
            return (Node) Class.forName(nodeTypeInput.get()).newInstance();
        } catch (Exception e) {
            throw new RuntimeException("Cannot create node of type "
                    + nodeTypeInput.get() + ": " + e.getMessage());
        }
        //return new NodeData();
    }

    protected void initArrays() {
        // initialise tree-as-array representation + its stored variant
        m_nodes = new Node[nodeCount];
        listNodes(root, m_nodes);
        m_storedNodes = new Node[nodeCount];
        final Node copy = root.copy();
        listNodes(copy, m_storedNodes);
    }


    public Tree() {
    }

    public Tree(final Node rootNode) {
        setRoot(rootNode);
        initArrays();
    }

    /**
     * Construct a tree from newick string -- will not automatically adjust tips to zero.
     */
    public Tree(final String newick) {
        this(new TreeParser(newick).getRoot());
    }

    /**
     * Ensure no negative branch lengths exist in tree.  This can occur if
     * leaf heights given as a trait are incompatible with the existing tree.
     */
    final static double EPSILON = 0.0000001;

    protected void adjustTreeNodeHeights(final Node node) {
        if (!node.isLeaf()) {
            for (final Node child : node.getChildren()) {
                adjustTreeNodeHeights(child);
            }
            for (final Node child : node.getChildren()) {
                final double minHeight = child.getHeight() + EPSILON;<commit_msg>Issue #570: post cache<commit_after>package beast.evolution.tree;

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import beast.core.Description;
import beast.core.Input;
import beast.core.Operator;
import beast.core.StateNode;
import beast.core.StateNodeInitialiser;
import beast.core.util.Log;
import beast.evolution.alignment.TaxonSet;
import beast.util.TreeParser;


@Description("Tree (the T in BEAST) representing gene beast.tree, species"
        + " beast.tree, language history, or other time-beast.tree"
        + " relationships among sequence data.")
public class Tree extends StateNode implements TreeInterface {
    final public Input<Tree> m_initial = new Input<>("initial", "tree to start with");
    final public Input<List<TraitSet>> m_traitList = new Input<>("trait",
            "trait information for initializing traits (like node dates) in the tree",
            new ArrayList<>());
    final public Input<TaxonSet> m_taxonset = new Input<>("taxonset",
            "set of taxa that correspond to the leafs in the tree");
    final public Input<String> nodeTypeInput = new Input<>("nodetype",
            "type of the nodes in the beast.tree", Node.class.getName());

    /**
     * state of dirtiness of a node in the tree
     * DIRTY means a property on the node has changed, but not the topology. "property" includes the node height
     *       and that branch length to its parent.
     * FILTHY means the nodes' parent or child has changed.
     */
    public static final int IS_CLEAN = 0, IS_DIRTY = 1, IS_FILTHY = 2;

    /**
     * counters of number of nodes, nodeCount = internalNodeCount + leafNodeCount *
     */
    protected int nodeCount = -1;
    protected int internalNodeCount = -1;
    protected int leafNodeCount = -1;

    /**
     * node representation of the beast.tree *
     */
    protected beast.evolution.tree.Node root;
    protected beast.evolution.tree.Node storedRoot;

    /**
     * array of all nodes in the tree *
     */
    protected Node[] m_nodes = null;

    protected Node[] m_storedNodes = null;

    /**
     * array of taxa names for the nodes in the tree
     * such that m_sTaxaNames[node.getNr()] == node.getID()*
     */
    String[] m_sTaxaNames = null;

    /**
     * Trait set which specifies leaf node times.
     */
    protected TraitSet timeTraitSet = null;

    /*
     * Whether or not TraitSets have been processed.
     */
    protected boolean traitsProcessed = false;

    @Override
    public void initAndValidate() {
        if (m_initial.get() != null && !(this instanceof StateNodeInitialiser)) {
        	throw new RuntimeException("initial-input should be specified for tree that is not a StateNodeInitialiser");
//            final Tree other = m_initial.get();
//            root = other.root.copy();
//            nodeCount = other.nodeCount;
//            internalNodeCount = other.internalNodeCount;
//            leafNodeCount = other.leafNodeCount;
        }

        if (nodeCount < 0) {
            if (m_taxonset.get() != null) {
                makeCaterpillar(0, 1, false);
            } else {
                // make dummy tree with a single root node
                root = newNode();
                root.labelNr = 0;
                root.height = 0;
                root.m_tree = this;
                nodeCount = 1;
                internalNodeCount = 0;
                leafNodeCount = 1;
            }
        }

        if (nodeCount >= 0) {
            initArrays();
        }

        processTraits(m_traitList.get());

        // Ensure tree is compatible with time trait.
        if (timeTraitSet != null)
            adjustTreeNodeHeights(root);
        
        // ensure all nodes have their taxon names set up
        String [] taxa = getTaxaNames();
        for (int i = 0; i < getNodeCount() && i < taxa.length; i++) {
        	if (taxa[i] != null)
        		m_nodes[i].setID(taxa[i]);
        }
    }

    public void makeCaterpillar(final double minInternalHeight, final double step, final boolean finalize) {
        // make a caterpillar
        final List<String> taxa = m_taxonset.get().asStringList();
        Node left = newNode();
        left.labelNr = 0;
        left.height = 0;
        left.setID(taxa.get(0));
        for (int i = 1; i < taxa.size(); i++) {
            final Node right = newNode();
            right.labelNr = i;
            right.height = 0;
            right.setID(taxa.get(i));
            final Node parent = newNode();
            parent.labelNr = taxa.size() + i - 1;
            parent.height = minInternalHeight + i * step;
            left.parent = parent;
            parent.setLeft(left);
            right.parent = parent;
            parent.setRight(right);
            left = parent;
        }
        root = left;
        leafNodeCount = taxa.size();
        nodeCount = leafNodeCount * 2 - 1;
        internalNodeCount = leafNodeCount - 1;

        if (finalize) {
            initArrays();
        }
    }

    /**
     * Process trait sets.
     *
     * @param traitList List of trait sets.
     */
    protected void processTraits(List<TraitSet> traitList) {
        for (TraitSet traitSet : traitList) {
            for (Node node : getExternalNodes()) {
            	String id = node.getID();
            	if (id != null) {
                    node.setMetaData(traitSet.getTraitName(), traitSet.getValue(id));
            	}
            }
            if (traitSet.isDateTrait())
                timeTraitSet = traitSet;
        }
        traitsProcessed = true;
    }

    /**
     * Overridable method to construct new node object of the specific type
     * defined by nodeTypeInput.
     *
     * @return new node object.
     */
    protected Node newNode() {
        try {
            return (Node) Class.forName(nodeTypeInput.get()).newInstance();
        } catch (Exception e) {
            throw new RuntimeException("Cannot create node of type "
                    + nodeTypeInput.get() + ": " + e.getMessage());
        }
        //return new NodeData();
    }

    protected void initArrays() {
        // initialise tree-as-array representation + its stored variant
        m_nodes = new Node[nodeCount];
        listNodes(root, m_nodes);
        m_storedNodes = new Node[nodeCount];
        final Node copy = root.copy();
        listNodes(copy, m_storedNodes);
        postCache = null;
    }


    public Tree() {
    }

    public Tree(final Node rootNode) {
        setRoot(rootNode);
        initArrays();
    }

    /**
     * Construct a tree from newick string -- will not automatically adjust tips to zero.
     */
    public Tree(final String newick) {
        this(new TreeParser(newick).getRoot());
    }

    /**
     * Ensure no negative branch lengths exist in tree.  This can occur if
     * leaf heights given as a trait are incompatible with the existing tree.
     */
    final static double EPSILON = 0.0000001;

    protected void adjustTreeNodeHeights(final Node node) {
        if (!node.isLeaf()) {
            for (final Node child : node.getChildren()) {
                adjustTreeNodeHeights(child);
            }
            for (final Node child : node.getChildren()) {
                final double minHeight = child.getHeight() + EPSILON;
{'fraction_non_alphanumeric': 0.10292205570382536, 'fraction_numerical': 0.004721823034284541, 'mean_word_length': 1.9879370271928032, 'pattern_counts': {'":': 2, '<': 35, '<?xml version=': 0, '>': 29, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6796107', 'n_tokens_mistral': 4166, 'n_tokens_neox': 4007, 'n_words': 1226}