forester/java/src/org/forester/phylogeny/Phylogeny.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 // Copyright (C) 2000-2001 Washington University School of Medicine
   8 // and Howard Hughes Medical Institute
   9 // All rights reserved
  10 //
  11 // This library is free software; you can redistribute it and/or
  12 // modify it under the terms of the GNU Lesser General Public
  13 // License as published by the Free Software Foundation; either
  14 // version 2.1 of the License, or (at your option) any later version.
  15 //
  16 // This library is distributed in the hope that it will be useful,
  17 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  18 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  19 // Lesser General Public License for more details.
  20 //
  21 // You should have received a copy of the GNU Lesser General Public
  22 // License along with this library; if not, write to the Free Software
  23 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
  24 //
  25 // Contact: phylosoft @ gmail . com
  26 // WWW: www.phylosoft.org/forester
  27
  28 package org.forester.phylogeny;
  29
  30 import java.io.IOException;
  31 import java.util.ArrayList;
  32 import java.util.Arrays;
  33 import java.util.Collection;
  34 import java.util.HashMap;
  35 import java.util.Iterator;
  36 import java.util.List;
  37 import java.util.Map;
  38 import java.util.NoSuchElementException;
  39 import java.util.Vector;
  40
  41 import org.forester.io.writers.PhylogenyWriter;
  42 import org.forester.phylogeny.PhylogenyNodeI.NH_CONVERSION_SUPPORT_VALUE_STYLE;
  43 import org.forester.phylogeny.data.BranchData;
  44 import org.forester.phylogeny.data.Confidence;
  45 import org.forester.phylogeny.data.Identifier;
  46 import org.forester.phylogeny.data.PhylogenyDataUtil;
  47 import org.forester.phylogeny.data.Sequence;
  48 import org.forester.phylogeny.data.SequenceRelation;
  49 import org.forester.phylogeny.data.SequenceRelation.SEQUENCE_RELATION_TYPE;
  50 import org.forester.phylogeny.iterators.ExternalForwardIterator;
  51 import org.forester.phylogeny.iterators.LevelOrderTreeIterator;
  52 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
  53 import org.forester.phylogeny.iterators.PostorderTreeIterator;
  54 import org.forester.phylogeny.iterators.PreorderTreeIterator;
  55 import org.forester.util.FailedConditionCheckException;
  56 import org.forester.util.ForesterUtil;
  57
  58 public class Phylogeny {
  59
  60     public final static boolean                                 ALLOW_MULTIPLE_PARENTS_DEFAULT = false;
  61     private PhylogenyNode                                       _root;
  62     private boolean                                             _rooted;
  63     private boolean                                             _allow_multiple_parents;
  64     private String                                              _name;
  65     private String                                              _type;
  66     private String                                              _description;
  67     private String                                              _distance_unit;
  68     private Confidence                                          _confidence;
  69     private Identifier                                          _identifier;
  70     private boolean                                             _rerootable;
  71     private HashMap<Integer, PhylogenyNode>                     _idhash;
  72     private List<PhylogenyNode>                                 _external_nodes_set;
  73     private Collection<Sequence>                                _sequenceRelationQueries;
  74     private Collection<SequenceRelation.SEQUENCE_RELATION_TYPE> _relevant_sequence_relation_types;
  75
  76     /**
  77      * Default Phylogeny constructor. Constructs an empty Phylogeny.
  78      */
  79     public Phylogeny() {
  80         init();
  81     }
  82
  83     /**
  84      * Adds this Phylogeny to the list of child nodes of PhylogenyNode parent
  85      * and sets the parent of this to parent.
  86      *
  87      * @param n
  88      *            the PhylogenyNode to add
  89      */
  90     public void addAsChild( final PhylogenyNode parent ) {
  91         if ( isEmpty() ) {
  92             throw new IllegalArgumentException( "Attempt to add an empty tree." );
  93         }
  94         if ( !isRooted() ) {
  95             throw new IllegalArgumentException( "Attempt to add an unrooted tree." );
  96         }
  97         parent.addAsChild( getRoot() );
  98         externalNodesHaveChanged();
  99     }
 100
 101     public void addAsSibling( final PhylogenyNode sibling ) {
 102         if ( isEmpty() ) {
 103             throw new IllegalArgumentException( "Attempt to add an empty tree." );
 104         }
 105         if ( !isRooted() ) {
 106             throw new IllegalArgumentException( "Attempt to add an unrooted tree." );
 107         }
 108         final int sibling_index = sibling.getChildNodeIndex();
 109         final PhylogenyNode new_node = new PhylogenyNode();
 110         final PhylogenyNode sibling_parent = sibling.getParent();
 111         new_node.setChild1( sibling );
 112         new_node.setChild2( getRoot() );
 113         new_node.setParent( sibling_parent );
 114         sibling.setParent( new_node );
 115         sibling_parent.setChildNode( sibling_index, new_node );
 116         final double new_dist = sibling.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ? PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT
 117                 : sibling.getDistanceToParent() / 2;
 118         new_node.setDistanceToParent( new_dist );
 119         sibling.setDistanceToParent( new_dist );
 120         externalNodesHaveChanged();
 121     }
 122
 123     /**
 124      * This calculates the height of the subtree emanating at n for rooted,
 125      * tree-shaped phylogenies
 126      *
 127      * @param n
 128      *            the root-node of a subtree
 129      * @return the height of the subtree emanating at n
 130      */
 131     public double calculateSubtreeHeight( final PhylogenyNode n ) {
 132         if ( n.isExternal() || n.isCollapse() ) {
 133             return ForesterUtil.isLargerOrEqualToZero( n.getDistanceToParent() );
 134         }
 135         else {
 136             double max = -Double.MAX_VALUE;
 137             for( int i = 0; i < n.getNumberOfDescendants(); ++i ) {
 138                 final double l = calculateSubtreeHeight( n.getChildNode( i ) );
 139                 if ( l > max ) {
 140                     max = l;
 141                 }
 142             }
 143             return max + ForesterUtil.isLargerOrEqualToZero( n.getDistanceToParent() );
 144         }
 145     }
 146
 147     /**
 148      * Returns a deep copy of this Phylogeny.
 149      * <p>
 150      * (The resulting Phylogeny has its references in the external nodes
 151      * corrected, if they are lacking/obsolete in this.)
 152      */
 153     public Phylogeny copy() {
 154         return copy( _root );
 155     }
 156
 157     /**
 158      * Returns a shallow copy of this Phylogeny.
 159      * <p>
 160      * (The resulting Phylogeny has its references in the external nodes
 161      * corrected, if they are lacking/obsolete in this.)
 162      */
 163     public Phylogeny copyShallow() {
 164         return copyShallow( _root );
 165     }
 166
 167     public Phylogeny copyShallow( final PhylogenyNode source ) {
 168         final Phylogeny tree = new Phylogeny();
 169         if ( isEmpty() ) {
 170             tree.init();
 171             return tree;
 172         }
 173         tree._rooted = _rooted;
 174         tree._name = _name;
 175         tree._description = _description;
 176         tree._type = _type;
 177         tree._rerootable = _rerootable;
 178         tree._distance_unit = _distance_unit;
 179         tree._confidence = _confidence;
 180         tree._identifier = _identifier;
 181         tree.setAllowMultipleParents( isAllowMultipleParents() );
 182         tree._root = PhylogenyMethods.copySubTreeShallow( source );
 183         return tree;
 184     }
 185
 186     /**
 187      * Returns a deep copy of this Phylogeny.
 188      * <p>
 189      * (The resulting Phylogeny has its references in the external nodes
 190      * corrected, if they are lacking/obsolete in this.)
 191      */
 192     public Phylogeny copy( final PhylogenyNode source ) {
 193         final Phylogeny tree = new Phylogeny();
 194         if ( isEmpty() ) {
 195             tree.init();
 196             return tree;
 197         }
 198         tree._rooted = _rooted;
 199         tree._name = new String( _name );
 200         tree._description = new String( _description );
 201         tree._type = new String( _type );
 202         tree._rerootable = _rerootable;
 203         tree._distance_unit = new String( _distance_unit );
 204         if ( _confidence != null ) {
 205             tree._confidence = ( Confidence ) _confidence.copy();
 206         }
 207         if ( _identifier != null ) {
 208             tree._identifier = ( Identifier ) _identifier.copy();
 209         }
 210         tree.setAllowMultipleParents( isAllowMultipleParents() );
 211         tree._root = PhylogenyMethods.copySubTree( source );
 212         return tree;
 213     }
 214
 215     /**
 216      * Need the delete and/or rehash _idhash (not done automatically
 217      * to allow client multiple deletions in linear time).
 218      * Need to call 'recalculateNumberOfExternalDescendants(boolean)' after this
 219      * if tree is to be displayed.
 220      *
 221      * @param remove_us the parent node of the subtree to be deleted
 222      */
 223     public void deleteSubtree( final PhylogenyNode remove_us, final boolean collapse_resulting_node_with_one_desc ) {
 224         if ( isEmpty() ) {
 225             return;
 226         }
 227         if ( remove_us.isRoot() ) {
 228             init();
 229             return;
 230         }
 231         if ( !collapse_resulting_node_with_one_desc ) {
 232             remove_us.getParent().removeChildNode( remove_us );
 233         }
 234         else {
 235             final PhylogenyNode removed_node = remove_us;
 236             final PhylogenyNode p = remove_us.getParent();
 237             if ( p.isRoot() ) {
 238                 if ( p.getNumberOfDescendants() == 2 ) {
 239                     if ( removed_node.isFirstChildNode() ) {
 240                         setRoot( getRoot().getChildNode( 1 ) );
 241                         getRoot().setParent( null );
 242                     }
 243                     else {
 244                         setRoot( getRoot().getChildNode( 0 ) );
 245                         getRoot().setParent( null );
 246                     }
 247                 }
 248                 else {
 249                     p.removeChildNode( removed_node.getChildNodeIndex() );
 250                 }
 251             }
 252             else {
 253                 final PhylogenyNode pp = removed_node.getParent().getParent();
 254                 if ( p.getNumberOfDescendants() == 2 ) {
 255                     final int pi = p.getChildNodeIndex();
 256                     if ( removed_node.isFirstChildNode() ) {
 257                         p.getChildNode( 1 ).setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p
 258                                 .getDistanceToParent(), p.getChildNode( 1 ).getDistanceToParent() ) );
 259                         pp.setChildNode( pi, p.getChildNode( 1 ) );
 260                     }
 261                     else {
 262                         p.getChildNode( 0 ).setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p
 263                                 .getDistanceToParent(), p.getChildNode( 0 ).getDistanceToParent() ) );
 264                         pp.setChildNode( pi, p.getChildNode( 0 ) );
 265                     }
 266                 }
 267                 else {
 268                     p.removeChildNode( removed_node.getChildNodeIndex() );
 269                 }
 270             }
 271         }
 272         remove_us.setParent( null );
 273         setIdHash( null );
 274         externalNodesHaveChanged();
 275     }
 276
 277     public void externalNodesHaveChanged() {
 278         _external_nodes_set = null;
 279     }
 280
 281     public String[] getAllExternalNodeNames() {
 282         int i = 0;
 283         if ( isEmpty() ) {
 284             return null;
 285         }
 286         final String[] names = new String[ getNumberOfExternalNodes() ];
 287         for( final PhylogenyNodeIterator iter = iteratorExternalForward(); iter.hasNext(); ) {
 288             names[ i++ ] = new String( iter.next().getName() );
 289         }
 290         return names;
 291     }
 292
 293     public Confidence getConfidence() {
 294         return _confidence;
 295     }
 296
 297     public String getDescription() {
 298         return _description;
 299     }
 300
 301     public String getDistanceUnit() {
 302         return _distance_unit;
 303     }
 304
 305     /**
 306      *
 307      * Warning. The order of the returned nodes is random
 308      * -- and hence cannot be relied on.
 309      *
 310      * @return Unordered set of PhylogenyNode
 311      */
 312     public List<PhylogenyNode> getExternalNodes() {
 313         if ( _external_nodes_set == null ) {
 314             _external_nodes_set = new ArrayList<PhylogenyNode>();
 315             for( final PhylogenyNodeIterator it = iteratorPostorder(); it.hasNext(); ) {
 316                 final PhylogenyNode n = it.next();
 317                 if ( n.isExternal() ) {
 318                     _external_nodes_set.add( n );
 319                 }
 320             }
 321         }
 322         return _external_nodes_set;
 323     }
 324
 325     /**
 326      * Returns the number of duplications of this Phylogeny (int). A return
 327      * value of -1 indicates that the number of duplications is unknown.
 328      */
 329     // public int getNumberOfDuplications() {
 330     // return _number_of_duplications;
 331     // } // getNumberOfDuplications()
 332     /**
 333      * Sets the number of duplications of this Phylogeny (int). A value of -1
 334      * indicates that the number of duplications is unknown.
 335      *
 336      * @param clean_nh
 337      *            set to true for clean NH format
 338      */
 339     // public void setNumberOfDuplications( int i ) {
 340     // if ( i < 0 ) {
 341     // _number_of_duplications = -1;
 342     // }
 343     // else {
 344     // _number_of_duplications = i;
 345     // }
 346     // } // setNumberOfDuplications( int )
 347     /**
 348      * Returns the first external PhylogenyNode.
 349      */
 350     public PhylogenyNode getFirstExternalNode() {
 351         if ( isEmpty() ) {
 352             throw new FailedConditionCheckException( "attempt to obtain first external node of empty phylogeney" );
 353         }
 354         PhylogenyNode node = getRoot();
 355         while ( node.isInternal() ) {
 356             node = node.getFirstChildNode();
 357         }
 358         return node;
 359     }
 360
 361     /**
 362      * This calculates the height for rooted, tree-shaped phylogenies. The
 363      * height is the longest distance from the root to an external node. Please
 364      * note. Child nodes of collapsed nodes are ignored -- which is useful for
 365      * display purposes but might be misleading for other applications.
 366      *
 367      * @return the height for rooted, tree-shaped phylogenies
 368      */
 369     public double getHeight() {
 370         if ( isEmpty() ) {
 371             return 0.0;
 372         }
 373         return calculateSubtreeHeight( getRoot() );
 374     }
 375
 376     public Identifier getIdentifier() {
 377         return _identifier;
 378     }
 379
 380     // ---------------------------------------------------------
 381     // Modification of Phylogeny topology and Phylogeny appearance
 382     // ---------------------------------------------------------
 383     private HashMap<Integer, PhylogenyNode> getIdHash() {
 384         return _idhash;
 385     }
 386
 387     /**
 388      * Returns the name of this Phylogeny.
 389      */
 390     public String getName() {
 391         return _name;
 392     }
 393
 394     /**
 395      * Finds the PhylogenyNode of this Phylogeny which has a matching ID number.
 396      * Takes O(n) time. After method hashIDs() has been called it runs in
 397      * constant time.
 398      *
 399      * @param id
 400      *            ID number (int) of the PhylogenyNode to find
 401      * @return PhylogenyNode with matching ID, null if not found
 402      */
 403     public PhylogenyNode getNode( final int id ) throws NoSuchElementException {
 404         if ( isEmpty() ) {
 405             throw new NoSuchElementException( "attempt to get node in an empty phylogeny" );
 406         }
 407         if ( _idhash != null ) {
 408             return _idhash.get( id );
 409         }
 410         else {
 411             for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 412                 final PhylogenyNode node = iter.next();
 413                 if ( node.getId() == id ) {
 414                     return node;
 415                 }
 416             }
 417         }
 418         return null;
 419     }
 420
 421     /**
 422      * Returns a PhylogenyNode of this Phylogeny which has a matching name.
 423      * Throws an Exception if seqname is not present in this or not unique.
 424      *
 425      * @param name
 426      *            name (String) of PhylogenyNode to find
 427      * @return PhylogenyNode with matchin name
 428      */
 429     public PhylogenyNode getNode( final String name ) {
 430         if ( isEmpty() ) {
 431             return null;
 432         }
 433         final List<PhylogenyNode> nodes = getNodes( name );
 434         if ( ( nodes == null ) || ( nodes.size() < 1 ) ) {
 435             throw new IllegalArgumentException( "node named [" + name + "] not found" );
 436         }
 437         if ( nodes.size() > 1 ) {
 438             throw new IllegalArgumentException( "node named [" + name + "] not unique" );
 439         }
 440         return nodes.get( 0 );
 441     }
 442
 443     /**
 444      * Return Node by TaxonomyId Olivier CHABROL :
 445      * olivier.chabrol@univ-provence.fr
 446      *
 447      * @param taxonomyID
 448      *            search taxonomy identifier
 449      * @param nodes
 450      *            sublist node to search
 451      * @return List node with the same taxonomy identifier
 452      */
 453     private List<PhylogenyNode> getNodeByTaxonomyID( final String taxonomyID, final List<PhylogenyNode> nodes ) {
 454         final List<PhylogenyNode> retour = new ArrayList<PhylogenyNode>();
 455         for( final PhylogenyNode node : nodes ) {
 456             if ( taxonomyID.equals( PhylogenyMethods.getTaxonomyIdentifier( node ) ) ) {
 457                 retour.add( node );
 458             }
 459         }
 460         return retour;
 461     }
 462
 463     /**
 464      * Returns a List with references to all Nodes of this Phylogeny which have
 465      * a matching name.
 466      *
 467      * @param name
 468      *            name (String) of Nodes to find
 469      * @return Vector of references to Nodes of this Phylogeny with matching
 470      *         names
 471      * @see #getNodesWithMatchingSpecies(String)
 472      */
 473     public List<PhylogenyNode> getNodes( final String name ) {
 474         if ( isEmpty() ) {
 475             return null;
 476         }
 477         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 478         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 479             final PhylogenyNode n = iter.next();
 480             if ( n.getName().equals( name ) ) {
 481                 nodes.add( n );
 482             }
 483         }
 484         return nodes;
 485     }
 486
 487     public List<PhylogenyNode> getNodesViaSequenceName( final String seq_name ) {
 488         if ( isEmpty() ) {
 489             return null;
 490         }
 491         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 492         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 493             final PhylogenyNode n = iter.next();
 494             if ( n.getNodeData().isHasSequence() && n.getNodeData().getSequence().getName().equals( seq_name ) ) {
 495                 nodes.add( n );
 496             }
 497         }
 498         return nodes;
 499     }
 500
 501     public List<PhylogenyNode> getNodesViaTaxonomyCode( final String taxonomy_code ) {
 502         if ( isEmpty() ) {
 503             return null;
 504         }
 505         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 506         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 507             final PhylogenyNode n = iter.next();
 508             if ( n.getNodeData().isHasTaxonomy()
 509                     && n.getNodeData().getTaxonomy().getTaxonomyCode().equals( taxonomy_code ) ) {
 510                 nodes.add( n );
 511             }
 512         }
 513         return nodes;
 514     }
 515
 516     /**
 517      * Returns a Vector with references to all Nodes of this Phylogeny which
 518      * have a matching species name.
 519      *
 520      * @param specname
 521      *            species name (String) of Nodes to find
 522      * @return Vector of references to Nodes of this Phylogeny with matching
 523      *         species names.
 524      * @see #getNodes(String)
 525      */
 526     public List<PhylogenyNode> getNodesWithMatchingSpecies( final String specname ) {
 527         if ( isEmpty() ) {
 528             return null;
 529         }
 530         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 531         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 532             final PhylogenyNode n = iter.next();
 533             if ( PhylogenyMethods.getSpecies( n ).equals( specname ) ) {
 534                 nodes.add( n );
 535             }
 536         }
 537         return nodes;
 538     }
 539
 540     public PhylogenyNode getNodeViaSequenceName( final String seq_name ) {
 541         if ( isEmpty() ) {
 542             return null;
 543         }
 544         final List<PhylogenyNode> nodes = getNodesViaSequenceName( seq_name );
 545         if ( ( nodes == null ) || ( nodes.size() < 1 ) ) {
 546             throw new IllegalArgumentException( "node with sequence named [" + seq_name + "] not found" );
 547         }
 548         if ( nodes.size() > 1 ) {
 549             throw new IllegalArgumentException( "node with sequence named [" + seq_name + "] not unique" );
 550         }
 551         return nodes.get( 0 );
 552     }
 553
 554     public PhylogenyNode getNodeViaTaxonomyCode( final String taxonomy_code ) {
 555         if ( isEmpty() ) {
 556             return null;
 557         }
 558         final List<PhylogenyNode> nodes = getNodesViaTaxonomyCode( taxonomy_code );
 559         if ( ( nodes == null ) || ( nodes.size() < 1 ) ) {
 560             throw new IllegalArgumentException( "node with taxonomy code \"" + taxonomy_code + "\" not found" );
 561         }
 562         if ( nodes.size() > 1 ) {
 563             throw new IllegalArgumentException( "node with taxonomy code \"" + taxonomy_code + "\" not unique" );
 564         }
 565         return nodes.get( 0 );
 566     }
 567
 568     /**
 569      * This is time-inefficient since it runs a iterator each time it is called.
 570      *
 571      */
 572     public int getNodeCount() {
 573         if ( isEmpty() ) {
 574             return 0;
 575         }
 576         int c = 0;
 577         for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); it.next() ) {
 578             ++c;
 579         }
 580         return c;
 581     }
 582
 583     public int getNumberOfBranches() {
 584         if ( isEmpty() ) {
 585             return 0;
 586         }
 587         int c = 0;
 588         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); iter.next() ) {
 589             ++c;
 590         }
 591         if ( !isRooted() ) {
 592             --c;
 593         }
 594         return c;
 595     }
 596
 597     /**
 598      * Returns the sum of external Nodes of this Phylogeny (int).
 599      */
 600     public int getNumberOfExternalNodes() {
 601         if ( isEmpty() ) {
 602             return 0;
 603         }
 604         return getExternalNodes().size();
 605     }
 606
 607     /**
 608      * Returns all paralogs of the external PhylogenyNode n of this Phylogeny.
 609      * paralog are returned as List of node references.
 610      * <p>
 611      * PRECONDITION: This tree must be binary and rooted, and speciation -
 612      * duplication need to be assigned for each of its internal Nodes.
 613      * <p>
 614      * Returns null if this Phylogeny is empty or if n is internal.
 615      * <p>
 616      * (Last modified: 11/22/00) Olivier CHABROL :
 617      * olivier.chabrol@univ-provence.fr
 618      *
 619      * @param n
 620      *            external PhylogenyNode whose orthologs are to be returned
 621      * @return Vector of references to all orthologous Nodes of PhylogenyNode n
 622      *         of this Phylogeny, null if this Phylogeny is empty or if n is
 623      *         internal
 624      */
 625     public List<PhylogenyNode> getParalogousNodes( final PhylogenyNode n, final String[] taxonomyCodeRange ) {
 626         PhylogenyNode node = n;
 627         PhylogenyNode prev = null;
 628         final List<PhylogenyNode> v = new ArrayList<PhylogenyNode>();
 629         final Map<PhylogenyNode, List<String>> map = new HashMap<PhylogenyNode, List<String>>();
 630         getTaxonomyMap( getRoot(), map );
 631         if ( !node.isExternal() || isEmpty() ) {
 632             return null;
 633         }
 634         final String searchNodeSpeciesId = PhylogenyMethods.getTaxonomyIdentifier( n );
 635         if ( !node.isExternal() || isEmpty() ) {
 636             return null;
 637         }
 638         List<String> taxIdList = null;
 639         final List<String> taxonomyCodeRangeList = Arrays.asList( taxonomyCodeRange );
 640         while ( !node.isRoot() ) {
 641             prev = node;
 642             node = node.getParent();
 643             taxIdList = map.get( node );
 644             if ( node.isDuplication() && isContains( taxIdList, taxonomyCodeRangeList ) ) {
 645                 if ( node.getChildNode1() == prev ) {
 646                     v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, node.getChildNode2()
 647                             .getAllExternalDescendants() ) );
 648                 }
 649                 else {
 650                     v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, node.getChildNode1()
 651                             .getAllExternalDescendants() ) );
 652                 }
 653             }
 654         }
 655         return v;
 656     }
 657
 658     public Collection<SequenceRelation.SEQUENCE_RELATION_TYPE> getRelevantSequenceRelationTypes() {
 659         if ( _relevant_sequence_relation_types == null ) {
 660             _relevant_sequence_relation_types = new Vector<SEQUENCE_RELATION_TYPE>();
 661         }
 662         return _relevant_sequence_relation_types;
 663     }
 664
 665     /**
 666      * Returns the root PhylogenyNode of this Phylogeny.
 667      */
 668     public PhylogenyNode getRoot() {
 669         return _root;
 670     }
 671
 672     public Collection<Sequence> getSequenceRelationQueries() {
 673         return _sequenceRelationQueries;
 674     }
 675
 676     /**
 677      * List all species contains in all leaf under a node Olivier CHABROL :
 678      * olivier.chabrol@univ-provence.fr
 679      *
 680      * @param node
 681      *            PhylogenyNode whose sub node species are returned
 682      * @return species contains in all leaf under the param node
 683      */
 684     private List<String> getSubNodeTaxonomy( final PhylogenyNode node ) {
 685         final List<String> taxonomyList = new ArrayList<String>();
 686         final List<PhylogenyNode> childs = node.getAllExternalDescendants();
 687         String speciesId = null;
 688         for( final PhylogenyNode phylogenyNode : childs ) {
 689             // taxId = new Long(phylogenyNode.getTaxonomyID());
 690             speciesId = PhylogenyMethods.getTaxonomyIdentifier( phylogenyNode );
 691             if ( !taxonomyList.contains( speciesId ) ) {
 692                 taxonomyList.add( speciesId );
 693             }
 694         }
 695         return taxonomyList;
 696     }
 697
 698     /**
 699      * Create a map [<PhylogenyNode, List<String>], the list contains the
 700      * species contains in all leaf under phylogeny node Olivier CHABROL :
 701      * olivier.chabrol@univ-provence.fr
 702      *
 703      * @param node
 704      *            the tree root node
 705      * @param map
 706      *            map to fill
 707      */
 708     private void getTaxonomyMap( final PhylogenyNode node, final Map<PhylogenyNode, List<String>> map ) {
 709         // node is leaf
 710         if ( node.isExternal() ) {
 711             return;
 712         }
 713         map.put( node, getSubNodeTaxonomy( node ) );
 714         getTaxonomyMap( node.getChildNode1(), map );
 715         getTaxonomyMap( node.getChildNode2(), map );
 716     }
 717
 718     public String getType() {
 719         return _type;
 720     }
 721
 722     /**
 723      * Hashes the ID number of each PhylogenyNode of this Phylogeny to its
 724      * corresponding PhylogenyNode, in order to make method getNode( id ) run in
 725      * constant time. Important: The user is responsible for calling this method
 726      * (again) after this Phylogeny has been changed/created/renumbered.
 727      */
 728     public void hashIDs() {
 729         if ( isEmpty() ) {
 730             return;
 731         }
 732         setIdHash( new HashMap<Integer, PhylogenyNode>() );
 733         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 734             final PhylogenyNode node = iter.next();
 735             getIdHash().put( node.getId(), node );
 736         }
 737     }
 738
 739     /**
 740      * Deletes this Phylogeny.
 741      */
 742     public void init() {
 743         _root = null;
 744         _rooted = false;
 745         _name = "";
 746         _description = "";
 747         _type = "";
 748         _distance_unit = "";
 749         _idhash = null;
 750         _confidence = null;
 751         _identifier = null;
 752         _rerootable = true;
 753         setAllowMultipleParents( Phylogeny.ALLOW_MULTIPLE_PARENTS_DEFAULT );
 754     }
 755
 756     private boolean isAllowMultipleParents() {
 757         return _allow_multiple_parents;
 758     }
 759
 760     /**
 761      * Returns whether this is a completely binary tree (i.e. all internal nodes
 762      * are bifurcations).
 763      *
 764      */
 765     public boolean isCompletelyBinary() {
 766         if ( isEmpty() ) {
 767             return false;
 768         }
 769         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 770             final PhylogenyNode node = iter.next();
 771             if ( node.isInternal() && ( node.getNumberOfDescendants() != 2 ) ) {
 772                 return false;
 773             }
 774         }
 775         return true;
 776     }
 777
 778     /**
 779      * Util method to check if all element of a list is contains in the
 780      * rangeList. Olivier CHABROL : olivier.chabrol@univ-provence.fr
 781      *
 782      * @param list
 783      *            list to be check
 784      * @param rangeList
 785      *            the range list to compare
 786      * @return <code>true</code> if all param list element are contains in param
 787      *         rangeList, <code>false</code> otherwise.
 788      */
 789     private boolean isContains( final List<String> list, final List<String> rangeList ) {
 790         if ( list.size() > rangeList.size() ) {
 791             return false;
 792         }
 793         String l = null;
 794         for( final Iterator<String> iterator = list.iterator(); iterator.hasNext(); ) {
 795             l = iterator.next();
 796             if ( !rangeList.contains( l ) ) {
 797                 return false;
 798             }
 799         }
 800         return true;
 801     }
 802
 803     /**
 804      * Checks whether a Phylogeny object is deleted (or empty).
 805      *
 806      * @return true if the tree is deleted (or empty), false otherwise
 807      */
 808     public boolean isEmpty() {
 809         return ( getRoot() == null );
 810     }
 811
 812     public boolean isRerootable() {
 813         return _rerootable;
 814     }
 815
 816     /**
 817      * Returns true is this Phylogeny is rooted.
 818      */
 819     public boolean isRooted() {
 820         return _rooted;
 821     } // isRooted()
 822
 823     public boolean isTree() {
 824         return true;
 825     }
 826
 827     public PhylogenyNodeIterator iteratorExternalForward() {
 828         return new ExternalForwardIterator( this );
 829     }
 830
 831     public PhylogenyNodeIterator iteratorLevelOrder() {
 832         return new LevelOrderTreeIterator( this );
 833     }
 834
 835     public PhylogenyNodeIterator iteratorPostorder() {
 836         return new PostorderTreeIterator( this );
 837     }
 838
 839     public PhylogenyNodeIterator iteratorPreorder() {
 840         return new PreorderTreeIterator( this );
 841     }
 842
 843     /**
 844      * Resets the ID numbers of the nodes of this Phylogeny in level order,
 845      * starting with start_label (for the root). <br>
 846      * WARNING. After this method has been called, node IDs are no longer
 847      * unique.
 848      */
 849     public void levelOrderReID() {
 850         if ( isEmpty() ) {
 851             return;
 852         }
 853         _idhash = null;
 854         int max = 0;
 855         for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); ) {
 856             final PhylogenyNode node = it.next();
 857             if ( node.isRoot() ) {
 858                 node.setId( PhylogenyNode.getNodeCount() );
 859             }
 860             else {
 861                 node.setId( node.getParent().getId() + 1 );
 862                 if ( node.getId() > max ) {
 863                     max = node.getId();
 864                 }
 865             }
 866         }
 867         PhylogenyNode.setNodeCount( max + 1 );
 868     }
 869
 870     /**
 871      * Arranges the order of childern for each node of this Phylogeny in such a
 872      * way that either the branch with more children is on top (right) or on
 873      * bottom (left), dependent on the value of boolean order.
 874      *
 875      * @param order
 876      *            decides in which direction to order
 877      */
 878     public void orderAppearance( final boolean order ) throws RuntimeException {
 879         if ( !isTree() ) {
 880             throw new FailedConditionCheckException( "Attempt to order appearance on phylogeny which is not tree-like." );
 881         }
 882         if ( isEmpty() ) {
 883             return;
 884         }
 885         orderAppearanceHelper( getRoot(), order );
 886     }
 887
 888     // Helper method for "orderAppearance(boolean)".
 889     // Traverses this Phylogeny recusively.
 890     private void orderAppearanceHelper( final PhylogenyNode n, final boolean order ) {
 891         if ( n.isExternal() ) {
 892             return;
 893         }
 894         else {
 895             PhylogenyNode temp = null;
 896             // FIXME
 897             if ( ( n.getNumberOfDescendants() == 2 )
 898                     && ( n.getChildNode1().getNumberOfExternalNodes() != n.getChildNode2().getNumberOfExternalNodes() )
 899                     && ( ( n.getChildNode1().getNumberOfExternalNodes() < n.getChildNode2().getNumberOfExternalNodes() ) == order ) ) {
 900                 temp = n.getChildNode1();
 901                 n.setChild1( n.getChildNode2() );
 902                 n.setChild2( temp );
 903             }
 904             for( int i = 0; i < n.getNumberOfDescendants(); ++i ) {
 905                 orderAppearanceHelper( n.getChildNode( i ), order );
 906             }
 907         }
 908     }
 909
 910     public void preOrderReId() {
 911         if ( isEmpty() ) {
 912             return;
 913         }
 914         setIdHash( null );
 915         int i = PhylogenyNode.getNodeCount();
 916         for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); ) {
 917             it.next().setId( i++ );
 918         }
 919         PhylogenyNode.setNodeCount( i );
 920     }
 921
 922     /**
 923      * Prints descriptions of all external Nodes of this Phylogeny to
 924      * System.out.
 925      */
 926     public void printExtNodes() {
 927         if ( isEmpty() ) {
 928             return;
 929         }
 930         for( final PhylogenyNodeIterator iter = iteratorExternalForward(); iter.hasNext(); ) {
 931             System.out.println( iter.next() + "\n" );
 932         }
 933     }
 934
 935     /**
 936      * (Re)counts the number of children for each PhylogenyNode of this
 937      * Phylogeny. As an example, this method needs to be called after a
 938      * Phylogeny has been reRooted and it is to be displayed.
 939      *
 940      * @param consider_collapsed_nodes
 941      *            set to true to take into account collapsed nodes (collapsed
 942      *            nodes have 1 child).
 943      */
 944     public void recalculateNumberOfExternalDescendants( final boolean consider_collapsed_nodes ) {
 945         if ( isEmpty() ) {
 946             return;
 947         }
 948         for( final PhylogenyNodeIterator iter = iteratorPostorder(); iter.hasNext(); ) {
 949             final PhylogenyNode node = iter.next();
 950             if ( node.isExternal() || ( consider_collapsed_nodes && node.isCollapse() ) ) {
 951                 node.setSumExtNodes( 1 );
 952             }
 953             else {
 954                 int sum = 0;
 955                 for( int i = 0; i < node.getNumberOfDescendants(); ++i ) {
 956                     sum += node.getChildNode( i ).getNumberOfExternalNodes();
 957                 }
 958                 node.setSumExtNodes( sum );
 959             }
 960         }
 961     }
 962
 963     /**
 964      * Places the root of this Phylogeny on the parent branch of the
 965      * PhylogenyNode with a corresponding ID. The new root is always placed on
 966      * the middle of the branch. If the resulting reRooted Phylogeny is to be
 967      * used any further, in most cases the following methods have to be called
 968      * on the resulting Phylogeny:
 969      * <p>
 970      * <li>recalculateNumberOfExternalDescendants(boolean)
 971      * <li>recalculateAndReset()
 972      *
 973      * @param id
 974      *            ID (int) of PhylogenyNode of this Phylogeny
 975      */
 976     public void reRoot( final int id ) {
 977         reRoot( getNode( id ) );
 978     }
 979
 980     /**
 981      * Places the root of this Phylogeny on Branch b. The new root is always
 982      * placed on the middle of the branch b.
 983      *
 984      */
 985     public void reRoot( final PhylogenyBranch b ) {
 986         final PhylogenyNode n1 = b.getFirstNode();
 987         final PhylogenyNode n2 = b.getSecondNode();
 988         if ( n1.isExternal() ) {
 989             reRoot( n1 );
 990         }
 991         else if ( n2.isExternal() ) {
 992             reRoot( n2 );
 993         }
 994         else if ( ( n2 == n1.getChildNode1() ) || ( n2 == n1.getChildNode2() ) ) {
 995             reRoot( n2 );
 996         }
 997         else if ( ( n1 == n2.getChildNode1() ) || ( n1 == n2.getChildNode2() ) ) {
 998             reRoot( n1 );
 999         }
1000         else if ( ( n1.getParent() != null ) && n1.getParent().isRoot()
1001                 && ( ( n1.getParent().getChildNode1() == n2 ) || ( n1.getParent().getChildNode2() == n2 ) ) ) {
1002             reRoot( n1 );
1003         }
1004         else {
1005             throw new IllegalArgumentException( "reRoot( Branch b ): b is not a branch." );
1006         }
1007     }
1008
1009     /**
1010      * Places the root of this Phylogeny on the parent branch PhylogenyNode n.
1011      * The new root is always placed on the middle of the branch.
1012      * <p>
1013      * If the resulting reRooted Phylogeny is to be used any further, in most
1014      * cases the following three methods have to be called on the resulting
1015      * Phylogeny:
1016      * <ul>
1017      * <li>recalculateNumberOfExternalDescendants(boolean) <li>recalculateAndReset()
1018      * </ul>
1019      * <p>
1020      * (Last modified: 10/01/01)
1021      *
1022      * @param n
1023      *            PhylogenyNode of this Phylogeny\
1024      */
1025     public void reRoot( final PhylogenyNode n ) {
1026         reRoot( n, -1 );
1027     }
1028
1029     public void reRoot( final PhylogenyNode n, final double distance_n_to_parent ) {
1030         if ( isEmpty() || ( getNumberOfExternalNodes() < 2 ) ) {
1031             return;
1032         }
1033         setRooted( true );
1034         if ( n.isRoot() ) {
1035             return;
1036         }
1037         else if ( n.getParent().isRoot() ) {
1038             if ( ( n.getParent().getNumberOfDescendants() == 2 ) && ( distance_n_to_parent >= 0 ) ) {
1039                 final double d = n.getParent().getChildNode1().getDistanceToParent()
1040                         + n.getParent().getChildNode2().getDistanceToParent();
1041                 PhylogenyNode other;
1042                 if ( n.getChildNodeIndex() == 0 ) {
1043                     other = n.getParent().getChildNode2();
1044                 }
1045                 else {
1046                     other = n.getParent().getChildNode1();
1047                 }
1048                 n.setDistanceToParent( distance_n_to_parent );
1049                 final double dm = d - distance_n_to_parent;
1050                 if ( dm >= 0 ) {
1051                     other.setDistanceToParent( dm );
1052                 }
1053                 else {
1054                     other.setDistanceToParent( 0 );
1055                 }
1056             }
1057             if ( n.getParent().getNumberOfDescendants() > 2 ) {
1058                 final int index = n.getChildNodeIndex();
1059                 final double dn = n.getDistanceToParent();
1060                 final PhylogenyNode prev_root = getRoot();
1061                 prev_root.getDescendants().remove( index );
1062                 final PhylogenyNode new_root = new PhylogenyNode();
1063                 new_root.setChildNode( 0, n );
1064                 new_root.setChildNode( 1, prev_root );
1065                 if ( n.getBranchDataDirectly() != null ) {
1066                     prev_root.setBranchData( ( BranchData ) n.getBranchDataDirectly().copy() );
1067                 }
1068                 setRoot( new_root );
1069                 if ( distance_n_to_parent >= 0 ) {
1070                     n.setDistanceToParent( distance_n_to_parent );
1071                     final double d = dn - distance_n_to_parent;
1072                     if ( d >= 0 ) {
1073                         prev_root.setDistanceToParent( d );
1074                     }
1075                     else {
1076                         prev_root.setDistanceToParent( 0 );
1077                     }
1078                 }
1079                 else {
1080                     if ( dn >= 0 ) {
1081                         final double d = dn / 2.0;
1082                         n.setDistanceToParent( d );
1083                         prev_root.setDistanceToParent( d );
1084                     }
1085                 }
1086             }
1087         }
1088         else {
1089             PhylogenyNode a = n;
1090             PhylogenyNode b = null;
1091             PhylogenyNode c = null;
1092             final PhylogenyNode new_root = new PhylogenyNode();
1093             double distance1 = 0.0;
1094             double distance2 = 0.0;
1095             BranchData branch_data_1 = null;
1096             BranchData branch_data_2 = null;
1097             b = a.getParent();
1098             c = b.getParent();
1099             new_root.setChildNode( 0, a );
1100             new_root.setChildNode( 1, b );
1101             distance1 = c.getDistanceToParent();
1102             if ( c.getBranchDataDirectly() != null ) {
1103                 branch_data_1 = ( BranchData ) c.getBranchDataDirectly().copy();
1104             }
1105             c.setDistanceToParent( b.getDistanceToParent() );
1106             if ( b.getBranchDataDirectly() != null ) {
1107                 c.setBranchData( ( BranchData ) b.getBranchDataDirectly().copy() );
1108             }
1109             if ( a.getBranchDataDirectly() != null ) {
1110                 b.setBranchData( ( BranchData ) a.getBranchDataDirectly().copy() );
1111             }
1112             // New root is always placed in the middle of the branch:
1113             if ( a.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ) {
1114                 b.setDistanceToParent( PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT );
1115             }
1116             else {
1117                 if ( distance_n_to_parent >= 0.0 ) {
1118                     final double diff = a.getDistanceToParent() - distance_n_to_parent;
1119                     a.setDistanceToParent( distance_n_to_parent );
1120                     b.setDistanceToParent( diff >= 0.0 ? diff : 0.0 );
1121                 }
1122                 else {
1123                     final double d = a.getDistanceToParent() / 2.0;
1124                     a.setDistanceToParent( d );
1125                     b.setDistanceToParent( d );
1126                 }
1127             }
1128             b.setChildNodeOnly( a.getChildNodeIndex( b ), c );
1129             // moving to the old root, swapping references:
1130             while ( !c.isRoot() ) {
1131                 a = b;
1132                 b = c;
1133                 c = c.getParent();
1134                 b.setChildNodeOnly( a.getChildNodeIndex( b ), c );
1135                 b.setParent( a );
1136                 distance2 = c.getDistanceToParent();
1137                 branch_data_2 = c.getBranchDataDirectly();
1138                 c.setDistanceToParent( distance1 );
1139                 c.setBranchData( branch_data_1 );
1140                 distance1 = distance2;
1141                 branch_data_1 = branch_data_2;
1142             }
1143             // removing the old root:
1144             if ( c.getNumberOfDescendants() == 2 ) {
1145                 final PhylogenyNode node = c.getChildNode( 1 - b.getChildNodeIndex( c ) );
1146                 node.setParent( b );
1147                 if ( ( c.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT )
1148                         && ( node.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ) ) {
1149                     node.setDistanceToParent( PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT );
1150                 }
1151                 else {
1152                     node.setDistanceToParent( ( c.getDistanceToParent() >= 0.0 ? c.getDistanceToParent() : 0.0 )
1153                             + ( node.getDistanceToParent() >= 0.0 ? node.getDistanceToParent() : 0.0 ) );
1154                 }
1155                 if ( c.getBranchDataDirectly() != null ) {
1156                     node.setBranchData( ( BranchData ) c.getBranchDataDirectly().copy() );
1157                 }
1158                 for( int i = 0; i < b.getNumberOfDescendants(); ++i ) {
1159                     if ( b.getChildNode( i ) == c ) {
1160                         b.setChildNodeOnly( i, node );
1161                         break;
1162                     }
1163                 }
1164             }
1165             else {
1166                 c.setParent( b );
1167                 c.removeChildNode( b.getChildNodeIndex( c ) );
1168             }
1169             setRoot( new_root );
1170         }
1171     }
1172
1173     /**
1174      * Sets all Nodes of this Phylogeny to not-collapsed.
1175      * <p>
1176      * In most cases methods adjustNodeCount(false) and recalculateAndReset()
1177      * need to be called after this method has been called.
1178      */
1179     public void setAllNodesToNotCollapse() {
1180         if ( isEmpty() ) {
1181             return;
1182         }
1183         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
1184             final PhylogenyNode node = iter.next();
1185             node.setCollapse( false );
1186         }
1187     }
1188
1189     private void setAllowMultipleParents( final boolean allow_multiple_parents ) {
1190         _allow_multiple_parents = allow_multiple_parents;
1191     }
1192
1193     public void setConfidence( final Confidence confidence ) {
1194         _confidence = confidence;
1195     }
1196
1197     public void setDescription( final String description ) {
1198         _description = description;
1199     }
1200
1201     public void setDistanceUnit( final String _distance_unit ) {
1202         this._distance_unit = _distance_unit;
1203     }
1204
1205     public void setIdentifier( final Identifier identifier ) {
1206         _identifier = identifier;
1207     }
1208
1209     void setIdHash( final HashMap<Integer, PhylogenyNode> idhash ) {
1210         _idhash = idhash;
1211     }
1212
1213     /**
1214      * Sets the indicators of all Nodes of this Phylogeny to 0.
1215      */
1216     public void setIndicatorsToZero() {
1217         if ( isEmpty() ) {
1218             return;
1219         }
1220         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
1221             iter.next().setIndicator( ( byte ) 0 );
1222         }
1223     } // setIndicatorsToZero()
1224
1225     /**
1226      * Sets the name of this Phylogeny to s.
1227      */
1228     public void setName( final String s ) {
1229         _name = s;
1230     }
1231
1232     public void setRelevantSequenceRelationTypes( final Collection<SequenceRelation.SEQUENCE_RELATION_TYPE> types ) {
1233         _relevant_sequence_relation_types = types;
1234     }
1235
1236     public void setRerootable( final boolean rerootable ) {
1237         _rerootable = rerootable;
1238     }
1239
1240     public void setRoot( final PhylogenyNode n ) {
1241         _root = n;
1242     } // setRoot( PhylogenyNode )
1243
1244     /**
1245      * Sets whether this Phylogeny is rooted or not.
1246      */
1247     public void setRooted( final boolean b ) {
1248         _rooted = b;
1249     } // setRooted( boolean )
1250
1251     public void setSequenceRelationQueries( final Collection<Sequence> sequencesByName ) {
1252         _sequenceRelationQueries = sequencesByName;
1253     }
1254
1255     public void setType( final String type ) {
1256         _type = type;
1257     }
1258
1259     /**
1260      * Swaps the the two childern of a PhylogenyNode node of this Phylogeny.
1261      * <p>
1262      * (Last modified: 06/13/01)
1263      *
1264      * @param node
1265      *            a PhylogenyNode of this Phylogeny
1266      */
1267     public void swapChildren( final PhylogenyNode node ) throws RuntimeException {
1268         if ( !isTree() ) {
1269             throw new FailedConditionCheckException( "Attempt to swap children on phylogeny which is not tree-like." );
1270         }
1271         if ( isEmpty() || node.isExternal() || ( node.getNumberOfDescendants() < 2 ) ) {
1272             return;
1273         }
1274         final PhylogenyNode first = node.getFirstChildNode();
1275         for( int i = 1; i < node.getNumberOfDescendants(); ++i ) {
1276             node.setChildNode( i - 1, node.getChildNode( i ) );
1277         }
1278         node.setChildNode( node.getNumberOfDescendants() - 1, first );
1279     } // swapChildren( PhylogenyNode )
1280
1281     public String toNewHampshire() {
1282         return toNewHampshire( false, NH_CONVERSION_SUPPORT_VALUE_STYLE.NONE );
1283     }
1284
1285     public String toNewHampshire( final boolean simple_nh,
1286                                   final NH_CONVERSION_SUPPORT_VALUE_STYLE nh_conversion_support_style ) {
1287         try {
1288             return new PhylogenyWriter().toNewHampshire( this, simple_nh, true, nh_conversion_support_style )
1289                     .toString();
1290         }
1291         catch ( final IOException e ) {
1292             throw new Error( "this should not have happend: " + e.getMessage() );
1293         }
1294     }
1295
1296     public String toNewHampshireX() {
1297         try {
1298             return new PhylogenyWriter().toNewHampshireX( this ).toString();
1299         }
1300         catch ( final IOException e ) {
1301             throw new Error( "this should not have happend: " + e.getMessage() );
1302         }
1303     }
1304
1305     public String toNexus( final NH_CONVERSION_SUPPORT_VALUE_STYLE svs ) {
1306         try {
1307             return new PhylogenyWriter().toNexus( this, svs ).toString();
1308         }
1309         catch ( final IOException e ) {
1310             throw new Error( "this should not have happend: " + e.getMessage() );
1311         }
1312     }
1313
1314     public String toNexus() {
1315         return toNexus( NH_CONVERSION_SUPPORT_VALUE_STYLE.NONE );
1316     }
1317
1318     public String toPhyloXML( final int phyloxml_level ) {
1319         try {
1320             return new PhylogenyWriter().toPhyloXML( this, phyloxml_level ).toString();
1321         }
1322         catch ( final IOException e ) {
1323             throw new Error( "this should not have happend: " + e.getMessage() );
1324         }
1325     }
1326
1327     // ---------------------------------------------------------
1328     // Writing of Phylogeny to Strings
1329     // ---------------------------------------------------------
1330     /**
1331      * Converts this Phylogeny to a New Hampshire X (String) representation.
1332      *
1333      * @return New Hampshire X (String) representation of this
1334      * @see #toNewHampshireX()
1335      */
1336     @Override
1337     public String toString() {
1338         return toNewHampshireX();
1339     }
1340
1341     /**
1342      * Removes the root PhylogenyNode this Phylogeny.
1343      */
1344     public void unRoot() throws RuntimeException {
1345         if ( !isTree() ) {
1346             throw new FailedConditionCheckException( "Attempt to unroot a phylogeny which is not tree-like." );
1347         }
1348         if ( isEmpty() ) {
1349             return;
1350         }
1351         setIndicatorsToZero();
1352         if ( !isRooted() || ( getNumberOfExternalNodes() <= 1 ) ) {
1353             return;
1354         }
1355         setRooted( false );
1356         return;
1357     } // unRoot()
1358 }