src/jalview/io/NewickFile.java

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