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