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