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