forester/java/src/org/forester/io/parsers/nhx/NHXParser.java

   1 // $Id:
   2 // FORESTER -- software libraries and applications
   3 // for evolutionary biology research and applications.
   4 //
   5 // Copyright (C) 2013 Christian M. Zmasek
   6 //
   7 // This library is free software; you can redistribute it and/or
   8 // modify it under the terms of the GNU Lesser General Public
   9 // License as published by the Free Software Foundation; either
  10 // version 2.1 of the License, or (at your option) any later version.
  11 //
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  15 // Lesser General Public License for more details.
  16 //
  17 // You should have received a copy of the GNU Lesser General Public
  18 // License along with this library; if not, write to the Free Software
  19 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
  20 //
  21 // Contact: phylosoft @ gmail . com
  22 // WWW: https://sites.google.com/site/cmzmasek/home/software/forester
  23
  24 package org.forester.io.parsers.nhx;
  25
  26 import java.awt.Color;
  27 import java.io.BufferedReader;
  28 import java.io.ByteArrayInputStream;
  29 import java.io.File;
  30 import java.io.FileInputStream;
  31 import java.io.IOException;
  32 import java.io.InputStream;
  33 import java.io.InputStreamReader;
  34 import java.net.URL;
  35 import java.util.ArrayList;
  36 import java.util.List;
  37 import java.util.StringTokenizer;
  38 import java.util.regex.Matcher;
  39 import java.util.regex.Pattern;
  40
  41 import org.forester.io.parsers.IteratingPhylogenyParser;
  42 import org.forester.io.parsers.PhylogenyParser;
  43 import org.forester.io.parsers.phyloxml.PhyloXmlDataFormatException;
  44 import org.forester.io.parsers.util.ParserUtils;
  45 import org.forester.io.parsers.util.PhylogenyParserException;
  46 import org.forester.phylogeny.Phylogeny;
  47 import org.forester.phylogeny.PhylogenyMethods;
  48 import org.forester.phylogeny.PhylogenyNode;
  49 import org.forester.phylogeny.data.Accession;
  50 import org.forester.phylogeny.data.BranchColor;
  51 import org.forester.phylogeny.data.Confidence;
  52 import org.forester.phylogeny.data.Event;
  53 import org.forester.phylogeny.data.Identifier;
  54 import org.forester.phylogeny.data.PhylogenyDataUtil;
  55 import org.forester.phylogeny.data.Sequence;
  56 import org.forester.phylogeny.data.Taxonomy;
  57 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
  58 import org.forester.util.ForesterConstants;
  59 import org.forester.util.ForesterUtil;
  60
  61 public final class NHXParser implements PhylogenyParser, IteratingPhylogenyParser {
  62
  63     private final static Pattern  MB_BL_PATTERN                              = Pattern.compile( "length.median=([-+eE0-9\\.]+)" );
  64     private final static Pattern  MB_PROB_PATTERN                            = Pattern.compile( "prob=([-+eE0-9\\.]+)" );
  65     private final static Pattern  MB_PROB_SD_PATTERN                         = Pattern.compile( "prob.stddev=([-+eE0-9\\.]+)" );
  66     private final static Pattern  NUMBERS_ONLY_PATTERN                       = Pattern.compile( "^[0-9\\.]+$" );
  67
  68     private final static Pattern  BEAST_STYLE_EXTENDED_BOOTSTRAP_PATTERN              = Pattern.compile( "boot?strap=([\\d\\.]+)" );
  69     private final static Pattern  BEAST_STYLE_EXTENDED_COLOR_PATTERN                  = Pattern.compile( "colou?r=(#[\\da-fA-F]{6})" );
  70     private final static Pattern  ENDS_WITH_NUMBER_PATTERN                   = Pattern.compile( "(:[-+eE0-9\\.]+$)" );
  71
  72
  73     public final static boolean  REPLACE_UNDERSCORES_DEFAULT                = false;
  74     private final static boolean ALLOW_ERRORS_IN_DISTANCE_TO_PARENT_DEFAULT = false;
  75     private final static byte    BUFFERED_READER                            = 3;
  76     private final static byte    CHAR_ARRAY                                 = 2;
  77     private final static boolean GUESS_IF_SUPPORT_VALUES                    = true;
  78     private final static boolean GUESS_ROOTEDNESS_DEFAULT                   = true;
  79     private final static boolean IGNORE_QUOTES_DEFAULT                      = false;
  80
  81     private final static char    BELL                                       = 7;
  82     private final static String  ENCODING_DEFAULT = ForesterConstants.UTF_8;
  83     private boolean              _allow_errors_in_distance_to_parent;
  84     private int                  _clade_level;
  85     private StringBuilder        _current_anotation;
  86     private PhylogenyNode        _current_node;
  87     private Phylogeny            _current_phylogeny;
  88     private boolean              _guess_rootedness;
  89     private int                  _i;
  90     private boolean              _ignore_quotes;
  91     private boolean              _in_comment                                = false;
  92     private boolean              _in_double_quote                           = false;
  93     private boolean              _in_open_bracket                           = false;
  94     private boolean              _in_single_quote                           = false;
  95     private byte                 _input_type;
  96     private BufferedReader       _my_source_br                              = null;
  97     private char[]               _my_source_charary                         = null;
  98     private Phylogeny            _next;
  99     private Object               _nhx_source;
 100     private boolean              _replace_underscores;
 101     private boolean              _saw_closing_paren;
 102     private boolean              _saw_colon                                 = false;
 103     private boolean              _saw_open_bracket                          = false;
 104     private Object               _source;
 105     private int                  _source_length;
 106     private TAXONOMY_EXTRACTION  _taxonomy_extraction;
 107     private boolean              _parse_beast_style_extended_tags           = false;
 108     private final String         _encoding;
 109
 110     public NHXParser() {
 111         _encoding = ENCODING_DEFAULT;
 112         init();
 113     }
 114
 115     public NHXParser( final String encoding ) {
 116         _encoding = encoding;
 117         init();
 118     }
 119
 120     @Override
 121     public String getName() {
 122         return "NH/NHX Parser";
 123     }
 124
 125     public final TAXONOMY_EXTRACTION getTaxonomyExtraction() {
 126         return _taxonomy_extraction;
 127     }
 128
 129     @Override
 130     public final boolean hasNext() {
 131         return _next != null;
 132     }
 133
 134     @Override
 135     public final Phylogeny next() throws NHXFormatException, IOException {
 136         final Phylogeny phy = _next;
 137         parseNext();
 138         return phy;
 139     }
 140
 141     @Override
 142     public final Phylogeny[] parse() throws IOException {
 143         final List<Phylogeny> l = new ArrayList<Phylogeny>();
 144         while ( hasNext() ) {
 145             l.add( next() );
 146         }
 147         final Phylogeny[] p = new Phylogeny[ l.size() ];
 148         for( int i = 0; i < l.size(); ++i ) {
 149             p[ i ] = l.get( i );
 150         }
 151         reset();
 152         return p;
 153     }
 154
 155     @Override
 156     public final void reset() throws NHXFormatException, IOException {
 157         _i = 0;
 158         _next = null;
 159         _in_comment = false;
 160         _saw_colon = false;
 161         _saw_open_bracket = false;
 162         _in_open_bracket = false;
 163         _in_double_quote = false;
 164         _in_single_quote = false;
 165         _clade_level = 0;
 166         _current_anotation = new StringBuilder();
 167         _current_phylogeny = null;
 168         _current_node = null;
 169         _my_source_charary = null;
 170         determineAndProcessSourceType( _source );
 171         switch ( _input_type ) {
 172             case CHAR_ARRAY:
 173                 _my_source_br = null;
 174                 _my_source_charary = ( char[] ) _nhx_source;
 175                 break;
 176             case BUFFERED_READER:
 177                 _my_source_br = ( BufferedReader ) _nhx_source;
 178                 break;
 179             default:
 180                 throw new RuntimeException( "unknown input type" );
 181         }
 182         parseNext();
 183     }
 184
 185     public final void setGuessRootedness( final boolean guess_rootedness ) {
 186         _guess_rootedness = guess_rootedness;
 187     }
 188
 189     public final void setIgnoreQuotes( final boolean ignore_quotes ) {
 190         _ignore_quotes = ignore_quotes;
 191     }
 192
 193     public final void setReplaceUnderscores( final boolean replace_underscores ) {
 194         _replace_underscores = replace_underscores;
 195     }
 196
 197     @Override
 198     public final void setSource( final Object nhx_source ) throws NHXFormatException, IOException {
 199         _source = nhx_source;
 200         reset();
 201     }
 202
 203     public final void setTaxonomyExtraction( final TAXONOMY_EXTRACTION taxonomy_extraction ) {
 204         _taxonomy_extraction = taxonomy_extraction;
 205     }
 206
 207     public final void setAllowErrorsInDistanceToParent( final boolean allow_errors_in_distance_to_parent ) {
 208         _allow_errors_in_distance_to_parent = allow_errors_in_distance_to_parent;
 209     }
 210
 211     private final void determineAndProcessSourceType( final Object nhx_source ) throws IOException {
 212         if ( nhx_source == null ) {
 213             throw new PhylogenyParserException( getClass() + ": attempt to parse null object." );
 214         }
 215         else if ( nhx_source instanceof String ) {
 216             _nhx_source = nhx_source;
 217             _input_type = NHXParser.BUFFERED_READER;
 218             _source_length = 0;
 219             InputStream is = new ByteArrayInputStream( (( String ) nhx_source ).getBytes(getEncoding()));
 220             final InputStreamReader isr = new InputStreamReader( is, getEncoding() );
 221             _nhx_source = new BufferedReader( isr );
 222         }
 223         else if ( nhx_source instanceof char[] ) {
 224             _input_type = NHXParser.CHAR_ARRAY;
 225             _source_length = ( ( char[] ) nhx_source ).length;
 226             _nhx_source = nhx_source;
 227         }
 228         else if ( nhx_source instanceof File ) {
 229             _input_type = NHXParser.BUFFERED_READER;
 230             _source_length = 0;
 231             if ( _my_source_br != null ) {
 232                 //I am REALLY not sure if it is a "good" idea NOT to close the stream...
 233                 //                try {
 234                 //                    _my_source_br.close();
 235                 //                }
 236                 //                catch ( final IOException e ) {
 237                 //                }
 238             }
 239             final File f = ( File ) nhx_source;
 240             final String error = ForesterUtil.isReadableFile( f );
 241             if ( !ForesterUtil.isEmpty( error ) ) {
 242                 throw new PhylogenyParserException( error );
 243             }
 244             final InputStream is = new FileInputStream( f );
 245             final InputStreamReader isr = new InputStreamReader( is, getEncoding() );
 246             _nhx_source = new BufferedReader( isr );
 247         }
 248         else if ( nhx_source instanceof URL ) {
 249             _input_type = NHXParser.BUFFERED_READER;
 250             _source_length = 0;
 251             if ( _my_source_br != null ) {
 252                 //I am REALLY not sure if it is a "good" idea NOT to close the stream...
 253                 //                try {
 254                 //                    _my_source_br.close();
 255                 //                }
 256                 //                catch ( final IOException e ) {
 257                 //                }
 258             }
 259             final InputStream is = ( ( URL ) nhx_source ).openStream();
 260             final InputStreamReader isr = new InputStreamReader( is, getEncoding() );
 261             _nhx_source = new BufferedReader( isr );
 262         }
 263         else if ( nhx_source instanceof InputStream ) {
 264             _input_type = NHXParser.BUFFERED_READER;
 265             _source_length = 0;
 266             if ( _my_source_br != null ) {
 267                 //I am REALLY not sure if it is a "good" idea NOT to close the stream...
 268                 //                try {
 269                 //                    _my_source_br.close();
 270                 //                }
 271                 //                catch ( final IOException e ) {
 272                 //                }
 273             }
 274             final InputStream is = ( InputStream ) nhx_source;
 275             final InputStreamReader isr = new InputStreamReader( is, getEncoding() );
 276              _nhx_source = new BufferedReader( isr );
 277         }
 278         else {
 279             throw new IllegalArgumentException( getClass() + " can only parse objects of type String,"
 280                     + " char[], File, InputStream, or URL "
 281                     + " [attempt to parse object of " + nhx_source.getClass() + "]." );
 282         }
 283     }
 284
 285     private final Phylogeny finishPhylogeny() throws PhylogenyParserException, NHXFormatException,
 286     PhyloXmlDataFormatException {
 287         if ( _current_phylogeny != null ) {
 288             parseNHX( _current_anotation != null ? _current_anotation.toString() : "",
 289                     _current_phylogeny.getRoot(),
 290                     getTaxonomyExtraction(),
 291                     isReplaceUnderscores(),
 292                     isAllowErrorsInDistanceToParent(),
 293                     true,
 294                     isParseBeastStyleExtendedTags());
 295             if ( GUESS_IF_SUPPORT_VALUES ) {
 296                 if ( isBranchLengthsLikeBootstrapValues( _current_phylogeny ) ) {
 297                     moveBranchLengthsToConfidenceValues( _current_phylogeny );
 298                 }
 299             }
 300             if ( isGuessRootedness() ) {
 301                 final PhylogenyNode root = _current_phylogeny.getRoot();
 302                 if ( ( root.getDistanceToParent() >= 0.0 ) || !ForesterUtil.isEmpty( root.getName() )
 303                         || !ForesterUtil.isEmpty( PhylogenyMethods.getSpecies( root ) ) || root.isHasAssignedEvent() ) {
 304                     _current_phylogeny.setRooted( true );
 305                 }
 306             }
 307             return _current_phylogeny;
 308         }
 309         return null;
 310     }
 311
 312     private final Phylogeny finishSingleNodePhylogeny() throws PhylogenyParserException, NHXFormatException,
 313     PhyloXmlDataFormatException {
 314         final PhylogenyNode new_node = new PhylogenyNode();
 315         parseNHX( _current_anotation.toString(),
 316                   new_node,
 317                   getTaxonomyExtraction(),
 318                   isReplaceUnderscores(),
 319                   isAllowErrorsInDistanceToParent(),
 320                   true,
 321                   isParseBeastStyleExtendedTags());
 322         _current_phylogeny = new Phylogeny();
 323         _current_phylogeny.setRoot( new_node );
 324         return _current_phylogeny;
 325     }
 326
 327     private final void init() {
 328         setTaxonomyExtraction( TAXONOMY_EXTRACTION.NO );
 329         setReplaceUnderscores( REPLACE_UNDERSCORES_DEFAULT );
 330         setGuessRootedness( GUESS_ROOTEDNESS_DEFAULT );
 331         setIgnoreQuotes( IGNORE_QUOTES_DEFAULT );
 332         setAllowErrorsInDistanceToParent( ALLOW_ERRORS_IN_DISTANCE_TO_PARENT_DEFAULT );
 333         setParseBeastStyleExtendedTags( false );
 334     }
 335
 336     private final boolean isAllowErrorsInDistanceToParent() {
 337         return _allow_errors_in_distance_to_parent;
 338     }
 339
 340     private final boolean isGuessRootedness() {
 341         return _guess_rootedness;
 342     }
 343
 344     private final boolean isIgnoreQuotes() {
 345         return _ignore_quotes;
 346     }
 347
 348     private final boolean isReplaceUnderscores() {
 349         return _replace_underscores;
 350     }
 351
 352     private final void parseNext() throws IOException, NHXFormatException {
 353         if ( _source == null ) {
 354             throw new IOException( "source is not set" );
 355         }
 356         while ( true ) {
 357             char c = '\b';
 358             if ( _input_type == BUFFERED_READER ) {
 359                 final int ci = _my_source_br.read();
 360                 if ( ci >= 0 ) {
 361                     c = ( char ) ci;
 362                 }
 363                 else {
 364                     break;
 365                 }
 366             }
 367             else {
 368                 if ( _i >= _source_length ) {
 369                     break;
 370                 }
 371                 c = _my_source_charary[ _i ];
 372             }
 373             if ( !_in_single_quote && !_in_double_quote ) {
 374                 if ( c == ':' ) {
 375                     _saw_colon = true;
 376                 }
 377                 else if ( !( ( c < 33 ) || ( c == 127 ) ) && _saw_colon
 378                         && ( ( c != '[' ) && ( c != '.' ) && ( ( c < 48 ) || ( c > 57 ) ) ) ) {
 379                     _saw_colon = false;
 380                 }
 381                 if ( _in_open_bracket && ( c == ']' ) ) {
 382                     _in_open_bracket = false;
 383                 }
 384             }
 385             // \n\t is always ignored,
 386             // "=34  '=39 space=32
 387             if ( ( c < 32 ) || ( c == 127 ) || ( isIgnoreQuotes() && ( ( c == 32 ) || ( c == 34 ) || ( c == 39 ) ) )
 388                     || ( ( c == 32 ) && ( !_in_single_quote && !_in_double_quote ) )
 389                     || ( ( _clade_level == 0 ) && ( c == ';' ) && ( !_in_single_quote && !_in_double_quote ) ) ) {
 390                 //do nothing
 391             }
 392             else if ( _in_comment ) {
 393                 if ( c == ']' ) {
 394                     _in_comment = false;
 395                 }
 396             }
 397             else if ( _in_double_quote ) {
 398                 if ( c == '"' ) {
 399                     _in_double_quote = false;
 400                 }
 401                 else {
 402                     _current_anotation.append( changeCharInParens( c ) );
 403                 }
 404             }
 405             else if ( ( c == '"' ) && !_in_single_quote ) {
 406                 _in_double_quote = true;
 407             }
 408             else if ( _in_single_quote ) {
 409                 if ( c == 39 ) {
 410                     _in_single_quote = false;
 411                 }
 412                 else {
 413                     _current_anotation.append( changeCharInParens( c ) );
 414                 }
 415             }
 416             else if ( c == 39 ) {
 417                 _in_single_quote = true;
 418             }
 419             else if ( c == '[' ) {
 420                 _saw_open_bracket = true;
 421                 _in_open_bracket = true;
 422             }
 423             else if ( _saw_open_bracket ) {
 424                 if ( c != ']' ) {
 425                     // everything not starting with "[&" is considered a comment
 426                     // unless ":digits and/or . [bootstrap]":
 427                     if ( c == '&' ) {
 428                         _current_anotation.append( "[&" );
 429                     }
 430                     else if ( _saw_colon ) {
 431                         _current_anotation.append( "[" + c );
 432                     }
 433                     else {
 434                         _in_comment = true;
 435                     }
 436                 }
 437                 // comment consisting just of "[]":
 438                 _saw_open_bracket = false;
 439             }
 440             else if ( ( c == '(' ) && !_in_open_bracket ) {
 441                 final Phylogeny phy = processOpenParen();
 442                 if ( phy != null ) {
 443                     ++_i;
 444                     _next = phy;
 445                     return;
 446                 }
 447             }
 448             else if ( ( c == ')' ) && !_in_open_bracket ) {
 449                 processCloseParen();
 450             }
 451             else if ( ( c == ',' ) && !_in_open_bracket ) {
 452                 processComma();
 453             }
 454             else {
 455                 _current_anotation.append( c );
 456             }
 457             ++_i;
 458         } //  while ( true )
 459         if ( _clade_level != 0 ) {
 460             throw new PhylogenyParserException( "error in NH (Newick) formatted data: most likely cause: number of open parens does not equal number of close parens" );
 461         }
 462         if ( _current_phylogeny != null ) {
 463             _next = finishPhylogeny();
 464             _current_phylogeny = null;
 465             _current_anotation = null;
 466         }
 467         else if ( ( _current_anotation != null ) && ( _current_anotation.length() > 0 ) ) {
 468             _next = finishSingleNodePhylogeny();
 469             _current_anotation = null;
 470         }
 471         else {
 472             _next = null;
 473         }
 474     }
 475
 476     private final static char changeCharInParens( char c ) {
 477         if ( c == ':' ) {
 478             c = BELL;
 479         }
 480         else if ( c == '[' ) {
 481             c = '{';
 482         }
 483         else if ( c == ']' ) {
 484             c = '}';
 485         }
 486         return c;
 487     }
 488
 489     private final void processCloseParen() throws PhylogenyParserException, NHXFormatException,
 490     PhyloXmlDataFormatException {
 491         if ( _clade_level < 0 ) {
 492             throw new PhylogenyParserException( "error in NH (Newick)/NHX formatted data: most likely cause: number of close parens is larger than number of open parens" );
 493         }
 494         --_clade_level;
 495         if ( !_saw_closing_paren ) {
 496             final PhylogenyNode new_node = new PhylogenyNode();
 497             parseNHX( _current_anotation.toString(),
 498                       new_node,
 499                       getTaxonomyExtraction(),
 500                       isReplaceUnderscores(),
 501                       isAllowErrorsInDistanceToParent(),
 502                       true,
 503                       isParseBeastStyleExtendedTags());
 504             _current_anotation = new StringBuilder();
 505             _current_node.addAsChild( new_node );
 506         }
 507         else {
 508             parseNHX( _current_anotation.toString(),
 509                       _current_node.getLastChildNode(),
 510                       getTaxonomyExtraction(),
 511                       isReplaceUnderscores(),
 512                       isAllowErrorsInDistanceToParent(),
 513                       true,
 514                       isParseBeastStyleExtendedTags());
 515             _current_anotation = new StringBuilder();
 516         }
 517         if ( !_current_node.isRoot() ) {
 518             _current_node = _current_node.getParent();
 519         }
 520         _saw_closing_paren = true;
 521     }
 522
 523     private final void processComma() throws PhylogenyParserException, NHXFormatException, PhyloXmlDataFormatException {
 524         if ( !_saw_closing_paren ) {
 525             final PhylogenyNode new_node = new PhylogenyNode();
 526             parseNHX( _current_anotation.toString(),
 527                       new_node,
 528                       getTaxonomyExtraction(),
 529                       isReplaceUnderscores(),
 530                       isAllowErrorsInDistanceToParent(),
 531                       true,
 532                       isParseBeastStyleExtendedTags());
 533             if ( _current_node == null ) {
 534                 throw new NHXFormatException( "format might not be NH or NHX" );
 535             }
 536             _current_node.addAsChild( new_node );
 537         }
 538         else {
 539             parseNHX( _current_anotation.toString(),
 540                       _current_node.getLastChildNode(),
 541                       getTaxonomyExtraction(),
 542                       isReplaceUnderscores(),
 543                       isAllowErrorsInDistanceToParent(),
 544                       true,
 545                       isParseBeastStyleExtendedTags());
 546         }
 547         _current_anotation = new StringBuilder();
 548         _saw_closing_paren = false;
 549     }
 550
 551     private final Phylogeny processOpenParen() throws PhylogenyParserException, NHXFormatException,
 552     PhyloXmlDataFormatException {
 553         Phylogeny phy = null;
 554         final PhylogenyNode new_node = new PhylogenyNode();
 555         if ( _clade_level == 0 ) {
 556             if ( _current_phylogeny != null ) {
 557                 phy = finishPhylogeny();
 558             }
 559             _clade_level = 1;
 560             _current_anotation = new StringBuilder();
 561             _current_phylogeny = new Phylogeny();
 562             _current_phylogeny.setRoot( new_node );
 563         }
 564         else {
 565             ++_clade_level;
 566             _current_node.addAsChild( new_node );
 567         }
 568         _current_node = new_node;
 569         _saw_closing_paren = false;
 570         return phy;
 571     }
 572
 573     private final static NHXParser createInstance( final Object nhx_source ) throws NHXFormatException, IOException {
 574         final NHXParser parser = new NHXParser();
 575         parser.setSource( nhx_source );
 576         return parser;
 577     }
 578
 579     public final static Phylogeny[] parse( final Object nhx_source ) throws NHXFormatException, IOException {
 580         return NHXParser.createInstance( nhx_source ).parse();
 581     }
 582
 583     public final static void parseNHX( String s,
 584                                        final PhylogenyNode node_to_annotate,
 585                                        final TAXONOMY_EXTRACTION taxonomy_extraction,
 586                                        final boolean replace_underscores,
 587                                        final boolean allow_errors_in_distance_to_parent,
 588                                        final boolean replace_bell,
 589                                        final boolean parse_beast_style_extended_tags ) throws NHXFormatException,
 590                                        PhyloXmlDataFormatException {
 591         if ( ( taxonomy_extraction != TAXONOMY_EXTRACTION.NO ) && replace_underscores ) {
 592             throw new IllegalArgumentException( "cannot extract taxonomies and replace under scores at the same time" );
 593         }
 594         if ( ( s != null ) && ( s.length() > 0 ) ) {
 595             if ( replace_underscores ) {
 596                 s = s.replaceAll( "_+", " " );
 597             }
 598             s = s.replaceAll( "\\s+", " " ).trim();
 599             boolean is_nhx = false;
 600             final int ob = s.indexOf( "[" );
 601             if ( ob > -1 ) {
 602                 String b = "";
 603                 is_nhx = true;
 604                 final int cb = s.indexOf( "]" );
 605                 if ( cb < 0 ) {
 606                     throw new NHXFormatException( "error in NHX formatted data: no closing \"]\" in \"" + s + "\"" );
 607                 }
 608                 if ( s.indexOf( "&&NHX" ) == ( ob + 1 ) ) {
 609                     b = s.substring( ob + 6, cb );
 610                 }
 611                 else {
 612                     // No &&NHX and digits only: is likely to be a support value.
 613                     final String bracketed = s.substring( ob + 1, cb );
 614                     final Matcher numbers_only = NUMBERS_ONLY_PATTERN.matcher( bracketed );
 615                     if ( numbers_only.matches() ) {
 616                         b = ":" + NHXtags.SUPPORT + bracketed;
 617                     }
 618                     else if ( s.indexOf( "prob=" ) > -1 ) {
 619                         processMrBayes3Data( s, node_to_annotate );
 620                     }
 621                     if ( parse_beast_style_extended_tags ) {
 622                         processBeastStyleExtendedData( s, node_to_annotate );
 623                     }
 624                     final Matcher ewn_matcher = ENDS_WITH_NUMBER_PATTERN.matcher( s );
 625                     if ( ewn_matcher.find() ) {
 626                         b = ewn_matcher.group(1);
 627                     }
 628                 }
 629                 s = s.substring( 0, ob ) + b;
 630                 if ( ( s.indexOf( "[" ) > -1 ) || ( s.indexOf( "]" ) > -1 ) ) {
 631                     throw new NHXFormatException( "error in NHX formatted data: more than one \"]\" or \"[\"" );
 632                 }
 633             }
 634             final StringTokenizer t = new StringTokenizer( s, ":" );
 635
 636             if ( t.countTokens() > 0 ) {
 637                 if ( !s.startsWith( ":" ) ) {
 638                     if ( ( s.indexOf( BELL ) <= -1 ) || !replace_bell ) {
 639                         node_to_annotate.setName( t.nextToken() );
 640                     }
 641                     else {
 642                         node_to_annotate.setName( t.nextToken().replace( BELL, ':' ) );
 643                     }
 644                     if ( !replace_underscores && ( !is_nhx && ( taxonomy_extraction != TAXONOMY_EXTRACTION.NO ) ) ) {
 645                         ParserUtils.extractTaxonomyDataFromNodeName( node_to_annotate, taxonomy_extraction );
 646                     }
 647                 }
 648                 while ( t.hasMoreTokens() ) {
 649                     s = t.nextToken();
 650                     if ( ( s.indexOf( BELL ) > -1 ) && replace_bell ) {
 651                         s = s.replace( BELL, ':' );
 652                     }
 653                     if ( s.indexOf( '=' ) < 0 ) {
 654                         if ( ( node_to_annotate.getDistanceToParent() != PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT )
 655                                 && !allow_errors_in_distance_to_parent ) {
 656                             throw new NHXFormatException( "error in NHX formatted data: more than one distance to parent:"
 657                                     + "\"" + s + "\"" );
 658                         }
 659                         node_to_annotate.setDistanceToParent( doubleValue( s, allow_errors_in_distance_to_parent ) );
 660                     }
 661                     else if ( s.startsWith( NHXtags.SPECIES_NAME ) ) {
 662                         if ( !node_to_annotate.getNodeData().isHasTaxonomy() ) {
 663                             node_to_annotate.getNodeData().setTaxonomy( new Taxonomy() );
 664                         }
 665                         node_to_annotate.getNodeData().getTaxonomy().setScientificName( s.substring( 2 ) );
 666                     }
 667                     else if ( s.startsWith( NHXtags.IS_DUPLICATION ) ) {
 668                         if ( ( s.charAt( 2 ) == 'Y' ) || ( s.charAt( 2 ) == 'T' ) ) {
 669                             node_to_annotate.getNodeData().setEvent( Event.createSingleDuplicationEvent() );
 670                         }
 671                         else if ( ( s.charAt( 2 ) == 'N' ) || ( s.charAt( 2 ) == 'F' ) ) {
 672                             node_to_annotate.getNodeData().setEvent( Event.createSingleSpeciationEvent() );
 673                         }
 674                         else if ( s.charAt( 2 ) == '?' ) {
 675                             node_to_annotate.getNodeData().setEvent( Event.createSingleSpeciationOrDuplicationEvent() );
 676                         }
 677                         else {
 678                             throw new NHXFormatException( "error in NHX formatted data: :D=Y or :D=N or :D=?" );
 679                         }
 680                     }
 681                     else if ( s.startsWith( NHXtags.SUPPORT ) ) {
 682                         PhylogenyMethods.setConfidence( node_to_annotate, doubleValue( s.substring( 2 ), false ) );
 683                     }
 684                     else if ( s.startsWith( NHXtags.TAXONOMY_ID ) ) {
 685                         if ( !node_to_annotate.getNodeData().isHasTaxonomy() ) {
 686                             node_to_annotate.getNodeData().setTaxonomy( new Taxonomy() );
 687                         }
 688                         node_to_annotate.getNodeData().getTaxonomy().setIdentifier( new Identifier( s.substring( 2 ) ) );
 689                     }
 690                     else if ( s.startsWith( NHXtags.SEQUENCE_ACCESSION ) ) {
 691                         if ( !node_to_annotate.getNodeData().isHasSequence() ) {
 692                             node_to_annotate.getNodeData().setSequence( new Sequence() );
 693                         }
 694                         node_to_annotate.getNodeData().getSequence()
 695                         .setAccession( new Accession( s.substring( 3 ), "?" ) );
 696                     }
 697                     else if ( s.startsWith( NHXtags.GENE_NAME ) ) {
 698                         if ( !node_to_annotate.getNodeData().isHasSequence() ) {
 699                             node_to_annotate.getNodeData().setSequence( new Sequence() );
 700                         }
 701                         node_to_annotate.getNodeData().getSequence().setName( s.substring( 3 ) );
 702                     }
 703                 } // while ( t.hasMoreTokens() )
 704             }
 705         }
 706     }
 707
 708     private final static double doubleValue( final String str, final boolean allow_errors ) throws NHXFormatException {
 709         try {
 710             return Double.valueOf( str ).doubleValue();
 711         }
 712         catch ( final NumberFormatException ex ) {
 713             if ( !allow_errors ) {
 714                 throw new NHXFormatException( "error in NH/NHX formatted data: failed to parse number from " + "\""
 715                         + str + "\"" );
 716             }
 717         }
 718         return 0.0;
 719     }
 720
 721     private final static boolean isBranchLengthsLikeBootstrapValues( final Phylogeny p ) {
 722         final PhylogenyNodeIterator it = p.iteratorExternalForward();
 723         final double d0 = it.next().getDistanceToParent();
 724         if ( ( d0 < 10 ) || !it.hasNext() ) {
 725             return false;
 726         }
 727         while ( it.hasNext() ) {
 728             final double d = it.next().getDistanceToParent();
 729             if ( ( d != d0 ) || ( d < 10 ) ) {
 730                 return false;
 731             }
 732         }
 733         return true;
 734     }
 735
 736     private final static void moveBranchLengthsToConfidenceValues( final Phylogeny p ) {
 737         final PhylogenyNodeIterator it = p.iteratorPostorder();
 738         while ( it.hasNext() ) {
 739             final PhylogenyNode n = it.next();
 740             PhylogenyMethods.setBootstrapConfidence( n, n.getDistanceToParent() );
 741             n.setDistanceToParent( PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT );
 742         }
 743     }
 744
 745     private final static void processBeastStyleExtendedData( final String s,
 746                                                      final PhylogenyNode node_to_annotate )
 747             throws NHXFormatException {
 748         final Matcher ft_bs_matcher = BEAST_STYLE_EXTENDED_BOOTSTRAP_PATTERN.matcher( s );
 749
 750         double bs = -1;
 751         if ( ft_bs_matcher.find() ) {
 752             try {
 753                 bs = Double.parseDouble( ft_bs_matcher.group( 1 ) );
 754             }
 755             catch ( final NumberFormatException e ) {
 756                 throw new NHXFormatException( "failed to parse bootstrap support from \""
 757                         + s + "\"" );
 758             }
 759             if ( bs >= 0.0 ) {
 760                 node_to_annotate.getBranchData()
 761                 .addConfidence( new Confidence( bs, "bootstrap" ) );
 762             }
 763         }
 764         final Matcher ft_color_matcher = BEAST_STYLE_EXTENDED_COLOR_PATTERN.matcher( s );
 765         Color c = null;
 766         if ( ft_color_matcher.find() ) {
 767             try {
 768                 c = Color.decode(ft_color_matcher.group( 1 ) );
 769             }
 770             catch ( final NumberFormatException e ) {
 771                 throw new NHXFormatException( "failed to parse color from \""
 772                         + s + "\""  );
 773             }
 774         }
 775         if ( c != null ) {
 776             node_to_annotate.getBranchData().setBranchColor( new BranchColor( c ) );
 777         }
 778     }
 779
 780     private final static void processMrBayes3Data( final String s, final PhylogenyNode node_to_annotate )
 781             throws NHXFormatException {
 782         double sd = -1;
 783         final Matcher mb_prob_sd_matcher = MB_PROB_SD_PATTERN.matcher( s );
 784         if ( mb_prob_sd_matcher.find() ) {
 785             try {
 786                 sd = Double.parseDouble( mb_prob_sd_matcher.group( 1 ) );
 787             }
 788             catch ( final NumberFormatException e ) {
 789                 throw new NHXFormatException( "failed to parse probability standard deviation (Mr Bayes output) from \""
 790                         + s + "\"" );
 791             }
 792         }
 793         final Matcher mb_prob_matcher = MB_PROB_PATTERN.matcher( s );
 794         if ( mb_prob_matcher.find() ) {
 795             double prob = -1;
 796             try {
 797                 prob = Double.parseDouble( mb_prob_matcher.group( 1 ) );
 798             }
 799             catch ( final NumberFormatException e ) {
 800                 throw new NHXFormatException( "failed to parse probability (Mr Bayes output) from \"" + s + "\"" );
 801             }
 802             if ( prob >= 0.0 ) {
 803                 if ( sd >= 0.0 ) {
 804                     node_to_annotate.getBranchData()
 805                     .addConfidence( new Confidence( prob, "posterior probability", sd ) );
 806                 }
 807                 else {
 808                     node_to_annotate.getBranchData().addConfidence( new Confidence( prob, "posterior probability" ) );
 809                 }
 810             }
 811         }
 812         final Matcher mb_bl_matcher = MB_BL_PATTERN.matcher( s );
 813         if ( mb_bl_matcher.find() ) {
 814             double bl = -1;
 815             try {
 816                 bl = Double.parseDouble( mb_bl_matcher.group( 1 ) );
 817             }
 818             catch ( final NumberFormatException e ) {
 819                 throw new NHXFormatException( "failed to parse median branch length (Mr Bayes output) from \"" + s
 820                                               + "\"" );
 821             }
 822             if ( bl >= 0.0 ) {
 823                 node_to_annotate.setDistanceToParent( bl );
 824             }
 825         }
 826     }
 827
 828     public String getEncoding() {
 829         return _encoding;
 830     }
 831
 832     private final boolean isParseBeastStyleExtendedTags() {
 833         return _parse_beast_style_extended_tags;
 834     }
 835
 836     public final void setParseBeastStyleExtendedTags( final boolean parse_beast_style_extended_tags ) {
 837         _parse_beast_style_extended_tags = parse_beast_style_extended_tags;
 838     }
 839
 840     public static enum TAXONOMY_EXTRACTION {
 841         AGGRESSIVE, NO, PFAM_STYLE_RELAXED, PFAM_STYLE_STRICT;
 842     }
 843 }