src/uk/ac/vamsas/objects/utils/trees/NewickFile.java

   1 /*\r
   2  * originally from \r
   3  * \r
   4  * Jalview - A Sequence Alignment Editor and Viewer\r
   5  * Copyright (C) 2007 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle\r
   6  *\r
   7  * This program is free software; you can redistribute it and/or\r
   8  * modify it under the terms of the GNU General Public License\r
   9  * as published by the Free Software Foundation; either version 2\r
  10  * of the License, or (at your option) any later version.\r
  11  *\r
  12  * This program is distributed in the hope that it will be useful,\r
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  15  * GNU General Public License for more details.\r
  16  *\r
  17  * You should have received a copy of the GNU General Public License\r
  18  * along with this program; if not, write to the Free Software\r
  19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA\r
  20  */\r
  21 \r
  22 // NewickFile.java\r
  23 // Tree I/O\r
  24 // http://evolution.genetics.washington.edu/phylip/newick_doc.html\r
  25 // TODO: Implement Basic NHX tag parsing and preservation\r
  26 // TODO: http://evolution.genetics.wustl.edu/eddy/forester/NHX.html\r
  27 // TODO: Extended SequenceNodeI to hold parsed NHX strings\r
  28 package uk.ac.vamsas.objects.utils.trees;\r
  29 \r
  30 import java.io.*;\r
  31 import java.util.Enumeration;\r
  32 import java.util.Hashtable;\r
  33 import java.util.Vector;\r
  34 import java.util.regex.Matcher;\r
  35 import java.util.regex.Pattern;\r
  36 \r
  37 import uk.ac.vamsas.client.Vobject;\r
  38 import uk.ac.vamsas.objects.core.Treenode;\r
  39 import uk.ac.vamsas.objects.core.Vref;\r
  40 \r
  41 /**\r
  42  * DOCUMENT ME!\r
  43  * \r
  44  * @author $author$\r
  45  * @version $Revision: 1.12 $\r
  46  */\r
  47 public class NewickFile {\r
  48   SequenceNode root;\r
  49 \r
  50   private boolean HasBootstrap = false;\r
  51 \r
  52   private boolean HasDistances = false;\r
  53 \r
  54   private boolean RootHasDistance = false;\r
  55 \r
  56   // File IO Flags\r
  57   boolean ReplaceUnderscores = true;\r
  58 \r
  59   boolean printRootInfo = false;\r
  60 \r
  61   private Pattern[] NodeSafeName = new Pattern[] {\r
  62       Pattern.compile("[\\[,:'()]"), // test for requiring quotes\r
  63       Pattern.compile("'"), // escaping quote characters\r
  64       Pattern.compile("\\s") // unqoted whitespace transformation\r
  65   };\r
  66 \r
  67   char QuoteChar = '\'';\r
  68 \r
  69   String newickFile = null;\r
  70 \r
  71   /**\r
  72    * Creates a new NewickFile object\r
  73    * \r
  74    * @param inStr\r
  75    *          Newick style tree string\r
  76    * \r
  77    * @throws IOException\r
  78    *           if string is not a valid newick file\r
  79    */\r
  80   public NewickFile(String inStr) throws IOException {\r
  81     newickFile = inStr;\r
  82     parse();\r
  83   }\r
  84 \r
  85   public NewickFile(File inFile) throws IOException {\r
  86     errormessage = "Problem's reading file " + inFile;\r
  87     dataIn = new java.io.BufferedReader(new InputStreamReader(\r
  88         new java.io.FileInputStream(inFile)));\r
  89     parse();\r
  90   }\r
  91 \r
  92   /**\r
  93    * Creates a new NewickFile object.\r
  94    * \r
  95    * @param newtree\r
  96    *          DOCUMENT ME!\r
  97    */\r
  98   public NewickFile(SequenceNode newtree) {\r
  99     root = newtree;\r
 100   }\r
 101 \r
 102   /**\r
 103    * Creates a new NewickFile object.\r
 104    * \r
 105    * @param newtree\r
 106    *          DOCUMENT ME!\r
 107    * @param bootstrap\r
 108    *          DOCUMENT ME!\r
 109    */\r
 110   public NewickFile(SequenceNode newtree, boolean bootstrap) {\r
 111     HasBootstrap = bootstrap;\r
 112     root = newtree;\r
 113   }\r
 114 \r
 115   /**\r
 116    * Creates a new NewickFile object.\r
 117    * \r
 118    * @param newtree\r
 119    *          DOCUMENT ME!\r
 120    * @param bootstrap\r
 121    *          DOCUMENT ME!\r
 122    * @param distances\r
 123    *          DOCUMENT ME!\r
 124    */\r
 125   public NewickFile(SequenceNode newtree, boolean bootstrap, boolean distances) {\r
 126     root = newtree;\r
 127     HasBootstrap = bootstrap;\r
 128     HasDistances = distances;\r
 129   }\r
 130 \r
 131   /**\r
 132    * Creates a new NewickFile object.\r
 133    * \r
 134    * @param newtree\r
 135    *          DOCUMENT ME!\r
 136    * @param bootstrap\r
 137    *          DOCUMENT ME!\r
 138    * @param distances\r
 139    *          DOCUMENT ME!\r
 140    * @param rootdistance\r
 141    *          DOCUMENT ME!\r
 142    */\r
 143   public NewickFile(SequenceNode newtree, boolean bootstrap, boolean distances,\r
 144       boolean rootdistance) {\r
 145     root = newtree;\r
 146     HasBootstrap = bootstrap;\r
 147     HasDistances = distances;\r
 148     RootHasDistance = rootdistance;\r
 149   }\r
 150 \r
 151   /**\r
 152    * DOCUMENT ME!\r
 153    * \r
 154    * @param Error\r
 155    *          Message prefix\r
 156    * @param Er\r
 157    *          Message qualifier (ie the incorrect data)\r
 158    * @param r\r
 159    *          range of characters either side to dump\r
 160    * @param p\r
 161    *          character position\r
 162    * @param s\r
 163    *          newick string being parsed\r
 164    * \r
 165    * @return composed error message\r
 166    */\r
 167   private String ErrorStringrange(String Error, String Er, int r, int p,\r
 168       String s) {\r
 169     return ((Error == null) ? "" : Error)\r
 170         + Er\r
 171         + " at position "\r
 172         + p\r
 173         + " ( "\r
 174         + s.substring(((p - r) < 0) ? 0 : (p - r), ((p + r) > s.length()) ? s\r
 175             .length() : (p + r)) + " )\n";\r
 176   }\r
 177 \r
 178   /**\r
 179    * \r
 180    * @return true if tree has bootstrap values\r
 181    */\r
 182   public boolean HasBootstrap() {\r
 183     return HasBootstrap;\r
 184   }\r
 185 \r
 186   /**\r
 187    * \r
 188    * @return true if tree has distances on branches\r
 189    */\r
 190   public boolean HasDistances() {\r
 191     return HasDistances;\r
 192   }\r
 193 \r
 194   /**\r
 195    * \r
 196    * @return true if root has a stem distance\r
 197    */\r
 198   public boolean HasRootDistance() {\r
 199     return RootHasDistance;\r
 200   }\r
 201 \r
 202   /*\r
 203    * hacked out of jalview code\r
 204    */\r
 205   boolean error;\r
 206 \r
 207   String errormessage;\r
 208 \r
 209   java.io.BufferedReader dataIn = null;\r
 210 \r
 211   public String nextLine() throws IOException {\r
 212     if (dataIn == null && newickFile == null)\r
 213       throw new IOException(\r
 214           "IMPLEMENTATION ERROR: NewickFile has not been initialised for reading a newick string.");\r
 215     if (dataIn == null) {\r
 216       dataIn = new BufferedReader(new StringReader(newickFile));\r
 217       error = false;\r
 218     }\r
 219     if (!error)\r
 220       return dataIn.readLine();\r
 221     throw new IOException("Invalid Source Stream:" + errormessage);\r
 222   }\r
 223 \r
 224   /**\r
 225    * call this to convert the newick string into a binary node linked tree\r
 226    * Note: this is automatically called by the constructors, so you normally\r
 227    * wouldn't need to use this.\r
 228    * \r
 229    * @throws IOException\r
 230    *           if the newick string cannot be parsed.\r
 231    */\r
 232   public void parse() throws IOException {\r
 233     String nf;\r
 234     if (newickFile == null) {\r
 235       // fill nf with complete tree file\r
 236 \r
 237       StringBuffer file = new StringBuffer();\r
 238 \r
 239       while ((nf = nextLine()) != null) {\r
 240         file.append(nf);\r
 241       }\r
 242 \r
 243       nf = file.toString();\r
 244     } else {\r
 245       nf = newickFile;\r
 246     }\r
 247 \r
 248     root = new SequenceNode();\r
 249 \r
 250     SequenceNode realroot = null;\r
 251     SequenceNode c = root;\r
 252 \r
 253     int d = -1;\r
 254     int cp = 0;\r
 255     // int flen = nf.length();\r
 256 \r
 257     String Error = null;\r
 258     String nodename = null;\r
 259 \r
 260     float DefDistance = (float) 0.001; // @param Default distance for a node -\r
 261     // very very small\r
 262     int DefBootstrap = -1; // @param Default bootstrap for a node\r
 263 \r
 264     float distance = DefDistance;\r
 265     int bootstrap = DefBootstrap;\r
 266 \r
 267     boolean ascending = false; // flag indicating that we are leaving the\r
 268     // current node\r
 269 \r
 270     Pattern majorsyms = Pattern.compile("[(\\['),;]");\r
 271 \r
 272     Matcher mjsyms = majorsyms.matcher(nf);\r
 273     char schar;\r
 274     int nextcp=0;\r
 275     int ncp = cp;\r
 276      while (mjsyms.find(cp) && (Error == null)) {\r
 277       int fcp = mjsyms.start();\r
 278 \r
 279       switch (schar = nf.charAt(fcp)) {\r
 280       case '(':\r
 281 \r
 282         // ascending should not be set\r
 283         // New Internal node\r
 284         if (ascending) {\r
 285           Error = ErrorStringrange(Error, "Unexpected '('", 7, fcp, nf);\r
 286 \r
 287           continue;\r
 288         }\r
 289 \r
 290         ;\r
 291         d++;\r
 292 \r
 293         if (c.right() == null) {\r
 294           c.setRight(new SequenceNode(null, c, null, DefDistance, DefBootstrap,\r
 295               false));\r
 296           c = (SequenceNode) c.right();\r
 297         } else {\r
 298           if (c.left() != null) {\r
 299             // Dummy node for polytomy - keeps c.left free for new node\r
 300             SequenceNode tmpn = new SequenceNode(null, c, null, 0, 0, true);\r
 301             tmpn.SetChildren(c.left(), c.right());\r
 302             c.setRight(tmpn);\r
 303           }\r
 304 \r
 305           c.setLeft(new SequenceNode(null, c, null, DefDistance, DefBootstrap,\r
 306               false));\r
 307           c = (SequenceNode) c.left();\r
 308         }\r
 309 \r
 310         if (realroot == null) {\r
 311           realroot = c;\r
 312         }\r
 313 \r
 314         nodename = null;\r
 315         distance = DefDistance;\r
 316         bootstrap = DefBootstrap;\r
 317         cp = fcp + 1;\r
 318 \r
 319         break;\r
 320 \r
 321       // Deal with quoted fields\r
 322       case '\'':\r
 323 \r
 324         Matcher qnodename = Pattern.compile("([^']|'')+'").matcher(nf);\r
 325         if (qnodename.find(fcp)) {\r
 326           nodename = new String(qnodename.group(1));\r
 327           cp = qnodename.end(0);\r
 328         } else {\r
 329           Error = ErrorStringrange(Error, "Unterminated quotes for nodename",\r
 330               7, fcp, nf);\r
 331         }\r
 332 \r
 333         break;\r
 334 \r
 335       default:\r
 336         // Reached termininating root node label.\r
 337         if (schar == ';' && d != -1) {\r
 338           Error = ErrorStringrange(Error,\r
 339               "Wayward semicolon (depth=" + d + ")", 7, fcp, nf);\r
 340         }\r
 341 \r
 342       // Skip Comment or structured/extended NH format info\r
 343         if (schar == '[') {\r
 344           if ((nextcp=nf.indexOf(']', fcp)) > -1) {\r
 345             // verified that comment is properly terminated.\r
 346             // now skip the comment field\r
 347             nextcp++;\r
 348             break; // go and search for the next node separator, leaving ncp at beginning of node info\r
 349           } else {\r
 350             Error = ErrorStringrange(Error, "Unterminated comment", 3, fcp, nf);\r
 351             nextcp = 0;\r
 352             break;\r
 353           }\r
 354         }\r
 355         \r
 356         // Parse simpler field strings from substring between ncp and node separator\r
 357         String fstring = nf.substring(ncp, fcp);\r
 358         // extract any comments from the nodeinfo.\r
 359         while (fstring.indexOf(']')>-1)\r
 360         {\r
 361           int cstart=fstring.indexOf('[');\r
 362           int cend=fstring.indexOf(']');\r
 363           String comment =  fstring.substring(cstart+1,cend); // TODO: put this somewhere ?\r
 364           fstring = fstring.substring(0, cstart)+fstring.substring(cend+1);\r
 365         }\r
 366         Matcher uqnodename = Pattern.compile("^([^' :;\\](),]+).*").matcher(\r
 367             fstring);\r
 368         if (uqnodename.matches()\r
 369             && ((uqnodename.start(1) == 0) || (fstring.charAt(uqnodename\r
 370                 .start(1) - 1) != ':'))) // JBPNote HACK!\r
 371         {\r
 372           if (nodename == null) {\r
 373             if (ReplaceUnderscores) {\r
 374               nodename = uqnodename.group(1).replace('_', ' ');\r
 375             } else {\r
 376               nodename = uqnodename.group(1);\r
 377             }\r
 378           } else {\r
 379             Error = ErrorStringrange(Error,\r
 380                 "File has broken algorithm - overwritten nodename", 10, fcp, nf);\r
 381           }\r
 382         }\r
 383 \r
 384         Matcher nbootstrap = Pattern.compile("\\s*([+0-9]+)\\s*:.*").matcher(\r
 385             fstring);\r
 386 \r
 387         if (nbootstrap.matches())\r
 388         {\r
 389           if (nodename!=null && nbootstrap.group(1).equals(nodename)) \r
 390           {\r
 391               nodename=null; // empty nodename - only bootstrap value\r
 392           }\r
 393           if ((nodename==null || nodename.length()==0) || nbootstrap.start(1)>=uqnodename.end(1))\r
 394           {\r
 395             try {\r
 396               bootstrap = (new Integer(nbootstrap.group(1))).intValue();\r
 397               HasBootstrap = true;\r
 398             } catch (Exception e) {\r
 399               Error = ErrorStringrange(Error, "Can't parse bootstrap value", 4,\r
 400                   ncp + nbootstrap.start(0), nf);\r
 401             }\r
 402           }\r
 403         }\r
 404         \r
 405         Matcher ndist = Pattern.compile(".*:([-0-9Ee.+]+)").matcher(fstring);\r
 406         boolean nodehasdistance = false;\r
 407 \r
 408         if (ndist.matches()) {\r
 409           try {\r
 410             distance = (new Float(ndist.group(1))).floatValue();\r
 411             HasDistances = true;\r
 412             nodehasdistance = true;\r
 413           } catch (Exception e) {\r
 414             Error = ErrorStringrange(Error, "Can't parse node distance value",\r
 415                 7, ncp + ndist.start(0), nf);\r
 416           }\r
 417         }\r
 418 \r
 419         if (ascending) {\r
 420           // Write node info here\r
 421           c.setName(nodename);\r
 422           // Trees without distances still need a render distance\r
 423           c.dist = (HasDistances) ? distance : DefDistance;\r
 424           // be consistent for internal bootstrap defaults too\r
 425           c.setBootstrap((HasBootstrap) ? bootstrap : DefBootstrap);\r
 426           if (c == realroot) {\r
 427             RootHasDistance = nodehasdistance; // JBPNote This is really\r
 428             // UGLY!!! Ensure root node gets\r
 429             // its given distance\r
 430           }\r
 431         } else {\r
 432           // Find a place to put the leaf\r
 433           SequenceNode newnode = new SequenceNode(null, c, nodename,\r
 434               (HasDistances) ? distance : DefDistance,\r
 435               (HasBootstrap) ? bootstrap : DefBootstrap, false);\r
 436 \r
 437           if (c.right() == null) {\r
 438             c.setRight(newnode);\r
 439           } else {\r
 440             if (c.left() == null) {\r
 441               c.setLeft(newnode);\r
 442             } else {\r
 443               // Insert a dummy node for polytomy\r
 444               // dummy nodes have distances\r
 445               SequenceNode newdummy = new SequenceNode(null, c, null,\r
 446                   (HasDistances ? 0 : DefDistance), 0, true);\r
 447               newdummy.SetChildren(c.left(), newnode);\r
 448               c.setLeft(newdummy);\r
 449             }\r
 450           }\r
 451         }\r
 452 \r
 453         if (ascending) {\r
 454           // move back up the tree from preceding closure\r
 455           c = c.AscendTree();\r
 456 \r
 457           if ((d > -1) && (c == null)) {\r
 458             Error = ErrorStringrange(\r
 459                 Error,\r
 460                 "File broke algorithm: Lost place in tree (is there an extra ')' ?)",\r
 461                 7, fcp, nf);\r
 462           }\r
 463         }\r
 464 \r
 465         if (nf.charAt(fcp) == ')') {\r
 466           d--;\r
 467           ascending = true;\r
 468         } else {\r
 469           if (nf.charAt(fcp) == ',') {\r
 470             if (ascending) {\r
 471               ascending = false;\r
 472             } else {\r
 473               // Just advance focus, if we need to\r
 474               if ((c.left() != null) && (!c.left().isLeaf())) {\r
 475                 c = (SequenceNode) c.left();\r
 476               }\r
 477             }\r
 478           }\r
 479         }\r
 480 \r
 481         // Reset new node properties to obvious fakes\r
 482         nodename = null;\r
 483         distance = DefDistance;\r
 484         bootstrap = DefBootstrap;\r
 485       }\r
 486       // Advance character pointers if necessary\r
 487       if (nextcp == 0) {\r
 488         ncp = cp = fcp + 1;\r
 489       } else {\r
 490         cp = nextcp;\r
 491         nextcp = 0;\r
 492       }\r
 493     }\r
 494 \r
 495     if (Error != null) {\r
 496       throw (new IOException("NewickFile: " + Error + "\n"));\r
 497     }\r
 498 \r
 499     root = (SequenceNode) root.right().detach(); // remove the imaginary root.\r
 500 \r
 501     if (!RootHasDistance) {\r
 502       root.dist = (HasDistances) ? 0 : DefDistance;\r
 503     }\r
 504   }\r
 505 \r
 506   /**\r
 507    * DOCUMENT ME!\r
 508    * \r
 509    * @return DOCUMENT ME!\r
 510    */\r
 511   public SequenceNode getTree() {\r
 512     return root;\r
 513   }\r
 514 \r
 515   public uk.ac.vamsas.objects.core.Treenode[] matchTreeNodeNames(\r
 516       String[] names, Vobject[] boundObjects) {\r
 517     // todo!\r
 518     // also - need to reconstruct a names object id mapping (or BInaryNode) mapping for the parsed tree file\r
 519     return null;\r
 520   }\r
 521 \r
 522   /**\r
 523    * Generate a newick format tree according to internal flags for bootstraps,\r
 524    * distances and root distances.\r
 525    * \r
 526    * @return new hampshire tree in a single line\r
 527    */\r
 528   public String print() {\r
 529     synchronized (this) {\r
 530       StringBuffer tf = new StringBuffer();\r
 531       print(tf, root);\r
 532 \r
 533       return (tf.append(";").toString());\r
 534     }\r
 535   }\r
 536 \r
 537   /**\r
 538    * \r
 539    * \r
 540    * Generate a newick format tree according to internal flags for distances and\r
 541    * root distances and user specificied writing of bootstraps.\r
 542    * \r
 543    * @param withbootstraps\r
 544    *          controls if bootstrap values are explicitly written.\r
 545    * \r
 546    * @return new hampshire tree in a single line\r
 547    */\r
 548   public String print(boolean withbootstraps) {\r
 549     synchronized (this) {\r
 550       boolean boots = this.HasBootstrap;\r
 551       this.HasBootstrap = withbootstraps;\r
 552 \r
 553       String rv = print();\r
 554       this.HasBootstrap = boots;\r
 555 \r
 556       return rv;\r
 557     }\r
 558   }\r
 559 \r
 560   /**\r
 561    * \r
 562    * Generate newick format tree according to internal flags for writing root\r
 563    * node distances.\r
 564    * \r
 565    * @param withbootstraps\r
 566    *          explicitly write bootstrap values\r
 567    * @param withdists\r
 568    *          explicitly write distances\r
 569    * \r
 570    * @return new hampshire tree in a single line\r
 571    */\r
 572   public String print(boolean withbootstraps, boolean withdists) {\r
 573     synchronized (this) {\r
 574       boolean dists = this.HasDistances;\r
 575       this.HasDistances = withdists;\r
 576 \r
 577       String rv = print(withbootstraps);\r
 578       this.HasDistances = dists;\r
 579 \r
 580       return rv;\r
 581     }\r
 582   }\r
 583 \r
 584   /**\r
 585    * Generate newick format tree according to user specified flags\r
 586    * \r
 587    * @param withbootstraps\r
 588    *          explicitly write bootstrap values\r
 589    * @param withdists\r
 590    *          explicitly write distances\r
 591    * @param printRootInfo\r
 592    *          explicitly write root distance\r
 593    * \r
 594    * @return new hampshire tree in a single line\r
 595    */\r
 596   public String print(boolean withbootstraps, boolean withdists,\r
 597       boolean printRootInfo) {\r
 598     synchronized (this) {\r
 599       boolean rootinfo = printRootInfo;\r
 600       this.printRootInfo = printRootInfo;\r
 601 \r
 602       String rv = print(withbootstraps, withdists);\r
 603       this.printRootInfo = rootinfo;\r
 604 \r
 605       return rv;\r
 606     }\r
 607   }\r
 608 \r
 609   /**\r
 610    * DOCUMENT ME!\r
 611    * \r
 612    * @return DOCUMENT ME!\r
 613    */\r
 614   char getQuoteChar() {\r
 615     return QuoteChar;\r
 616   }\r
 617 \r
 618   /**\r
 619    * DOCUMENT ME!\r
 620    * \r
 621    * @param c\r
 622    *          DOCUMENT ME!\r
 623    * \r
 624    * @return DOCUMENT ME!\r
 625    */\r
 626   char setQuoteChar(char c) {\r
 627     char old = QuoteChar;\r
 628     QuoteChar = c;\r
 629 \r
 630     return old;\r
 631   }\r
 632 \r
 633   /**\r
 634    * DOCUMENT ME!\r
 635    * \r
 636    * @param name\r
 637    *          DOCUMENT ME!\r
 638    * \r
 639    * @return DOCUMENT ME!\r
 640    */\r
 641   private String nodeName(String name) {\r
 642     if (NodeSafeName[0].matcher(name).find()) {\r
 643       return QuoteChar + NodeSafeName[1].matcher(name).replaceAll("''")\r
 644           + QuoteChar; // quite \r
 645     } else {\r
 646       return NodeSafeName[2].matcher(name).replaceAll("_"); // whitespace\r
 647     }\r
 648   }\r
 649 \r
 650   /**\r
 651    * DOCUMENT ME!\r
 652    * \r
 653    * @param c\r
 654    *          DOCUMENT ME!\r
 655    * \r
 656    * @return DOCUMENT ME!\r
 657    */\r
 658   private String printNodeField(SequenceNode c) {\r
 659     return //c.getNewickNodeName()\r
 660     ((c.getName() == null) ? "" : nodeName(c.getName()))\r
 661         + ((HasBootstrap) ? ((c.getBootstrap() > -1) ? (((c.getName()==null) ? " " : "") + c.getBootstrap())\r
 662             : "") : "") + ((HasDistances) ? (":" + c.dist) : "");\r
 663   }\r
 664 \r
 665   /**\r
 666    * DOCUMENT ME!\r
 667    * \r
 668    * @param root\r
 669    *          DOCUMENT ME!\r
 670    * \r
 671    * @return DOCUMENT ME!\r
 672    */\r
 673   private String printRootField(SequenceNode root) {\r
 674     return (printRootInfo) ? (((root.getName() == null) ? "" : nodeName(root\r
 675         .getName()))\r
 676         + ((HasBootstrap) ? ((root.getBootstrap() > -1) ? ((root.getName()!=null ? " " : "") + root\r
 677             .getBootstrap()) : "") : "") + ((RootHasDistance) ? (":" + root.dist)\r
 678         : ""))\r
 679         : "";\r
 680   }\r
 681 \r
 682   // Non recursive call deals with root node properties\r
 683   public void print(StringBuffer tf, SequenceNode root) {\r
 684     if (root != null) {\r
 685       if (root.isLeaf() && printRootInfo) {\r
 686         tf.append(printRootField(root));\r
 687       } else {\r
 688         if (root.isDummy()) {\r
 689           _print(tf, (SequenceNode) root.right());\r
 690           _print(tf, (SequenceNode) root.left());\r
 691         } else {\r
 692           tf.append("(");\r
 693           _print(tf, (SequenceNode) root.right());\r
 694 \r
 695           if (root.left() != null) {\r
 696             tf.append(",");\r
 697           }\r
 698 \r
 699           _print(tf, (SequenceNode) root.left());\r
 700           tf.append(")" + printRootField(root));\r
 701         }\r
 702       }\r
 703     }\r
 704   }\r
 705 \r
 706   // Recursive call for non-root nodes\r
 707   public void _print(StringBuffer tf, SequenceNode c) {\r
 708     if (c != null) {\r
 709       if (c.isLeaf()) {\r
 710         tf.append(printNodeField(c));\r
 711       } else {\r
 712         if (c.isDummy()) {\r
 713           _print(tf, (SequenceNode) c.left());\r
 714           if (c.left() != null) {\r
 715             tf.append(",");\r
 716           }\r
 717           _print(tf, (SequenceNode) c.right());\r
 718         } else {\r
 719           tf.append("(");\r
 720           _print(tf, (SequenceNode) c.right());\r
 721 \r
 722           if (c.left() != null) {\r
 723             tf.append(",");\r
 724           }\r
 725 \r
 726           _print(tf, (SequenceNode) c.left());\r
 727           tf.append(")" + printNodeField(c));\r
 728         }\r
 729       }\r
 730     }\r
 731   }\r
 732 \r
 733   // Test\r
 734   public static void main(String[] args) {\r
 735     try {\r
 736       if (args == null || args.length != 1) {\r
 737         System.err\r
 738             .println("Takes one argument - file name of a newick tree file.");\r
 739         System.exit(0);\r
 740       }\r
 741 \r
 742       File fn = new File(args[0]);\r
 743 \r
 744       StringBuffer newickfile = new StringBuffer();\r
 745       BufferedReader treefile = new BufferedReader(new FileReader(fn));\r
 746       String l;\r
 747 \r
 748       while ((l = treefile.readLine()) != null) {\r
 749         newickfile.append(l);\r
 750       }\r
 751 \r
 752       treefile.close();\r
 753       System.out.println("Read file :\n");\r
 754       NewickFile trf = new NewickFile(fn);\r
 755       // trf.parse();\r
 756       System.out.println("Original file :\n");\r
 757 \r
 758       System.out.println(Pattern.compile("\n+").matcher(newickfile.toString())\r
 759           .replaceAll("")\r
 760           + "\n");\r
 761 \r
 762       System.out.println("Parsed file.\n");\r
 763       System.out.println("Default output type for original input.\n");\r
 764       System.out.println(trf.print());\r
 765       System.out.println("Without bootstraps.\n");\r
 766       System.out.println(trf.print(false));\r
 767       System.out.println("Without distances.\n");\r
 768       System.out.println(trf.print(true, false));\r
 769       System.out.println("Without bootstraps but with distanecs.\n");\r
 770       System.out.println(trf.print(false, true));\r
 771       System.out.println("Without bootstraps or distanecs.\n");\r
 772       System.out.println(trf.print(false, false));\r
 773       System.out.println("With bootstraps and with distances.\n");\r
 774       System.out.println(trf.print(true, true));\r
 775       System.out.println("leaves.\n");\r
 776       Vector lvs = new Vector();\r
 777       trf.findLeaves(trf.root, lvs);\r
 778       Enumeration lv = lvs.elements();\r
 779       while (lv.hasMoreElements()) {\r
 780         BinaryNode leave = (BinaryNode) lv.nextElement();\r
 781         if (leave.getName() != null) {\r
 782           System.out.println("Node:'" + leave.getName() + "'");\r
 783         }\r
 784       }\r
 785     } catch (java.io.IOException e) {\r
 786       System.err.println("Exception\n" + e);\r
 787       e.printStackTrace();\r
 788     }\r
 789   }\r
 790 \r
 791   /**\r
 792    * Search for leaf nodes.\r
 793    *\r
 794    * @param node root node to search from\r
 795    * @param leaves Vector of leaves to add leaf node objects too.\r
 796    *\r
 797    * @return Vector of leaf nodes on binary tree\r
 798    */\r
 799   public Vector findLeaves(SequenceNode node, Vector leaves) {\r
 800     if (node == null) {\r
 801       return leaves;\r
 802     }\r
 803 \r
 804     if ((node.left() == null) && (node.right() == null)) // Interior node detection\r
 805     {\r
 806       leaves.addElement(node);\r
 807 \r
 808       return leaves;\r
 809     } else {\r
 810       /*  TODO: Identify internal nodes...    if (node.isSequenceLabel())\r
 811        {\r
 812        leaves.addElement(node);\r
 813        }*/\r
 814       findLeaves((SequenceNode) node.left(), leaves);\r
 815       findLeaves((SequenceNode) node.right(), leaves);\r
 816     }\r
 817 \r
 818     return leaves;\r
 819   }\r
 820 \r
 821   /**\r
 822    * make tree node vector from a newick tree structure with associated vamsas objects\r
 823    * @param ntree\r
 824    * @return Treenode definitions for nodes with associated objects\r
 825    */\r
 826   public Treenode[] makeTreeNodes() {\r
 827     return makeTreeNodes(true);\r
 828   }\r
 829 \r
 830   /**\r
 831    * make treenode vector for a parsed tree with/out leaf node associations \r
 832    * @param ignoreplaceholders if true means only associated nodes are returned\r
 833    * @return treenode vector for associated or all leaves\r
 834    */\r
 835   public Treenode[] makeTreeNodes(boolean ignoreplaceholders) {\r
 836     Vector leaves = new Vector();\r
 837     findLeaves(root, leaves);\r
 838     Vector tnv = new Vector();\r
 839     Enumeration l = leaves.elements();\r
 840     Hashtable nodespecs = new Hashtable();\r
 841     while (l.hasMoreElements()) {\r
 842       BinaryNode tnode = (BinaryNode) l.nextElement();\r
 843       if (tnode instanceof SequenceNode) {\r
 844         if (!(ignoreplaceholders && ((SequenceNode) tnode).isPlaceholder())) {\r
 845           Object assocseq = ((SequenceNode) tnode).element();\r
 846           if (assocseq instanceof Vobject) {\r
 847             Vobject vobj = (Vobject) assocseq;\r
 848             if (vobj != null) {\r
 849               Treenode node = new Treenode();\r
 850               node.setNodespec(makeNodeSpec(nodespecs, tnode));\r
 851               node.setName(tnode.getName());\r
 852               Vref vr = new Vref();\r
 853               vr.addRefs(vobj);\r
 854               node.addVref(vr);\r
 855               tnv.addElement(node);\r
 856             } else {\r
 857               System.err.println("WARNING: Unassociated treeNode "\r
 858                   + tnode.element().toString()\r
 859                   + " "\r
 860                   + ((tnode.getName() != null) ? " label " + tnode.getName()\r
 861                       : ""));\r
 862             }\r
 863           }\r
 864         }\r
 865       }\r
 866     }\r
 867     if (tnv.size() > 0) {\r
 868       Treenode[] tn = new Treenode[tnv.size()];\r
 869       tnv.copyInto(tn);\r
 870       return tn;\r
 871     }\r
 872     return new Treenode[] {};\r
 873   }\r
 874 \r
 875   private String makeNodeSpec(Hashtable nodespecs, BinaryNode tnode) {\r
 876     String nname = new String(tnode.getName());\r
 877     Integer nindx = (Integer) nodespecs.get(nname);\r
 878     if (nindx == null) {\r
 879       nindx = new Integer(1);\r
 880     }\r
 881     nname = nindx.toString() + " " + nname;\r
 882     return nname;\r
 883   }\r
 884 \r
 885   /**\r
 886    * call to match up Treenode specs to NJTree parsed from document object.\r
 887    * \r
 888    * @param nodespec\r
 889    * @param leaves\r
 890    *          as returned from NJTree.findLeaves( .., ..) ..\r
 891    * @return\r
 892    */\r
 893   private BinaryNode findNodeSpec(String nodespec, Vector leaves) {\r
 894     int occurence = -1;\r
 895     String nspec = nodespec.substring(nodespec.indexOf(' ') + 1);\r
 896     String oval = nodespec.substring(0, nodespec.indexOf(' '));\r
 897     try {\r
 898       occurence = new Integer(oval).intValue();\r
 899     } catch (Exception e) {\r
 900       System.err.println("Invalid nodespec '" + nodespec + "'");\r
 901       return null;\r
 902     }\r
 903     BinaryNode bn = null;\r
 904 \r
 905     int nocc = 0;\r
 906     Enumeration en = leaves.elements();\r
 907     while (en.hasMoreElements() && nocc < occurence) {\r
 908       bn = (BinaryNode) en.nextElement();\r
 909       if (bn instanceof SequenceNode && bn.getName().equals(nspec)) {\r
 910         --occurence;\r
 911       } else\r
 912         bn = null;\r
 913     }\r
 914     return bn;\r
 915   }\r
 916 \r
 917   /**\r
 918    *\r
 919    * re-decorate the newick node representation with the VorbaId of an object mapped by its corresponding TreeNode. \r
 920    * Note: this only takes the first object in the first set of references.\r
 921    * @param tn\r
 922    * @return vector of mappings { treenode, SequenceNode, Vobject for VorbaId on sequence node }\r
 923    */\r
 924   public Vector attachTreeMap(Treenode[] tn) {\r
 925     if (root != null || tn == null)\r
 926       return null;\r
 927     Vector leaves = new Vector();\r
 928     Vector nodemap = new Vector();\r
 929     findLeaves(root, leaves);\r
 930     int sz = tn.length;\r
 931     int i = 0;\r
 932 \r
 933     while (i < sz) {\r
 934       Treenode node = tn[i++];\r
 935       BinaryNode mappednode = findNodeSpec(node.getNodespec(), leaves);\r
 936       if (mappednode != null && mappednode instanceof SequenceNode) {\r
 937         SequenceNode leaf = (SequenceNode) leaves.elementAt(i++);\r
 938         // check if we can make the specified association\r
 939         Vobject noderef = null;\r
 940         int vrf = 0, refv = 0;\r
 941         while (noderef == null && vrf < node.getVrefCount()) {\r
 942           if (refv < node.getVref(vrf).getRefsCount()) {\r
 943             Object ref = node.getVref(vrf).getRefs(refv++);\r
 944             if (ref instanceof Vobject) {\r
 945               noderef = (Vobject) ref;\r
 946             }\r
 947           } else {\r
 948             refv = 0;\r
 949             vrf++;\r
 950           }\r
 951         }\r
 952         if (noderef != null) {\r
 953           nodemap.addElement(new Object[] { node, leaf, noderef });\r
 954           leaf.setElement(noderef);\r
 955           leaf.setPlaceholder(false);\r
 956         } else {\r
 957           leaf.setPlaceholder(true);\r
 958         }\r
 959       }\r
 960     }\r
 961     return nodemap;\r
 962   }\r
 963 \r
 964 }\r