src/jalview/io/NewickFile.java

   1 /*
   2 * Jalview - A Sequence Alignment Editor and Viewer
   3 * Copyright (C) 2005 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle
   4 *
   5 * This program is free software; you can redistribute it and/or
   6 * modify it under the terms of the GNU General Public License
   7 * as published by the Free Software Foundation; either version 2
   8 * of the License, or (at your option) any later version.
   9 *
  10 * This program is distributed in the hope that it will be useful,
  11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 * GNU General Public License for more details.
  14 *
  15 * You should have received a copy of the GNU General Public License
  16 * along with this program; if not, write to the Free Software
  17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
  18 */
  19
  20 // NewickFile.java
  21 // Tree I/O
  22 // http://evolution.genetics.washington.edu/phylip/newick_doc.html
  23
  24 package jalview.io;
  25
  26 import java.io.*;
  27 import java.util.*;
  28 import jalview.datamodel.*;
  29
  30 public class NewickFile extends FileParse
  31 {
  32   SequenceNode root;
  33
  34   private boolean HasBootstrap = false;
  35   private boolean HasDistances = false;
  36   private boolean RootHasDistance = false;
  37
  38   private String ErrorStringrange(String Error, String Er, int r, int p, String s) {
  39     return ((Error==null) ? "" : Error)
  40         + Er +
  41         " at position "+p+" ( "
  42         + s.substring((p-r)<0 ? 0 : (p-r),
  43                       (p+r)>s.length() ? s.length() : (p+r))
  44         + " )\n";
  45   }
  46
  47   // @tree annotations
  48   // These are set automatically by the reader
  49   public boolean HasBootstrap() {
  50     return HasBootstrap;
  51   }
  52
  53   public boolean HasDistances() {
  54     return HasDistances;
  55   }
  56   public NewickFile(String inStr) throws IOException
  57   {
  58     super(inStr, "Paste");
  59   }
  60
  61   public NewickFile(String inFile, String type)
  62       throws IOException
  63   {
  64
  65     super(inFile, type);
  66   }
  67   // File IO Flags
  68   boolean ReplaceUnderscores = false;
  69
  70   public void parse() throws IOException
  71   {
  72     String nf;
  73
  74     { // fill nf with complete tree file
  75       StringBuffer file = new StringBuffer();
  76       while ( (nf = nextLine()) != null)
  77       {
  78         file.append(nf);
  79       }
  80       nf = file.toString();
  81     }
  82
  83     root = new SequenceNode();
  84     SequenceNode realroot = null;
  85     SequenceNode c = root;
  86
  87     int d = -1;
  88     int cp = 0;
  89     int flen = nf.length();
  90
  91     String Error = null;
  92     String nodename = null;
  93
  94     float DefDistance = (float) 0.00001; // @param Default distance for a node - very very small
  95     int DefBootstrap = 0; // @param Default bootstrap for a node
  96
  97     float distance=DefDistance;
  98     int bootstrap=DefBootstrap;
  99
 100     boolean ascending = false; // flag indicating that we are leaving the current node
 101
 102     com.stevesoft.pat.Regex majorsyms = new com.stevesoft.pat.Regex("[(\\['),;]");
 103
 104     while (majorsyms.searchFrom(nf, cp) && Error==null) {
 105       int fcp = majorsyms.matchedFrom();
 106       switch (nf.charAt(fcp)) {
 107
 108         case '[': // Comment or structured/extended NH format info
 109           com.stevesoft.pat.Regex comment = new com.stevesoft.pat.Regex("]");
 110           if (comment.searchFrom(nf, fcp))
 111           {
 112             // Skip the comment field
 113             cp = 1 + comment.matchedFrom();
 114           }
 115           else
 116           {
 117             Error = ErrorStringrange(Error, "Unterminated comment", 3, fcp, nf);
 118           }
 119           ;
 120           break;
 121
 122         case '(':
 123
 124           // ascending should not be set
 125           // New Internal node
 126           if (ascending)
 127           {
 128             Error = ErrorStringrange(Error, "Unexpected '('", 7, fcp, nf);
 129             continue;
 130           }
 131           ;
 132           d++;
 133           if (c.right() == null)
 134           {
 135             c.setRight(new SequenceNode(null, c, null, DefDistance, DefBootstrap, false));
 136             c = (SequenceNode) c.right();
 137           }
 138           else
 139           {
 140             if (c.left() != null)
 141             {
 142               // Dummy node for polytomy - keeps c.left free for new node
 143               SequenceNode tmpn = new SequenceNode(null, c, null, 0, 0, true);
 144               tmpn.SetChildren(c.left(), c.right());
 145               c.setRight(tmpn);
 146             }
 147             c.setLeft(new SequenceNode(null, c, null, DefDistance, DefBootstrap, false));
 148             c = (SequenceNode) c.left();
 149           }
 150           if (realroot==null) {
 151             realroot = c;
 152           }
 153           nodename = null;
 154           distance = DefDistance;
 155           bootstrap = DefBootstrap;
 156           cp = fcp + 1;
 157           break;
 158
 159           // Deal with quoted fields
 160         case '\'':
 161           com.stevesoft.pat.Regex qnodename = new com.stevesoft.pat.Regex(
 162               "([^']|'')+'");
 163           if (qnodename.searchFrom(nf, fcp))
 164           {
 165             int nl = qnodename.stringMatched().length();
 166             nodename = new String(qnodename.stringMatched().substring(0, nl - 1));
 167             cp = fcp + nl + 1;
 168           }
 169           else
 170           {
 171             Error = ErrorStringrange(Error, "Unterminated quotes for nodename",
 172                                      7, fcp, nf);
 173           }
 174           break;
 175
 176         case ';':
 177           if (d != -1)
 178           {
 179             Error = ErrorStringrange(Error,
 180                                      "Wayward semicolon (depth=" + d + ")", 7,
 181                                      fcp, nf);
 182           }
 183           // cp advanced at the end of default
 184
 185         default:
 186
 187           // Parse simpler field strings
 188           String fstring = nf.substring(cp, fcp);
 189           com.stevesoft.pat.Regex uqnodename = new com.stevesoft.pat.Regex(
 190               "\\b([^' :;\\](),]+)");
 191           com.stevesoft.pat.Regex nbootstrap = new com.stevesoft.pat.Regex(
 192               "\\S+([0-9+]+)\\S*:");
 193           com.stevesoft.pat.Regex ndist = new com.stevesoft.pat.Regex(
 194               ":([-0-9.+]+)");
 195           if (uqnodename.search(fstring)
 196               && (uqnodename.matchedFrom(1) == 0
 197                   || fstring.charAt(uqnodename.matchedFrom(1) - 1) != ':')) // JBPNote HACK!
 198
 199           {
 200             if (nodename == null)
 201             {
 202               if (ReplaceUnderscores) {
 203                 nodename = uqnodename.stringMatched(1).replace('_', ' ');
 204               } else {
 205                 nodename = uqnodename.stringMatched(1);
 206               }
 207             }
 208             else
 209             {
 210               Error = ErrorStringrange(Error,
 211                                        "File has broken algorithm - overwritten nodename",
 212                                        10, fcp,
 213                                        nf);
 214             }
 215           }
 216           if (nbootstrap.search(fstring)
 217               &&
 218               nbootstrap.matchedFrom(1)
 219               > uqnodename.matchedFrom(1) + uqnodename.stringMatched().length())
 220           {
 221             try
 222             {
 223               bootstrap = (new Integer(nbootstrap.stringMatched(1))).intValue();
 224               HasBootstrap = true;
 225             }
 226             catch (Exception e)
 227             {
 228               Error = ErrorStringrange(Error, "Can't parse bootstrap value", 4,
 229                                        cp + nbootstrap.matchedFrom(), nf);
 230             }
 231           }
 232           boolean nodehasdistance=false;
 233           if (ndist.search(fstring))
 234           {
 235             try
 236             {
 237               distance = (new Float(ndist.stringMatched(1))).floatValue();
 238               HasDistances = true;
 239               nodehasdistance = true;
 240             }
 241             catch (Exception e)
 242             {
 243               Error = ErrorStringrange(Error, "Can't parse node distance value",
 244                                        7, cp + ndist.matchedFrom(), nf);
 245             }
 246           }
 247
 248           if (ascending)
 249           {
 250             // Write node info here
 251             c.setName(nodename);
 252             c.dist = (HasDistances) ? distance : 0;
 253             c.setBootstrap((HasBootstrap) ? bootstrap : 0);
 254             if (c==realroot) {
 255               RootHasDistance = nodehasdistance; // JBPNote This is really UGLY!!!
 256             }
 257           }
 258           else
 259           {
 260             // Find a place to put the leaf
 261             SequenceNode newnode =
 262             new SequenceNode(null, c,
 263                              nodename,
 264                              (HasDistances) ? distance : DefDistance,
 265                              (HasBootstrap) ? bootstrap : DefBootstrap,
 266                              false);
 267
 268             if (c.right() == null)
 269             {
 270               c.setRight(newnode);
 271             }
 272             else
 273             {
 274               if (c.left() == null)
 275               {
 276                 c.setLeft(newnode);
 277               }
 278               else
 279               {
 280                 // Insert a dummy node for polytomy
 281                 SequenceNode newdummy = new SequenceNode(null, c, null, 0, 0, true);
 282                 newdummy.SetChildren(c.left(), newnode);
 283                 c.setLeft(newdummy);
 284               }
 285             }
 286           }
 287           if (ascending)
 288           {
 289             // move back up the tree from preceding closure
 290             c = c.AscendTree();
 291             if (d > -1 && c == null)
 292             {
 293               Error = ErrorStringrange(Error,
 294                                        "File broke algorithm: Lost place in tree (is there an extra ')' ?)",
 295                                        7, fcp, nf);
 296             }
 297           }
 298
 299           if (nf.charAt(fcp) == ')') {
 300             d--;
 301             ascending = true;
 302           } else {
 303             if (nf.charAt(fcp) == ',') {
 304               if (ascending) {
 305                ascending = false;
 306              } else {
 307                // Just advance focus, if we need to
 308                if (c.left()!=null && (!c.left().isLeaf())) {
 309                  c = (SequenceNode) c.left();
 310                }
 311              }
 312             } // else : We do nothing if ';' is encountered.
 313           }
 314           // Reset new node properties to obvious fakes
 315           nodename = null;
 316           distance = DefDistance;
 317           bootstrap = DefBootstrap;
 318
 319           cp=fcp+1;
 320       }
 321     }
 322
 323     if (Error!=null) {
 324       throw(new IOException("NewickFile: "+Error+"\n"));
 325     }
 326
 327     root = (SequenceNode) root.right().detach(); // remove the imaginary root.
 328     if (!RootHasDistance) {
 329       root.dist = 0;
 330     }
 331
 332   }
 333
 334   public NewickFile(SequenceNode newtree) {
 335     root = newtree;
 336   }
 337
 338   public NewickFile(SequenceNode newtree, boolean bootstrap) {
 339     HasBootstrap = bootstrap;
 340     root=newtree;
 341   }
 342   public NewickFile(SequenceNode newtree, boolean bootstrap, boolean distances) {
 343     root = newtree;
 344     HasBootstrap = bootstrap;
 345     HasDistances = distances;
 346   }
 347
 348   public NewickFile(SequenceNode newtree, boolean bootstrap, boolean distances, boolean rootdistance) {
 349       root = newtree;
 350       HasBootstrap = bootstrap;
 351       HasDistances = distances;
 352       RootHasDistance = rootdistance;
 353     }
 354
 355   public SequenceNode getTree() {
 356     return root;
 357   }
 358
 359   public String print() {
 360     synchronized (this) {
 361       StringBuffer tf = new StringBuffer();
 362       print(tf, root);
 363       return (tf.append(";").toString());
 364     }
 365   }
 366
 367   public String print(boolean withbootstraps) {
 368     synchronized(this) {
 369       boolean boots = this.HasBootstrap;
 370       this.HasBootstrap = withbootstraps;
 371       String rv = print();
 372       this.HasBootstrap = boots;
 373       return rv;
 374     }
 375   }
 376
 377   public String print(boolean withbootstraps, boolean withdists) {
 378     synchronized(this) {
 379       boolean dists = this.HasDistances;
 380       this.HasDistances = withdists;
 381       String rv = print(withbootstraps);
 382       this.HasDistances = dists;
 383       return rv;
 384     }
 385   }
 386   boolean printRootInfo = false;
 387
 388
 389   public String print(boolean withbootstraps, boolean withdists, boolean printRootInfo) {
 390     synchronized(this) {
 391       boolean rootinfo = printRootInfo;
 392       this.printRootInfo = printRootInfo;
 393       String rv = print(withbootstraps, withdists);
 394       this.printRootInfo = rootinfo;
 395       return rv;
 396     }
 397   }
 398   private com.stevesoft.pat.Regex[] NodeSafeName =
 399       new com.stevesoft.pat.Regex[]
 400       { new com.stevesoft.pat.Regex().perlCode("m/[\\[,:'()]/"), // test for requiring quotes
 401       new com.stevesoft.pat.Regex().perlCode("s/'/''/"), // escaping quote characters
 402       new com.stevesoft.pat.Regex().perlCode("s/\\/w/_/") // unqoted whitespace transformation
 403   };
 404   char QuoteChar='\'';
 405   char getQuoteChar() {
 406     return QuoteChar;
 407   }
 408
 409   char setQuoteChar(char c) {
 410     char old = QuoteChar;
 411     QuoteChar = c;
 412     return old;
 413   }
 414
 415   private String nodeName(String name) {
 416     if (NodeSafeName[0].search(name)) {
 417       return QuoteChar + NodeSafeName[1].replaceAll(name) + QuoteChar;
 418     } else {
 419       return NodeSafeName[2].replaceAll(name);
 420     }
 421   }
 422   private String printNodeField(SequenceNode c) {
 423
 424     return ( (c.getName() == null) ? ""
 425              : nodeName(c.getName()))
 426         + ( (HasBootstrap)
 427             ? ( (c.getBootstrap() > -1)
 428                 ? " " + c.getBootstrap()
 429                 : "")
 430             : "")
 431         + ( (HasDistances)
 432             ? ":" + c.dist : "");
 433   }
 434   private String printRootField(SequenceNode root) {
 435
 436       return (printRootInfo)
 437           ? (( (root.getName() == null) ? ""
 438                : nodeName(root.getName()))
 439              + ( (HasBootstrap)
 440                  ? ( (root.getBootstrap() > -1)
 441                      ? " " + root.getBootstrap()
 442                      : "")
 443                  : "")
 444              + ( (RootHasDistance)
 445                  ? ":" + root.dist : ""))
 446           : "";
 447     }
 448
 449 // Non recursive call deals with root node properties
 450   public void print(StringBuffer tf, SequenceNode root) {
 451     if (root!=null) {
 452       if (root.isLeaf() && printRootInfo) {
 453         tf.append(printRootField(root));
 454       } else {
 455         if (root.isDummy()) {
 456           _print(tf, (SequenceNode) root.right());
 457           _print(tf, (SequenceNode) root.left());
 458         } else {
 459           tf.append("(");
 460           _print(tf, (SequenceNode) root.right());
 461           if (root.left() != null) {
 462             tf.append(",");
 463           }
 464           _print(tf, (SequenceNode) root.left());
 465           tf.append(")" + printRootField(root));
 466         }
 467       }
 468     }
 469   }
 470
 471   // Recursive call for non-root nodes
 472   public void _print(StringBuffer tf, SequenceNode c) {
 473     if (c!=null) {
 474       if (c.isLeaf()) {
 475         tf.append(printNodeField(c));
 476       } else {
 477         if (c.isDummy()) {
 478           _print(tf, (SequenceNode) c.right());
 479           _print(tf, (SequenceNode) c.left());
 480         } else {
 481           tf.append("(");
 482           _print(tf, (SequenceNode) c.right());
 483           if (c.left() != null) {
 484             tf.append(",");
 485           }
 486           _print(tf, (SequenceNode) c.left());
 487           tf.append(")" + printNodeField(c));
 488         }
 489       }
 490     }
 491   }
 492
 493 // Test
 494   public static void main(String[] args)
 495 {
 496   try
 497   {
 498     File fn = new File(args[0]);
 499
 500     StringBuffer newickfile =  new StringBuffer();
 501     BufferedReader treefile =
 502         new BufferedReader(new FileReader(fn));
 503     String l;
 504     while ((l = treefile.readLine())!=null) {
 505       newickfile.append(l);
 506     }
 507     treefile.close();
 508     System.out.println("Read file :\n");
 509     NewickFile trf = new NewickFile(args[0], "File");
 510     trf.parse();
 511     System.out.println("Original file :\n");
 512     com.stevesoft.pat.Regex nonl = new com.stevesoft.pat.Regex("\n+", "");
 513     System.out.println(nonl.replaceAll(newickfile.toString())+"\n");
 514
 515     System.out.println("Parsed file.\n");
 516     System.out.println("Default output type for original input.\n");
 517     System.out.println(trf.print());
 518     System.out.println("Without bootstraps.\n");
 519     System.out.println(trf.print(false));
 520     System.out.println("Without distances.\n");
 521     System.out.println(trf.print(true,false));
 522     System.out.println("Without bootstraps but with distanecs.\n");
 523     System.out.println(trf.print(false, true));
 524     System.out.println("Without bootstraps or distanecs.\n");
 525     System.out.println(trf.print(false, false));
 526     System.out.println("With bootstraps and with distances.\n");
 527     System.out.println(trf.print(true, true));
 528   }
 529   catch (java.io.IOException e)
 530   {
 531     System.err.println("Exception\n" + e);
 532     e.printStackTrace();
 533   }
 534 }
 535
 536 }