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