forester/java/src/org/forester/phylogeny/PhylogenyNode.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.util.ArrayList;
  31 import java.util.List;
  32
  33 import org.forester.io.parsers.nhx.NHXFormatException;
  34 import org.forester.io.parsers.nhx.NHXParser;
  35 import org.forester.io.parsers.phyloxml.PhyloXmlUtil;
  36 import org.forester.phylogeny.data.BranchData;
  37 import org.forester.phylogeny.data.Confidence;
  38 import org.forester.phylogeny.data.NodeData;
  39 import org.forester.phylogeny.data.PhylogenyDataUtil;
  40 import org.forester.phylogeny.iterators.ChildNodeIteratorForward;
  41 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
  42 import org.forester.phylogeny.iterators.PreorderTreeIterator;
  43 import org.forester.util.ForesterUtil;
  44
  45 public final class PhylogenyNode implements PhylogenyNodeI, Comparable<PhylogenyNode> {
  46
  47     private static int               _node_count      = 0;
  48     private byte                     _indicator;
  49     private int                      _id;
  50     private int                      _sum_ext_nodes;
  51     private float                    _x;
  52     private float                    _y;
  53     private double                   _distance_parent = PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT;
  54     private boolean                  _collapse;
  55     private PhylogenyNode            _parent;
  56     private PhylogenyNode            _link;
  57     private ArrayList<PhylogenyNode> _descendants;
  58     private NodeData                 _node_data;
  59     private BranchData               _branch_data;
  60     private float                    _x_secondary;
  61     private float                    _y_secondary;
  62
  63     /**
  64      * Default constructor for PhylogenyNode.
  65      */
  66     public PhylogenyNode() {
  67         //  init();
  68         setId( PhylogenyNode.getNodeCount() );
  69         PhylogenyNode.increaseNodeCount();
  70         setSumExtNodes( 1 ); // For ext node, this number is 1 (not 0!!)
  71     }
  72
  73     public void removeConnections() {
  74         _parent = null;
  75         _link = null;
  76         _descendants = null;
  77     }
  78
  79     /**
  80      * Adds PhylogenyNode n to the list of child nodes and sets the _parent of n
  81      * to this.
  82      *
  83      * @param n
  84      *            the PhylogenyNode to add
  85      */
  86     @Override
  87     final public void addAsChild( final PhylogenyNodeI node ) {
  88         final PhylogenyNode n = ( PhylogenyNode ) node;
  89         addChildNode( n );
  90         n.setParent( this );
  91     }
  92
  93     /**
  94      * Adds PhylogenyNode n to the list of child nodes. But does NOT set the
  95      * _parent of n to this.
  96      *
  97      * @see addAsChild( PhylogenyNode n )
  98      * @param n
  99      *            the PhylogenyNode to add
 100      */
 101     final private void addChildNode( final PhylogenyNode child ) {
 102         getDescendants().add( child );
 103     }
 104
 105     @Override
 106     // this is poor, as it only compares on names!
 107     final public int compareTo( final PhylogenyNode o ) {
 108         final PhylogenyNode n = o;
 109         if ( ( getName() == null ) || ( n.getName() == null ) ) {
 110             return 0;
 111         }
 112         return getName().compareTo( n.getName() );
 113     }
 114
 115     // ---------------------------------------------------------
 116     // Copy and delete Nodes, copy subtress
 117     // ---------------------------------------------------------
 118     /**
 119      * Returns a new PhylogenyNode which has its data copied from this
 120      * PhylogenyNode. Links to the other Nodes in the same Phylogeny are NOT
 121      * copied (e.g. _link to _parent). Field "_link" IS copied.
 122      *
 123      * @see #getLink()
 124      */
 125     final public PhylogenyNode copyNodeData() {
 126         final PhylogenyNode node = new PhylogenyNode();
 127         PhylogenyNode.decreaseNodeCount();
 128         node._id = _id;
 129         node._sum_ext_nodes = _sum_ext_nodes;
 130         node._indicator = _indicator;
 131         node._x = _x;
 132         node._y = _y;
 133         node._distance_parent = _distance_parent;
 134         node._collapse = _collapse;
 135         node._link = _link;
 136         if ( _node_data != null ) {
 137             node._node_data = ( NodeData ) _node_data.copy();
 138         }
 139         if ( _branch_data != null ) {
 140             node._branch_data = ( BranchData ) _branch_data.copy();
 141         }
 142         return node;
 143     }
 144
 145     /**
 146      * Returns a new PhylogenyNode which has the same data as this
 147      * PhylogenyNode. Links to the other Nodes in the same Phylogeny are NOT
 148      * copied (e.g. _link to _parent). Field "_link" IS copied.
 149      *
 150      * @see #getLink()
 151      */
 152     final public PhylogenyNode copyNodeDataShallow() {
 153         final PhylogenyNode node = new PhylogenyNode();
 154         PhylogenyNode.decreaseNodeCount();
 155         node._id = _id;
 156         node._sum_ext_nodes = _sum_ext_nodes;
 157         node._indicator = _indicator;
 158         node._x = _x;
 159         node._y = _y;
 160         node._distance_parent = _distance_parent;
 161         node._collapse = _collapse;
 162         node._link = _link;
 163         node._node_data = _node_data;
 164         node._branch_data = _branch_data;
 165         return node;
 166     }
 167
 168     @Override
 169     /**
 170      * Based on node name, sequence, and taxonomy.
 171      *
 172      *
 173      */
 174     final public boolean equals( final Object o ) {
 175         if ( this == o ) {
 176             return true;
 177         }
 178         else if ( o == null ) {
 179             return false;
 180         }
 181         else if ( o.getClass() != this.getClass() ) {
 182             throw new IllegalArgumentException( "attempt to check [" + this.getClass() + "] equality to " + o + " ["
 183                     + o.getClass() + "]" );
 184         }
 185         else {
 186             final PhylogenyNode other = ( PhylogenyNode ) o;
 187             if ( !getName().equals( other.getName() ) ) {
 188                 return false;
 189             }
 190             final NodeData this_data = getNodeData();
 191             final NodeData other_data = other.getNodeData();
 192             if ( ( this_data.isHasSequence() && other_data.isHasSequence() )
 193                     && ( this_data.isHasTaxonomy() && other_data.isHasTaxonomy() ) ) {
 194                 return ( this_data.getTaxonomy().isEqual( other_data.getTaxonomy() ) && this_data.getSequence()
 195                         .isEqual( other_data.getSequence() ) );
 196             }
 197             else if ( this_data.isHasTaxonomy() && other_data.isHasTaxonomy() ) {
 198                 return ( this_data.getTaxonomy().isEqual( other_data.getTaxonomy() ) );
 199             }
 200             else if ( this_data.isHasSequence() && other_data.isHasSequence() ) {
 201                 return ( this_data.getSequence().isEqual( other_data.getSequence() ) );
 202             }
 203             else if ( getName().length() > 0 ) {
 204                 // Node name is not empty, and equal.
 205                 return true;
 206             }
 207             else {
 208                 return false;
 209             }
 210         }
 211     }
 212
 213     // ---------------------------------------------------------
 214     // Obtaining of Nodes
 215     // ---------------------------------------------------------
 216     /**
 217      * Returns a List containing references to all external children of this
 218      * PhylogenyNode.
 219      *
 220      * @return List of references to external Nodes
 221      */
 222     final public List<PhylogenyNode> getAllExternalDescendants() {
 223         final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
 224         if ( isExternal() ) {
 225             nodes.add( this );
 226             return nodes;
 227         }
 228         PhylogenyNode node1 = this;
 229         while ( !node1.isExternal() ) {
 230             node1 = node1.getFirstChildNode();
 231         }
 232         PhylogenyNode node2 = this;
 233         while ( !node2.isExternal() ) {
 234             node2 = node2.getLastChildNode();
 235         }
 236         while ( node1 != node2 ) {
 237             nodes.add( node1 );
 238             node1 = node1.getNextExternalNode();
 239         }
 240         nodes.add( node2 );
 241         return nodes;
 242     }
 243
 244     /**
 245      * Returns a List containing references to all names of the external
 246      * children of this PhylogenyNode.
 247      *
 248      * @return List of references to names of external Nodes
 249      */
 250     final public List<String> getAllExternalDescendantsNames() {
 251         final List<PhylogenyNode> c = getAllExternalDescendants();
 252         final List<String> n = new ArrayList<String>( c.size() );
 253         for( final PhylogenyNode phylogenyNode : c ) {
 254             n.add( phylogenyNode.getName() );
 255         }
 256         return n;
 257     }
 258
 259     final public BranchData getBranchData() {
 260         if ( _branch_data == null ) {
 261             _branch_data = new BranchData();
 262         }
 263         return _branch_data;
 264     }
 265
 266     final BranchData getBranchDataDirectly() {
 267         return _branch_data;
 268     }
 269
 270     /**
 271      * This return child node n of this node.
 272      *
 273      * @param n
 274      *            the index of the child to get
 275      * @return the child node with index n
 276      * @throws IllegalArgumentException
 277      *             if n is out of bounds
 278      */
 279     @Override
 280     final public PhylogenyNode getChildNode( final int i ) {
 281         if ( isExternal() ) {
 282             throw new UnsupportedOperationException( "attempt to get the child node of an external node." );
 283         }
 284         if ( ( i >= getNumberOfDescendants() ) || ( i < 0 ) ) {
 285             throw new IllegalArgumentException( "attempt to get child node " + i + " of a node with "
 286                     + getNumberOfDescendants() + " child nodes" );
 287         }
 288         return getDescendants().get( i );
 289     }
 290
 291     /**
 292      * Convenience method. Returns the first child PhylogenyNode of this
 293      * PhylogenyNode.
 294      */
 295     final public PhylogenyNode getChildNode1() {
 296         return getChildNode( 0 );
 297     }
 298
 299     /**
 300      * Convenience method. Returns the second child PhylogenyNode of this
 301      * PhylogenyNode.
 302      * <p>
 303      * [last modified May 18, 2005 by CMZ]
 304      */
 305     final public PhylogenyNode getChildNode2() {
 306         return getChildNode( 1 );
 307     }
 308
 309     /**
 310      * This gets the child node index of this node.
 311      * <p>
 312      *
 313      * @return the child node index of this node
 314      * @throws UnsupportedOperationException
 315      *             if this node is a root node
 316      */
 317     final public int getChildNodeIndex() {
 318         return getChildNodeIndex( getParent() );
 319     }
 320
 321     /**
 322      * This gets the child node index of this node, given that parent is its
 323      * parent
 324      * <p>
 325      * [last modified Aug 14, 2006 by CMZ]
 326      *
 327      * @return the child node index of this node
 328      * @throws UnsupportedOperationException
 329      *             if this node is a root node
 330      */
 331     final public int getChildNodeIndex( final PhylogenyNode parent ) {
 332         if ( isRoot() ) {
 333             throw new UnsupportedOperationException( "Cannot get the child index for a root node." );
 334         }
 335         for( int i = 0; i < parent.getNumberOfDescendants(); ++i ) {
 336             if ( parent.getChildNode( i ) == this ) {
 337                 return i;
 338             }
 339         }
 340         throw new RuntimeException( "Unexpected exception: Could not determine the child index for node: " + this );
 341     }
 342
 343     final public List<PhylogenyNode> getDescendants() {
 344         if ( _descendants == null ) {
 345             _descendants = new ArrayList<PhylogenyNode>();
 346         }
 347         return _descendants;
 348     }
 349
 350     /**
 351      * Returns the length of the branch leading to the _parent of this
 352      * PhylogenyNode (double).
 353      */
 354     @Override
 355     final public double getDistanceToParent() {
 356         return _distance_parent;
 357     }
 358
 359     /**
 360      * Convenience method. Returns the first child node of this node.
 361      * <p>
 362      * [last modified May 18, 2005 by CMZ]
 363      *
 364      * @return the first child node of this node
 365      */
 366     public final PhylogenyNode getFirstChildNode() {
 367         return getChildNode( 0 );
 368     }
 369
 370     /**
 371      * Returns the _indicator value of this PhylogenyNode.
 372      */
 373     public final byte getIndicator() {
 374         return _indicator;
 375     }
 376
 377     /**
 378      * Convenience method. Returns the last child node of this node.
 379      * <p>
 380      * [last modified May 18, 2005 by CMZ]
 381      *
 382      * @return the last child node of this node
 383      */
 384     public final PhylogenyNode getLastChildNode() {
 385         return getChildNode( getNumberOfDescendants() - 1 );
 386     }
 387
 388     /**
 389      * Returns a refernce to the linked PhylogenyNode of this PhylogenyNode.
 390      * Currently, this method is only used for the speciation-_duplication
 391      * assignment algorithms.
 392      */
 393     public final PhylogenyNode getLink() {
 394         return _link;
 395     }
 396
 397     /**
 398      * Returns a refernce to the next external PhylogenyNode of this
 399      * PhylogenyNode. TODO should be in Phylogeny. Returns null if no next
 400      * external node is available.
 401      */
 402     public final PhylogenyNode getNextExternalNode() {
 403         if ( isInternal() ) {
 404             throw new UnsupportedOperationException( "attempt to get next external node of an internal node" );
 405         }
 406         else if ( isLastExternalNode() ) {
 407             return null;
 408         }
 409         int index = getChildNodeIndex();
 410         PhylogenyNode previous_node = this;
 411         PhylogenyNode current_node = getParent();
 412         while ( !current_node.isRoot()
 413                 && ( ( current_node.getNumberOfDescendants() == 1 ) || previous_node.isLastChildNode() ) ) {
 414             index = current_node.getChildNodeIndex();
 415             previous_node = current_node;
 416             current_node = current_node.getParent();
 417         }
 418         current_node = current_node.getChildNode( index + 1 );
 419         while ( current_node.isInternal() ) {
 420             current_node = current_node.getFirstChildNode();
 421         }
 422         return current_node;
 423     }
 424
 425     public final PhylogenyNode getNextExternalNodeWhileTakingIntoAccountCollapsedNodes() {
 426         //TODO work on me ~~
 427         if ( isInternal() && !isCollapse() ) {
 428             throw new UnsupportedOperationException( "attempt to get next external node of an uncollapsed internal node" );
 429         }
 430         if ( isRoot() ) {
 431             return null;
 432         }
 433         if ( getParent().isCollapse() ) {
 434             throw new UnsupportedOperationException( "attempt to get next external node of node with a collapsed parent" );
 435         }
 436         // This checks if last node.
 437         PhylogenyNode n = this;
 438         boolean last = true;
 439         while ( !n.isRoot() ) {
 440             if ( !n.isLastChildNode() ) {
 441                 last = false;
 442                 break;
 443             }
 444             n = n.getParent();
 445         }
 446         if ( last ) {
 447             return null;
 448         }
 449         int index = getChildNodeIndex();
 450         PhylogenyNode previous_node = this;
 451         PhylogenyNode current_node = getParent();
 452         while ( !current_node.isRoot()
 453                 && ( current_node.isCollapse() || ( current_node.getNumberOfDescendants() == 1 ) || previous_node
 454                         .isLastChildNode() ) ) {
 455             index = current_node.getChildNodeIndex();
 456             previous_node = current_node;
 457             current_node = current_node.getParent();
 458         }
 459         if ( index < current_node.getNumberOfDescendants() - 1 ) {
 460             current_node = current_node.getChildNode( index + 1 );
 461         }
 462         while ( current_node.isInternal() && !current_node.isCollapse() ) {
 463             current_node = current_node.getFirstChildNode();
 464         }
 465         return current_node;
 466     }
 467
 468     public final NodeData getNodeData() {
 469         if ( _node_data == null ) {
 470             _node_data = new NodeData();
 471         }
 472         return _node_data;
 473     }
 474
 475     final NodeData getNodeDataDirectly() {
 476         return _node_data;
 477     }
 478
 479     // ---------------------------------------------------------
 480     // Set and get methods for Nodes
 481     // ---------------------------------------------------------
 482     /**
 483      * Returns the ID (int) of this PhylogenyNode.
 484      */
 485     @Override
 486     final public int getId() {
 487         return _id;
 488     }
 489
 490     /**
 491      * Returns the name of this node.
 492      */
 493     @Override
 494     final public String getName() {
 495         return getNodeData().getNodeName();
 496     }
 497
 498     final public int getNumberOfDescendants() {
 499         if ( _descendants == null ) {
 500             return 0;
 501         }
 502         return _descendants.size();
 503     }
 504
 505     /**
 506      * Returns the total number of external Nodes originating from this
 507      * PhylogenyNode (int).
 508      */
 509     final public int getNumberOfExternalNodes() {
 510         return _sum_ext_nodes;
 511     }
 512
 513     final public int getNumberOfParents() {
 514         return 1;
 515     }
 516
 517     /**
 518      * Returns a refernce to the parent PhylogenyNode of this PhylogenyNode.
 519      */
 520     final public PhylogenyNode getParent() {
 521         return _parent;
 522     }
 523
 524     /**
 525      * Returns a refernce to the next external PhylogenyNode of this
 526      * PhylogenyNode. TODO should be in Phylogeny. Returns null if no next
 527      * external node is available.
 528      */
 529     final public PhylogenyNode getPreviousExternalNode() {
 530         if ( isInternal() ) {
 531             throw new UnsupportedOperationException( "Cannot get the previous external node for an internal node." );
 532         }
 533         else if ( isRoot() /* TODO && tree is rooted */) {
 534             throw new UnsupportedOperationException( "Cannot get the previous external node for a root node." );
 535         }
 536         else if ( isFirstExternalNode() ) {
 537             throw new UnsupportedOperationException( "Attempt to get previous external node of the first external node." );
 538         }
 539         int index = getChildNodeIndex();
 540         PhylogenyNode previous_node = this;
 541         PhylogenyNode current_node = getParent();
 542         while ( !current_node.isRoot()
 543                 && ( ( current_node.getNumberOfDescendants() == 1 ) || previous_node.isFirstChildNode() ) ) {
 544             index = current_node.getChildNodeIndex();
 545             previous_node = current_node;
 546             current_node = current_node.getParent();
 547         }
 548         current_node = current_node.getChildNode( index - 1 );
 549         while ( current_node.isInternal() ) {
 550             current_node = current_node.getLastChildNode();
 551         }
 552         return current_node;
 553     }
 554
 555     /**
 556      * Used for drawing of Trees.
 557      */
 558     final public float getXcoord() {
 559         return _x;
 560     }
 561
 562     final public float getXSecondary() {
 563         return _x_secondary;
 564     }
 565
 566     /**
 567      * Used for drawing of Trees.
 568      */
 569     final public float getYcoord() {
 570         return _y;
 571     }
 572
 573     final public float getYSecondary() {
 574         return _y_secondary;
 575     }
 576
 577     @Override
 578     final public int hashCode() {
 579         final NodeData data = getNodeData();
 580         if ( ( getName().length() < 1 ) && !data.isHasSequence() && !data.isHasTaxonomy() ) {
 581             return super.hashCode();
 582         }
 583         int result = getName().hashCode();
 584         if ( data.isHasSequence() ) {
 585             result ^= data.getSequence().hashCode();
 586         }
 587         if ( data.isHasTaxonomy() ) {
 588             result ^= data.getTaxonomy().hashCode();
 589         }
 590         return result;
 591     }
 592
 593     // final private void init() {
 594     //_descendants = new ArrayList<PhylogenyNode>();
 595     //  _parent = null; //TODO not needed?
 596     //  _id = 0; //TODO not needed?
 597     //initializeData(); //TODO not needed?
 598     //}
 599     /**
 600      * Deletes data of this PhylogenyNode. Links to the other Nodes in the
 601      * Phylogeny, the ID and the sum of external nodes are NOT deleted. Field
 602      * "_link" (_link to Nodes in other Phylogeny) IS deleted.
 603      *
 604      * @see #getLink() (Last modified: 12/20/03)
 605      */
 606     //    final private void initializeData() {
 607     //        _indicator = 0;
 608     //        _x = 0;
 609     //        _y = 0;
 610     //        //_node_name = "";
 611     //        _distance_parent = PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT;
 612     //        _collapse = false;
 613     //        _link = null;
 614     //        _branch_data = null;
 615     //        _node_data = null;
 616     //    }
 617     /**
 618      * Returns whether this PhylogenyNode should be drawn as collapsed.
 619      */
 620     final public boolean isCollapse() {
 621         return _collapse;
 622     }
 623
 624     /**
 625      * Returns true if this PhylogenyNode represents a _duplication event, false
 626      * otherwise.
 627      */
 628     final public boolean isDuplication() {
 629         return getNodeData().isHasEvent() && getNodeData().getEvent().isDuplication();
 630     }
 631
 632     /**
 633      * Checks whether this PhylogenyNode is external (tip).
 634      *
 635      * @return true if this PhylogenyNode is external, false otherwise
 636      */
 637     final public boolean isExternal() {
 638         if ( _descendants == null ) {
 639             return true;
 640         }
 641         return ( getNumberOfDescendants() < 1 );
 642     }
 643
 644     /**
 645      * DOCUMENT ME!
 646      *
 647      * @return DOCUMENT ME!
 648      */
 649     final public boolean isFirstChildNode() {
 650         if ( isRoot() /* and tree is rooted TODO */) {
 651             throw new UnsupportedOperationException( "Cannot determine whether the root is the first child node of its _parent." );
 652         }
 653         return ( getChildNodeIndex() == 0 );
 654     }
 655
 656     /**
 657      * DOCUMENT ME!
 658      *
 659      * @return DOCUMENT ME!
 660      */
 661     final public boolean isFirstExternalNode() {
 662         if ( isInternal() ) {
 663             return false;
 664         }
 665         PhylogenyNode node = this;
 666         while ( !node.isRoot() ) {
 667             if ( !node.isFirstChildNode() ) {
 668                 return false;
 669             }
 670             node = node.getParent();
 671         }
 672         return true;
 673     }
 674
 675     /**
 676      * Returns whether a _duplication or speciation event has been assigned for
 677      * this PhylogenyNode.
 678      */
 679     final public boolean isHasAssignedEvent() {
 680         if ( !getNodeData().isHasEvent() ) {
 681             return false;
 682         }
 683         if ( ( getNodeData().getEvent() ).isUnassigned() ) {
 684             return false;
 685         }
 686         return true;
 687     }
 688
 689     /**
 690      * Checks whether this PhylogenyNode is internal (tip).
 691      *
 692      * @return true if this PhylogenyNode is external, false otherwise
 693      */
 694     final public boolean isInternal() {
 695         return ( !isExternal() );
 696     }
 697
 698     /**
 699      * Returns true if this node is the last child node of its _parent.
 700      * <p>
 701      * [last modified June 01, 2005 by CMZ]
 702      *
 703      * @return true if this node is the last child node of its _parent, false
 704      *         otherwise
 705      */
 706     final public boolean isLastChildNode() {
 707         if ( isRoot() /* and tree is rooted TODO */) {
 708             throw new UnsupportedOperationException( "Cannot determine whether the root is the last child node of its _parent." );
 709         }
 710         return ( getChildNodeIndex() == ( getParent().getNumberOfDescendants() - 1 ) );
 711     }
 712
 713     /**
 714      * DOCUMENT ME!
 715      *
 716      * @return DOCUMENT ME!
 717      */
 718     final public boolean isLastExternalNode() {
 719         if ( isInternal() ) {
 720             return false;
 721         }
 722         PhylogenyNode node = this;
 723         while ( !node.isRoot() ) {
 724             if ( !node.isLastChildNode() ) {
 725                 return false;
 726             }
 727             node = node.getParent();
 728         }
 729         return true;
 730     }
 731
 732     /**
 733      * Checks whether this PhylogenyNode is a root.
 734      *
 735      * @return true if this PhylogenyNode is the root, false otherwise
 736      */
 737     final public boolean isRoot() {
 738         return _parent == null;
 739     }
 740
 741     final public boolean isSpeciation() {
 742         return getNodeData().isHasEvent() && getNodeData().getEvent().isSpeciation();
 743     }
 744
 745     // ---------------------------------------------------------
 746     // Iterator
 747     // ---------------------------------------------------------
 748     final public PhylogenyNodeIterator iterateChildNodesForward() {
 749         return new ChildNodeIteratorForward( this );
 750     }
 751
 752     // ---------------------------------------------------------
 753     // Basic printing
 754     // ---------------------------------------------------------
 755     /**
 756      * Prints to the console the subtree originating from this PhylogenyNode in
 757      * preorder.
 758      */
 759     public void preorderPrint() {
 760         System.out.println( this + "\n" );
 761         if ( isInternal() ) {
 762             for( int i = 0; i < getNumberOfDescendants(); ++i ) {
 763                 getChildNode( i ).preorderPrint();
 764             }
 765         }
 766     }
 767
 768     final public void removeChildNode( final int i ) {
 769         if ( isExternal() ) {
 770             throw new UnsupportedOperationException( "cannot get the child node for a external node." );
 771         }
 772         if ( ( i >= getNumberOfDescendants() ) || ( i < 0 ) ) {
 773             throw new IllegalArgumentException( "attempt to get child node " + i + " of a node with "
 774                     + getNumberOfDescendants() + " child nodes." );
 775         }
 776         getDescendants().remove( i );
 777     }
 778
 779     final public void removeChildNode( final PhylogenyNode remove_me ) {
 780         removeChildNode( remove_me.getChildNodeIndex() );
 781     }
 782
 783     final public void setBranchData( final BranchData branch_data ) {
 784         _branch_data = branch_data;
 785     }
 786
 787     /**
 788      * Sets the first child PhylogenyNode of this PhylogenyNode to n.
 789      */
 790     final public void setChild1( final PhylogenyNode n ) {
 791         setChildNode( 0, n );
 792     }
 793
 794     /**
 795      * Sets the second child PhylogenyNode of this PhylogenyNode to n.
 796      */
 797     final public void setChild2( final PhylogenyNode n ) {
 798         setChildNode( 1, n );
 799     }
 800
 801     /**
 802      * Inserts PhylogenyNode n at the specified position i into the list of
 803      * child nodes. This does not allow null slots in the list of child nodes:
 804      * If i is larger than the number of child nodes, n is just added to the
 805      * list, not place at index i.
 806      *
 807      * @param i
 808      *            the index of position where to add the child
 809      * @param n
 810      *            the PhylogenyNode to add
 811      */
 812     final public void setChildNode( final int i, final PhylogenyNode node ) {
 813         node.setParent( this );
 814         if ( getNumberOfDescendants() <= i ) {
 815             addChildNode( node );
 816         }
 817         else {
 818             getDescendants().set( i, node );
 819         }
 820     }
 821
 822     final void setChildNodeOnly( final int i, final PhylogenyNode node ) {
 823         if ( getNumberOfDescendants() <= i ) {
 824             addChildNode( node );
 825         }
 826         else {
 827             getDescendants().set( i, node );
 828         }
 829     }
 830
 831     /**
 832      * Sets whether this PhylogenyNode should be drawn as collapsed.
 833      */
 834     final public void setCollapse( final boolean b ) {
 835         _collapse = b;
 836     }
 837
 838     /**
 839      * Sets the length of the branch leading to the _parent of this
 840      * PhylogenyNode to double d.
 841      */
 842     @Override
 843     final public void setDistanceToParent( final double d ) {
 844         _distance_parent = d;
 845     }
 846
 847     /**
 848      * Sets the _indicator value of this PhylogenyNode to i.
 849      */
 850     final public void setIndicator( final byte i ) {
 851         _indicator = i;
 852     }
 853
 854     // --------------------------------------------------------------------
 855     // Adjust methods (related to Phylogeny construction and
 856     // Phylogeny modification)
 857     // --------------------------------------------------------------------
 858     /**
 859      * Sets the indicators of all the children of this PhylogenyNode to zero.
 860      */
 861     final void setIndicatorsToZero() {
 862         for( final PreorderTreeIterator it = new PreorderTreeIterator( this ); it.hasNext(); ) {
 863             it.next().setIndicator( ( byte ) 0 );
 864         }
 865     }
 866
 867     /**
 868      * Sets the linked PhylogenyNode of this PhylogenyNode to n. Currently, this
 869      * method is only used for the speciation-_duplication assignment
 870      * algorithms.
 871      */
 872     final public void setLink( final PhylogenyNode n ) {
 873         _link = n;
 874     }
 875
 876     /**
 877      * Sets the name of this node.
 878      */
 879     @Override
 880     final public void setName( final String node_name ) {
 881         getNodeData().setNodeName( node_name );
 882     }
 883
 884     /**
 885      * Sets the Id of this PhylogenyNode to i. In most cases, this number
 886      * should not be set to values lower than getNodeCount() -- which this method
 887      * does not allow.
 888      */
 889     synchronized final protected void setId( final int i ) {
 890         if ( i < getNodeCount() ) {
 891             throw new IllegalArgumentException( "attempt to set node id to a value less than total node count (thus violating the uniqueness of node ids)" );
 892         }
 893         _id = i;
 894     }
 895
 896     /**
 897      * Sets the _parent PhylogenyNode of this PhylogenyNode to n.
 898      */
 899     @Override
 900     final public void setParent( final PhylogenyNode n ) {
 901         _parent = n;
 902     }
 903
 904     /**
 905      * Sets the total number of external Nodes originating from this
 906      * PhylogenyNode to i (int).
 907      */
 908     final public void setSumExtNodes( final int i ) {
 909         if ( i < 0 ) {
 910             throw new IllegalArgumentException( "attempt to set sum of external nodes to less than one" );
 911         }
 912         _sum_ext_nodes = i;
 913     }
 914
 915     /**
 916      * Used for drawing of Trees.
 917      */
 918     final public void setXcoord( final float x ) {
 919         _x = x;
 920     }
 921
 922     final public void setXSecondary( final float x_secondary ) {
 923         _x_secondary = x_secondary;
 924     }
 925
 926     // -----------
 927     /**
 928      * Used for drawing of Trees.
 929      */
 930     final public void setYcoord( final float y ) {
 931         _y = y;
 932     }
 933
 934     final public void setYSecondary( final float y_secondary ) {
 935         _y_secondary = y_secondary;
 936     }
 937
 938     // ---------------------------------------------------------
 939     // Writing of Nodes to Strings
 940     // ---------------------------------------------------------
 941     final public String toNewHampshire( final boolean simple_nh,
 942                                         final boolean write_distance_to_parent,
 943                                         final NH_CONVERSION_SUPPORT_VALUE_STYLE svs ) {
 944         final StringBuilder sb = new StringBuilder();
 945         String data = "";
 946         if ( ( svs == NH_CONVERSION_SUPPORT_VALUE_STYLE.AS_INTERNAL_NODE_NAMES ) && !isExternal() ) {
 947             if ( getBranchData().isHasConfidences()
 948                     && ( getBranchData().getConfidence( 0 ).getValue() != Confidence.CONFIDENCE_DEFAULT_VALUE ) ) {
 949                 data = Confidence.FORMATTER.format( ForesterUtil
 950                         .round( getBranchData().getConfidence( 0 ).getValue(),
 951                                 PhyloXmlUtil.ROUNDING_DIGITS_FOR_PHYLOXML_DOUBLE_OUTPUT ) );
 952             }
 953         }
 954         else if ( !ForesterUtil.isEmpty( getName() ) ) {
 955             data = getName();
 956         }
 957         else if ( getNodeData().isHasTaxonomy() ) {
 958             if ( !ForesterUtil.isEmpty( getNodeData().getTaxonomy().getTaxonomyCode() ) ) {
 959                 data = getNodeData().getTaxonomy().getTaxonomyCode();
 960             }
 961             else if ( !ForesterUtil.isEmpty( getNodeData().getTaxonomy().getScientificName() ) ) {
 962                 data = getNodeData().getTaxonomy().getScientificName();
 963             }
 964             else if ( !ForesterUtil.isEmpty( getNodeData().getTaxonomy().getCommonName() ) ) {
 965                 data = getNodeData().getTaxonomy().getCommonName();
 966             }
 967             else if ( getNodeData().getTaxonomy().getTaxonomyCode() != null ) {
 968                 data = getNodeData().getTaxonomy().getTaxonomyCode();
 969             }
 970         }
 971         else if ( getNodeData().isHasSequence() ) {
 972             if ( !ForesterUtil.isEmpty( getNodeData().getSequence().getName() ) ) {
 973                 data = getNodeData().getSequence().getName();
 974             }
 975         }
 976         if ( data.length() > 0 ) {
 977             data = ForesterUtil.replaceIllegalNhCharacters( data );
 978             if ( simple_nh && ( data.length() > 10 ) ) {
 979                 data = data.substring( 0, 11 );
 980             }
 981             if ( ForesterUtil.isContainsParanthesesableNhCharacter( data ) ) {
 982                 sb.append( '\'' );
 983                 sb.append( data );
 984                 sb.append( '\'' );
 985             }
 986             else {
 987                 sb.append( data );
 988             }
 989         }
 990         if ( write_distance_to_parent && ( getDistanceToParent() != PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ) ) {
 991             sb.append( ":" );
 992             sb.append( getDistanceToParent() );
 993         }
 994         if ( ( svs == NH_CONVERSION_SUPPORT_VALUE_STYLE.IN_SQUARE_BRACKETS ) && !isExternal()
 995                 && getBranchData().isHasConfidences()
 996                 && ( getBranchData().getConfidence( 0 ).getValue() != Confidence.CONFIDENCE_DEFAULT_VALUE ) ) {
 997             sb.append( "[" );
 998             sb.append( Confidence.FORMATTER.format( ForesterUtil
 999                     .round( getBranchData().getConfidence( 0 ).getValue(),
1000                             PhyloXmlUtil.ROUNDING_DIGITS_FOR_PHYLOXML_DOUBLE_OUTPUT ) ) );
1001             sb.append( "]" );
1002         }
1003         return sb.toString();
1004     }
1005
1006     /**
1007      * Swaps the the two childern of a PhylogenyNode node of this Phylogeny.
1008      */
1009     public final void swapChildren() throws RuntimeException {
1010         if ( isExternal() ) {
1011             throw new RuntimeException( "attempt to swap descendants of external node" );
1012         }
1013         if ( getNumberOfDescendants() != 2 ) {
1014             throw new RuntimeException( "attempt to swap descendants of node with " + getNumberOfDescendants()
1015                     + " descendants" );
1016         }
1017         final PhylogenyNode a = getChildNode( 0 );
1018         final PhylogenyNode b = getChildNode( 1 );
1019         setChildNode( 0, b );
1020         setChildNode( 1, a );
1021     }
1022
1023     /**
1024      * Converts this PhylogenyNode to a New Hampshire X (NHX) String
1025      * representation.
1026      */
1027     final public String toNewHampshireX() {
1028         final StringBuffer sb = new StringBuffer();
1029         final StringBuffer s_nhx = new StringBuffer();
1030         if ( !ForesterUtil.isEmpty( getName() ) ) {
1031             final String name = ForesterUtil.replaceIllegalNhCharacters( getName() );
1032             if ( ForesterUtil.isContainsParanthesesableNhCharacter( name ) ) {
1033                 sb.append( '\'' );
1034                 sb.append( name );
1035                 sb.append( '\'' );
1036             }
1037             else {
1038                 sb.append( name );
1039             }
1040         }
1041         if ( getDistanceToParent() != PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ) {
1042             sb.append( ":" );
1043             sb.append( getDistanceToParent() );
1044         }
1045         if ( getNodeDataDirectly() != null ) {
1046             s_nhx.append( getNodeDataDirectly().toNHX() );
1047         }
1048         if ( getBranchDataDirectly() != null ) {
1049             s_nhx.append( getBranchDataDirectly().toNHX() );
1050         }
1051         if ( s_nhx.length() > 0 ) {
1052             sb.append( "[&&NHX" );
1053             sb.append( s_nhx );
1054             sb.append( "]" );
1055         }
1056         return sb.toString();
1057     }
1058
1059     @Override
1060     final public String toString() {
1061         StringBuilder sb = new StringBuilder();
1062         if ( ForesterUtil.isEmpty( getName() ) ) {
1063             sb.append( getName() );
1064             sb.append( " " );
1065         }
1066         if ( getNodeData().isHasTaxonomy() ) {
1067             if ( !ForesterUtil.isEmpty( getNodeData().getTaxonomy().getScientificName() ) ) {
1068                 sb.append( getNodeData().getTaxonomy().getScientificName() );
1069                 sb.append( " " );
1070             }
1071             else if ( !ForesterUtil.isEmpty( getNodeData().getTaxonomy().getTaxonomyCode() ) ) {
1072                 sb.append( getNodeData().getTaxonomy().getTaxonomyCode() );
1073                 sb.append( " " );
1074             }
1075             else if ( getNodeData().getTaxonomy().getIdentifier() != null ) {
1076                 sb.append( getNodeData().getTaxonomy().getIdentifier().toString() );
1077                 sb.append( " " );
1078             }
1079         }
1080         if ( getNodeData().isHasSequence() ) {
1081             if ( !ForesterUtil.isEmpty( getNodeData().getSequence().getName() ) ) {
1082                 sb.append( getNodeData().getSequence().getName() );
1083                 sb.append( " " );
1084             }
1085             else if ( !ForesterUtil.isEmpty( getNodeData().getSequence().getSymbol() ) ) {
1086                 sb.append( getNodeData().getSequence().getSymbol() );
1087                 sb.append( " " );
1088             }
1089             else if ( getNodeData().getSequence().getAccession() != null ) {
1090                 sb.append( getNodeData().getTaxonomy().getIdentifier().toString() );
1091                 sb.append( " " );
1092             }
1093         }
1094         if ( sb.length() <= 1 ) {
1095             sb.append( "[" );
1096             sb.append( getId() );
1097             sb.append( "]" );
1098         }
1099         return sb.toString().trim();
1100     }
1101
1102     /**
1103      * Decreases the total number of all Nodes created so far by one.
1104      */
1105     final static synchronized void decreaseNodeCount() {
1106         --PhylogenyNode._node_count;
1107     }
1108
1109     /**
1110      * Returns the total number of all Nodes created so far.
1111      *
1112      * @return total number of Nodes (int)
1113      */
1114     synchronized final public static int getNodeCount() {
1115         return PhylogenyNode._node_count;
1116     }
1117
1118     /**
1119      * Increases the total number of all Nodes created so far by one.
1120      */
1121     synchronized final private static void increaseNodeCount() {
1122         ++PhylogenyNode._node_count;
1123     }
1124
1125     /**
1126      * Sets the total number of all Nodes created so far to i (int).
1127      */
1128     synchronized final static void setNodeCount( final int i ) {
1129         PhylogenyNode._node_count = i;
1130     }
1131
1132     public static PhylogenyNode createInstanceFromNhxString( final String nhx ) throws NHXFormatException {
1133         return new PhylogenyNode( nhx, PhylogenyMethods.TAXONOMY_EXTRACTION.NO, false );
1134     }
1135
1136     public static PhylogenyNode createInstanceFromNhxString( final String nhx,
1137                                                              final PhylogenyMethods.TAXONOMY_EXTRACTION taxonomy_extraction )
1138             throws NHXFormatException {
1139         return new PhylogenyNode( nhx, taxonomy_extraction, false );
1140     }
1141
1142     public static PhylogenyNode createInstanceFromNhxString( final String nhx,
1143                                                              final PhylogenyMethods.TAXONOMY_EXTRACTION taxonomy_extraction,
1144                                                              final boolean replace_underscores )
1145             throws NHXFormatException {
1146         return new PhylogenyNode( nhx, taxonomy_extraction, replace_underscores );
1147     }
1148
1149     private PhylogenyNode( final String nhx,
1150                            final PhylogenyMethods.TAXONOMY_EXTRACTION taxonomy_extraction,
1151                            final boolean replace_underscores ) throws NHXFormatException {
1152         //  init();
1153         NHXParser.parseNHX( nhx, this, taxonomy_extraction, replace_underscores );
1154         setId( PhylogenyNode.getNodeCount() );
1155         PhylogenyNode.increaseNodeCount();
1156         setSumExtNodes( 1 ); // For ext node, this number is 1 (not 0!!)
1157     }
1158 }