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