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