X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=forester%2Fjava%2Fsrc%2Forg%2Fforester%2Fphylogeny%2FPhylogeny.java;h=0416f41472ecfe90c55a4097c1ec6e55fc242304;hb=03e7c823c2f9f2b9766bf486a164a8eec69d5214;hp=42470baf3c75c5b37651a5e3d3f868cdde6f8f36;hpb=b27e63e1badc730396c24ec7666e2d9e2628e2e9;p=jalview.git diff --git a/forester/java/src/org/forester/phylogeny/Phylogeny.java b/forester/java/src/org/forester/phylogeny/Phylogeny.java index 42470ba..0416f41 100644 --- a/forester/java/src/org/forester/phylogeny/Phylogeny.java +++ b/forester/java/src/org/forester/phylogeny/Phylogeny.java @@ -23,7 +23,7 @@ // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA // // Contact: phylosoft @ gmail . com -// WWW: www.phylosoft.org/forester +// WWW: https://sites.google.com/site/cmzmasek/home/software/forester package org.forester.phylogeny; @@ -37,9 +37,12 @@ import java.util.List; import java.util.Map; import java.util.NoSuchElementException; import java.util.Vector; +import java.util.regex.Matcher; +import java.util.regex.Pattern; +import org.forester.io.parsers.nhx.NHXParser; import org.forester.io.writers.PhylogenyWriter; -import org.forester.phylogeny.PhylogenyNodeI.NH_CONVERSION_SUPPORT_VALUE_STYLE; +import org.forester.phylogeny.PhylogenyNode.NH_CONVERSION_SUPPORT_VALUE_STYLE; import org.forester.phylogeny.data.BranchData; import org.forester.phylogeny.data.Confidence; import org.forester.phylogeny.data.Identifier; @@ -47,6 +50,8 @@ import org.forester.phylogeny.data.PhylogenyDataUtil; import org.forester.phylogeny.data.Sequence; import org.forester.phylogeny.data.SequenceRelation; import org.forester.phylogeny.data.SequenceRelation.SEQUENCE_RELATION_TYPE; +import org.forester.phylogeny.factories.ParserBasedPhylogenyFactory; +import org.forester.phylogeny.factories.PhylogenyFactory; import org.forester.phylogeny.iterators.ExternalForwardIterator; import org.forester.phylogeny.iterators.LevelOrderTreeIterator; import org.forester.phylogeny.iterators.PhylogenyNodeIterator; @@ -68,7 +73,7 @@ public class Phylogeny { private Confidence _confidence; private Identifier _identifier; private boolean _rerootable; - private HashMap _idhash; + private HashMap _id_to_node_map; private List _external_nodes_set; private Collection _sequenceRelationQueries; private Collection _relevant_sequence_relation_types; @@ -83,7 +88,7 @@ public class Phylogeny { /** * Adds this Phylogeny to the list of child nodes of PhylogenyNode parent * and sets the parent of this to parent. - * + * * @param n * the PhylogenyNode to add */ @@ -113,8 +118,8 @@ public class Phylogeny { new_node.setParent( sibling_parent ); sibling.setParent( new_node ); sibling_parent.setChildNode( sibling_index, new_node ); - final double new_dist = sibling.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ? PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT - : sibling.getDistanceToParent() / 2; + final double new_dist = sibling.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT + ? PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT : sibling.getDistanceToParent() / 2; new_node.setDistanceToParent( new_dist ); sibling.setDistanceToParent( new_dist ); externalNodesHaveChanged(); @@ -123,27 +128,31 @@ public class Phylogeny { /** * This calculates the height of the subtree emanating at n for rooted, * tree-shaped phylogenies - * + * * @param n * the root-node of a subtree * @return the height of the subtree emanating at n */ - public double calculateSubtreeHeight( final PhylogenyNode n ) { - if ( n.isExternal() || n.isCollapse() ) { - return ForesterUtil.isLargerOrEqualToZero( n.getDistanceToParent() ); + public double calculateSubtreeHeight( final PhylogenyNode n, final boolean take_collapse_into_account ) { + if ( n.isExternal() || ( take_collapse_into_account && n.isCollapse() ) ) { + return n.getDistanceToParent() > 0 ? n.getDistanceToParent() : 0; } else { double max = -Double.MAX_VALUE; for( int i = 0; i < n.getNumberOfDescendants(); ++i ) { - final double l = calculateSubtreeHeight( n.getChildNode( i ) ); + final double l = calculateSubtreeHeight( n.getChildNode( i ), take_collapse_into_account ); if ( l > max ) { max = l; } } - return max + ForesterUtil.isLargerOrEqualToZero( n.getDistanceToParent() ); + return max + ( n.getDistanceToParent() > 0 ? n.getDistanceToParent() : 0 ); } } + public void clearHashIdToNodeMap() { + setIdToNodeMap( null ); + } + /** * Returns a deep copy of this Phylogeny. *

