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     final public int compareTo( final PhylogenyNode o ) {
 107         final PhylogenyNode n = o;
 108         if ( ( getName() == null ) || ( n.getName() == null ) ) {
 109             return 0;
 110         }
 111         return getName().compareTo( n.getName() );
 112     }
 113
 114     // ---------------------------------------------------------
 115     // Copy and delete Nodes, copy subtress
 116     // ---------------------------------------------------------
 117     /**
 118      * Returns a new PhylogenyNode which has its data copied from this
 119      * PhylogenyNode. Links to the other Nodes in the same Phylogeny are NOT
 120      * copied (e.g. _link to _parent). Field "_link" IS copied.
 121      *
 122      * @see #getLink()
 123      */
 124     final public PhylogenyNode copyNodeData() {
 125         final PhylogenyNode node = new PhylogenyNode();
 126         PhylogenyNode.decreaseNodeCount();
 127         node._id = _id;
 128         node._sum_ext_nodes = _sum_ext_nodes;
 129         node._indicator = _indicator;
 130         node._x = _x;
 131         node._y = _y;
 132         node._distance_parent = _distance_parent;
 133         node._collapse = _collapse;
 134         node._link = _link;
 135         if ( _node_data != null ) {
 136             node._node_data = ( NodeData ) _node_data.copy();
 137         }
 138         if ( _branch_data != null ) {
 139             node._branch_data = ( BranchData ) _branch_data.copy();
 140         }
 141         return node;
 142     }
 143
 144     /**
 145      * Returns a new PhylogenyNode which has the same data as this
 146      * PhylogenyNode. Links to the other Nodes in the same Phylogeny are NOT
 147      * copied (e.g. _link to _parent). Field "_link" IS copied.
 148      *
 149      * @see #getLink()
 150      */
 151     final public PhylogenyNode copyNodeDataShallow() {
 152         final PhylogenyNode node = new PhylogenyNode();
 153         PhylogenyNode.decreaseNodeCount();
 154         node._id = _id;
 155         node._sum_ext_nodes = _sum_ext_nodes;
 156         node._indicator = _indicator;
 157         node._x = _x;
 158         node._y = _y;
 159         node._distance_parent = _distance_parent;
 160         node._collapse = _collapse;
 161         node._link = _link;
 162         node._node_data = _node_data;
 163         node._branch_data = _branch_data;
 164         return node;
 165     }
 166
 167     @Override
 168     /**
 169      * Based on node name, sequence, and taxonomy.
 170      *
 171      *
 172      */
 173     final public boolean equals( final Object o ) {
 174         System.out.print( " PN___e___ " );
 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         System.out.print( " PNh " );
 580         final NodeData data = getNodeData();
 581         if ( ( getName().length() < 1 ) && !data.isHasSequence() && !data.isHasTaxonomy() ) {
 582             return super.hashCode();
 583         }
 584         int result = getName().hashCode();
 585         if ( data.isHasSequence() ) {
 586             result ^= data.getSequence().hashCode();
 587         }
 588         if ( data.isHasTaxonomy() ) {
 589             result ^= data.getTaxonomy().hashCode();
 590         }
 591         return result;
 592     }
 593
 594     // final private void init() {
 595     //_descendants = new ArrayList<PhylogenyNode>();
 596     //  _parent = null; //TODO not needed?
 597     //  _id = 0; //TODO not needed?
 598     //initializeData(); //TODO not needed?
 599     //}
 600     /**
 601      * Deletes data of this PhylogenyNode. Links to the other Nodes in the
 602      * Phylogeny, the ID and the sum of external nodes are NOT deleted. Field
 603      * "_link" (_link to Nodes in other Phylogeny) IS deleted.
 604      *
 605      * @see #getLink() (Last modified: 12/20/03)
 606      */
 607     //    final private void initializeData() {
 608     //        _indicator = 0;
 609     //        _x = 0;
 610     //        _y = 0;
 611     //        //_node_name = "";
 612     //        _distance_parent = PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT;
 613     //        _collapse = false;
 614     //        _link = null;
 615     //        _branch_data = null;
 616     //        _node_data = null;
 617     //    }
 618     /**
 619      * Returns whether this PhylogenyNode should be drawn as collapsed.
 620      */
 621     final public boolean isCollapse() {
 622         return _collapse;
 623     }
 624
 625     /**
 626      * Returns true if this PhylogenyNode represents a _duplication event, false
 627      * otherwise.
 628      */
 629     final public boolean isDuplication() {
 630         return getNodeData().isHasEvent() && getNodeData().getEvent().isDuplication();
 631     }
 632
 633     /**
 634      * Checks whether this PhylogenyNode is external (tip).
 635      *
 636      * @return true if this PhylogenyNode is external, false otherwise
 637      */
 638     final public boolean isExternal() {
 639         if ( _descendants == null ) {
 640             return true;
 641         }
 642         return ( getNumberOfDescendants() < 1 );
 643     }
 644
 645     /**
 646      * DOCUMENT ME!
 647      *
 648      * @return DOCUMENT ME!
 649      */
 650     final public boolean isFirstChildNode() {
 651         if ( isRoot() /* and tree is rooted TODO */) {
 652             throw new UnsupportedOperationException( "Cannot determine whether the root is the first child node of its _parent." );
 653         }
 654         return ( getChildNodeIndex() == 0 );
 655     }
 656
 657     /**
 658      * DOCUMENT ME!
 659      *
 660      * @return DOCUMENT ME!
 661      */
 662     final public boolean isFirstExternalNode() {
 663         if ( isInternal() ) {
 664             return false;
 665         }
 666         PhylogenyNode node = this;
 667         while ( !node.isRoot() ) {
 668             if ( !node.isFirstChildNode() ) {
 669                 return false;
 670             }
 671             node = node.getParent();
 672         }
 673         return true;
 674     }
 675
 676     /**
 677      * Returns whether a _duplication or speciation event has been assigned for
 678      * this PhylogenyNode.
 679      */
 680     final public boolean isHasAssignedEvent() {
 681         if ( !getNodeData().isHasEvent() ) {
 682             return false;
 683         }
 684         if ( ( getNodeData().getEvent() ).isUnassigned() ) {
 685             return false;
 686         }
 687         return true;
 688     }
 689
 690     /**
 691      * Checks whether this PhylogenyNode is internal (tip).
 692      *
 693      * @return true if this PhylogenyNode is external, false otherwise
 694      */
 695     final public boolean isInternal() {
 696         return ( !isExternal() );
 697     }
 698
 699     /**
 700      * Returns true if this node is the last child node of its _parent.
 701      * <p>
 702      * [last modified June 01, 2005 by CMZ]
 703      *
 704      * @return true if this node is the last child node of its _parent, false
 705      *         otherwise
 706      */
 707     final public boolean isLastChildNode() {
 708         if ( isRoot() /* and tree is rooted TODO */) {
 709             throw new UnsupportedOperationException( "Cannot determine whether the root is the last child node of its _parent." );
 710         }
 711         return ( getChildNodeIndex() == ( getParent().getNumberOfDescendants() - 1 ) );
 712     }
 713
 714     /**
 715      * DOCUMENT ME!
 716      *
 717      * @return DOCUMENT ME!
 718      */
 719     final public boolean isLastExternalNode() {
 720         if ( isInternal() ) {
 721             return false;
 722         }
 723         PhylogenyNode node = this;
 724         while ( !node.isRoot() ) {
 725             if ( !node.isLastChildNode() ) {
 726                 return false;
 727             }
 728             node = node.getParent();
 729         }
 730         return true;
 731     }
 732
 733     /**
 734      * Checks whether this PhylogenyNode is a root.
 735      *
 736      * @return true if this PhylogenyNode is the root, false otherwise
 737      */
 738     final public boolean isRoot() {
 739         return _parent == null;
 740     }
 741
 742     final public boolean isSpeciation() {
 743         return getNodeData().isHasEvent() && getNodeData().getEvent().isSpeciation();
 744     }
 745
 746     // ---------------------------------------------------------
 747     // Iterator
 748     // ---------------------------------------------------------
 749     final public PhylogenyNodeIterator iterateChildNodesForward() {
 750         return new ChildNodeIteratorForward( this );
 751     }
 752
 753     // ---------------------------------------------------------
 754     // Basic printing
 755     // ---------------------------------------------------------
 756     /**
 757      * Prints to the console the subtree originating from this PhylogenyNode in
 758      * preorder.
 759      */
 760     public void preorderPrint() {
 761         System.out.println( this + "\n" );
 762         if ( isInternal() ) {
 763             for( int i = 0; i < getNumberOfDescendants(); ++i ) {
 764                 getChildNode( i ).preorderPrint();
 765             }
 766         }
 767     }
 768
 769     final public void removeChildNode( final int i ) {
 770         if ( isExternal() ) {
 771             throw new UnsupportedOperationException( "cannot get the child node for a external node." );
 772         }
 773         if ( ( i >= getNumberOfDescendants() ) || ( i < 0 ) ) {
 774             throw new IllegalArgumentException( "attempt to get child node " + i + " of a node with "
 775                     + getNumberOfDescendants() + " child nodes." );
 776         }
 777         getDescendants().remove( i );
 778     }
 779
 780     final public void removeChildNode( final PhylogenyNode remove_me ) {
 781         removeChildNode( remove_me.getChildNodeIndex() );
 782     }
 783
 784     final public void setBranchData( final BranchData branch_data ) {
 785         _branch_data = branch_data;
 786     }
 787
 788     /**
 789      * Sets the first child PhylogenyNode of this PhylogenyNode to n.
 790      */
 791     final public void setChild1( final PhylogenyNode n ) {
 792         setChildNode( 0, n );
 793     }
 794
 795     /**
 796      * Sets the second child PhylogenyNode of this PhylogenyNode to n.
 797      */
 798     final public void setChild2( final PhylogenyNode n ) {
 799         setChildNode( 1, n );
 800     }
 801
 802     /**
 803      * Inserts PhylogenyNode n at the specified position i into the list of
 804      * child nodes. This does not allow null slots in the list of child nodes:
 805      * If i is larger than the number of child nodes, n is just added to the
 806      * list, not place at index i.
 807      *
 808      * @param i
 809      *            the index of position where to add the child
 810      * @param n
 811      *            the PhylogenyNode to add
 812      */
 813     final public void setChildNode( final int i, final PhylogenyNode node ) {
 814         node.setParent( this );
 815         if ( getNumberOfDescendants() <= i ) {
 816             addChildNode( node );
 817         }
 818         else {
 819             getDescendants().set( i, node );
 820         }
 821     }
 822
 823     final void setChildNodeOnly( final int i, final PhylogenyNode node ) {
 824         if ( getNumberOfDescendants() <= i ) {
 825             addChildNode( node );
 826         }
 827         else {
 828             getDescendants().set( i, node );
 829         }
 830     }
 831
 832     /**
 833      * Sets whether this PhylogenyNode should be drawn as collapsed.
 834      */
 835     final public void setCollapse( final boolean b ) {
 836         _collapse = b;
 837     }
 838
 839     /**
 840      * Sets the length of the branch leading to the _parent of this
 841      * PhylogenyNode to double d.
 842      */
 843     @Override
 844     final public void setDistanceToParent( final double d ) {
 845         _distance_parent = d;
 846     }
 847
 848     /**
 849      * Sets the _indicator value of this PhylogenyNode to i.
 850      */
 851     final public void setIndicator( final byte i ) {
 852         _indicator = i;
 853     }
 854
 855     // --------------------------------------------------------------------
 856     // Adjust methods (related to Phylogeny construction and
 857     // Phylogeny modification)
 858     // --------------------------------------------------------------------
 859     /**
 860      * Sets the indicators of all the children of this PhylogenyNode to zero.
 861      */
 862     final void setIndicatorsToZero() {
 863         for( final PreorderTreeIterator it = new PreorderTreeIterator( this ); it.hasNext(); ) {
 864             it.next().setIndicator( ( byte ) 0 );
 865         }
 866     }
 867
 868     /**
 869      * Sets the linked PhylogenyNode of this PhylogenyNode to n. Currently, this
 870      * method is only used for the speciation-_duplication assignment
 871      * algorithms.
 872      */
 873     final public void setLink( final PhylogenyNode n ) {
 874         _link = n;
 875     }
 876
 877     /**
 878      * Sets the name of this node.
 879      */
 880     @Override
 881     final public void setName( final String node_name ) {
 882         getNodeData().setNodeName( node_name );
 883     }
 884
 885     /**
 886      * Sets the Id of this PhylogenyNode to i. In most cases, this number
 887      * should not be set to values lower than getNodeCount() -- which this method
 888      * does not allow.
 889      */
 890     synchronized final protected void setId( final int i ) {
 891         if ( i < getNodeCount() ) {
 892             throw new IllegalArgumentException( "attempt to set node id to a value less than total node count (thus violating the uniqueness of node ids)" );
 893         }
 894         _id = i;
 895     }
 896
 897     /**
 898      * Sets the _parent PhylogenyNode of this PhylogenyNode to n.
 899      */
 900     @Override
 901     final public void setParent( final PhylogenyNode n ) {
 902         _parent = n;
 903     }
 904
 905     /**
 906      * Sets the total number of external Nodes originating from this
 907      * PhylogenyNode to i (int).
 908      */
 909     final public void setSumExtNodes( final int i ) {
 910         if ( i < 0 ) {
 911             throw new IllegalArgumentException( "attempt to set sum of external nodes to less than one" );
 912         }
 913         _sum_ext_nodes = i;
 914     }
 915
 916     /**
 917      * Used for drawing of Trees.
 918      */
 919     final public void setXcoord( final float x ) {
 920         _x = x;
 921     }
 922
 923     final public void setXSecondary( final float x_secondary ) {
 924         _x_secondary = x_secondary;
 925     }
 926
 927     // -----------
 928     /**
 929      * Used for drawing of Trees.
 930      */
 931     final public void setYcoord( final float y ) {
 932         _y = y;
 933     }
 934
 935     final public void setYSecondary( final float y_secondary ) {
 936         _y_secondary = y_secondary;
 937     }
 938
 939     // ---------------------------------------------------------
 940     // Writing of Nodes to Strings
 941     // ---------------------------------------------------------
 942     final public String toNewHampshire( final boolean simple_nh,
 943                                         final boolean write_distance_to_parent,
 944                                         final NH_CONVERSION_SUPPORT_VALUE_STYLE svs ) {
 945         final StringBuilder sb = new StringBuilder();
 946         String data = "";
 947         if ( ( svs == NH_CONVERSION_SUPPORT_VALUE_STYLE.AS_INTERNAL_NODE_NAMES ) && !isExternal() ) {
 948             if ( getBranchData().isHasConfidences()
 949                     && ( getBranchData().getConfidence( 0 ).getValue() != Confidence.CONFIDENCE_DEFAULT_VALUE ) ) {
 950                 data = Confidence.FORMATTER.format( ForesterUtil
 951                         .round( getBranchData().getConfidence( 0 ).getValue(),
 952                                 PhyloXmlUtil.ROUNDING_DIGITS_FOR_PHYLOXML_DOUBLE_OUTPUT ) );
 953             }
 954         }
 955         else if ( !ForesterUtil.isEmpty( getName() ) ) {
 956             data = getName();
 957         }
 958         else if ( getNodeData().isHasTaxonomy() ) {
 959             if ( !ForesterUtil.isEmpty( getNodeData().getTaxonomy().getTaxonomyCode() ) ) {
 960                 data = getNodeData().getTaxonomy().getTaxonomyCode();
 961             }
 962             else if ( !ForesterUtil.isEmpty( getNodeData().getTaxonomy().getScientificName() ) ) {
 963                 data = getNodeData().getTaxonomy().getScientificName();
 964             }
 965             else if ( !ForesterUtil.isEmpty( getNodeData().getTaxonomy().getCommonName() ) ) {
 966                 data = getNodeData().getTaxonomy().getCommonName();
 967             }
 968             else if ( getNodeData().getTaxonomy().getTaxonomyCode() != null ) {
 969                 data = getNodeData().getTaxonomy().getTaxonomyCode();
 970             }
 971         }
 972         else if ( getNodeData().isHasSequence() ) {
 973             if ( !ForesterUtil.isEmpty( getNodeData().getSequence().getName() ) ) {
 974                 data = getNodeData().getSequence().getName();
 975             }
 976         }
 977         if ( data.length() > 0 ) {
 978             data = ForesterUtil.replaceIllegalNhCharacters( data );
 979             if ( simple_nh && ( data.length() > 10 ) ) {
 980                 data = data.substring( 0, 11 );
 981             }
 982             if ( ForesterUtil.isContainsParanthesesableNhCharacter( data ) ) {
 983                 sb.append( '\'' );
 984                 sb.append( data );
 985                 sb.append( '\'' );
 986             }
 987             else {
 988                 sb.append( data );
 989             }
 990         }
 991         if ( write_distance_to_parent && ( getDistanceToParent() != PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ) ) {
 992             sb.append( ":" );
 993             sb.append( getDistanceToParent() );
 994         }
 995         if ( ( svs == NH_CONVERSION_SUPPORT_VALUE_STYLE.IN_SQUARE_BRACKETS ) && !isExternal()
 996                 && getBranchData().isHasConfidences()
 997                 && ( getBranchData().getConfidence( 0 ).getValue() != Confidence.CONFIDENCE_DEFAULT_VALUE ) ) {
 998             sb.append( "[" );
 999             sb.append( Confidence.FORMATTER.format( ForesterUtil
1000                     .round( getBranchData().getConfidence( 0 ).getValue(),
1001                             PhyloXmlUtil.ROUNDING_DIGITS_FOR_PHYLOXML_DOUBLE_OUTPUT ) ) );
1002             sb.append( "]" );
1003         }
1004         return sb.toString();
1005     }
1006
1007     /**
1008      * Swaps the the two childern of a PhylogenyNode node of this Phylogeny.
1009      */
1010     public final void swapChildren() throws RuntimeException {
1011         if ( isExternal() ) {
1012             throw new RuntimeException( "attempt to swap descendants of external node" );
1013         }
1014         if ( getNumberOfDescendants() != 2 ) {
1015             throw new RuntimeException( "attempt to swap descendants of node with " + getNumberOfDescendants()
1016                     + " descendants" );
1017         }
1018         final PhylogenyNode a = getChildNode( 0 );
1019         final PhylogenyNode b = getChildNode( 1 );
1020         setChildNode( 0, b );
1021         setChildNode( 1, a );
1022     }
1023
1024     /**
1025      * Converts this PhylogenyNode to a New Hampshire X (NHX) String
1026      * representation.
1027      */
1028     final public String toNewHampshireX() {
1029         final StringBuffer sb = new StringBuffer();
1030         final StringBuffer s_nhx = new StringBuffer();
1031         if ( !ForesterUtil.isEmpty( getName() ) ) {
1032             final String name = ForesterUtil.replaceIllegalNhCharacters( getName() );
1033             if ( ForesterUtil.isContainsParanthesesableNhCharacter( name ) ) {
1034                 sb.append( '\'' );
1035                 sb.append( name );
1036                 sb.append( '\'' );
1037             }
1038             else {
1039                 sb.append( name );
1040             }
1041         }
1042         if ( getDistanceToParent() != PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ) {
1043             sb.append( ":" );
1044             sb.append( getDistanceToParent() );
1045         }
1046         if ( getNodeDataDirectly() != null ) {
1047             s_nhx.append( getNodeDataDirectly().toNHX() );
1048         }
1049         if ( getBranchDataDirectly() != null ) {
1050             s_nhx.append( getBranchDataDirectly().toNHX() );
1051         }
1052         if ( s_nhx.length() > 0 ) {
1053             sb.append( "[&&NHX" );
1054             sb.append( s_nhx );
1055             sb.append( "]" );
1056         }
1057         return sb.toString();
1058     }
1059
1060     @Override
1061     final public String toString() {
1062         StringBuilder sb = new StringBuilder();
1063         if ( ForesterUtil.isEmpty( getName() ) ) {
1064             sb.append( getName() );
1065             sb.append( " " );
1066         }
1067         if ( getNodeData().isHasTaxonomy() ) {
1068             if ( !ForesterUtil.isEmpty( getNodeData().getTaxonomy().getScientificName() ) ) {
1069                 sb.append( getNodeData().getTaxonomy().getScientificName() );
1070                 sb.append( " " );
1071             }
1072             else if ( !ForesterUtil.isEmpty( getNodeData().getTaxonomy().getTaxonomyCode() ) ) {
1073                 sb.append( getNodeData().getTaxonomy().getTaxonomyCode() );
1074                 sb.append( " " );
1075             }
1076             else if ( getNodeData().getTaxonomy().getIdentifier() != null ) {
1077                 sb.append( getNodeData().getTaxonomy().getIdentifier().toString() );
1078                 sb.append( " " );
1079             }
1080         }
1081         if ( getNodeData().isHasSequence() ) {
1082             if ( !ForesterUtil.isEmpty( getNodeData().getSequence().getName() ) ) {
1083                 sb.append( getNodeData().getSequence().getName() );
1084                 sb.append( " " );
1085             }
1086             else if ( !ForesterUtil.isEmpty( getNodeData().getSequence().getSymbol() ) ) {
1087                 sb.append( getNodeData().getSequence().getSymbol() );
1088                 sb.append( " " );
1089             }
1090             else if ( getNodeData().getSequence().getAccession() != null ) {
1091                 sb.append( getNodeData().getTaxonomy().getIdentifier().toString() );
1092                 sb.append( " " );
1093             }
1094         }
1095         if ( sb.length() <= 1 ) {
1096             sb.append( "[" );
1097             sb.append( getId() );
1098             sb.append( "]" );
1099         }
1100         return sb.toString().trim();
1101     }
1102
1103     /**
1104      * Decreases the total number of all Nodes created so far by one.
1105      */
1106     final static synchronized void decreaseNodeCount() {
1107         --PhylogenyNode._node_count;
1108     }
1109
1110     /**
1111      * Returns the total number of all Nodes created so far.
1112      *
1113      * @return total number of Nodes (int)
1114      */
1115     synchronized final public static int getNodeCount() {
1116         return PhylogenyNode._node_count;
1117     }
1118
1119     /**
1120      * Increases the total number of all Nodes created so far by one.
1121      */
1122     synchronized final private static void increaseNodeCount() {
1123         ++PhylogenyNode._node_count;
1124     }
1125
1126     /**
1127      * Sets the total number of all Nodes created so far to i (int).
1128      */
1129     synchronized final static void setNodeCount( final int i ) {
1130         PhylogenyNode._node_count = i;
1131     }
1132
1133     public static PhylogenyNode createInstanceFromNhxString( final String nhx ) throws NHXFormatException {
1134         return new PhylogenyNode( nhx, PhylogenyMethods.TAXONOMY_EXTRACTION.NO, false );
1135     }
1136
1137     public static PhylogenyNode createInstanceFromNhxString( final String nhx,
1138                                                              final PhylogenyMethods.TAXONOMY_EXTRACTION taxonomy_extraction )
1139             throws NHXFormatException {
1140         return new PhylogenyNode( nhx, taxonomy_extraction, false );
1141     }
1142
1143     public static PhylogenyNode createInstanceFromNhxString( final String nhx,
1144                                                              final PhylogenyMethods.TAXONOMY_EXTRACTION taxonomy_extraction,
1145                                                              final boolean replace_underscores )
1146             throws NHXFormatException {
1147         return new PhylogenyNode( nhx, taxonomy_extraction, replace_underscores );
1148     }
1149
1150     private PhylogenyNode( final String nhx,
1151                            final PhylogenyMethods.TAXONOMY_EXTRACTION taxonomy_extraction,
1152                            final boolean replace_underscores ) throws NHXFormatException {
1153         //  init();
1154         NHXParser.parseNHX( nhx, this, taxonomy_extraction, replace_underscores );
1155         setId( PhylogenyNode.getNodeCount() );
1156         PhylogenyNode.increaseNodeCount();
1157         setSumExtNodes( 1 ); // For ext node, this number is 1 (not 0!!)
1158     }
1159 }