forester/java/src/org/forester/phylogeny/PhylogenyNode.java

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