@@ -155,76 +164,76 @@ public class Phylogeny { } /** - * Returns a shallow copy of this Phylogeny. + * Returns a deep copy of this Phylogeny. *

* (The resulting Phylogeny has its references in the external nodes * corrected, if they are lacking/obsolete in this.) */ - public Phylogeny copyShallow() { - return copyShallow( _root ); - } - - public Phylogeny copyShallow( final PhylogenyNode source ) { + public Phylogeny copy( final PhylogenyNode source ) { final Phylogeny tree = new Phylogeny(); if ( isEmpty() ) { tree.init(); return tree; } tree._rooted = _rooted; - tree._name = _name; - tree._description = _description; - tree._type = _type; + tree._name = new String( _name ); + tree._description = new String( _description ); + tree._type = new String( _type ); tree._rerootable = _rerootable; - tree._distance_unit = _distance_unit; - tree._confidence = _confidence; - tree._identifier = _identifier; + tree._distance_unit = new String( _distance_unit ); + if ( _confidence != null ) { + tree._confidence = ( Confidence ) _confidence.copy(); + } + if ( _identifier != null ) { + tree._identifier = ( Identifier ) _identifier.copy(); + } tree.setAllowMultipleParents( isAllowMultipleParents() ); - tree._root = PhylogenyMethods.copySubTreeShallow( source ); + tree._root = PhylogenyMethods.copySubTree( source ); return tree; } /** - * Returns a deep copy of this Phylogeny. + * Returns a shallow copy of this Phylogeny. *

* (The resulting Phylogeny has its references in the external nodes * corrected, if they are lacking/obsolete in this.) */ - public Phylogeny copy( final PhylogenyNode source ) { + public Phylogeny copyShallow() { + return copyShallow( _root ); + } + + public Phylogeny copyShallow( final PhylogenyNode source ) { final Phylogeny tree = new Phylogeny(); if ( isEmpty() ) { tree.init(); return tree; } tree._rooted = _rooted; - tree._name = new String( _name ); - tree._description = new String( _description ); - tree._type = new String( _type ); + tree._name = _name; + tree._description = _description; + tree._type = _type; tree._rerootable = _rerootable; - tree._distance_unit = new String( _distance_unit ); - if ( _confidence != null ) { - tree._confidence = ( Confidence ) _confidence.copy(); - } - if ( _identifier != null ) { - tree._identifier = ( Identifier ) _identifier.copy(); - } + tree._distance_unit = _distance_unit; + tree._confidence = _confidence; + tree._identifier = _identifier; tree.setAllowMultipleParents( isAllowMultipleParents() ); - tree._root = PhylogenyMethods.copySubTree( source ); + tree._root = PhylogenyMethods.copySubTreeShallow( source ); return tree; } /** - * Need the delete and/or rehash _idhash (not done automatically + * Need to call clearHashIdToNodeMap() afterwards (not done automatically * to allow client multiple deletions in linear time). - * Need to call 'recalculateNumberOfExternalDescendants(boolean)' after this + * Need to call 'recalculateNumberOfExternalDescendants(boolean)' after this * if tree is to be displayed. - * + * * @param remove_us the parent node of the subtree to be deleted */ public void deleteSubtree( final PhylogenyNode remove_us, final boolean collapse_resulting_node_with_one_desc ) { - if ( isEmpty() || ( remove_us.isRoot() && getNumberOfExternalNodes() != 1 ) ) { + if ( isEmpty() || ( remove_us.isRoot() && ( getNumberOfExternalNodes() != 1 ) ) ) { return; } - if ( remove_us.isRoot() && getNumberOfExternalNodes() == 1 ) { + if ( remove_us.isRoot() && ( getNumberOfExternalNodes() == 1 ) ) { init(); } else if ( !collapse_resulting_node_with_one_desc ) { @@ -253,13 +262,17 @@ public class Phylogeny { if ( p.getNumberOfDescendants() == 2 ) { final int pi = p.getChildNodeIndex(); if ( removed_node.isFirstChildNode() ) { - p.getChildNode( 1 ).setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p - .getDistanceToParent(), p.getChildNode( 1 ).getDistanceToParent() ) ); + p.getChildNode( 1 ) + .setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p.getDistanceToParent(), + p.getChildNode( 1 ) + .getDistanceToParent() ) ); pp.setChildNode( pi, p.getChildNode( 1 ) ); } else { - p.getChildNode( 0 ).setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p - .getDistanceToParent(), p.getChildNode( 0 ).getDistanceToParent() ) ); + p.getChildNode( 0 ) + .setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p.getDistanceToParent(), + p.getChildNode( 0 ) + .getDistanceToParent() ) ); pp.setChildNode( pi, p.getChildNode( 0 ) ); } } @@ -269,7 +282,6 @@ public class Phylogeny { } } remove_us.removeConnections(); - setIdHash( null ); externalNodesHaveChanged(); } @@ -301,16 +313,21 @@ public class Phylogeny { return _distance_unit; } + public final static Phylogeny createInstanceFromNhxString( final String nhx ) throws IOException { + final PhylogenyFactory factory = ParserBasedPhylogenyFactory.getInstance(); + return factory.create( nhx, new NHXParser() )[ 0 ]; + } + /** - * + * * Warning. The order of the returned nodes is random * -- and hence cannot be relied on. - * + * * @return Unordered set of PhylogenyNode */ public List getExternalNodes() { if ( _external_nodes_set == null ) { - _external_nodes_set = new ArrayList(); + _external_nodes_set = new ArrayList<>(); for( final PhylogenyNodeIterator it = iteratorPostorder(); it.hasNext(); ) { final PhylogenyNode n = it.next(); if ( n.isExternal() ) { @@ -322,28 +339,6 @@ public class Phylogeny { } /** - * Returns the number of duplications of this Phylogeny (int). A return - * value of -1 indicates that the number of duplications is unknown. - */ - // public int getNumberOfDuplications() { - // return _number_of_duplications; - // } // getNumberOfDuplications() - /** - * Sets the number of duplications of this Phylogeny (int). A value of -1 - * indicates that the number of duplications is unknown. - * - * @param clean_nh - * set to true for clean NH format - */ - // public void setNumberOfDuplications( int i ) { - // if ( i < 0 ) { - // _number_of_duplications = -1; - // } - // else { - // _number_of_duplications = i; - // } - // } // setNumberOfDuplications( int ) - /** * Returns the first external PhylogenyNode. */ public PhylogenyNode getFirstExternalNode() { @@ -359,30 +354,21 @@ public class Phylogeny { /** * This calculates the height for rooted, tree-shaped phylogenies. The - * height is the longest distance from the root to an external node. Please - * note. Child nodes of collapsed nodes are ignored -- which is useful for - * display purposes but might be misleading for other applications. - * + * height is the longest distance from the root to an external node. + * * @return the height for rooted, tree-shaped phylogenies */ - public double getHeight() { + public double calculateHeight( final boolean take_collapse_into_account ) { if ( isEmpty() ) { return 0.0; } - return calculateSubtreeHeight( getRoot() ); + return calculateSubtreeHeight( getRoot(), take_collapse_into_account ); } public Identifier getIdentifier() { return _identifier; } - // --------------------------------------------------------- - // Modification of Phylogeny topology and Phylogeny appearance - // --------------------------------------------------------- - private HashMap getIdHash() { - return _idhash; - } - /** * Returns the name of this Phylogeny. */ @@ -392,35 +378,22 @@ public class Phylogeny { /** * Finds the PhylogenyNode of this Phylogeny which has a matching ID number. - * Takes O(n) time. After method hashIDs() has been called it runs in - * constant time. - * - * @param id - * ID number (int) of the PhylogenyNode to find * @return PhylogenyNode with matching ID, null if not found */ - public PhylogenyNode getNode( final int id ) throws NoSuchElementException { + public PhylogenyNode getNode( final long id ) throws NoSuchElementException { if ( isEmpty() ) { throw new NoSuchElementException( "attempt to get node in an empty phylogeny" ); } - if ( _idhash != null ) { - return _idhash.get( id ); + if ( ( getIdToNodeMap() == null ) || getIdToNodeMap().isEmpty() ) { + reHashIdToNodeMap(); } - else { - for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { - final PhylogenyNode node = iter.next(); - if ( node.getId() == id ) { - return node; - } - } - } - return null; + return getIdToNodeMap().get( id ); } /** * Returns a PhylogenyNode of this Phylogeny which has a matching name. * Throws an Exception if seqname is not present in this or not unique. - * + * * @param name * name (String) of PhylogenyNode to find * @return PhylogenyNode with matchin name @@ -431,38 +404,33 @@ public class Phylogeny { } final List nodes = getNodes( name ); if ( ( nodes == null ) || ( nodes.size() < 1 ) ) { - throw new IllegalArgumentException( "node named [" + name + "] not found" ); + throw new IllegalArgumentException( "node named \"" + name + "\" not found" ); } if ( nodes.size() > 1 ) { - throw new IllegalArgumentException( "node named [" + name + "] not unique" ); + throw new IllegalArgumentException( "node named \"" + name + "\" not unique" ); } return nodes.get( 0 ); } /** - * Return Node by TaxonomyId Olivier CHABROL : - * olivier.chabrol@univ-provence.fr - * - * @param taxonomyID - * search taxonomy identifier - * @param nodes - * sublist node to search - * @return List node with the same taxonomy identifier + * This is time-inefficient since it runs a iterator each time it is called. + * */ - private List getNodeByTaxonomyID( final String taxonomyID, final List nodes ) { - final List retour = new ArrayList(); - for( final PhylogenyNode node : nodes ) { - if ( taxonomyID.equals( PhylogenyMethods.getTaxonomyIdentifier( node ) ) ) { - retour.add( node ); - } + public int getNodeCount() { + if ( isEmpty() ) { + return 0; } - return retour; + int c = 0; + for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); it.next() ) { + ++c; + } + return c; } /** * Returns a List with references to all Nodes of this Phylogeny which have * a matching name. - * + * * @param name * name (String) of Nodes to find * @return Vector of references to Nodes of this Phylogeny with matching @@ -473,7 +441,7 @@ public class Phylogeny { if ( isEmpty() ) { return null; } - final List nodes = new ArrayList(); + final List nodes = new ArrayList<>(); for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { final PhylogenyNode n = iter.next(); if ( n.getName().equals( name ) ) { @@ -483,11 +451,28 @@ public class Phylogeny { return nodes; } + public List getNodes( final Pattern p ) { + if ( isEmpty() ) { + return null; + } + final List nodes = new ArrayList<>(); + for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { + final PhylogenyNode n = iter.next(); + if ( n.getName() != null ) { + final Matcher m = p.matcher( n.getName() ); + if ( m.find() ) { + nodes.add( n ); + } + } + } + return nodes; + } + public List getNodesViaSequenceName( final String seq_name ) { if ( isEmpty() ) { return null; } - final List nodes = new ArrayList(); + final List nodes = new ArrayList<>(); for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { final PhylogenyNode n = iter.next(); if ( n.getNodeData().isHasSequence() && n.getNodeData().getSequence().getName().equals( seq_name ) ) { @@ -497,11 +482,39 @@ public class Phylogeny { return nodes; } + public List getNodesViaSequenceSymbol( final String seq_name ) { + if ( isEmpty() ) { + return null; + } + final List nodes = new ArrayList<>(); + for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { + final PhylogenyNode n = iter.next(); + if ( n.getNodeData().isHasSequence() && n.getNodeData().getSequence().getSymbol().equals( seq_name ) ) { + nodes.add( n ); + } + } + return nodes; + } + + public List getNodesViaGeneName( final String seq_name ) { + if ( isEmpty() ) { + return null; + } + final List nodes = new ArrayList<>(); + for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { + final PhylogenyNode n = iter.next(); + if ( n.getNodeData().isHasSequence() && n.getNodeData().getSequence().getGeneName().equals( seq_name ) ) { + nodes.add( n ); + } + } + return nodes; + } + public List getNodesViaTaxonomyCode( final String taxonomy_code ) { if ( isEmpty() ) { return null; } - final List nodes = new ArrayList(); + final List nodes = new ArrayList<>(); for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { final PhylogenyNode n = iter.next(); if ( n.getNodeData().isHasTaxonomy() @@ -515,7 +528,7 @@ public class Phylogeny { /** * Returns a Vector with references to all Nodes of this Phylogeny which * have a matching species name. - * + * * @param specname * species name (String) of Nodes to find * @return Vector of references to Nodes of this Phylogeny with matching @@ -526,7 +539,7 @@ public class Phylogeny { if ( isEmpty() ) { return null; } - final List nodes = new ArrayList(); + final List nodes = new ArrayList<>(); for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { final PhylogenyNode n = iter.next(); if ( PhylogenyMethods.getSpecies( n ).equals( specname ) ) { @@ -564,28 +577,29 @@ public class Phylogeny { return nodes.get( 0 ); } - /** - * This is time-inefficient since it runs a iterator each time it is called. - * - */ - public int getNodeCount() { + public int getNumberOfBranches() { if ( isEmpty() ) { return 0; } int c = 0; - for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); it.next() ) { + for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); iter.next() ) { ++c; } + if ( !isRooted() ) { + --c; + } return c; } - public int getNumberOfBranches() { + public int getNumberOfInternalNodes() { if ( isEmpty() ) { return 0; } int c = 0; - for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); iter.next() ) { - ++c; + for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { + if ( iter.next().isInternal() ) { + ++c; + } } if ( !isRooted() ) { --c; @@ -614,7 +628,7 @@ public class Phylogeny { *

* (Last modified: 11/22/00) Olivier CHABROL : * olivier.chabrol@univ-provence.fr - * + * * @param n * external PhylogenyNode whose orthologs are to be returned * @return Vector of references to all orthologous Nodes of PhylogenyNode n @@ -624,8 +638,8 @@ public class Phylogeny { public List getParalogousNodes( final PhylogenyNode n, final String[] taxonomyCodeRange ) { PhylogenyNode node = n; PhylogenyNode prev = null; - final List v = new ArrayList(); - final Map> map = new HashMap>(); + final List v = new ArrayList<>(); + final Map> map = new HashMap<>(); getTaxonomyMap( getRoot(), map ); if ( !node.isExternal() || isEmpty() ) { return null; @@ -642,12 +656,12 @@ public class Phylogeny { taxIdList = map.get( node ); if ( node.isDuplication() && isContains( taxIdList, taxonomyCodeRangeList ) ) { if ( node.getChildNode1() == prev ) { - v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, node.getChildNode2() - .getAllExternalDescendants() ) ); + v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, + node.getChildNode2().getAllExternalDescendants() ) ); } else { - v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, node.getChildNode1() - .getAllExternalDescendants() ) ); + v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, + node.getChildNode1().getAllExternalDescendants() ) ); } } } @@ -656,7 +670,7 @@ public class Phylogeny { public Collection getRelevantSequenceRelationTypes() { if ( _relevant_sequence_relation_types == null ) { - _relevant_sequence_relation_types = new Vector(); + _relevant_sequence_relation_types = new Vector<>(); } return _relevant_sequence_relation_types; } @@ -672,70 +686,11 @@ public class Phylogeny { return _sequenceRelationQueries; } - /** - * List all species contains in all leaf under a node Olivier CHABROL : - * olivier.chabrol@univ-provence.fr - * - * @param node - * PhylogenyNode whose sub node species are returned - * @return species contains in all leaf under the param node - */ - private List getSubNodeTaxonomy( final PhylogenyNode node ) { - final List taxonomyList = new ArrayList(); - final List childs = node.getAllExternalDescendants(); - String speciesId = null; - for( final PhylogenyNode phylogenyNode : childs ) { - // taxId = new Long(phylogenyNode.getTaxonomyID()); - speciesId = PhylogenyMethods.getTaxonomyIdentifier( phylogenyNode ); - if ( !taxonomyList.contains( speciesId ) ) { - taxonomyList.add( speciesId ); - } - } - return taxonomyList; - } - - /** - * Create a map [], the list contains the - * species contains in all leaf under phylogeny node Olivier CHABROL : - * olivier.chabrol@univ-provence.fr - * - * @param node - * the tree root node - * @param map - * map to fill - */ - private void getTaxonomyMap( final PhylogenyNode node, final Map> map ) { - // node is leaf - if ( node.isExternal() ) { - return; - } - map.put( node, getSubNodeTaxonomy( node ) ); - getTaxonomyMap( node.getChildNode1(), map ); - getTaxonomyMap( node.getChildNode2(), map ); - } - public String getType() { return _type; } /** - * Hashes the ID number of each PhylogenyNode of this Phylogeny to its - * corresponding PhylogenyNode, in order to make method getNode( id ) run in - * constant time. Important: The user is responsible for calling this method - * (again) after this Phylogeny has been changed/created/renumbered. - */ - public void hashIDs() { - if ( isEmpty() ) { - return; - } - setIdHash( new HashMap() ); - for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { - final PhylogenyNode node = iter.next(); - getIdHash().put( node.getId(), node ); - } - } - - /** * Deletes this Phylogeny. */ public void init() { @@ -745,21 +700,17 @@ public class Phylogeny { _description = ""; _type = ""; _distance_unit = ""; - _idhash = null; + _id_to_node_map = null; _confidence = null; _identifier = null; _rerootable = true; setAllowMultipleParents( Phylogeny.ALLOW_MULTIPLE_PARENTS_DEFAULT ); } - private boolean isAllowMultipleParents() { - return _allow_multiple_parents; - } - /** * Returns whether this is a completely binary tree (i.e. all internal nodes * are bifurcations). - * + * */ public boolean isCompletelyBinary() { if ( isEmpty() ) { @@ -774,26 +725,22 @@ public class Phylogeny { return true; } - /** - * Util method to check if all element of a list is contains in the - * rangeList. Olivier CHABROL : olivier.chabrol@univ-provence.fr - * - * @param list - * list to be check - * @param rangeList - * the range list to compare - * @return true if all param list element are contains in param - * rangeList, false otherwise. - */ - private boolean isContains( final List list, final List rangeList ) { - if ( list.size() > rangeList.size() ) { + public boolean isCompletelyBinaryAllow3ChildrenAtRoot() { + if ( isEmpty() ) { return false; } - String l = null; - for( final Iterator iterator = list.iterator(); iterator.hasNext(); ) { - l = iterator.next(); - if ( !rangeList.contains( l ) ) { - return false; + for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { + final PhylogenyNode node = iter.next(); + if ( node.isRoot() ) { + if ( node.isInternal() + && ( ( node.getNumberOfDescendants() != 2 ) && ( node.getNumberOfDescendants() != 3 ) ) ) { + return false; + } + } + else { + if ( node.isInternal() && ( node.getNumberOfDescendants() != 2 ) ) { + return false; + } } } return true; @@ -801,7 +748,7 @@ public class Phylogeny { /** * Checks whether a Phylogeny object is deleted (or empty). - * + * * @return true if the tree is deleted (or empty), false otherwise */ public boolean isEmpty() { @@ -843,14 +790,14 @@ public class Phylogeny { * Resets the ID numbers of the nodes of this Phylogeny in level order, * starting with start_label (for the root).
* WARNING. After this method has been called, node IDs are no longer - * unique. + * unique. */ public void levelOrderReID() { if ( isEmpty() ) { return; } - _idhash = null; - int max = 0; + _id_to_node_map = null; + long max = 0; for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); ) { final PhylogenyNode node = it.next(); if ( node.isRoot() ) { @@ -866,18 +813,6 @@ public class Phylogeny { PhylogenyNode.setNodeCount( max + 1 ); } - public void preOrderReId() { - if ( isEmpty() ) { - return; - } - setIdHash( null ); - int i = PhylogenyNode.getNodeCount(); - for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); ) { - it.next().setId( i++ ); - } - PhylogenyNode.setNodeCount( i ); - } - /** * Prints descriptions of all external Nodes of this Phylogeny to * System.out. @@ -895,7 +830,7 @@ public class Phylogeny { * (Re)counts the number of children for each PhylogenyNode of this * Phylogeny. As an example, this method needs to be called after a * Phylogeny has been reRooted and it is to be displayed. - * + * * @param consider_collapsed_nodes * set to true to take into account collapsed nodes (collapsed * nodes have 1 child). @@ -928,44 +863,15 @@ public class Phylogeny { *

*

  • recalculateNumberOfExternalDescendants(boolean) *
  • recalculateAndReset() - * + * * @param id * ID (int) of PhylogenyNode of this Phylogeny */ - public void reRoot( final int id ) { + public void reRoot( final long id ) { reRoot( getNode( id ) ); } /** - * Places the root of this Phylogeny on Branch b. The new root is always - * placed on the middle of the branch b. - * - */ - public void reRoot( final PhylogenyBranch b ) { - final PhylogenyNode n1 = b.getFirstNode(); - final PhylogenyNode n2 = b.getSecondNode(); - if ( n1.isExternal() ) { - reRoot( n1 ); - } - else if ( n2.isExternal() ) { - reRoot( n2 ); - } - else if ( ( n2 == n1.getChildNode1() ) || ( n2 == n1.getChildNode2() ) ) { - reRoot( n2 ); - } - else if ( ( n1 == n2.getChildNode1() ) || ( n1 == n2.getChildNode2() ) ) { - reRoot( n1 ); - } - else if ( ( n1.getParent() != null ) && n1.getParent().isRoot() - && ( ( n1.getParent().getChildNode1() == n2 ) || ( n1.getParent().getChildNode2() == n2 ) ) ) { - reRoot( n1 ); - } - else { - throw new IllegalArgumentException( "reRoot( Branch b ): b is not a branch." ); - } - } - - /** * Places the root of this Phylogeny on the parent branch PhylogenyNode n. * The new root is always placed on the middle of the branch. *

    @@ -977,7 +883,7 @@ public class Phylogeny { * *

    * (Last modified: 10/01/01) - * + * * @param n * PhylogenyNode of this Phylogeny\ */ @@ -1145,10 +1051,6 @@ public class Phylogeny { } } - private void setAllowMultipleParents( final boolean allow_multiple_parents ) { - _allow_multiple_parents = allow_multiple_parents; - } - public void setConfidence( final Confidence confidence ) { _confidence = confidence; } @@ -1165,8 +1067,8 @@ public class Phylogeny { _identifier = identifier; } - void setIdHash( final HashMap idhash ) { - _idhash = idhash; + public void setIdToNodeMap( final HashMap idhash ) { + _id_to_node_map = idhash; } /** @@ -1198,14 +1100,14 @@ public class Phylogeny { public void setRoot( final PhylogenyNode n ) { _root = n; - } // setRoot( PhylogenyNode ) + } /** * Sets whether this Phylogeny is rooted or not. */ public void setRooted( final boolean b ) { _rooted = b; - } // setRooted( boolean ) + } public void setSequenceRelationQueries( final Collection sequencesByName ) { _sequenceRelationQueries = sequencesByName; @@ -1216,14 +1118,12 @@ public class Phylogeny { } public String toNewHampshire() { - return toNewHampshire( false, NH_CONVERSION_SUPPORT_VALUE_STYLE.NONE ); + return toNewHampshire( NH_CONVERSION_SUPPORT_VALUE_STYLE.NONE ); } - public String toNewHampshire( final boolean simple_nh, - final NH_CONVERSION_SUPPORT_VALUE_STYLE nh_conversion_support_style ) { + public String toNewHampshire( final NH_CONVERSION_SUPPORT_VALUE_STYLE nh_conversion_support_style ) { try { - return new PhylogenyWriter().toNewHampshire( this, simple_nh, true, nh_conversion_support_style ) - .toString(); + return new PhylogenyWriter().toNewHampshire( this, true, nh_conversion_support_style ).toString(); } catch ( final IOException e ) { throw new Error( "this should not have happend: " + e.getMessage() ); @@ -1239,6 +1139,10 @@ public class Phylogeny { } } + public String toNexus() { + return toNexus( NH_CONVERSION_SUPPORT_VALUE_STYLE.NONE ); + } + public String toNexus( final NH_CONVERSION_SUPPORT_VALUE_STYLE svs ) { try { return new PhylogenyWriter().toNexus( this, svs ).toString(); @@ -1248,10 +1152,6 @@ public class Phylogeny { } } - public String toNexus() { - return toNexus( NH_CONVERSION_SUPPORT_VALUE_STYLE.NONE ); - } - public String toPhyloXML( final int phyloxml_level ) { try { return new PhylogenyWriter().toPhyloXML( this, phyloxml_level ).toString(); @@ -1266,7 +1166,7 @@ public class Phylogeny { // --------------------------------------------------------- /** * Converts this Phylogeny to a New Hampshire X (String) representation. - * + * * @return New Hampshire X (String) representation of this * @see #toNewHampshireX() */ @@ -1292,4 +1192,120 @@ public class Phylogeny { setRooted( false ); return; } // unRoot() + + private HashMap getIdToNodeMap() { + return _id_to_node_map; + } + + /** + * Return Node by TaxonomyId Olivier CHABROL : + * olivier.chabrol@univ-provence.fr + * + * @param taxonomyID + * search taxonomy identifier + * @param nodes + * sublist node to search + * @return List node with the same taxonomy identifier + */ + private List getNodeByTaxonomyID( final String taxonomyID, final List nodes ) { + final List retour = new ArrayList<>(); + for( final PhylogenyNode node : nodes ) { + if ( taxonomyID.equals( PhylogenyMethods.getTaxonomyIdentifier( node ) ) ) { + retour.add( node ); + } + } + return retour; + } + + /** + * List all species contains in all leaf under a node Olivier CHABROL : + * olivier.chabrol@univ-provence.fr + * + * @param node + * PhylogenyNode whose sub node species are returned + * @return species contains in all leaf under the param node + */ + private List getSubNodeTaxonomy( final PhylogenyNode node ) { + final List taxonomyList = new ArrayList<>(); + final List childs = node.getAllExternalDescendants(); + String speciesId = null; + for( final PhylogenyNode phylogenyNode : childs ) { + // taxId = new Long(phylogenyNode.getTaxonomyID()); + speciesId = PhylogenyMethods.getTaxonomyIdentifier( phylogenyNode ); + if ( !taxonomyList.contains( speciesId ) ) { + taxonomyList.add( speciesId ); + } + } + return taxonomyList; + } + + /** + * Create a map [], the list contains the + * species contains in all leaf under phylogeny node Olivier CHABROL : + * olivier.chabrol@univ-provence.fr + * + * @param node + * the tree root node + * @param map + * map to fill + */ + private void getTaxonomyMap( final PhylogenyNode node, final Map> map ) { + // node is leaf + if ( node.isExternal() ) { + return; + } + map.put( node, getSubNodeTaxonomy( node ) ); + getTaxonomyMap( node.getChildNode1(), map ); + getTaxonomyMap( node.getChildNode2(), map ); + } + + private boolean isAllowMultipleParents() { + return _allow_multiple_parents; + } + + /** + * Util method to check if all element of a list is contains in the + * rangeList. Olivier CHABROL : olivier.chabrol@univ-provence.fr + * + * @param list + * list to be check + * @param rangeList + * the range list to compare + * @return true if all param list element are contains in param + * rangeList, false otherwise. + */ + private boolean isContains( final List list, final List rangeList ) { + if ( list.size() > rangeList.size() ) { + return false; + } + String l = null; + for( final Iterator iterator = list.iterator(); iterator.hasNext(); ) { + l = iterator.next(); + if ( !rangeList.contains( l ) ) { + return false; + } + } + return true; + } + + /** + * Hashes the ID number of each PhylogenyNode of this Phylogeny to its + * corresponding PhylogenyNode, in order to make method getNode( id ) run in + * constant time. Important: The user is responsible for calling this method + * (again) after this Phylogeny has been changed/created/renumbered. + */ + private void reHashIdToNodeMap() { + if ( isEmpty() ) { + return; + } + setIdToNodeMap( new HashMap() ); + for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { + final PhylogenyNode node = iter.next(); + getIdToNodeMap().put( node.getId(), node ); + } + } + + private void setAllowMultipleParents( final boolean allow_multiple_parents ) { + _allow_multiple_parents = allow_multiple_parents; + } }