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