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