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

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