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