forester/java/src/org/forester/phylogeny/Phylogeny.java

   1 // $Id:
   2 // FORESTER -- software libraries and applications
   3 // for evolutionary biology research and applications.
   4 //
   5 // Copyright (C) 2008-2009 Christian M. Zmasek
   6 // Copyright (C) 2008-2009 Burnham Institute for Medical Research
   7 // Copyright (C) 2000-2001 Washington University School of Medicine
   8 // and Howard Hughes Medical Institute
   9 // All rights reserved
  10 //
  11 // This library is free software; you can redistribute it and/or
  12 // modify it under the terms of the GNU Lesser General Public
  13 // License as published by the Free Software Foundation; either
  14 // version 2.1 of the License, or (at your option) any later version.
  15 //
  16 // This library is distributed in the hope that it will be useful,
  17 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  18 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  19 // Lesser General Public License for more details.
  20 //
  21 // You should have received a copy of the GNU Lesser General Public
  22 // License along with this library; if not, write to the Free Software
  23 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
  24 //
  25 // Contact: phylosoft @ gmail . com
  26 // WWW: https://sites.google.com/site/cmzmasek/home/software/forester
  27
  28 package org.forester.phylogeny;
  29
  30 import java.io.IOException;
  31 import java.util.ArrayList;
  32 import java.util.Arrays;
  33 import java.util.Collection;
  34 import java.util.HashMap;
  35 import java.util.Iterator;
  36 import java.util.List;
  37 import java.util.Map;
  38 import java.util.NoSuchElementException;
  39 import java.util.Vector;
  40 import java.util.regex.Matcher;
  41 import java.util.regex.Pattern;
  42
  43 import org.forester.io.parsers.nhx.NHXParser;
  44 import org.forester.io.writers.PhylogenyWriter;
  45 import org.forester.phylogeny.PhylogenyNode.NH_CONVERSION_SUPPORT_VALUE_STYLE;
  46 import org.forester.phylogeny.data.BranchData;
  47 import org.forester.phylogeny.data.Confidence;
  48 import org.forester.phylogeny.data.Identifier;
  49 import org.forester.phylogeny.data.PhylogenyDataUtil;
  50 import org.forester.phylogeny.data.Sequence;
  51 import org.forester.phylogeny.data.SequenceRelation;
  52 import org.forester.phylogeny.data.SequenceRelation.SEQUENCE_RELATION_TYPE;
  53 import org.forester.phylogeny.factories.ParserBasedPhylogenyFactory;
  54 import org.forester.phylogeny.factories.PhylogenyFactory;
  55 import org.forester.phylogeny.iterators.ExternalForwardIterator;
  56 import org.forester.phylogeny.iterators.LevelOrderTreeIterator;
  57 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
  58 import org.forester.phylogeny.iterators.PostorderTreeIterator;
  59 import org.forester.phylogeny.iterators.PreorderTreeIterator;
  60 import org.forester.util.FailedConditionCheckException;
  61 import org.forester.util.ForesterUtil;
  62
  63 public class Phylogeny {
  64
  65     public final static boolean                                 ALLOW_MULTIPLE_PARENTS_DEFAULT = false;
  66     private PhylogenyNode                                       _root;
  67     private boolean                                             _rooted;
  68     private boolean                                             _allow_multiple_parents;
  69     private String                                              _name;
  70     private String                                              _type;
  71     private String                                              _description;
  72     private String                                              _distance_unit;
  73     private Confidence                                          _confidence;
  74     private Identifier                                          _identifier;
  75     private boolean                                             _rerootable;
  76     private HashMap<Long, PhylogenyNode>                        _id_to_node_map;
  77     private List<PhylogenyNode>                                 _external_nodes_set;
  78     private Collection<Sequence>                                _sequenceRelationQueries;
  79     private Collection<SequenceRelation.SEQUENCE_RELATION_TYPE> _relevant_sequence_relation_types;
  80
  81     /**
  82      * Default Phylogeny constructor. Constructs an empty Phylogeny.
  83      */
  84     public Phylogeny() {
  85         init();
  86     }
  87
  88     /**
  89      * Adds this Phylogeny to the list of child nodes of PhylogenyNode parent
  90      * and sets the parent of this to parent.
  91      *
  92      * @param n
  93      *            the PhylogenyNode to add
  94      */
  95     public void addAsChild( final PhylogenyNode parent ) {
  96         if ( isEmpty() ) {
  97             throw new IllegalArgumentException( "Attempt to add an empty tree." );
  98         }
  99         if ( !isRooted() ) {
 100             throw new IllegalArgumentException( "Attempt to add an unrooted tree." );
 101         }
 102         parent.addAsChild( getRoot() );
 103         externalNodesHaveChanged();
 104     }
 105
 106     public void addAsSibling( final PhylogenyNode sibling ) {
 107         if ( isEmpty() ) {
 108             throw new IllegalArgumentException( "Attempt to add an empty tree." );
 109         }
 110         if ( !isRooted() ) {
 111             throw new IllegalArgumentException( "Attempt to add an unrooted tree." );
 112         }
 113         final int sibling_index = sibling.getChildNodeIndex();
 114         final PhylogenyNode new_node = new PhylogenyNode();
 115         final PhylogenyNode sibling_parent = sibling.getParent();
 116         new_node.setChild1( sibling );
 117         new_node.setChild2( getRoot() );
 118         new_node.setParent( sibling_parent );
 119         sibling.setParent( new_node );
 120         sibling_parent.setChildNode( sibling_index, new_node );
 121         final double new_dist = sibling.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT
 122                 ? PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT : sibling.getDistanceToParent() / 2;
 123         new_node.setDistanceToParent( new_dist );
 124         sibling.setDistanceToParent( new_dist );
 125         externalNodesHaveChanged();
 126     }
 127
 128     /**
 129      * This calculates the height of the subtree emanating at n for rooted,
 130      * tree-shaped phylogenies
 131      *
 132      * @param n
 133      *            the root-node of a subtree
 134      * @return the height of the subtree emanating at n
 135      */
 136     public double calculateSubtreeHeight( final PhylogenyNode n, final boolean take_collapse_into_account ) {
 137         if ( n.isExternal() || ( take_collapse_into_account && n.isCollapse() ) ) {
 138             return n.getDistanceToParent() > 0 ? n.getDistanceToParent() : 0;
 139         }
 140         else {
 141             double max = -Double.MAX_VALUE;
 142             for( int i = 0; i < n.getNumberOfDescendants(); ++i ) {
 143                 final double l = calculateSubtreeHeight( n.getChildNode( i ), take_collapse_into_account );
 144                 if ( l > max ) {
 145                     max = l;
 146                 }
 147             }
 148             return max + ( n.getDistanceToParent() > 0 ? n.getDistanceToParent() : 0 );
 149         }
 150     }
 151
 152     public void clearHashIdToNodeMap() {
 153         setIdToNodeMap( null );
 154     }
 155
 156     /**
 157      * Returns a deep copy of this Phylogeny.
 158      * <p>
 159      * (The resulting Phylogeny has its references in the external nodes
 160      * corrected, if they are lacking/obsolete in this.)
 161      */
 162     public Phylogeny copy() {
 163         return copy( _root );
 164     }
 165
 166     /**
 167      * Returns a deep copy of this Phylogeny.
 168      * <p>
 169      * (The resulting Phylogeny has its references in the external nodes
 170      * corrected, if they are lacking/obsolete in this.)
 171      */
 172     public Phylogeny copy( final PhylogenyNode source ) {
 173         final Phylogeny tree = new Phylogeny();
 174         if ( isEmpty() ) {
 175             tree.init();
 176             return tree;
 177         }
 178         tree._rooted = _rooted;
 179         tree._name = new String( _name );
 180         tree._description = new String( _description );
 181         tree._type = new String( _type );
 182         tree._rerootable = _rerootable;
 183         tree._distance_unit = new String( _distance_unit );
 184         if ( _confidence != null ) {
 185             tree._confidence = ( Confidence ) _confidence.copy();
 186         }
 187         if ( _identifier != null ) {
 188             tree._identifier = ( Identifier ) _identifier.copy();
 189         }
 190         tree.setAllowMultipleParents( isAllowMultipleParents() );
 191         tree._root = PhylogenyMethods.copySubTree( source );
 192         return tree;
 193     }
 194
 195     /**
 196      * Returns a shallow copy of this Phylogeny.
 197      * <p>
 198      * (The resulting Phylogeny has its references in the external nodes
 199      * corrected, if they are lacking/obsolete in this.)
 200      */
 201     public Phylogeny copyShallow() {
 202         return copyShallow( _root );
 203     }
 204
 205     public Phylogeny copyShallow( final PhylogenyNode source ) {
 206         final Phylogeny tree = new Phylogeny();
 207         if ( isEmpty() ) {
 208             tree.init();
 209             return tree;
 210         }
 211         tree._rooted = _rooted;
 212         tree._name = _name;
 213         tree._description = _description;
 214         tree._type = _type;
 215         tree._rerootable = _rerootable;
 216         tree._distance_unit = _distance_unit;
 217         tree._confidence = _confidence;
 218         tree._identifier = _identifier;
 219         tree.setAllowMultipleParents( isAllowMultipleParents() );
 220         tree._root = PhylogenyMethods.copySubTreeShallow( source );
 221         return tree;
 222     }
 223
 224     /**
 225      * Need to call clearHashIdToNodeMap() afterwards (not done automatically
 226      * to allow client multiple deletions in linear time).
 227      * Need to call 'recalculateNumberOfExternalDescendants(boolean)' after this
 228      * if tree is to be displayed.
 229      *
 230      * @param remove_us the parent node of the subtree to be deleted
 231      */
 232     public void deleteSubtree( final PhylogenyNode remove_us, final boolean collapse_resulting_node_with_one_desc ) {
 233         if ( isEmpty() || ( remove_us.isRoot() && ( getNumberOfExternalNodes() != 1 ) ) ) {
 234             return;
 235         }
 236         if ( remove_us.isRoot() && ( getNumberOfExternalNodes() == 1 ) ) {
 237             init();
 238         }
 239         else if ( !collapse_resulting_node_with_one_desc ) {
 240             remove_us.getParent().removeChildNode( remove_us );
 241         }
 242         else {
 243             final PhylogenyNode removed_node = remove_us;
 244             final PhylogenyNode p = remove_us.getParent();
 245             if ( p.isRoot() ) {
 246                 if ( p.getNumberOfDescendants() == 2 ) {
 247                     if ( removed_node.isFirstChildNode() ) {
 248                         setRoot( getRoot().getChildNode( 1 ) );
 249                         getRoot().setParent( null );
 250                     }
 251                     else {
 252                         setRoot( getRoot().getChildNode( 0 ) );
 253                         getRoot().setParent( null );
 254                     }
 255                 }
 256                 else {
 257                     p.removeChildNode( removed_node.getChildNodeIndex() );
 258                 }
 259             }
 260             else {
 261                 final PhylogenyNode pp = removed_node.getParent().getParent();
 262                 if ( p.getNumberOfDescendants() == 2 ) {
 263                     final int pi = p.getChildNodeIndex();
 264                     if ( removed_node.isFirstChildNode() ) {
 265                         p.getChildNode( 1 )
 266                                 .setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p.getDistanceToParent(),
 267                                                                                               p.getChildNode( 1 )
 268                                                                                                       .getDistanceToParent() ) );
 269                         pp.setChildNode( pi, p.getChildNode( 1 ) );
 270                     }
 271                     else {
 272                         p.getChildNode( 0 )
 273                                 .setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p.getDistanceToParent(),
 274                                                                                               p.getChildNode( 0 )
 275                                                                                                       .getDistanceToParent() ) );
 276                         pp.setChildNode( pi, p.getChildNode( 0 ) );
 277                     }
 278                 }
 279                 else {
 280                     p.removeChildNode( removed_node.getChildNodeIndex() );
 281                 }
 282             }
 283         }
 284         remove_us.removeConnections();
 285         externalNodesHaveChanged();
 286     }
 287
 288     public void externalNodesHaveChanged() {
 289         _external_nodes_set = null;
 290     }
 291
 292     public String[] getAllExternalNodeNames() {
 293         int i = 0;
 294         if ( isEmpty() ) {
 295             return null;
 296         }
 297         final String[] names = new String[ getNumberOfExternalNodes() ];
 298         for( final PhylogenyNodeIterator iter = iteratorExternalForward(); iter.hasNext(); ) {
 299             names[ i++ ] = new String( iter.next().getName() );
 300         }
 301         return names;
 302     }
 303
 304     public Confidence getConfidence() {
 305         return _confidence;
 306     }
 307
 308     public String getDescription() {
 309         return _description;
 310     }
 311
 312     public String getDistanceUnit() {
 313         return _distance_unit;
 314     }
 315
 316     public final static Phylogeny createInstanceFromNhxString( final String nhx ) throws IOException {
 317         final PhylogenyFactory factory = ParserBasedPhylogenyFactory.getInstance();
 318         return factory.create( nhx, new NHXParser() )[ 0 ];
 319     }
 320
 321     /**
 322      *
 323      * Warning. The order of the returned nodes is random
 324      * -- and hence cannot be relied on.
 325      *
 326      * @return Unordered set of PhylogenyNode
 327      */
 328     public List<PhylogenyNode> getExternalNodes() {
 329         if ( _external_nodes_set == null ) {
 330             _external_nodes_set = new ArrayList<>();
 331             for( final PhylogenyNodeIterator it = iteratorPostorder(); it.hasNext(); ) {
 332                 final PhylogenyNode n = it.next();
 333                 if ( n.isExternal() ) {
 334                     _external_nodes_set.add( n );
 335                 }
 336             }
 337         }
 338         return _external_nodes_set;
 339     }
 340
 341     /**
 342      * Returns the first external PhylogenyNode.
 343      */
 344     public PhylogenyNode getFirstExternalNode() {
 345         if ( isEmpty() ) {
 346             throw new FailedConditionCheckException( "attempt to obtain first external node of empty phylogeney" );
 347         }
 348         PhylogenyNode node = getRoot();
 349         while ( node.isInternal() ) {
 350             node = node.getFirstChildNode();
 351         }
 352         return node;
 353     }
 354
 355     /**
 356      * This calculates the height for rooted, tree-shaped phylogenies. The
 357      * height is the longest distance from the root to an external node.
 358      *
 359      * @return the height for rooted, tree-shaped phylogenies
 360      */
 361     public double calculateHeight( final boolean take_collapse_into_account ) {
 362         if ( isEmpty() ) {
 363             return 0.0;
 364         }
 365         return calculateSubtreeHeight( getRoot(), take_collapse_into_account );
 366     }
 367
 368     public Identifier getIdentifier() {
 369         return _identifier;
 370     }
 371
 372     /**
 373      * Returns the name of this Phylogeny.
 374      */
 375     public String getName() {
 376         return _name;
 377     }
 378
 379     /**
 380      * Finds the PhylogenyNode of this Phylogeny which has a matching ID number.
 381      * @return PhylogenyNode with matching ID, null if not found
 382      */
 383     public PhylogenyNode getNode( final long id ) throws NoSuchElementException {
 384         if ( isEmpty() ) {
 385             throw new NoSuchElementException( "attempt to get node in an empty phylogeny" );
 386         }
 387         if ( ( getIdToNodeMap() == null ) || getIdToNodeMap().isEmpty() ) {
 388             reHashIdToNodeMap();
 389         }
 390         return getIdToNodeMap().get( id );
 391     }
 392
 393     /**
 394      * Returns a PhylogenyNode of this Phylogeny which has a matching name.
 395      * Throws an Exception if seqname is not present in this or not unique.
 396      *
 397      * @param name
 398      *            name (String) of PhylogenyNode to find
 399      * @return PhylogenyNode with matchin name
 400      */
 401     public PhylogenyNode getNode( final String name ) {
 402         if ( isEmpty() ) {
 403             return null;
 404         }
 405         final List<PhylogenyNode> nodes = getNodes( name );
 406         if ( ( nodes == null ) || ( nodes.size() < 1 ) ) {
 407             throw new IllegalArgumentException( "node named \"" + name + "\" not found" );
 408         }
 409         if ( nodes.size() > 1 ) {
 410             throw new IllegalArgumentException( "node named \"" + name + "\" not unique" );
 411         }
 412         return nodes.get( 0 );
 413     }
 414
 415     /**
 416      * This is time-inefficient since it runs a iterator each time it is called.
 417      *
 418      */
 419     public int getNodeCount() {
 420         if ( isEmpty() ) {
 421             return 0;
 422         }
 423         int c = 0;
 424         for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); it.next() ) {
 425             ++c;
 426         }
 427         return c;
 428     }
 429
 430     /**
 431      * Returns a List with references to all Nodes of this Phylogeny which have
 432      * a matching name.
 433      *
 434      * @param name
 435      *            name (String) of Nodes to find
 436      * @return Vector of references to Nodes of this Phylogeny with matching
 437      *         names
 438      * @see #getNodesWithMatchingSpecies(String)
 439      */
 440     public List<PhylogenyNode> getNodes( final String name ) {
 441         if ( isEmpty() ) {
 442             return null;
 443         }
 444         final List<PhylogenyNode> nodes = new ArrayList<>();
 445         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 446             final PhylogenyNode n = iter.next();
 447             if ( n.getName().equals( name ) ) {
 448                 nodes.add( n );
 449             }
 450         }
 451         return nodes;
 452     }
 453
 454     public List<PhylogenyNode> getNodes( final Pattern p ) {
 455         if ( isEmpty() ) {
 456             return null;
 457         }
 458         final List<PhylogenyNode> nodes = new ArrayList<>();
 459         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 460             final PhylogenyNode n = iter.next();
 461             if ( n.getName() != null ) {
 462                 final Matcher m = p.matcher( n.getName() );
 463                 if ( m.find() ) {
 464                     nodes.add( n );
 465                 }
 466             }
 467         }
 468         return nodes;
 469     }
 470
 471     public List<PhylogenyNode> getNodesViaSequenceName( final String seq_name ) {
 472         if ( isEmpty() ) {
 473             return null;
 474         }
 475         final List<PhylogenyNode> nodes = new ArrayList<>();
 476         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 477             final PhylogenyNode n = iter.next();
 478             if ( n.getNodeData().isHasSequence() && n.getNodeData().getSequence().getName().equals( seq_name ) ) {
 479                 nodes.add( n );
 480             }
 481         }
 482         return nodes;
 483     }
 484
 485     public List<PhylogenyNode> getNodesViaSequenceSymbol( final String seq_name ) {
 486         if ( isEmpty() ) {
 487             return null;
 488         }
 489         final List<PhylogenyNode> nodes = new ArrayList<>();
 490         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 491             final PhylogenyNode n = iter.next();
 492             if ( n.getNodeData().isHasSequence() && n.getNodeData().getSequence().getSymbol().equals( seq_name ) ) {
 493                 nodes.add( n );
 494             }
 495         }
 496         return nodes;
 497     }
 498
 499     public List<PhylogenyNode> getNodesViaGeneName( final String seq_name ) {
 500         if ( isEmpty() ) {
 501             return null;
 502         }
 503         final List<PhylogenyNode> nodes = new ArrayList<>();
 504         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 505             final PhylogenyNode n = iter.next();
 506             if ( n.getNodeData().isHasSequence() && n.getNodeData().getSequence().getGeneName().equals( seq_name ) ) {
 507                 nodes.add( n );
 508             }
 509         }
 510         return nodes;
 511     }
 512
 513     public List<PhylogenyNode> getNodesViaTaxonomyCode( final String taxonomy_code ) {
 514         if ( isEmpty() ) {
 515             return null;
 516         }
 517         final List<PhylogenyNode> nodes = new ArrayList<>();
 518         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 519             final PhylogenyNode n = iter.next();
 520             if ( n.getNodeData().isHasTaxonomy()
 521                     && n.getNodeData().getTaxonomy().getTaxonomyCode().equals( taxonomy_code ) ) {
 522                 nodes.add( n );
 523             }
 524         }
 525         return nodes;
 526     }
 527
 528     /**
 529      * Returns a Vector with references to all Nodes of this Phylogeny which
 530      * have a matching species name.
 531      *
 532      * @param specname
 533      *            species name (String) of Nodes to find
 534      * @return Vector of references to Nodes of this Phylogeny with matching
 535      *         species names.
 536      * @see #getNodes(String)
 537      */
 538     public List<PhylogenyNode> getNodesWithMatchingSpecies( final String specname ) {
 539         if ( isEmpty() ) {
 540             return null;
 541         }
 542         final List<PhylogenyNode> nodes = new ArrayList<>();
 543         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 544             final PhylogenyNode n = iter.next();
 545             if ( PhylogenyMethods.getSpecies( n ).equals( specname ) ) {
 546                 nodes.add( n );
 547             }
 548         }
 549         return nodes;
 550     }
 551
 552     public PhylogenyNode getNodeViaSequenceName( final String seq_name ) {
 553         if ( isEmpty() ) {
 554             return null;
 555         }
 556         final List<PhylogenyNode> nodes = getNodesViaSequenceName( seq_name );
 557         if ( ( nodes == null ) || ( nodes.size() < 1 ) ) {
 558             throw new IllegalArgumentException( "node with sequence named [" + seq_name + "] not found" );
 559         }
 560         if ( nodes.size() > 1 ) {
 561             throw new IllegalArgumentException( "node with sequence named [" + seq_name + "] not unique" );
 562         }
 563         return nodes.get( 0 );
 564     }
 565
 566     public PhylogenyNode getNodeViaTaxonomyCode( final String taxonomy_code ) {
 567         if ( isEmpty() ) {
 568             return null;
 569         }
 570         final List<PhylogenyNode> nodes = getNodesViaTaxonomyCode( taxonomy_code );
 571         if ( ( nodes == null ) || ( nodes.size() < 1 ) ) {
 572             throw new IllegalArgumentException( "node with taxonomy code \"" + taxonomy_code + "\" not found" );
 573         }
 574         if ( nodes.size() > 1 ) {
 575             throw new IllegalArgumentException( "node with taxonomy code \"" + taxonomy_code + "\" not unique" );
 576         }
 577         return nodes.get( 0 );
 578     }
 579
 580     public int getNumberOfBranches() {
 581         if ( isEmpty() ) {
 582             return 0;
 583         }
 584         int c = 0;
 585         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); iter.next() ) {
 586             ++c;
 587         }
 588         if ( !isRooted() ) {
 589             --c;
 590         }
 591         return c;
 592     }
 593
 594     public int getNumberOfInternalNodes() {
 595         if ( isEmpty() ) {
 596             return 0;
 597         }
 598         int c = 0;
 599         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 600             if ( iter.next().isInternal() ) {
 601                 ++c;
 602             }
 603         }
 604         if ( !isRooted() ) {
 605             --c;
 606         }
 607         return c;
 608     }
 609
 610     /**
 611      * Returns the sum of external Nodes of this Phylogeny (int).
 612      */
 613     public int getNumberOfExternalNodes() {
 614         if ( isEmpty() ) {
 615             return 0;
 616         }
 617         return getExternalNodes().size();
 618     }
 619
 620     /**
 621      * Returns all paralogs of the external PhylogenyNode n of this Phylogeny.
 622      * paralog are returned as List of node references.
 623      * <p>
 624      * PRECONDITION: This tree must be binary and rooted, and speciation -
 625      * duplication need to be assigned for each of its internal Nodes.
 626      * <p>
 627      * Returns null if this Phylogeny is empty or if n is internal.
 628      * <p>
 629      * (Last modified: 11/22/00) Olivier CHABROL :
 630      * olivier.chabrol@univ-provence.fr
 631      *
 632      * @param n
 633      *            external PhylogenyNode whose orthologs are to be returned
 634      * @return Vector of references to all orthologous Nodes of PhylogenyNode n
 635      *         of this Phylogeny, null if this Phylogeny is empty or if n is
 636      *         internal
 637      */
 638     public List<PhylogenyNode> getParalogousNodes( final PhylogenyNode n, final String[] taxonomyCodeRange ) {
 639         PhylogenyNode node = n;
 640         PhylogenyNode prev = null;
 641         final List<PhylogenyNode> v = new ArrayList<>();
 642         final Map<PhylogenyNode, List<String>> map = new HashMap<>();
 643         getTaxonomyMap( getRoot(), map );
 644         if ( !node.isExternal() || isEmpty() ) {
 645             return null;
 646         }
 647         final String searchNodeSpeciesId = PhylogenyMethods.getTaxonomyIdentifier( n );
 648         if ( !node.isExternal() || isEmpty() ) {
 649             return null;
 650         }
 651         List<String> taxIdList = null;
 652         final List<String> taxonomyCodeRangeList = Arrays.asList( taxonomyCodeRange );
 653         while ( !node.isRoot() ) {
 654             prev = node;
 655             node = node.getParent();
 656             taxIdList = map.get( node );
 657             if ( node.isDuplication() && isContains( taxIdList, taxonomyCodeRangeList ) ) {
 658                 if ( node.getChildNode1() == prev ) {
 659                     v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId,
 660                                                    node.getChildNode2().getAllExternalDescendants() ) );
 661                 }
 662                 else {
 663                     v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId,
 664                                                    node.getChildNode1().getAllExternalDescendants() ) );
 665                 }
 666             }
 667         }
 668         return v;
 669     }
 670
 671     public Collection<SequenceRelation.SEQUENCE_RELATION_TYPE> getRelevantSequenceRelationTypes() {
 672         if ( _relevant_sequence_relation_types == null ) {
 673             _relevant_sequence_relation_types = new Vector<>();
 674         }
 675         return _relevant_sequence_relation_types;
 676     }
 677
 678     /**
 679      * Returns the root PhylogenyNode of this Phylogeny.
 680      */
 681     public PhylogenyNode getRoot() {
 682         return _root;
 683     }
 684
 685     public Collection<Sequence> getSequenceRelationQueries() {
 686         return _sequenceRelationQueries;
 687     }
 688
 689     public String getType() {
 690         return _type;
 691     }
 692
 693     /**
 694      * Deletes this Phylogeny.
 695      */
 696     public void init() {
 697         _root = null;
 698         _rooted = false;
 699         _name = "";
 700         _description = "";
 701         _type = "";
 702         _distance_unit = "";
 703         _id_to_node_map = null;
 704         _confidence = null;
 705         _identifier = null;
 706         _rerootable = true;
 707         setAllowMultipleParents( Phylogeny.ALLOW_MULTIPLE_PARENTS_DEFAULT );
 708     }
 709
 710     /**
 711      * Returns whether this is a completely binary tree (i.e. all internal nodes
 712      * are bifurcations).
 713      *
 714      */
 715     public boolean isCompletelyBinary() {
 716         if ( isEmpty() ) {
 717             return false;
 718         }
 719         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 720             final PhylogenyNode node = iter.next();
 721             if ( node.isInternal() && ( node.getNumberOfDescendants() != 2 ) ) {
 722                 return false;
 723             }
 724         }
 725         return true;
 726     }
 727
 728     public boolean isCompletelyBinaryAllow3ChildrenAtRoot() {
 729         if ( isEmpty() ) {
 730             return false;
 731         }
 732         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 733             final PhylogenyNode node = iter.next();
 734             if ( node.isRoot() ) {
 735                 if ( node.isInternal()
 736                         && ( ( node.getNumberOfDescendants() != 2 ) && ( node.getNumberOfDescendants() != 3 ) ) ) {
 737                     return false;
 738                 }
 739             }
 740             else {
 741                 if ( node.isInternal() && ( node.getNumberOfDescendants() != 2 ) ) {
 742                     return false;
 743                 }
 744             }
 745         }
 746         return true;
 747     }
 748
 749     /**
 750      * Checks whether a Phylogeny object is deleted (or empty).
 751      *
 752      * @return true if the tree is deleted (or empty), false otherwise
 753      */
 754     public boolean isEmpty() {
 755         return ( getRoot() == null );
 756     }
 757
 758     public boolean isRerootable() {
 759         return _rerootable;
 760     }
 761
 762     /**
 763      * Returns true is this Phylogeny is rooted.
 764      */
 765     public boolean isRooted() {
 766         return _rooted;
 767     } // isRooted()
 768
 769     public boolean isTree() {
 770         return true;
 771     }
 772
 773     public PhylogenyNodeIterator iteratorExternalForward() {
 774         return new ExternalForwardIterator( this );
 775     }
 776
 777     public PhylogenyNodeIterator iteratorLevelOrder() {
 778         return new LevelOrderTreeIterator( this );
 779     }
 780
 781     public PhylogenyNodeIterator iteratorPostorder() {
 782         return new PostorderTreeIterator( this );
 783     }
 784
 785     public PhylogenyNodeIterator iteratorPreorder() {
 786         return new PreorderTreeIterator( this );
 787     }
 788
 789     /**
 790      * Resets the ID numbers of the nodes of this Phylogeny in level order,
 791      * starting with start_label (for the root). <br>
 792      * WARNING. After this method has been called, node IDs are no longer
 793      * unique.
 794      */
 795     public void levelOrderReID() {
 796         if ( isEmpty() ) {
 797             return;
 798         }
 799         _id_to_node_map = null;
 800         long max = 0;
 801         for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); ) {
 802             final PhylogenyNode node = it.next();
 803             if ( node.isRoot() ) {
 804                 node.setId( PhylogenyNode.getNodeCount() );
 805             }
 806             else {
 807                 node.setId( node.getParent().getId() + 1 );
 808                 if ( node.getId() > max ) {
 809                     max = node.getId();
 810                 }
 811             }
 812         }
 813         PhylogenyNode.setNodeCount( max + 1 );
 814     }
 815
 816     /**
 817      * Prints descriptions of all external Nodes of this Phylogeny to
 818      * System.out.
 819      */
 820     public void printExtNodes() {
 821         if ( isEmpty() ) {
 822             return;
 823         }
 824         for( final PhylogenyNodeIterator iter = iteratorExternalForward(); iter.hasNext(); ) {
 825             System.out.println( iter.next() + "\n" );
 826         }
 827     }
 828
 829     /**
 830      * (Re)counts the number of children for each PhylogenyNode of this
 831      * Phylogeny. As an example, this method needs to be called after a
 832      * Phylogeny has been reRooted and it is to be displayed.
 833      *
 834      * @param consider_collapsed_nodes
 835      *            set to true to take into account collapsed nodes (collapsed
 836      *            nodes have 1 child).
 837      */
 838     public void recalculateNumberOfExternalDescendants( final boolean consider_collapsed_nodes ) {
 839         if ( isEmpty() ) {
 840             return;
 841         }
 842         for( final PhylogenyNodeIterator iter = iteratorPostorder(); iter.hasNext(); ) {
 843             final PhylogenyNode node = iter.next();
 844             if ( node.isExternal() || ( consider_collapsed_nodes && node.isCollapse() ) ) {
 845                 node.setSumExtNodes( 1 );
 846             }
 847             else {
 848                 int sum = 0;
 849                 for( int i = 0; i < node.getNumberOfDescendants(); ++i ) {
 850                     sum += node.getChildNode( i ).getNumberOfExternalNodes();
 851                 }
 852                 node.setSumExtNodes( sum );
 853             }
 854         }
 855     }
 856
 857     /**
 858      * Places the root of this Phylogeny on the parent branch of the
 859      * PhylogenyNode with a corresponding ID. The new root is always placed on
 860      * the middle of the branch. If the resulting reRooted Phylogeny is to be
 861      * used any further, in most cases the following methods have to be called
 862      * on the resulting Phylogeny:
 863      * <p>
 864      * <li>recalculateNumberOfExternalDescendants(boolean)
 865      * <li>recalculateAndReset()
 866      *
 867      * @param id
 868      *            ID (int) of PhylogenyNode of this Phylogeny
 869      */
 870     public void reRoot( final long id ) {
 871         reRoot( getNode( id ) );
 872     }
 873
 874     /**
 875      * Places the root of this Phylogeny on the parent branch PhylogenyNode n.
 876      * The new root is always placed on the middle of the branch.
 877      * <p>
 878      * If the resulting reRooted Phylogeny is to be used any further, in most
 879      * cases the following three methods have to be called on the resulting
 880      * Phylogeny:
 881      * <ul>
 882      * <li>recalculateNumberOfExternalDescendants(boolean) <li>recalculateAndReset()
 883      * </ul>
 884      * <p>
 885      * (Last modified: 10/01/01)
 886      *
 887      * @param n
 888      *            PhylogenyNode of this Phylogeny\
 889      */
 890     public void reRoot( final PhylogenyNode n ) {
 891         reRoot( n, -1 );
 892     }
 893
 894     public void reRoot( final PhylogenyNode n, final double distance_n_to_parent ) {
 895         if ( isEmpty() || ( getNumberOfExternalNodes() < 2 ) ) {
 896             return;
 897         }
 898         setRooted( true );
 899         if ( n.isRoot() ) {
 900             return;
 901         }
 902         else if ( n.getParent().isRoot() ) {
 903             if ( ( n.getParent().getNumberOfDescendants() == 2 ) && ( distance_n_to_parent >= 0 ) ) {
 904                 final double d = n.getParent().getChildNode1().getDistanceToParent()
 905                         + n.getParent().getChildNode2().getDistanceToParent();
 906                 PhylogenyNode other;
 907                 if ( n.getChildNodeIndex() == 0 ) {
 908                     other = n.getParent().getChildNode2();
 909                 }
 910                 else {
 911                     other = n.getParent().getChildNode1();
 912                 }
 913                 n.setDistanceToParent( distance_n_to_parent );
 914                 final double dm = d - distance_n_to_parent;
 915                 if ( dm >= 0 ) {
 916                     other.setDistanceToParent( dm );
 917                 }
 918                 else {
 919                     other.setDistanceToParent( 0 );
 920                 }
 921             }
 922             if ( n.getParent().getNumberOfDescendants() > 2 ) {
 923                 final int index = n.getChildNodeIndex();
 924                 final double dn = n.getDistanceToParent();
 925                 final PhylogenyNode prev_root = getRoot();
 926                 prev_root.getDescendants().remove( index );
 927                 final PhylogenyNode new_root = new PhylogenyNode();
 928                 new_root.setChildNode( 0, n );
 929                 new_root.setChildNode( 1, prev_root );
 930                 if ( n.getBranchDataDirectly() != null ) {
 931                     prev_root.setBranchData( ( BranchData ) n.getBranchDataDirectly().copy() );
 932                 }
 933                 setRoot( new_root );
 934                 if ( distance_n_to_parent >= 0 ) {
 935                     n.setDistanceToParent( distance_n_to_parent );
 936                     final double d = dn - distance_n_to_parent;
 937                     if ( d >= 0 ) {
 938                         prev_root.setDistanceToParent( d );
 939                     }
 940                     else {
 941                         prev_root.setDistanceToParent( 0 );
 942                     }
 943                 }
 944                 else {
 945                     if ( dn >= 0 ) {
 946                         final double d = dn / 2.0;
 947                         n.setDistanceToParent( d );
 948                         prev_root.setDistanceToParent( d );
 949                     }
 950                 }
 951             }
 952         }
 953         else {
 954             PhylogenyNode a = n;
 955             PhylogenyNode b = null;
 956             PhylogenyNode c = null;
 957             final PhylogenyNode new_root = new PhylogenyNode();
 958             double distance1 = 0.0;
 959             double distance2 = 0.0;
 960             BranchData branch_data_1 = null;
 961             BranchData branch_data_2 = null;
 962             b = a.getParent();
 963             c = b.getParent();
 964             new_root.setChildNode( 0, a );
 965             new_root.setChildNode( 1, b );
 966             distance1 = c.getDistanceToParent();
 967             if ( c.getBranchDataDirectly() != null ) {
 968                 branch_data_1 = ( BranchData ) c.getBranchDataDirectly().copy();
 969             }
 970             c.setDistanceToParent( b.getDistanceToParent() );
 971             if ( b.getBranchDataDirectly() != null ) {
 972                 c.setBranchData( ( BranchData ) b.getBranchDataDirectly().copy() );
 973             }
 974             if ( a.getBranchDataDirectly() != null ) {
 975                 b.setBranchData( ( BranchData ) a.getBranchDataDirectly().copy() );
 976             }
 977             // New root is always placed in the middle of the branch:
 978             if ( a.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ) {
 979                 b.setDistanceToParent( PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT );
 980             }
 981             else {
 982                 if ( distance_n_to_parent >= 0.0 ) {
 983                     final double diff = a.getDistanceToParent() - distance_n_to_parent;
 984                     a.setDistanceToParent( distance_n_to_parent );
 985                     b.setDistanceToParent( diff >= 0.0 ? diff : 0.0 );
 986                 }
 987                 else {
 988                     final double d = a.getDistanceToParent() / 2.0;
 989                     a.setDistanceToParent( d );
 990                     b.setDistanceToParent( d );
 991                 }
 992             }
 993             b.setChildNodeOnly( a.getChildNodeIndex( b ), c );
 994             // moving to the old root, swapping references:
 995             while ( !c.isRoot() ) {
 996                 a = b;
 997                 b = c;
 998                 c = c.getParent();
 999                 b.setChildNodeOnly( a.getChildNodeIndex( b ), c );
1000                 b.setParent( a );
1001                 distance2 = c.getDistanceToParent();
1002                 branch_data_2 = c.getBranchDataDirectly();
1003                 c.setDistanceToParent( distance1 );
1004                 c.setBranchData( branch_data_1 );
1005                 distance1 = distance2;
1006                 branch_data_1 = branch_data_2;
1007             }
1008             // removing the old root:
1009             if ( c.getNumberOfDescendants() == 2 ) {
1010                 final PhylogenyNode node = c.getChildNode( 1 - b.getChildNodeIndex( c ) );
1011                 node.setParent( b );
1012                 if ( ( c.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT )
1013                         && ( node.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ) ) {
1014                     node.setDistanceToParent( PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT );
1015                 }
1016                 else {
1017                     node.setDistanceToParent( ( c.getDistanceToParent() >= 0.0 ? c.getDistanceToParent() : 0.0 )
1018                             + ( node.getDistanceToParent() >= 0.0 ? node.getDistanceToParent() : 0.0 ) );
1019                 }
1020                 if ( c.getBranchDataDirectly() != null ) {
1021                     node.setBranchData( ( BranchData ) c.getBranchDataDirectly().copy() );
1022                 }
1023                 for( int i = 0; i < b.getNumberOfDescendants(); ++i ) {
1024                     if ( b.getChildNode( i ) == c ) {
1025                         b.setChildNodeOnly( i, node );
1026                         break;
1027                     }
1028                 }
1029             }
1030             else {
1031                 c.setParent( b );
1032                 c.removeChildNode( b.getChildNodeIndex( c ) );
1033             }
1034             setRoot( new_root );
1035         }
1036     }
1037
1038     /**
1039      * Sets all Nodes of this Phylogeny to not-collapsed.
1040      * <p>
1041      * In most cases methods adjustNodeCount(false) and recalculateAndReset()
1042      * need to be called after this method has been called.
1043      */
1044     public void setAllNodesToNotCollapse() {
1045         if ( isEmpty() ) {
1046             return;
1047         }
1048         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
1049             final PhylogenyNode node = iter.next();
1050             node.setCollapse( false );
1051         }
1052     }
1053
1054     public void setConfidence( final Confidence confidence ) {
1055         _confidence = confidence;
1056     }
1057
1058     public void setDescription( final String description ) {
1059         _description = description;
1060     }
1061
1062     public void setDistanceUnit( final String _distance_unit ) {
1063         this._distance_unit = _distance_unit;
1064     }
1065
1066     public void setIdentifier( final Identifier identifier ) {
1067         _identifier = identifier;
1068     }
1069
1070     public void setIdToNodeMap( final HashMap<Long, PhylogenyNode> idhash ) {
1071         _id_to_node_map = idhash;
1072     }
1073
1074     /**
1075      * Sets the indicators of all Nodes of this Phylogeny to 0.
1076      */
1077     public void setIndicatorsToZero() {
1078         if ( isEmpty() ) {
1079             return;
1080         }
1081         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
1082             iter.next().setIndicator( ( byte ) 0 );
1083         }
1084     } // setIndicatorsToZero()
1085
1086     /**
1087      * Sets the name of this Phylogeny to s.
1088      */
1089     public void setName( final String s ) {
1090         _name = s;
1091     }
1092
1093     public void setRelevantSequenceRelationTypes( final Collection<SequenceRelation.SEQUENCE_RELATION_TYPE> types ) {
1094         _relevant_sequence_relation_types = types;
1095     }
1096
1097     public void setRerootable( final boolean rerootable ) {
1098         _rerootable = rerootable;
1099     }
1100
1101     public void setRoot( final PhylogenyNode n ) {
1102         _root = n;
1103     }
1104
1105     /**
1106      * Sets whether this Phylogeny is rooted or not.
1107      */
1108     public void setRooted( final boolean b ) {
1109         _rooted = b;
1110     }
1111
1112     public void setSequenceRelationQueries( final Collection<Sequence> sequencesByName ) {
1113         _sequenceRelationQueries = sequencesByName;
1114     }
1115
1116     public void setType( final String type ) {
1117         _type = type;
1118     }
1119
1120     public String toNewHampshire() {
1121         return toNewHampshire( NH_CONVERSION_SUPPORT_VALUE_STYLE.NONE );
1122     }
1123
1124     public String toNewHampshire( final NH_CONVERSION_SUPPORT_VALUE_STYLE nh_conversion_support_style ) {
1125         try {
1126             return new PhylogenyWriter().toNewHampshire( this, true, nh_conversion_support_style ).toString();
1127         }
1128         catch ( final IOException e ) {
1129             throw new Error( "this should not have happend: " + e.getMessage() );
1130         }
1131     }
1132
1133     public String toNewHampshireX() {
1134         try {
1135             return new PhylogenyWriter().toNewHampshireX( this ).toString();
1136         }
1137         catch ( final IOException e ) {
1138             throw new Error( "this should not have happend: " + e.getMessage() );
1139         }
1140     }
1141
1142     public String toNexus() {
1143         return toNexus( NH_CONVERSION_SUPPORT_VALUE_STYLE.NONE );
1144     }
1145
1146     public String toNexus( final NH_CONVERSION_SUPPORT_VALUE_STYLE svs ) {
1147         try {
1148             return new PhylogenyWriter().toNexus( this, svs ).toString();
1149         }
1150         catch ( final IOException e ) {
1151             throw new Error( "this should not have happend: " + e.getMessage() );
1152         }
1153     }
1154
1155     public String toPhyloXML( final int phyloxml_level ) {
1156         try {
1157             return new PhylogenyWriter().toPhyloXML( this, phyloxml_level ).toString();
1158         }
1159         catch ( final IOException e ) {
1160             throw new Error( "this should not have happend: " + e.getMessage() );
1161         }
1162     }
1163
1164     // ---------------------------------------------------------
1165     // Writing of Phylogeny to Strings
1166     // ---------------------------------------------------------
1167     /**
1168      * Converts this Phylogeny to a New Hampshire X (String) representation.
1169      *
1170      * @return New Hampshire X (String) representation of this
1171      * @see #toNewHampshireX()
1172      */
1173     @Override
1174     public String toString() {
1175         return toNewHampshireX();
1176     }
1177
1178     /**
1179      * Removes the root PhylogenyNode this Phylogeny.
1180      */
1181     public void unRoot() throws RuntimeException {
1182         if ( !isTree() ) {
1183             throw new FailedConditionCheckException( "Attempt to unroot a phylogeny which is not tree-like." );
1184         }
1185         if ( isEmpty() ) {
1186             return;
1187         }
1188         setIndicatorsToZero();
1189         if ( !isRooted() || ( getNumberOfExternalNodes() <= 1 ) ) {
1190             return;
1191         }
1192         setRooted( false );
1193         return;
1194     } // unRoot()
1195
1196     private HashMap<Long, PhylogenyNode> getIdToNodeMap() {
1197         return _id_to_node_map;
1198     }
1199
1200     /**
1201      * Return Node by TaxonomyId Olivier CHABROL :
1202      * olivier.chabrol@univ-provence.fr
1203      *
1204      * @param taxonomyID
1205      *            search taxonomy identifier
1206      * @param nodes
1207      *            sublist node to search
1208      * @return List node with the same taxonomy identifier
1209      */
1210     private List<PhylogenyNode> getNodeByTaxonomyID( final String taxonomyID, final List<PhylogenyNode> nodes ) {
1211         final List<PhylogenyNode> retour = new ArrayList<>();
1212         for( final PhylogenyNode node : nodes ) {
1213             if ( taxonomyID.equals( PhylogenyMethods.getTaxonomyIdentifier( node ) ) ) {
1214                 retour.add( node );
1215             }
1216         }
1217         return retour;
1218     }
1219
1220     /**
1221      * List all species contains in all leaf under a node Olivier CHABROL :
1222      * olivier.chabrol@univ-provence.fr
1223      *
1224      * @param node
1225      *            PhylogenyNode whose sub node species are returned
1226      * @return species contains in all leaf under the param node
1227      */
1228     private List<String> getSubNodeTaxonomy( final PhylogenyNode node ) {
1229         final List<String> taxonomyList = new ArrayList<>();
1230         final List<PhylogenyNode> childs = node.getAllExternalDescendants();
1231         String speciesId = null;
1232         for( final PhylogenyNode phylogenyNode : childs ) {
1233             // taxId = new Long(phylogenyNode.getTaxonomyID());
1234             speciesId = PhylogenyMethods.getTaxonomyIdentifier( phylogenyNode );
1235             if ( !taxonomyList.contains( speciesId ) ) {
1236                 taxonomyList.add( speciesId );
1237             }
1238         }
1239         return taxonomyList;
1240     }
1241
1242     /**
1243      * Create a map [<PhylogenyNode, List<String>], the list contains the
1244      * species contains in all leaf under phylogeny node Olivier CHABROL :
1245      * olivier.chabrol@univ-provence.fr
1246      *
1247      * @param node
1248      *            the tree root node
1249      * @param map
1250      *            map to fill
1251      */
1252     private void getTaxonomyMap( final PhylogenyNode node, final Map<PhylogenyNode, List<String>> map ) {
1253         // node is leaf
1254         if ( node.isExternal() ) {
1255             return;
1256         }
1257         map.put( node, getSubNodeTaxonomy( node ) );
1258         getTaxonomyMap( node.getChildNode1(), map );
1259         getTaxonomyMap( node.getChildNode2(), map );
1260     }
1261
1262     private boolean isAllowMultipleParents() {
1263         return _allow_multiple_parents;
1264     }
1265
1266     /**
1267      * Util method to check if all element of a list is contains in the
1268      * rangeList. Olivier CHABROL : olivier.chabrol@univ-provence.fr
1269      *
1270      * @param list
1271      *            list to be check
1272      * @param rangeList
1273      *            the range list to compare
1274      * @return <code>true</code> if all param list element are contains in param
1275      *         rangeList, <code>false</code> otherwise.
1276      */
1277     private boolean isContains( final List<String> list, final List<String> rangeList ) {
1278         if ( list.size() > rangeList.size() ) {
1279             return false;
1280         }
1281         String l = null;
1282         for( final Iterator<String> iterator = list.iterator(); iterator.hasNext(); ) {
1283             l = iterator.next();
1284             if ( !rangeList.contains( l ) ) {
1285                 return false;
1286             }
1287         }
1288         return true;
1289     }
1290
1291     /**
1292      * Hashes the ID number of each PhylogenyNode of this Phylogeny to its
1293      * corresponding PhylogenyNode, in order to make method getNode( id ) run in
1294      * constant time. Important: The user is responsible for calling this method
1295      * (again) after this Phylogeny has been changed/created/renumbered.
1296      */
1297     private void reHashIdToNodeMap() {
1298         if ( isEmpty() ) {
1299             return;
1300         }
1301         setIdToNodeMap( new HashMap<Long, PhylogenyNode>() );
1302         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
1303             final PhylogenyNode node = iter.next();
1304             getIdToNodeMap().put( node.getId(), node );
1305         }
1306     }
1307
1308     private void setAllowMultipleParents( final boolean allow_multiple_parents ) {
1309         _allow_multiple_parents = allow_multiple_parents;
1310     }
1311 }