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