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