forester/java/src/org/forester/phylogeny/PhylogenyMethods.java

   1 // $Id:
   2 // FORESTER -- software libraries and applications
   3 // for evolutionary biology research and applications.
   4 //
   5 // Copyright (C) 2008-2009 Christian M. Zmasek
   6 // Copyright (C) 2008-2009 Burnham Institute for Medical Research
   7 // All rights reserved
   8 //
   9 // This library is free software; you can redistribute it and/or
  10 // modify it under the terms of the GNU Lesser General Public
  11 // License as published by the Free Software Foundation; either
  12 // version 2.1 of the License, or (at your option) any later version.
  13 //
  14 // This library is distributed in the hope that it will be useful,
  15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  17 // Lesser General Public License for more details.
  18 //
  19 // You should have received a copy of the GNU Lesser General Public
  20 // License along with this library; if not, write to the Free Software
  21 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
  22 //
  23 // Contact: phylosoft @ gmail . com
  24 // WWW: www.phylosoft.org/forester
  25
  26 package org.forester.phylogeny;
  27
  28 import java.awt.Color;
  29 import java.io.File;
  30 import java.io.IOException;
  31 import java.util.ArrayList;
  32 import java.util.Arrays;
  33 import java.util.Collections;
  34 import java.util.Comparator;
  35 import java.util.HashMap;
  36 import java.util.HashSet;
  37 import java.util.Iterator;
  38 import java.util.List;
  39 import java.util.Set;
  40 import java.util.SortedMap;
  41 import java.util.TreeMap;
  42
  43 import org.forester.io.parsers.PhylogenyParser;
  44 import org.forester.io.parsers.phyloxml.PhyloXmlDataFormatException;
  45 import org.forester.io.parsers.phyloxml.PhyloXmlUtil;
  46 import org.forester.io.parsers.util.PhylogenyParserException;
  47 import org.forester.phylogeny.data.BranchColor;
  48 import org.forester.phylogeny.data.BranchWidth;
  49 import org.forester.phylogeny.data.Confidence;
  50 import org.forester.phylogeny.data.DomainArchitecture;
  51 import org.forester.phylogeny.data.Event;
  52 import org.forester.phylogeny.data.Identifier;
  53 import org.forester.phylogeny.data.PhylogenyDataUtil;
  54 import org.forester.phylogeny.data.Sequence;
  55 import org.forester.phylogeny.data.Taxonomy;
  56 import org.forester.phylogeny.factories.ParserBasedPhylogenyFactory;
  57 import org.forester.phylogeny.factories.PhylogenyFactory;
  58 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
  59 import org.forester.util.BasicDescriptiveStatistics;
  60 import org.forester.util.DescriptiveStatistics;
  61 import org.forester.util.FailedConditionCheckException;
  62 import org.forester.util.ForesterUtil;
  63
  64 public class PhylogenyMethods {
  65
  66     private static PhylogenyMethods _instance   = null;
  67     private PhylogenyNode           _farthest_1 = null;
  68     private PhylogenyNode           _farthest_2 = null;
  69
  70     private PhylogenyMethods() {
  71         // Hidden constructor.
  72     }
  73
  74     /**
  75      * Calculates the distance between PhylogenyNodes node1 and node2.
  76      *
  77      *
  78      * @param node1
  79      * @param node2
  80      * @return distance between node1 and node2
  81      */
  82     public double calculateDistance( final PhylogenyNode node1, final PhylogenyNode node2 ) {
  83         final PhylogenyNode lca = calculateLCA( node1, node2 );
  84         final PhylogenyNode n1 = node1;
  85         final PhylogenyNode n2 = node2;
  86         return ( PhylogenyMethods.getDistance( n1, lca ) + PhylogenyMethods.getDistance( n2, lca ) );
  87     }
  88
  89     public double calculateFurthestDistance( final Phylogeny phylogeny ) {
  90         if ( phylogeny.getNumberOfExternalNodes() < 2 ) {
  91             return 0.0;
  92         }
  93         _farthest_1 = null;
  94         _farthest_2 = null;
  95         PhylogenyNode node_1 = null;
  96         PhylogenyNode node_2 = null;
  97         double farthest_d = -Double.MAX_VALUE;
  98         final PhylogenyMethods methods = PhylogenyMethods.getInstance();
  99         final List<PhylogenyNode> ext_nodes = phylogeny.getRoot().getAllExternalDescendants();
 100         for( int i = 1; i < ext_nodes.size(); ++i ) {
 101             for( int j = 0; j < i; ++j ) {
 102                 final double d = methods.calculateDistance( ext_nodes.get( i ), ext_nodes.get( j ) );
 103                 if ( d < 0.0 ) {
 104                     throw new RuntimeException( "distance cannot be negative" );
 105                 }
 106                 if ( d > farthest_d ) {
 107                     farthest_d = d;
 108                     node_1 = ext_nodes.get( i );
 109                     node_2 = ext_nodes.get( j );
 110                 }
 111             }
 112         }
 113         _farthest_1 = node_1;
 114         _farthest_2 = node_2;
 115         return farthest_d;
 116     }
 117
 118     @Override
 119     public Object clone() throws CloneNotSupportedException {
 120         throw new CloneNotSupportedException();
 121     }
 122
 123     public PhylogenyNode getFarthestNode1() {
 124         return _farthest_1;
 125     }
 126
 127     public PhylogenyNode getFarthestNode2() {
 128         return _farthest_2;
 129     }
 130
 131     public static DescriptiveStatistics calculatBranchLengthStatistics( final Phylogeny phy ) {
 132         final DescriptiveStatistics stats = new BasicDescriptiveStatistics();
 133         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 134             final PhylogenyNode n = iter.next();
 135             if ( !n.isRoot() && ( n.getDistanceToParent() >= 0.0 ) ) {
 136                 stats.addValue( n.getDistanceToParent() );
 137             }
 138         }
 139         return stats;
 140     }
 141
 142     public static List<DescriptiveStatistics> calculatConfidenceStatistics( final Phylogeny phy ) {
 143         final List<DescriptiveStatistics> stats = new ArrayList<DescriptiveStatistics>();
 144         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 145             final PhylogenyNode n = iter.next();
 146             if ( !n.isExternal() && !n.isRoot() ) {
 147                 if ( n.getBranchData().isHasConfidences() ) {
 148                     for( int i = 0; i < n.getBranchData().getConfidences().size(); ++i ) {
 149                         final Confidence c = n.getBranchData().getConfidences().get( i );
 150                         if ( ( i > ( stats.size() - 1 ) ) || ( stats.get( i ) == null ) ) {
 151                             stats.add( i, new BasicDescriptiveStatistics() );
 152                         }
 153                         if ( !ForesterUtil.isEmpty( c.getType() ) ) {
 154                             if ( !ForesterUtil.isEmpty( stats.get( i ).getDescription() ) ) {
 155                                 if ( !stats.get( i ).getDescription().equalsIgnoreCase( c.getType() ) ) {
 156                                     throw new IllegalArgumentException( "support values in node [" + n.toString()
 157                                             + "] appear inconsistently ordered" );
 158                                 }
 159                             }
 160                             stats.get( i ).setDescription( c.getType() );
 161                         }
 162                         stats.get( i ).addValue( ( ( c != null ) && ( c.getValue() >= 0 ) ) ? c.getValue() : 0 );
 163                     }
 164                 }
 165             }
 166         }
 167         return stats;
 168     }
 169
 170     /**
 171      * Returns the LCA of PhylogenyNodes node1 and node2.
 172      *
 173      *
 174      * @param node1
 175      * @param node2
 176      * @return LCA of node1 and node2
 177      */
 178     public final static PhylogenyNode calculateLCA( PhylogenyNode node1, PhylogenyNode node2 ) {
 179         if ( node1 == null ) {
 180             throw new IllegalArgumentException( "first argument (node) is null" );
 181         }
 182         if ( node2 == null ) {
 183             throw new IllegalArgumentException( "second argument (node) is null" );
 184         }
 185         if ( node1 == node2 ) {
 186             return node1;
 187         }
 188         if ( ( node1.getParent() == node2.getParent() ) ) {
 189             return node1.getParent();
 190         }
 191         int depth1 = node1.calculateDepth();
 192         int depth2 = node2.calculateDepth();
 193         while ( ( depth1 > -1 ) && ( depth2 > -1 ) ) {
 194             if ( depth1 > depth2 ) {
 195                 node1 = node1.getParent();
 196                 depth1--;
 197             }
 198             else if ( depth2 > depth1 ) {
 199                 node2 = node2.getParent();
 200                 depth2--;
 201             }
 202             else {
 203                 if ( node1 == node2 ) {
 204                     return node1;
 205                 }
 206                 node1 = node1.getParent();
 207                 node2 = node2.getParent();
 208                 depth1--;
 209                 depth2--;
 210             }
 211         }
 212         throw new IllegalArgumentException( "illegal attempt to calculate LCA of two nodes which do not share a common root" );
 213     }
 214
 215     /**
 216      * Returns the LCA of PhylogenyNodes node1 and node2.
 217      * Precondition: ids are in pre-order (or level-order).
 218      *
 219      *
 220      * @param node1
 221      * @param node2
 222      * @return LCA of node1 and node2
 223      */
 224     public final static PhylogenyNode calculateLCAonTreeWithIdsInPreOrder( PhylogenyNode node1, PhylogenyNode node2 ) {
 225         if ( node1 == null ) {
 226             throw new IllegalArgumentException( "first argument (node) is null" );
 227         }
 228         if ( node2 == null ) {
 229             throw new IllegalArgumentException( "second argument (node) is null" );
 230         }
 231         while ( node1 != node2 ) {
 232             if ( node1.getId() > node2.getId() ) {
 233                 node1 = node1.getParent();
 234             }
 235             else {
 236                 node2 = node2.getParent();
 237             }
 238         }
 239         return node1;
 240     }
 241
 242     public static short calculateMaxBranchesToLeaf( final PhylogenyNode node ) {
 243         if ( node.isExternal() ) {
 244             return 0;
 245         }
 246         short max = 0;
 247         for( PhylogenyNode d : node.getAllExternalDescendants() ) {
 248             short steps = 0;
 249             while ( d != node ) {
 250                 if ( d.isCollapse() ) {
 251                     steps = 0;
 252                 }
 253                 else {
 254                     steps++;
 255                 }
 256                 d = d.getParent();
 257             }
 258             if ( max < steps ) {
 259                 max = steps;
 260             }
 261         }
 262         return max;
 263     }
 264
 265     public static int calculateMaxDepth( final Phylogeny phy ) {
 266         int max = 0;
 267         for( final PhylogenyNodeIterator iter = phy.iteratorExternalForward(); iter.hasNext(); ) {
 268             final PhylogenyNode node = iter.next();
 269             final int steps = node.calculateDepth();
 270             if ( steps > max ) {
 271                 max = steps;
 272             }
 273         }
 274         return max;
 275     }
 276
 277     public static double calculateMaxDistanceToRoot( final Phylogeny phy ) {
 278         double max = 0.0;
 279         for( final PhylogenyNodeIterator iter = phy.iteratorExternalForward(); iter.hasNext(); ) {
 280             final PhylogenyNode node = iter.next();
 281             final double d = node.calculateDistanceToRoot();
 282             if ( d > max ) {
 283                 max = d;
 284             }
 285         }
 286         return max;
 287     }
 288
 289     public static int calculateNumberOfExternalNodesWithoutTaxonomy( final PhylogenyNode node ) {
 290         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 291         int x = 0;
 292         for( final PhylogenyNode n : descs ) {
 293             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 294                 x++;
 295             }
 296         }
 297         return x;
 298     }
 299
 300     public static DescriptiveStatistics calculatNumberOfDescendantsPerNodeStatistics( final Phylogeny phy ) {
 301         final DescriptiveStatistics stats = new BasicDescriptiveStatistics();
 302         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 303             final PhylogenyNode n = iter.next();
 304             if ( !n.isExternal() ) {
 305                 stats.addValue( n.getNumberOfDescendants() );
 306             }
 307         }
 308         return stats;
 309     }
 310
 311     public static int countNumberOfPolytomies( final Phylogeny phy ) {
 312         int count = 0;
 313         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 314             final PhylogenyNode n = iter.next();
 315             if ( !n.isExternal() && ( n.getNumberOfDescendants() > 2 ) ) {
 316                 count++;
 317             }
 318         }
 319         return count;
 320     }
 321
 322     public static final HashMap<String, PhylogenyNode> createNameToExtNodeMap( final Phylogeny phy ) {
 323         final HashMap<String, PhylogenyNode> nodes = new HashMap<String, PhylogenyNode>();
 324         for( final PhylogenyNodeIterator iter = phy.iteratorExternalForward(); iter.hasNext(); ) {
 325             final PhylogenyNode n = iter.next();
 326             nodes.put( n.getName(), n );
 327         }
 328         return nodes;
 329     }
 330
 331     public static void deleteExternalNodesNegativeSelection( final Set<Integer> to_delete, final Phylogeny phy ) {
 332         phy.clearHashIdToNodeMap();
 333         for( final Integer id : to_delete ) {
 334             phy.deleteSubtree( phy.getNode( id ), true );
 335         }
 336         phy.clearHashIdToNodeMap();
 337         phy.externalNodesHaveChanged();
 338     }
 339
 340     public static void deleteExternalNodesNegativeSelection( final String[] node_names_to_delete, final Phylogeny p )
 341             throws IllegalArgumentException {
 342         for( final String element : node_names_to_delete ) {
 343             if ( ForesterUtil.isEmpty( element ) ) {
 344                 continue;
 345             }
 346             List<PhylogenyNode> nodes = null;
 347             nodes = p.getNodes( element );
 348             final Iterator<PhylogenyNode> it = nodes.iterator();
 349             while ( it.hasNext() ) {
 350                 final PhylogenyNode n = it.next();
 351                 if ( !n.isExternal() ) {
 352                     throw new IllegalArgumentException( "attempt to delete non-external node \"" + element + "\"" );
 353                 }
 354                 p.deleteSubtree( n, true );
 355             }
 356         }
 357         p.clearHashIdToNodeMap();
 358         p.externalNodesHaveChanged();
 359     }
 360
 361     public static void deleteExternalNodesPositiveSelection( final Set<Taxonomy> species_to_keep, final Phylogeny phy ) {
 362         //   final Set<Integer> to_delete = new HashSet<Integer>();
 363         for( final PhylogenyNodeIterator it = phy.iteratorExternalForward(); it.hasNext(); ) {
 364             final PhylogenyNode n = it.next();
 365             if ( n.getNodeData().isHasTaxonomy() ) {
 366                 if ( !species_to_keep.contains( n.getNodeData().getTaxonomy() ) ) {
 367                     //to_delete.add( n.getNodeId() );
 368                     phy.deleteSubtree( n, true );
 369                 }
 370             }
 371             else {
 372                 throw new IllegalArgumentException( "node " + n.getId() + " has no taxonomic data" );
 373             }
 374         }
 375         phy.clearHashIdToNodeMap();
 376         phy.externalNodesHaveChanged();
 377     }
 378
 379     public static List<String> deleteExternalNodesPositiveSelection( final String[] node_names_to_keep,
 380                                                                      final Phylogeny p ) {
 381         final PhylogenyNodeIterator it = p.iteratorExternalForward();
 382         final String[] to_delete = new String[ p.getNumberOfExternalNodes() ];
 383         int i = 0;
 384         Arrays.sort( node_names_to_keep );
 385         while ( it.hasNext() ) {
 386             final String curent_name = it.next().getName();
 387             if ( Arrays.binarySearch( node_names_to_keep, curent_name ) < 0 ) {
 388                 to_delete[ i++ ] = curent_name;
 389             }
 390         }
 391         PhylogenyMethods.deleteExternalNodesNegativeSelection( to_delete, p );
 392         final List<String> deleted = new ArrayList<String>();
 393         for( final String n : to_delete ) {
 394             if ( !ForesterUtil.isEmpty( n ) ) {
 395                 deleted.add( n );
 396             }
 397         }
 398         return deleted;
 399     }
 400
 401     final public static void deleteNonOrthologousExternalNodes( final Phylogeny phy, final PhylogenyNode n ) {
 402         if ( n.isInternal() ) {
 403             throw new IllegalArgumentException( "node is not external" );
 404         }
 405         final ArrayList<PhylogenyNode> to_delete = new ArrayList<PhylogenyNode>();
 406         for( final PhylogenyNodeIterator it = phy.iteratorExternalForward(); it.hasNext(); ) {
 407             final PhylogenyNode i = it.next();
 408             if ( !PhylogenyMethods.getEventAtLCA( n, i ).isSpeciation() ) {
 409                 to_delete.add( i );
 410             }
 411         }
 412         for( final PhylogenyNode d : to_delete ) {
 413             phy.deleteSubtree( d, true );
 414         }
 415         phy.clearHashIdToNodeMap();
 416         phy.externalNodesHaveChanged();
 417     }
 418
 419     public static List<PhylogenyNode> getAllDescendants( final PhylogenyNode node ) {
 420         final List<PhylogenyNode> descs = new ArrayList<PhylogenyNode>();
 421         final Set<Integer> encountered = new HashSet<Integer>();
 422         if ( !node.isExternal() ) {
 423             final List<PhylogenyNode> exts = node.getAllExternalDescendants();
 424             for( PhylogenyNode current : exts ) {
 425                 descs.add( current );
 426                 while ( current != node ) {
 427                     current = current.getParent();
 428                     if ( encountered.contains( current.getId() ) ) {
 429                         continue;
 430                     }
 431                     descs.add( current );
 432                     encountered.add( current.getId() );
 433                 }
 434             }
 435         }
 436         return descs;
 437     }
 438
 439     /**
 440      *
 441      * Convenience method
 442      *
 443      * @param node
 444      * @return
 445      */
 446     public static Color getBranchColorValue( final PhylogenyNode node ) {
 447         if ( node.getBranchData().getBranchColor() == null ) {
 448             return null;
 449         }
 450         return node.getBranchData().getBranchColor().getValue();
 451     }
 452
 453     /**
 454      * Convenience method
 455      */
 456     public static double getBranchWidthValue( final PhylogenyNode node ) {
 457         if ( !node.getBranchData().isHasBranchWidth() ) {
 458             return BranchWidth.BRANCH_WIDTH_DEFAULT_VALUE;
 459         }
 460         return node.getBranchData().getBranchWidth().getValue();
 461     }
 462
 463     /**
 464      * Convenience method
 465      */
 466     public static double getConfidenceValue( final PhylogenyNode node ) {
 467         if ( !node.getBranchData().isHasConfidences() ) {
 468             return Confidence.CONFIDENCE_DEFAULT_VALUE;
 469         }
 470         return node.getBranchData().getConfidence( 0 ).getValue();
 471     }
 472
 473     /**
 474      * Convenience method
 475      */
 476     public static double[] getConfidenceValuesAsArray( final PhylogenyNode node ) {
 477         if ( !node.getBranchData().isHasConfidences() ) {
 478             return new double[ 0 ];
 479         }
 480         final double[] values = new double[ node.getBranchData().getConfidences().size() ];
 481         int i = 0;
 482         for( final Confidence c : node.getBranchData().getConfidences() ) {
 483             values[ i++ ] = c.getValue();
 484         }
 485         return values;
 486     }
 487
 488     final public static Event getEventAtLCA( final PhylogenyNode n1, final PhylogenyNode n2 ) {
 489         return calculateLCA( n1, n2 ).getNodeData().getEvent();
 490     }
 491
 492     /**
 493      * Returns taxonomy t if all external descendants have
 494      * the same taxonomy t, null otherwise.
 495      *
 496      */
 497     public static Taxonomy getExternalDescendantsTaxonomy( final PhylogenyNode node ) {
 498         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 499         Taxonomy tax = null;
 500         for( final PhylogenyNode n : descs ) {
 501             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 502                 return null;
 503             }
 504             else if ( tax == null ) {
 505                 tax = n.getNodeData().getTaxonomy();
 506             }
 507             else if ( n.getNodeData().getTaxonomy().isEmpty() || !tax.isEqual( n.getNodeData().getTaxonomy() ) ) {
 508                 return null;
 509             }
 510         }
 511         return tax;
 512     }
 513
 514     public static PhylogenyNode getFurthestDescendant( final PhylogenyNode node ) {
 515         final List<PhylogenyNode> children = node.getAllExternalDescendants();
 516         PhylogenyNode farthest = null;
 517         double longest = -Double.MAX_VALUE;
 518         for( final PhylogenyNode child : children ) {
 519             if ( PhylogenyMethods.getDistance( child, node ) > longest ) {
 520                 farthest = child;
 521                 longest = PhylogenyMethods.getDistance( child, node );
 522             }
 523         }
 524         return farthest;
 525     }
 526
 527     public static PhylogenyMethods getInstance() {
 528         if ( PhylogenyMethods._instance == null ) {
 529             PhylogenyMethods._instance = new PhylogenyMethods();
 530         }
 531         return PhylogenyMethods._instance;
 532     }
 533
 534     /**
 535      * Returns the largest confidence value found on phy.
 536      */
 537     static public double getMaximumConfidenceValue( final Phylogeny phy ) {
 538         double max = -Double.MAX_VALUE;
 539         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 540             final double s = PhylogenyMethods.getConfidenceValue( iter.next() );
 541             if ( ( s != Confidence.CONFIDENCE_DEFAULT_VALUE ) && ( s > max ) ) {
 542                 max = s;
 543             }
 544         }
 545         return max;
 546     }
 547
 548     static public int getMinimumDescendentsPerInternalNodes( final Phylogeny phy ) {
 549         int min = Integer.MAX_VALUE;
 550         int d = 0;
 551         PhylogenyNode n;
 552         for( final PhylogenyNodeIterator it = phy.iteratorPreorder(); it.hasNext(); ) {
 553             n = it.next();
 554             if ( n.isInternal() ) {
 555                 d = n.getNumberOfDescendants();
 556                 if ( d < min ) {
 557                     min = d;
 558                 }
 559             }
 560         }
 561         return min;
 562     }
 563
 564     /**
 565      * Convenience method for display purposes.
 566      * Not intended for algorithms.
 567      */
 568     public static String getSpecies( final PhylogenyNode node ) {
 569         if ( !node.getNodeData().isHasTaxonomy() ) {
 570             return "";
 571         }
 572         else if ( !ForesterUtil.isEmpty( node.getNodeData().getTaxonomy().getScientificName() ) ) {
 573             return node.getNodeData().getTaxonomy().getScientificName();
 574         }
 575         if ( !ForesterUtil.isEmpty( node.getNodeData().getTaxonomy().getTaxonomyCode() ) ) {
 576             return node.getNodeData().getTaxonomy().getTaxonomyCode();
 577         }
 578         else {
 579             return node.getNodeData().getTaxonomy().getCommonName();
 580         }
 581     }
 582
 583     /**
 584      * Convenience method for display purposes.
 585      * Not intended for algorithms.
 586      */
 587     public static String getTaxonomyIdentifier( final PhylogenyNode node ) {
 588         if ( !node.getNodeData().isHasTaxonomy() || ( node.getNodeData().getTaxonomy().getIdentifier() == null ) ) {
 589             return "";
 590         }
 591         return node.getNodeData().getTaxonomy().getIdentifier().getValue();
 592     }
 593
 594     public final static boolean isAllDecendentsAreDuplications( final PhylogenyNode n ) {
 595         if ( n.isExternal() ) {
 596             return true;
 597         }
 598         else {
 599             if ( n.isDuplication() ) {
 600                 for( final PhylogenyNode desc : n.getDescendants() ) {
 601                     if ( !isAllDecendentsAreDuplications( desc ) ) {
 602                         return false;
 603                     }
 604                 }
 605                 return true;
 606             }
 607             else {
 608                 return false;
 609             }
 610         }
 611     }
 612
 613     public static boolean isHasExternalDescendant( final PhylogenyNode node ) {
 614         for( int i = 0; i < node.getNumberOfDescendants(); ++i ) {
 615             if ( node.getChildNode( i ).isExternal() ) {
 616                 return true;
 617             }
 618         }
 619         return false;
 620     }
 621
 622     /*
 623      * This is case insensitive.
 624      *
 625      */
 626     public synchronized static boolean isTaxonomyHasIdentifierOfGivenProvider( final Taxonomy tax,
 627                                                                                final String[] providers ) {
 628         if ( ( tax.getIdentifier() != null ) && !ForesterUtil.isEmpty( tax.getIdentifier().getProvider() ) ) {
 629             final String my_tax_prov = tax.getIdentifier().getProvider();
 630             for( final String provider : providers ) {
 631                 if ( provider.equalsIgnoreCase( my_tax_prov ) ) {
 632                     return true;
 633                 }
 634             }
 635             return false;
 636         }
 637         else {
 638             return false;
 639         }
 640     }
 641
 642     public static void midpointRoot( final Phylogeny phylogeny ) {
 643         if ( phylogeny.getNumberOfExternalNodes() < 2 ) {
 644             return;
 645         }
 646         final PhylogenyMethods methods = getInstance();
 647         final double farthest_d = methods.calculateFurthestDistance( phylogeny );
 648         final PhylogenyNode f1 = methods.getFarthestNode1();
 649         final PhylogenyNode f2 = methods.getFarthestNode2();
 650         if ( farthest_d <= 0.0 ) {
 651             return;
 652         }
 653         double x = farthest_d / 2.0;
 654         PhylogenyNode n = f1;
 655         if ( PhylogenyMethods.getDistance( f1, phylogeny.getRoot() ) < PhylogenyMethods.getDistance( f2, phylogeny
 656                 .getRoot() ) ) {
 657             n = f2;
 658         }
 659         while ( ( x > n.getDistanceToParent() ) && !n.isRoot() ) {
 660             x -= ( n.getDistanceToParent() > 0 ? n.getDistanceToParent() : 0 );
 661             n = n.getParent();
 662         }
 663         phylogeny.reRoot( n, x );
 664         phylogeny.recalculateNumberOfExternalDescendants( true );
 665         final PhylogenyNode a = getFurthestDescendant( phylogeny.getRoot().getChildNode1() );
 666         final PhylogenyNode b = getFurthestDescendant( phylogeny.getRoot().getChildNode2() );
 667         final double da = getDistance( a, phylogeny.getRoot() );
 668         final double db = getDistance( b, phylogeny.getRoot() );
 669         if ( Math.abs( da - db ) > 0.000001 ) {
 670             throw new FailedConditionCheckException( "this should not have happened: midpoint rooting failed:  da="
 671                     + da + ",  db=" + db + ",  diff=" + Math.abs( da - db ) );
 672         }
 673     }
 674
 675     public static void normalizeBootstrapValues( final Phylogeny phylogeny,
 676                                                  final double max_bootstrap_value,
 677                                                  final double max_normalized_value ) {
 678         for( final PhylogenyNodeIterator iter = phylogeny.iteratorPreorder(); iter.hasNext(); ) {
 679             final PhylogenyNode node = iter.next();
 680             if ( node.isInternal() ) {
 681                 final double confidence = getConfidenceValue( node );
 682                 if ( confidence != Confidence.CONFIDENCE_DEFAULT_VALUE ) {
 683                     if ( confidence >= max_bootstrap_value ) {
 684                         setBootstrapConfidence( node, max_normalized_value );
 685                     }
 686                     else {
 687                         setBootstrapConfidence( node, ( confidence * max_normalized_value ) / max_bootstrap_value );
 688                     }
 689                 }
 690             }
 691         }
 692     }
 693
 694     public static List<PhylogenyNode> obtainAllNodesAsList( final Phylogeny phy ) {
 695         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 696         if ( phy.isEmpty() ) {
 697             return nodes;
 698         }
 699         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 700             nodes.add( iter.next() );
 701         }
 702         return nodes;
 703     }
 704
 705     /**
 706      * Returns the set of distinct taxonomies of
 707      * all external nodes of node.
 708      * If at least one the external nodes has no taxonomy,
 709      * null is returned.
 710      *
 711      */
 712     public static Set<Taxonomy> obtainDistinctTaxonomies( final PhylogenyNode node ) {
 713         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 714         final Set<Taxonomy> tax_set = new HashSet<Taxonomy>();
 715         for( final PhylogenyNode n : descs ) {
 716             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 717                 return null;
 718             }
 719             tax_set.add( n.getNodeData().getTaxonomy() );
 720         }
 721         return tax_set;
 722     }
 723
 724     /**
 725      * Returns a map of distinct taxonomies of
 726      * all external nodes of node.
 727      * If at least one of the external nodes has no taxonomy,
 728      * null is returned.
 729      *
 730      */
 731     public static SortedMap<Taxonomy, Integer> obtainDistinctTaxonomyCounts( final PhylogenyNode node ) {
 732         final List<PhylogenyNode> descs = node.getAllExternalDescendants();
 733         final SortedMap<Taxonomy, Integer> tax_map = new TreeMap<Taxonomy, Integer>();
 734         for( final PhylogenyNode n : descs ) {
 735             if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) {
 736                 return null;
 737             }
 738             final Taxonomy t = n.getNodeData().getTaxonomy();
 739             if ( tax_map.containsKey( t ) ) {
 740                 tax_map.put( t, tax_map.get( t ) + 1 );
 741             }
 742             else {
 743                 tax_map.put( t, 1 );
 744             }
 745         }
 746         return tax_map;
 747     }
 748
 749     /**
 750      * Arranges the order of childern for each node of this Phylogeny in such a
 751      * way that either the branch with more children is on top (right) or on
 752      * bottom (left), dependent on the value of boolean order.
 753      *
 754      * @param order
 755      *            decides in which direction to order
 756      * @param pri
 757      */
 758     public static void orderAppearance( final PhylogenyNode n,
 759                                         final boolean order,
 760                                         final boolean order_ext_alphabetically,
 761                                         final DESCENDANT_SORT_PRIORITY pri ) {
 762         if ( n.isExternal() ) {
 763             return;
 764         }
 765         else {
 766             PhylogenyNode temp = null;
 767             if ( ( n.getNumberOfDescendants() == 2 )
 768                     && ( n.getChildNode1().getNumberOfExternalNodes() != n.getChildNode2().getNumberOfExternalNodes() )
 769                     && ( ( n.getChildNode1().getNumberOfExternalNodes() < n.getChildNode2().getNumberOfExternalNodes() ) == order ) ) {
 770                 temp = n.getChildNode1();
 771                 n.setChild1( n.getChildNode2() );
 772                 n.setChild2( temp );
 773             }
 774             else if ( order_ext_alphabetically ) {
 775                 boolean all_ext = true;
 776                 for( final PhylogenyNode i : n.getDescendants() ) {
 777                     if ( !i.isExternal() ) {
 778                         all_ext = false;
 779                         break;
 780                     }
 781                 }
 782                 if ( all_ext ) {
 783                     PhylogenyMethods.sortNodeDescendents( n, pri );
 784                 }
 785             }
 786             for( int i = 0; i < n.getNumberOfDescendants(); ++i ) {
 787                 orderAppearance( n.getChildNode( i ), order, order_ext_alphabetically, pri );
 788             }
 789         }
 790     }
 791
 792     public static void postorderBranchColorAveragingExternalNodeBased( final Phylogeny p ) {
 793         for( final PhylogenyNodeIterator iter = p.iteratorPostorder(); iter.hasNext(); ) {
 794             final PhylogenyNode node = iter.next();
 795             double red = 0.0;
 796             double green = 0.0;
 797             double blue = 0.0;
 798             int n = 0;
 799             if ( node.isInternal() ) {
 800                 //for( final PhylogenyNodeIterator iterator = node.iterateChildNodesForward(); iterator.hasNext(); ) {
 801                 for( int i = 0; i < node.getNumberOfDescendants(); ++i ) {
 802                     final PhylogenyNode child_node = node.getChildNode( i );
 803                     final Color child_color = getBranchColorValue( child_node );
 804                     if ( child_color != null ) {
 805                         ++n;
 806                         red += child_color.getRed();
 807                         green += child_color.getGreen();
 808                         blue += child_color.getBlue();
 809                     }
 810                 }
 811                 setBranchColorValue( node,
 812                                      new Color( ForesterUtil.roundToInt( red / n ),
 813                                                 ForesterUtil.roundToInt( green / n ),
 814                                                 ForesterUtil.roundToInt( blue / n ) ) );
 815             }
 816         }
 817     }
 818
 819     public static final void preOrderReId( final Phylogeny phy ) {
 820         if ( phy.isEmpty() ) {
 821             return;
 822         }
 823         phy.setIdToNodeMap( null );
 824         int i = PhylogenyNode.getNodeCount();
 825         for( final PhylogenyNodeIterator it = phy.iteratorPreorder(); it.hasNext(); ) {
 826             it.next().setId( i++ );
 827         }
 828         PhylogenyNode.setNodeCount( i );
 829     }
 830
 831     public final static Phylogeny[] readPhylogenies( final PhylogenyParser parser, final File file ) throws IOException {
 832         final PhylogenyFactory factory = ParserBasedPhylogenyFactory.getInstance();
 833         final Phylogeny[] trees = factory.create( file, parser );
 834         if ( ( trees == null ) || ( trees.length == 0 ) ) {
 835             throw new PhylogenyParserException( "Unable to parse phylogeny from file: " + file );
 836         }
 837         return trees;
 838     }
 839
 840     public final static Phylogeny[] readPhylogenies( final PhylogenyParser parser, final List<File> files )
 841             throws IOException {
 842         final List<Phylogeny> tree_list = new ArrayList<Phylogeny>();
 843         for( final File file : files ) {
 844             final PhylogenyFactory factory = ParserBasedPhylogenyFactory.getInstance();
 845             final Phylogeny[] trees = factory.create( file, parser );
 846             if ( ( trees == null ) || ( trees.length == 0 ) ) {
 847                 throw new PhylogenyParserException( "Unable to parse phylogeny from file: " + file );
 848             }
 849             tree_list.addAll( Arrays.asList( trees ) );
 850         }
 851         return tree_list.toArray( new Phylogeny[ tree_list.size() ] );
 852     }
 853
 854     public static void removeNode( final PhylogenyNode remove_me, final Phylogeny phylogeny ) {
 855         if ( remove_me.isRoot() ) {
 856             throw new IllegalArgumentException( "ill advised attempt to remove root node" );
 857         }
 858         if ( remove_me.isExternal() ) {
 859             phylogeny.deleteSubtree( remove_me, false );
 860             phylogeny.clearHashIdToNodeMap();
 861             phylogeny.externalNodesHaveChanged();
 862         }
 863         else {
 864             final PhylogenyNode parent = remove_me.getParent();
 865             final List<PhylogenyNode> descs = remove_me.getDescendants();
 866             parent.removeChildNode( remove_me );
 867             for( final PhylogenyNode desc : descs ) {
 868                 parent.addAsChild( desc );
 869                 desc.setDistanceToParent( addPhylogenyDistances( remove_me.getDistanceToParent(),
 870                                                                  desc.getDistanceToParent() ) );
 871             }
 872             remove_me.setParent( null );
 873             phylogeny.clearHashIdToNodeMap();
 874             phylogeny.externalNodesHaveChanged();
 875         }
 876     }
 877
 878     public static List<PhylogenyNode> searchData( final String query,
 879                                                   final Phylogeny phy,
 880                                                   final boolean case_sensitive,
 881                                                   final boolean partial,
 882                                                   final boolean search_domains ) {
 883         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 884         if ( phy.isEmpty() || ( query == null ) ) {
 885             return nodes;
 886         }
 887         if ( ForesterUtil.isEmpty( query ) ) {
 888             return nodes;
 889         }
 890         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 891             final PhylogenyNode node = iter.next();
 892             boolean match = false;
 893             if ( match( node.getName(), query, case_sensitive, partial ) ) {
 894                 match = true;
 895             }
 896             else if ( node.getNodeData().isHasTaxonomy()
 897                     && match( node.getNodeData().getTaxonomy().getTaxonomyCode(), query, case_sensitive, partial ) ) {
 898                 match = true;
 899             }
 900             else if ( node.getNodeData().isHasTaxonomy()
 901                     && match( node.getNodeData().getTaxonomy().getCommonName(), query, case_sensitive, partial ) ) {
 902                 match = true;
 903             }
 904             else if ( node.getNodeData().isHasTaxonomy()
 905                     && match( node.getNodeData().getTaxonomy().getScientificName(), query, case_sensitive, partial ) ) {
 906                 match = true;
 907             }
 908             else if ( node.getNodeData().isHasTaxonomy()
 909                     && ( node.getNodeData().getTaxonomy().getIdentifier() != null )
 910                     && match( node.getNodeData().getTaxonomy().getIdentifier().getValue(),
 911                               query,
 912                               case_sensitive,
 913                               partial ) ) {
 914                 match = true;
 915             }
 916             else if ( node.getNodeData().isHasTaxonomy() && !node.getNodeData().getTaxonomy().getSynonyms().isEmpty() ) {
 917                 final List<String> syns = node.getNodeData().getTaxonomy().getSynonyms();
 918                 I: for( final String syn : syns ) {
 919                     if ( match( syn, query, case_sensitive, partial ) ) {
 920                         match = true;
 921                         break I;
 922                     }
 923                 }
 924             }
 925             if ( !match && node.getNodeData().isHasSequence()
 926                     && match( node.getNodeData().getSequence().getName(), query, case_sensitive, partial ) ) {
 927                 match = true;
 928             }
 929             if ( !match && node.getNodeData().isHasSequence()
 930                     && match( node.getNodeData().getSequence().getSymbol(), query, case_sensitive, partial ) ) {
 931                 match = true;
 932             }
 933             if ( !match
 934                     && node.getNodeData().isHasSequence()
 935                     && ( node.getNodeData().getSequence().getAccession() != null )
 936                     && match( node.getNodeData().getSequence().getAccession().getValue(),
 937                               query,
 938                               case_sensitive,
 939                               partial ) ) {
 940                 match = true;
 941             }
 942             if ( search_domains && !match && node.getNodeData().isHasSequence()
 943                     && ( node.getNodeData().getSequence().getDomainArchitecture() != null ) ) {
 944                 final DomainArchitecture da = node.getNodeData().getSequence().getDomainArchitecture();
 945                 I: for( int i = 0; i < da.getNumberOfDomains(); ++i ) {
 946                     if ( match( da.getDomain( i ).getName(), query, case_sensitive, partial ) ) {
 947                         match = true;
 948                         break I;
 949                     }
 950                 }
 951             }
 952             if ( !match && ( node.getNodeData().getBinaryCharacters() != null ) ) {
 953                 Iterator<String> it = node.getNodeData().getBinaryCharacters().getPresentCharacters().iterator();
 954                 I: while ( it.hasNext() ) {
 955                     if ( match( it.next(), query, case_sensitive, partial ) ) {
 956                         match = true;
 957                         break I;
 958                     }
 959                 }
 960                 it = node.getNodeData().getBinaryCharacters().getGainedCharacters().iterator();
 961                 I: while ( it.hasNext() ) {
 962                     if ( match( it.next(), query, case_sensitive, partial ) ) {
 963                         match = true;
 964                         break I;
 965                     }
 966                 }
 967             }
 968             if ( match ) {
 969                 nodes.add( node );
 970             }
 971         }
 972         return nodes;
 973     }
 974
 975     public static List<PhylogenyNode> searchDataLogicalAnd( final String[] queries,
 976                                                             final Phylogeny phy,
 977                                                             final boolean case_sensitive,
 978                                                             final boolean partial,
 979                                                             final boolean search_domains ) {
 980         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 981         if ( phy.isEmpty() || ( queries == null ) || ( queries.length < 1 ) ) {
 982             return nodes;
 983         }
 984         for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) {
 985             final PhylogenyNode node = iter.next();
 986             boolean all_matched = true;
 987             for( final String query : queries ) {
 988                 boolean match = false;
 989                 if ( ForesterUtil.isEmpty( query ) ) {
 990                     continue;
 991                 }
 992                 if ( match( node.getName(), query, case_sensitive, partial ) ) {
 993                     match = true;
 994                 }
 995                 else if ( node.getNodeData().isHasTaxonomy()
 996                         && match( node.getNodeData().getTaxonomy().getTaxonomyCode(), query, case_sensitive, partial ) ) {
 997                     match = true;
 998                 }
 999                 else if ( node.getNodeData().isHasTaxonomy()
1000                         && match( node.getNodeData().getTaxonomy().getCommonName(), query, case_sensitive, partial ) ) {
1001                     match = true;
1002                 }
1003                 else if ( node.getNodeData().isHasTaxonomy()
1004                         && match( node.getNodeData().getTaxonomy().getScientificName(), query, case_sensitive, partial ) ) {
1005                     match = true;
1006                 }
1007                 else if ( node.getNodeData().isHasTaxonomy()
1008                         && ( node.getNodeData().getTaxonomy().getIdentifier() != null )
1009                         && match( node.getNodeData().getTaxonomy().getIdentifier().getValue(),
1010                                   query,
1011                                   case_sensitive,
1012                                   partial ) ) {
1013                     match = true;
1014                 }
1015                 else if ( node.getNodeData().isHasTaxonomy()
1016                         && !node.getNodeData().getTaxonomy().getSynonyms().isEmpty() ) {
1017                     final List<String> syns = node.getNodeData().getTaxonomy().getSynonyms();
1018                     I: for( final String syn : syns ) {
1019                         if ( match( syn, query, case_sensitive, partial ) ) {
1020                             match = true;
1021                             break I;
1022                         }
1023                     }
1024                 }
1025                 if ( !match && node.getNodeData().isHasSequence()
1026                         && match( node.getNodeData().getSequence().getName(), query, case_sensitive, partial ) ) {
1027                     match = true;
1028                 }
1029                 if ( !match && node.getNodeData().isHasSequence()
1030                         && match( node.getNodeData().getSequence().getSymbol(), query, case_sensitive, partial ) ) {
1031                     match = true;
1032                 }
1033                 if ( !match
1034                         && node.getNodeData().isHasSequence()
1035                         && ( node.getNodeData().getSequence().getAccession() != null )
1036                         && match( node.getNodeData().getSequence().getAccession().getValue(),
1037                                   query,
1038                                   case_sensitive,
1039                                   partial ) ) {
1040                     match = true;
1041                 }
1042                 if ( search_domains && !match && node.getNodeData().isHasSequence()
1043                         && ( node.getNodeData().getSequence().getDomainArchitecture() != null ) ) {
1044                     final DomainArchitecture da = node.getNodeData().getSequence().getDomainArchitecture();
1045                     I: for( int i = 0; i < da.getNumberOfDomains(); ++i ) {
1046                         if ( match( da.getDomain( i ).getName(), query, case_sensitive, partial ) ) {
1047                             match = true;
1048                             break I;
1049                         }
1050                     }
1051                 }
1052                 if ( !match && ( node.getNodeData().getBinaryCharacters() != null ) ) {
1053                     Iterator<String> it = node.getNodeData().getBinaryCharacters().getPresentCharacters().iterator();
1054                     I: while ( it.hasNext() ) {
1055                         if ( match( it.next(), query, case_sensitive, partial ) ) {
1056                             match = true;
1057                             break I;
1058                         }
1059                     }
1060                     it = node.getNodeData().getBinaryCharacters().getGainedCharacters().iterator();
1061                     I: while ( it.hasNext() ) {
1062                         if ( match( it.next(), query, case_sensitive, partial ) ) {
1063                             match = true;
1064                             break I;
1065                         }
1066                     }
1067                 }
1068                 if ( !match ) {
1069                     all_matched = false;
1070                     break;
1071                 }
1072             }
1073             if ( all_matched ) {
1074                 nodes.add( node );
1075             }
1076         }
1077         return nodes;
1078     }
1079
1080     /**
1081      * Convenience method.
1082      * Sets value for the first confidence value (created if not present, values overwritten otherwise).
1083      */
1084     public static void setBootstrapConfidence( final PhylogenyNode node, final double bootstrap_confidence_value ) {
1085         setConfidence( node, bootstrap_confidence_value, "bootstrap" );
1086     }
1087
1088     public static void setBranchColorValue( final PhylogenyNode node, final Color color ) {
1089         if ( node.getBranchData().getBranchColor() == null ) {
1090             node.getBranchData().setBranchColor( new BranchColor() );
1091         }
1092         node.getBranchData().getBranchColor().setValue( color );
1093     }
1094
1095     /**
1096      * Convenience method
1097      */
1098     public static void setBranchWidthValue( final PhylogenyNode node, final double branch_width_value ) {
1099         node.getBranchData().setBranchWidth( new BranchWidth( branch_width_value ) );
1100     }
1101
1102     /**
1103      * Convenience method.
1104      * Sets value for the first confidence value (created if not present, values overwritten otherwise).
1105      */
1106     public static void setConfidence( final PhylogenyNode node, final double confidence_value ) {
1107         setConfidence( node, confidence_value, "" );
1108     }
1109
1110     /**
1111      * Convenience method.
1112      * Sets value for the first confidence value (created if not present, values overwritten otherwise).
1113      */
1114     public static void setConfidence( final PhylogenyNode node, final double confidence_value, final String type ) {
1115         Confidence c = null;
1116         if ( node.getBranchData().getNumberOfConfidences() > 0 ) {
1117             c = node.getBranchData().getConfidence( 0 );
1118         }
1119         else {
1120             c = new Confidence();
1121             node.getBranchData().addConfidence( c );
1122         }
1123         c.setType( type );
1124         c.setValue( confidence_value );
1125     }
1126
1127     public static void setScientificName( final PhylogenyNode node, final String scientific_name ) {
1128         if ( !node.getNodeData().isHasTaxonomy() ) {
1129             node.getNodeData().setTaxonomy( new Taxonomy() );
1130         }
1131         node.getNodeData().getTaxonomy().setScientificName( scientific_name );
1132     }
1133
1134     /**
1135      * Convenience method to set the taxonomy code of a phylogeny node.
1136      *
1137      *
1138      * @param node
1139      * @param taxonomy_code
1140      * @throws PhyloXmlDataFormatException
1141      */
1142     public static void setTaxonomyCode( final PhylogenyNode node, final String taxonomy_code )
1143             throws PhyloXmlDataFormatException {
1144         if ( !node.getNodeData().isHasTaxonomy() ) {
1145             node.getNodeData().setTaxonomy( new Taxonomy() );
1146         }
1147         node.getNodeData().getTaxonomy().setTaxonomyCode( taxonomy_code );
1148     }
1149
1150     final static public void sortNodeDescendents( final PhylogenyNode node, final DESCENDANT_SORT_PRIORITY pri ) {
1151         class PhylogenyNodeSortTaxonomyPriority implements Comparator<PhylogenyNode> {
1152
1153             @Override
1154             public int compare( final PhylogenyNode n1, final PhylogenyNode n2 ) {
1155                 if ( n1.getNodeData().isHasTaxonomy() && n2.getNodeData().isHasTaxonomy() ) {
1156                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getScientificName() ) )
1157                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getScientificName() ) ) ) {
1158                         return n1.getNodeData().getTaxonomy().getScientificName().toLowerCase()
1159                                 .compareTo( n2.getNodeData().getTaxonomy().getScientificName().toLowerCase() );
1160                     }
1161                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getTaxonomyCode() ) )
1162                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) {
1163                         return n1.getNodeData().getTaxonomy().getTaxonomyCode()
1164                                 .compareTo( n2.getNodeData().getTaxonomy().getTaxonomyCode() );
1165                     }
1166                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getCommonName() ) )
1167                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getCommonName() ) ) ) {
1168                         return n1.getNodeData().getTaxonomy().getCommonName().toLowerCase()
1169                                 .compareTo( n2.getNodeData().getTaxonomy().getCommonName().toLowerCase() );
1170                     }
1171                 }
1172                 if ( n1.getNodeData().isHasSequence() && n2.getNodeData().isHasSequence() ) {
1173                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getName() ) )
1174                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getName() ) ) ) {
1175                         return n1.getNodeData().getSequence().getName().toLowerCase()
1176                                 .compareTo( n2.getNodeData().getSequence().getName().toLowerCase() );
1177                     }
1178                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getSymbol() ) )
1179                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getSymbol() ) ) ) {
1180                         return n1.getNodeData().getSequence().getSymbol()
1181                                 .compareTo( n2.getNodeData().getSequence().getSymbol() );
1182                     }
1183                     if ( ( n1.getNodeData().getSequence().getAccession() != null )
1184                             && ( n2.getNodeData().getSequence().getAccession() != null )
1185                             && !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getAccession().getValue() )
1186                             && !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getAccession().getValue() ) ) {
1187                         return n1.getNodeData().getSequence().getAccession().getValue()
1188                                 .compareTo( n2.getNodeData().getSequence().getAccession().getValue() );
1189                     }
1190                 }
1191                 if ( ( !ForesterUtil.isEmpty( n1.getName() ) ) && ( !ForesterUtil.isEmpty( n2.getName() ) ) ) {
1192                     return n1.getName().toLowerCase().compareTo( n2.getName().toLowerCase() );
1193                 }
1194                 return 0;
1195             }
1196         }
1197         class PhylogenyNodeSortSequencePriority implements Comparator<PhylogenyNode> {
1198
1199             @Override
1200             public int compare( final PhylogenyNode n1, final PhylogenyNode n2 ) {
1201                 if ( n1.getNodeData().isHasSequence() && n2.getNodeData().isHasSequence() ) {
1202                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getName() ) )
1203                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getName() ) ) ) {
1204                         return n1.getNodeData().getSequence().getName().toLowerCase()
1205                                 .compareTo( n2.getNodeData().getSequence().getName().toLowerCase() );
1206                     }
1207                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getSymbol() ) )
1208                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getSymbol() ) ) ) {
1209                         return n1.getNodeData().getSequence().getSymbol()
1210                                 .compareTo( n2.getNodeData().getSequence().getSymbol() );
1211                     }
1212                     if ( ( n1.getNodeData().getSequence().getAccession() != null )
1213                             && ( n2.getNodeData().getSequence().getAccession() != null )
1214                             && !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getAccession().getValue() )
1215                             && !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getAccession().getValue() ) ) {
1216                         return n1.getNodeData().getSequence().getAccession().getValue()
1217                                 .compareTo( n2.getNodeData().getSequence().getAccession().getValue() );
1218                     }
1219                 }
1220                 if ( n1.getNodeData().isHasTaxonomy() && n2.getNodeData().isHasTaxonomy() ) {
1221                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getScientificName() ) )
1222                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getScientificName() ) ) ) {
1223                         return n1.getNodeData().getTaxonomy().getScientificName().toLowerCase()
1224                                 .compareTo( n2.getNodeData().getTaxonomy().getScientificName().toLowerCase() );
1225                     }
1226                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getTaxonomyCode() ) )
1227                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) {
1228                         return n1.getNodeData().getTaxonomy().getTaxonomyCode()
1229                                 .compareTo( n2.getNodeData().getTaxonomy().getTaxonomyCode() );
1230                     }
1231                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getCommonName() ) )
1232                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getCommonName() ) ) ) {
1233                         return n1.getNodeData().getTaxonomy().getCommonName().toLowerCase()
1234                                 .compareTo( n2.getNodeData().getTaxonomy().getCommonName().toLowerCase() );
1235                     }
1236                 }
1237                 if ( ( !ForesterUtil.isEmpty( n1.getName() ) ) && ( !ForesterUtil.isEmpty( n2.getName() ) ) ) {
1238                     return n1.getName().toLowerCase().compareTo( n2.getName().toLowerCase() );
1239                 }
1240                 return 0;
1241             }
1242         }
1243         class PhylogenyNodeSortNodeNamePriority implements Comparator<PhylogenyNode> {
1244
1245             @Override
1246             public int compare( final PhylogenyNode n1, final PhylogenyNode n2 ) {
1247                 if ( ( !ForesterUtil.isEmpty( n1.getName() ) ) && ( !ForesterUtil.isEmpty( n2.getName() ) ) ) {
1248                     return n1.getName().toLowerCase().compareTo( n2.getName().toLowerCase() );
1249                 }
1250                 if ( n1.getNodeData().isHasTaxonomy() && n2.getNodeData().isHasTaxonomy() ) {
1251                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getScientificName() ) )
1252                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getScientificName() ) ) ) {
1253                         return n1.getNodeData().getTaxonomy().getScientificName().toLowerCase()
1254                                 .compareTo( n2.getNodeData().getTaxonomy().getScientificName().toLowerCase() );
1255                     }
1256                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getTaxonomyCode() ) )
1257                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) {
1258                         return n1.getNodeData().getTaxonomy().getTaxonomyCode()
1259                                 .compareTo( n2.getNodeData().getTaxonomy().getTaxonomyCode() );
1260                     }
1261                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getCommonName() ) )
1262                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getCommonName() ) ) ) {
1263                         return n1.getNodeData().getTaxonomy().getCommonName().toLowerCase()
1264                                 .compareTo( n2.getNodeData().getTaxonomy().getCommonName().toLowerCase() );
1265                     }
1266                 }
1267                 if ( n1.getNodeData().isHasSequence() && n2.getNodeData().isHasSequence() ) {
1268                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getName() ) )
1269                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getName() ) ) ) {
1270                         return n1.getNodeData().getSequence().getName().toLowerCase()
1271                                 .compareTo( n2.getNodeData().getSequence().getName().toLowerCase() );
1272                     }
1273                     if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getSymbol() ) )
1274                             && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getSymbol() ) ) ) {
1275                         return n1.getNodeData().getSequence().getSymbol()
1276                                 .compareTo( n2.getNodeData().getSequence().getSymbol() );
1277                     }
1278                     if ( ( n1.getNodeData().getSequence().getAccession() != null )
1279                             && ( n2.getNodeData().getSequence().getAccession() != null )
1280                             && !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getAccession().getValue() )
1281                             && !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getAccession().getValue() ) ) {
1282                         return n1.getNodeData().getSequence().getAccession().getValue()
1283                                 .compareTo( n2.getNodeData().getSequence().getAccession().getValue() );
1284                     }
1285                 }
1286                 return 0;
1287             }
1288         }
1289         Comparator<PhylogenyNode> c;
1290         switch ( pri ) {
1291             case SEQUENCE:
1292                 c = new PhylogenyNodeSortSequencePriority();
1293                 break;
1294             case NODE_NAME:
1295                 c = new PhylogenyNodeSortNodeNamePriority();
1296                 break;
1297             default:
1298                 c = new PhylogenyNodeSortTaxonomyPriority();
1299         }
1300         final List<PhylogenyNode> descs = node.getDescendants();
1301         Collections.sort( descs, c );
1302         int i = 0;
1303         for( final PhylogenyNode desc : descs ) {
1304             node.setChildNode( i++, desc );
1305         }
1306     }
1307
1308     /**
1309      * Removes from Phylogeny to_be_stripped all external Nodes which are
1310      * associated with a species NOT found in Phylogeny reference.
1311      *
1312      * @param reference
1313      *            a reference Phylogeny
1314      * @param to_be_stripped
1315      *            Phylogeny to be stripped
1316      * @return nodes removed from to_be_stripped
1317      */
1318     public static List<PhylogenyNode> taxonomyBasedDeletionOfExternalNodes( final Phylogeny reference,
1319                                                                             final Phylogeny to_be_stripped ) {
1320         final Set<String> ref_ext_taxo = new HashSet<String>();
1321         for( final PhylogenyNodeIterator it = reference.iteratorExternalForward(); it.hasNext(); ) {
1322             final PhylogenyNode n = it.next();
1323             if ( !n.getNodeData().isHasTaxonomy() ) {
1324                 throw new IllegalArgumentException( "no taxonomic data in node: " + n );
1325             }
1326             //  ref_ext_taxo.add( getSpecies( n ) );
1327             if ( !ForesterUtil.isEmpty( n.getNodeData().getTaxonomy().getScientificName() ) ) {
1328                 ref_ext_taxo.add( n.getNodeData().getTaxonomy().getScientificName() );
1329             }
1330             if ( !ForesterUtil.isEmpty( n.getNodeData().getTaxonomy().getTaxonomyCode() ) ) {
1331                 ref_ext_taxo.add( n.getNodeData().getTaxonomy().getTaxonomyCode() );
1332             }
1333         }
1334         final ArrayList<PhylogenyNode> nodes_to_delete = new ArrayList<PhylogenyNode>();
1335         for( final PhylogenyNodeIterator it = to_be_stripped.iteratorExternalForward(); it.hasNext(); ) {
1336             final PhylogenyNode n = it.next();
1337             if ( !n.getNodeData().isHasTaxonomy() ) {
1338                 nodes_to_delete.add( n );
1339             }
1340             else if ( !( ref_ext_taxo.contains( n.getNodeData().getTaxonomy().getScientificName() ) )
1341                     && !( ref_ext_taxo.contains( n.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) {
1342                 nodes_to_delete.add( n );
1343             }
1344         }
1345         for( final PhylogenyNode n : nodes_to_delete ) {
1346             to_be_stripped.deleteSubtree( n, true );
1347         }
1348         to_be_stripped.clearHashIdToNodeMap();
1349         to_be_stripped.externalNodesHaveChanged();
1350         return nodes_to_delete;
1351     }
1352
1353     final static public void transferInternalNamesToBootstrapSupport( final Phylogeny phy ) {
1354         final PhylogenyNodeIterator it = phy.iteratorPostorder();
1355         while ( it.hasNext() ) {
1356             final PhylogenyNode n = it.next();
1357             if ( !n.isExternal() && !ForesterUtil.isEmpty( n.getName() ) ) {
1358                 double value = -1;
1359                 try {
1360                     value = Double.parseDouble( n.getName() );
1361                 }
1362                 catch ( final NumberFormatException e ) {
1363                     throw new IllegalArgumentException( "failed to parse number from [" + n.getName() + "]: "
1364                             + e.getLocalizedMessage() );
1365                 }
1366                 if ( value >= 0.0 ) {
1367                     n.getBranchData().addConfidence( new Confidence( value, "bootstrap" ) );
1368                     n.setName( "" );
1369                 }
1370             }
1371         }
1372     }
1373
1374     final static public void transferInternalNodeNamesToConfidence( final Phylogeny phy ) {
1375         final PhylogenyNodeIterator it = phy.iteratorPostorder();
1376         while ( it.hasNext() ) {
1377             final PhylogenyNode n = it.next();
1378             if ( !n.isExternal() && !n.getBranchData().isHasConfidences() ) {
1379                 if ( !ForesterUtil.isEmpty( n.getName() ) ) {
1380                     double d = -1.0;
1381                     try {
1382                         d = Double.parseDouble( n.getName() );
1383                     }
1384                     catch ( final Exception e ) {
1385                         d = -1.0;
1386                     }
1387                     if ( d >= 0.0 ) {
1388                         n.getBranchData().addConfidence( new Confidence( d, "" ) );
1389                         n.setName( "" );
1390                     }
1391                 }
1392             }
1393         }
1394     }
1395
1396     final static public void transferNodeNameToField( final Phylogeny phy,
1397                                                       final PhylogenyNodeField field,
1398                                                       final boolean external_only ) throws PhyloXmlDataFormatException {
1399         final PhylogenyNodeIterator it = phy.iteratorPostorder();
1400         while ( it.hasNext() ) {
1401             final PhylogenyNode n = it.next();
1402             if ( external_only && n.isInternal() ) {
1403                 continue;
1404             }
1405             final String name = n.getName().trim();
1406             if ( !ForesterUtil.isEmpty( name ) ) {
1407                 switch ( field ) {
1408                     case TAXONOMY_CODE:
1409                         n.setName( "" );
1410                         setTaxonomyCode( n, name );
1411                         break;
1412                     case TAXONOMY_SCIENTIFIC_NAME:
1413                         n.setName( "" );
1414                         if ( !n.getNodeData().isHasTaxonomy() ) {
1415                             n.getNodeData().setTaxonomy( new Taxonomy() );
1416                         }
1417                         n.getNodeData().getTaxonomy().setScientificName( name );
1418                         break;
1419                     case TAXONOMY_COMMON_NAME:
1420                         n.setName( "" );
1421                         if ( !n.getNodeData().isHasTaxonomy() ) {
1422                             n.getNodeData().setTaxonomy( new Taxonomy() );
1423                         }
1424                         n.getNodeData().getTaxonomy().setCommonName( name );
1425                         break;
1426                     case SEQUENCE_SYMBOL:
1427                         n.setName( "" );
1428                         if ( !n.getNodeData().isHasSequence() ) {
1429                             n.getNodeData().setSequence( new Sequence() );
1430                         }
1431                         n.getNodeData().getSequence().setSymbol( name );
1432                         break;
1433                     case SEQUENCE_NAME:
1434                         n.setName( "" );
1435                         if ( !n.getNodeData().isHasSequence() ) {
1436                             n.getNodeData().setSequence( new Sequence() );
1437                         }
1438                         n.getNodeData().getSequence().setName( name );
1439                         break;
1440                     case TAXONOMY_ID_UNIPROT_1: {
1441                         if ( !n.getNodeData().isHasTaxonomy() ) {
1442                             n.getNodeData().setTaxonomy( new Taxonomy() );
1443                         }
1444                         String id = name;
1445                         final int i = name.indexOf( '_' );
1446                         if ( i > 0 ) {
1447                             id = name.substring( 0, i );
1448                         }
1449                         else {
1450                             n.setName( "" );
1451                         }
1452                         n.getNodeData().getTaxonomy()
1453                                 .setIdentifier( new Identifier( id, PhyloXmlUtil.UNIPROT_TAX_PROVIDER ) );
1454                         break;
1455                     }
1456                     case TAXONOMY_ID_UNIPROT_2: {
1457                         if ( !n.getNodeData().isHasTaxonomy() ) {
1458                             n.getNodeData().setTaxonomy( new Taxonomy() );
1459                         }
1460                         String id = name;
1461                         final int i = name.indexOf( '_' );
1462                         if ( i > 0 ) {
1463                             id = name.substring( i + 1, name.length() );
1464                         }
1465                         else {
1466                             n.setName( "" );
1467                         }
1468                         n.getNodeData().getTaxonomy()
1469                                 .setIdentifier( new Identifier( id, PhyloXmlUtil.UNIPROT_TAX_PROVIDER ) );
1470                         break;
1471                     }
1472                     case TAXONOMY_ID: {
1473                         if ( !n.getNodeData().isHasTaxonomy() ) {
1474                             n.getNodeData().setTaxonomy( new Taxonomy() );
1475                         }
1476                         n.getNodeData().getTaxonomy().setIdentifier( new Identifier( name ) );
1477                         break;
1478                     }
1479                 }
1480             }
1481         }
1482     }
1483
1484     static double addPhylogenyDistances( final double a, final double b ) {
1485         if ( ( a >= 0.0 ) && ( b >= 0.0 ) ) {
1486             return a + b;
1487         }
1488         else if ( a >= 0.0 ) {
1489             return a;
1490         }
1491         else if ( b >= 0.0 ) {
1492             return b;
1493         }
1494         return PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT;
1495     }
1496
1497     /**
1498      * Deep copies the phylogeny originating from this node.
1499      */
1500     static PhylogenyNode copySubTree( final PhylogenyNode source ) {
1501         if ( source == null ) {
1502             return null;
1503         }
1504         else {
1505             final PhylogenyNode newnode = source.copyNodeData();
1506             if ( !source.isExternal() ) {
1507                 for( int i = 0; i < source.getNumberOfDescendants(); ++i ) {
1508                     newnode.setChildNode( i, PhylogenyMethods.copySubTree( source.getChildNode( i ) ) );
1509                 }
1510             }
1511             return newnode;
1512         }
1513     }
1514
1515     /**
1516      * Shallow copies the phylogeny originating from this node.
1517      */
1518     static PhylogenyNode copySubTreeShallow( final PhylogenyNode source ) {
1519         if ( source == null ) {
1520             return null;
1521         }
1522         else {
1523             final PhylogenyNode newnode = source.copyNodeDataShallow();
1524             if ( !source.isExternal() ) {
1525                 for( int i = 0; i < source.getNumberOfDescendants(); ++i ) {
1526                     newnode.setChildNode( i, PhylogenyMethods.copySubTreeShallow( source.getChildNode( i ) ) );
1527                 }
1528             }
1529             return newnode;
1530         }
1531     }
1532
1533     /**
1534      * Calculates the distance between PhylogenyNodes n1 and n2.
1535      * PRECONDITION: n1 is a descendant of n2.
1536      *
1537      * @param n1
1538      *            a descendant of n2
1539      * @param n2
1540      * @return distance between n1 and n2
1541      */
1542     private static double getDistance( PhylogenyNode n1, final PhylogenyNode n2 ) {
1543         double d = 0.0;
1544         while ( n1 != n2 ) {
1545             if ( n1.getDistanceToParent() > 0.0 ) {
1546                 d += n1.getDistanceToParent();
1547             }
1548             n1 = n1.getParent();
1549         }
1550         return d;
1551     }
1552
1553     private static boolean match( final String s,
1554                                   final String query,
1555                                   final boolean case_sensitive,
1556                                   final boolean partial ) {
1557         if ( ForesterUtil.isEmpty( s ) || ForesterUtil.isEmpty( query ) ) {
1558             return false;
1559         }
1560         String my_s = s.trim();
1561         String my_query = query.trim();
1562         if ( !case_sensitive ) {
1563             my_s = my_s.toLowerCase();
1564             my_query = my_query.toLowerCase();
1565         }
1566         if ( partial ) {
1567             return my_s.indexOf( my_query ) >= 0;
1568         }
1569         else {
1570             return my_s.equals( my_query );
1571         }
1572     }
1573
1574     public static enum DESCENDANT_SORT_PRIORITY {
1575         TAXONOMY, SEQUENCE, NODE_NAME;
1576     }
1577
1578     public static enum PhylogenyNodeField {
1579         CLADE_NAME,
1580         TAXONOMY_CODE,
1581         TAXONOMY_SCIENTIFIC_NAME,
1582         TAXONOMY_COMMON_NAME,
1583         SEQUENCE_SYMBOL,
1584         SEQUENCE_NAME,
1585         TAXONOMY_ID_UNIPROT_1,
1586         TAXONOMY_ID_UNIPROT_2,
1587         TAXONOMY_ID;
1588     }
1589 }