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