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

   1 /*\r
   2  * This file is part of the Vamsas Client version 0.1. \r
   3  * Copyright 2009 by Jim Procter, Iain Milne, Pierre Marguerite, \r
   4  *  Andrew Waterhouse and Dominik Lindner.\r
   5  * \r
   6  * Earlier versions have also been incorporated into Jalview version 2.4 \r
   7  * since 2008, and TOPALi version 2 since 2007.\r
   8  * \r
   9  * The Vamsas Client is free software: you can redistribute it and/or modify\r
  10  * it under the terms of the GNU Lesser General Public License as published by\r
  11  * the Free Software Foundation, either version 3 of the License, or\r
  12  * (at your option) any later version.\r
  13  *  \r
  14  * The Vamsas Client is distributed in the hope that it will be useful,\r
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  17  * GNU Lesser General Public License for more details.\r
  18  * \r
  19  * You should have received a copy of the GNU Lesser General Public License\r
  20  * along with the Vamsas Client.  If not, see <http://www.gnu.org/licenses/>.\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 = true; // in case root has anything to preserve\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 Note:\r
 226    * this is automatically called by the constructors, so you normally wouldn't\r
 227    * 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\r
 349                    // beginning of node info\r
 350           } else {\r
 351             Error = ErrorStringrange(Error, "Unterminated comment", 3, fcp, nf);\r
 352             nextcp = 0;\r
 353             break;\r
 354           }\r
 355         }\r
 356 \r
 357         // Parse simpler field strings from substring between ncp and node\r
 358         // separator\r
 359         String fstring = nf.substring(ncp, fcp);\r
 360         // extract any comments from the nodeinfo.\r
 361         while (fstring.indexOf(']') > -1) {\r
 362           int cstart = fstring.indexOf('[');\r
 363           int cend = fstring.indexOf(']');\r
 364           String comment = fstring.substring(cstart + 1, cend); // TODO: put\r
 365                                                                 // this\r
 366                                                                 // somewhere ?\r
 367           fstring = fstring.substring(0, cstart) + fstring.substring(cend + 1);\r
 368         }\r
 369         Matcher uqnodename = Pattern.compile("^([^' :;\\](),]+).*").matcher(\r
 370             fstring);\r
 371         if (uqnodename.matches()\r
 372             && ((uqnodename.start(1) == 0) || (fstring.charAt(uqnodename\r
 373                 .start(1) - 1) != ':'))) // JBPNote HACK!\r
 374         {\r
 375           if (nodename == null) {\r
 376             if (ReplaceUnderscores) {\r
 377               nodename = uqnodename.group(1).replace('_', ' ');\r
 378             } else {\r
 379               nodename = uqnodename.group(1);\r
 380             }\r
 381           } else {\r
 382             Error = ErrorStringrange(Error,\r
 383                 "File has broken algorithm - overwritten nodename", 10, fcp, nf);\r
 384           }\r
 385         }\r
 386 \r
 387         Matcher nbootstrap = Pattern.compile("\\s*([+0-9]+)\\s*:.*").matcher(\r
 388             fstring);\r
 389 \r
 390         if (nbootstrap.matches()) {\r
 391           if (nodename != null && nbootstrap.group(1).equals(nodename)) {\r
 392             nodename = null; // empty nodename - only bootstrap value\r
 393           }\r
 394           if ((nodename == null || nodename.length() == 0)\r
 395               || nbootstrap.start(1) >= uqnodename.end(1)) {\r
 396             try {\r
 397               bootstrap = (new Integer(nbootstrap.group(1))).intValue();\r
 398               HasBootstrap = true;\r
 399             } catch (Exception e) {\r
 400               Error = ErrorStringrange(Error, "Can't parse bootstrap value", 4,\r
 401                   ncp + nbootstrap.start(0), nf);\r
 402             }\r
 403           }\r
 404         }\r
 405 \r
 406         Matcher ndist = Pattern.compile(".*:([-0-9Ee.+]+)").matcher(fstring);\r
 407         boolean nodehasdistance = false;\r
 408 \r
 409         if (ndist.matches()) {\r
 410           try {\r
 411             distance = (new Float(ndist.group(1))).floatValue();\r
 412             HasDistances = true;\r
 413             nodehasdistance = true;\r
 414           } catch (Exception e) {\r
 415             Error = ErrorStringrange(Error, "Can't parse node distance value",\r
 416                 7, ncp + ndist.start(0), nf);\r
 417           }\r
 418         }\r
 419 \r
 420         if (ascending) {\r
 421           // Write node info here\r
 422           c.setName(nodename);\r
 423           // Trees without distances still need a render distance\r
 424           c.dist = (HasDistances) ? distance : DefDistance;\r
 425           // be consistent for internal bootstrap defaults too\r
 426           c.setBootstrap((HasBootstrap) ? bootstrap : DefBootstrap);\r
 427           if (c == realroot) {\r
 428             RootHasDistance = nodehasdistance; // JBPNote This is really\r
 429             // UGLY!!! Ensure root node gets\r
 430             // its given distance\r
 431           }\r
 432         } else {\r
 433           // Find a place to put the leaf\r
 434           SequenceNode newnode = new SequenceNode(null, c, nodename,\r
 435               (HasDistances) ? distance : DefDistance,\r
 436               (HasBootstrap) ? bootstrap : DefBootstrap, false);\r
 437 \r
 438           if (c.right() == null) {\r
 439             c.setRight(newnode);\r
 440           } else {\r
 441             if (c.left() == null) {\r
 442               c.setLeft(newnode);\r
 443             } else {\r
 444               // Insert a dummy node for polytomy\r
 445               // dummy nodes have distances\r
 446               SequenceNode newdummy = new SequenceNode(null, c, null,\r
 447                   (HasDistances ? 0 : DefDistance), 0, true);\r
 448               newdummy.SetChildren(c.left(), newnode);\r
 449               c.setLeft(newdummy);\r
 450             }\r
 451           }\r
 452         }\r
 453 \r
 454         if (ascending) {\r
 455           // move back up the tree from preceding closure\r
 456           c = c.AscendTree();\r
 457 \r
 458           if ((d > -1) && (c == null)) {\r
 459             Error = ErrorStringrange(\r
 460                 Error,\r
 461                 "File broke algorithm: Lost place in tree (is there an extra ')' ?)",\r
 462                 7, fcp, nf);\r
 463           }\r
 464         }\r
 465 \r
 466         if (nf.charAt(fcp) == ')') {\r
 467           d--;\r
 468           ascending = true;\r
 469         } else {\r
 470           if (nf.charAt(fcp) == ',') {\r
 471             if (ascending) {\r
 472               ascending = false;\r
 473             } else {\r
 474               // Just advance focus, if we need to\r
 475               if ((c.left() != null) && (!c.left().isLeaf())) {\r
 476                 c = (SequenceNode) c.left();\r
 477               }\r
 478             }\r
 479           }\r
 480         }\r
 481 \r
 482         // Reset new node properties to obvious fakes\r
 483         nodename = null;\r
 484         distance = DefDistance;\r
 485         bootstrap = DefBootstrap;\r
 486       }\r
 487       // Advance character pointers if necessary\r
 488       if (nextcp == 0) {\r
 489         ncp = cp = fcp + 1;\r
 490       } else {\r
 491         cp = nextcp;\r
 492         nextcp = 0;\r
 493       }\r
 494     }\r
 495 \r
 496     if (Error != null) {\r
 497       throw (new IOException("NewickFile: " + Error + "\n"));\r
 498     }\r
 499 \r
 500     root = (SequenceNode) root.right().detach(); // remove the imaginary root.\r
 501 \r
 502     if (!RootHasDistance) {\r
 503       root.dist = (HasDistances) ? 0 : DefDistance;\r
 504     }\r
 505   }\r
 506 \r
 507   /**\r
 508    * DOCUMENT ME!\r
 509    * \r
 510    * @return DOCUMENT ME!\r
 511    */\r
 512   public SequenceNode getTree() {\r
 513     return root;\r
 514   }\r
 515 \r
 516   public uk.ac.vamsas.objects.core.Treenode[] matchTreeNodeNames(\r
 517       String[] names, Vobject[] boundObjects) {\r
 518     // todo!\r
 519     // also - need to reconstruct a names object id mapping (or BInaryNode)\r
 520     // mapping for the parsed tree file\r
 521     return null;\r
 522   }\r
 523 \r
 524   /**\r
 525    * Generate a newick format tree according to internal flags for bootstraps,\r
 526    * distances and root distances.\r
 527    * \r
 528    * @return new hampshire tree in a single line\r
 529    */\r
 530   public String print() {\r
 531     synchronized (this) {\r
 532       StringBuffer tf = new StringBuffer();\r
 533       print(tf, root);\r
 534 \r
 535       return (tf.append(";").toString());\r
 536     }\r
 537   }\r
 538 \r
 539   /**\r
 540    * \r
 541    * \r
 542    * Generate a newick format tree according to internal flags for distances and\r
 543    * root distances and user specificied writing of bootstraps.\r
 544    * \r
 545    * @param withbootstraps\r
 546    *          controls if bootstrap values are explicitly written.\r
 547    * \r
 548    * @return new hampshire tree in a single line\r
 549    */\r
 550   public String print(boolean withbootstraps) {\r
 551     synchronized (this) {\r
 552       boolean boots = this.HasBootstrap;\r
 553       this.HasBootstrap = withbootstraps;\r
 554 \r
 555       String rv = print();\r
 556       this.HasBootstrap = boots;\r
 557 \r
 558       return rv;\r
 559     }\r
 560   }\r
 561 \r
 562   /**\r
 563    * \r
 564    * Generate newick format tree according to internal flags for writing root\r
 565    * node distances.\r
 566    * \r
 567    * @param withbootstraps\r
 568    *          explicitly write bootstrap values\r
 569    * @param withdists\r
 570    *          explicitly write distances\r
 571    * \r
 572    * @return new hampshire tree in a single line\r
 573    */\r
 574   public String print(boolean withbootstraps, boolean withdists) {\r
 575     synchronized (this) {\r
 576       boolean dists = this.HasDistances;\r
 577       this.HasDistances = withdists;\r
 578 \r
 579       String rv = print(withbootstraps);\r
 580       this.HasDistances = dists;\r
 581 \r
 582       return rv;\r
 583     }\r
 584   }\r
 585 \r
 586   /**\r
 587    * Generate newick format tree according to user specified flags\r
 588    * \r
 589    * @param withbootstraps\r
 590    *          explicitly write bootstrap values\r
 591    * @param withdists\r
 592    *          explicitly write distances\r
 593    * @param printRootInfo\r
 594    *          explicitly write root distance\r
 595    * \r
 596    * @return new hampshire tree in a single line\r
 597    */\r
 598   public String print(boolean withbootstraps, boolean withdists,\r
 599       boolean printRootInfo) {\r
 600     synchronized (this) {\r
 601       boolean rootinfo = printRootInfo;\r
 602       this.printRootInfo = printRootInfo;\r
 603 \r
 604       String rv = print(withbootstraps, withdists);\r
 605       this.printRootInfo = rootinfo;\r
 606 \r
 607       return rv;\r
 608     }\r
 609   }\r
 610 \r
 611   /**\r
 612    * DOCUMENT ME!\r
 613    * \r
 614    * @return DOCUMENT ME!\r
 615    */\r
 616   char getQuoteChar() {\r
 617     return QuoteChar;\r
 618   }\r
 619 \r
 620   /**\r
 621    * DOCUMENT ME!\r
 622    * \r
 623    * @param c\r
 624    *          DOCUMENT ME!\r
 625    * \r
 626    * @return DOCUMENT ME!\r
 627    */\r
 628   char setQuoteChar(char c) {\r
 629     char old = QuoteChar;\r
 630     QuoteChar = c;\r
 631 \r
 632     return old;\r
 633   }\r
 634 \r
 635   /**\r
 636    * DOCUMENT ME!\r
 637    * \r
 638    * @param name\r
 639    *          DOCUMENT ME!\r
 640    * \r
 641    * @return DOCUMENT ME!\r
 642    */\r
 643   private String nodeName(String name) {\r
 644     if (NodeSafeName[0].matcher(name).find()) {\r
 645       return QuoteChar + NodeSafeName[1].matcher(name).replaceAll("''")\r
 646           + QuoteChar; // quite\r
 647     } else {\r
 648       return NodeSafeName[2].matcher(name).replaceAll("_"); // whitespace\r
 649     }\r
 650   }\r
 651 \r
 652   /**\r
 653    * DOCUMENT ME!\r
 654    * \r
 655    * @param c\r
 656    *          DOCUMENT ME!\r
 657    * \r
 658    * @return DOCUMENT ME!\r
 659    */\r
 660   private String printNodeField(SequenceNode c) {\r
 661     return // c.getNewickNodeName()\r
 662     ((c.getName() == null) ? "" : nodeName(c.getName()))\r
 663         + ((HasBootstrap) ? ((c.getBootstrap() > -1) ? (((c.getName() == null) ? " "\r
 664             : "") + c.getBootstrap())\r
 665             : "")\r
 666             : "") + ((HasDistances) ? (":" + c.dist) : "");\r
 667   }\r
 668 \r
 669   /**\r
 670    * DOCUMENT ME!\r
 671    * \r
 672    * @param root\r
 673    *          DOCUMENT ME!\r
 674    * \r
 675    * @return DOCUMENT ME!\r
 676    */\r
 677   private String printRootField(SequenceNode root) {\r
 678     return (printRootInfo) ? (((root.getName() == null) ? "" : nodeName(root\r
 679         .getName()))\r
 680         + ((HasBootstrap) ? ((root.getBootstrap() > -1) ? ((root.getName() != null ? " "\r
 681             : "") + root.getBootstrap())\r
 682             : "")\r
 683             : "") + ((RootHasDistance) ? (":" + root.dist) : ""))\r
 684         : "";\r
 685   }\r
 686 \r
 687   // Non recursive call deals with root node properties\r
 688   public void print(StringBuffer tf, SequenceNode root) {\r
 689     if (root != null) {\r
 690       if (root.isLeaf() && printRootInfo) {\r
 691         tf.append(printRootField(root));\r
 692       } else {\r
 693         if (root.isDummy()) {\r
 694           _print(tf, (SequenceNode) root.right());\r
 695           _print(tf, (SequenceNode) root.left());\r
 696         } else {\r
 697           tf.append("(");\r
 698           _print(tf, (SequenceNode) root.right());\r
 699 \r
 700           if (root.left() != null) {\r
 701             tf.append(",");\r
 702           }\r
 703 \r
 704           _print(tf, (SequenceNode) root.left());\r
 705           tf.append(")" + printRootField(root));\r
 706         }\r
 707       }\r
 708     }\r
 709   }\r
 710 \r
 711   // Recursive call for non-root nodes\r
 712   public void _print(StringBuffer tf, SequenceNode c) {\r
 713     if (c != null) {\r
 714       if (c.isLeaf()) {\r
 715         tf.append(printNodeField(c));\r
 716       } else {\r
 717         if (c.isDummy()) {\r
 718           _print(tf, (SequenceNode) c.left());\r
 719           if (c.left() != null) {\r
 720             tf.append(",");\r
 721           }\r
 722           _print(tf, (SequenceNode) c.right());\r
 723         } else {\r
 724           tf.append("(");\r
 725           _print(tf, (SequenceNode) c.right());\r
 726 \r
 727           if (c.left() != null) {\r
 728             tf.append(",");\r
 729           }\r
 730 \r
 731           _print(tf, (SequenceNode) c.left());\r
 732           tf.append(")" + printNodeField(c));\r
 733         }\r
 734       }\r
 735     }\r
 736   }\r
 737 \r
 738   // Test\r
 739   public static void main(String[] args) {\r
 740     try {\r
 741       if (args == null || args.length != 1) {\r
 742         System.err\r
 743             .println("Takes one argument - file name of a newick tree file.");\r
 744         System.exit(0);\r
 745       }\r
 746 \r
 747       File fn = new File(args[0]);\r
 748 \r
 749       StringBuffer newickfile = new StringBuffer();\r
 750       BufferedReader treefile = new BufferedReader(new FileReader(fn));\r
 751       String l;\r
 752 \r
 753       while ((l = treefile.readLine()) != null) {\r
 754         newickfile.append(l);\r
 755       }\r
 756 \r
 757       treefile.close();\r
 758       System.out.println("Read file :\n");\r
 759       NewickFile trf = new NewickFile(fn);\r
 760       // trf.parse();\r
 761       System.out.println("Original file :\n");\r
 762 \r
 763       System.out.println(Pattern.compile("\n+").matcher(newickfile.toString())\r
 764           .replaceAll("")\r
 765           + "\n");\r
 766 \r
 767       System.out.println("Parsed file.\n");\r
 768       System.out.println("Default output type for original input.\n");\r
 769       System.out.println(trf.print());\r
 770       System.out.println("Without bootstraps.\n");\r
 771       System.out.println(trf.print(false));\r
 772       System.out.println("Without distances.\n");\r
 773       System.out.println(trf.print(true, false));\r
 774       System.out.println("Without bootstraps but with distanecs.\n");\r
 775       System.out.println(trf.print(false, true));\r
 776       System.out.println("Without bootstraps or distanecs.\n");\r
 777       System.out.println(trf.print(false, false));\r
 778       System.out.println("With bootstraps and with distances.\n");\r
 779       System.out.println(trf.print(true, true));\r
 780       System.out.println("leaves.\n");\r
 781       Vector lvs = new Vector();\r
 782       trf.findLeaves(trf.root, lvs);\r
 783       Enumeration lv = lvs.elements();\r
 784       while (lv.hasMoreElements()) {\r
 785         BinaryNode leave = (BinaryNode) lv.nextElement();\r
 786         if (leave.getName() != null) {\r
 787           System.out.println("Node:'" + leave.getName() + "'");\r
 788         }\r
 789       }\r
 790     } catch (java.io.IOException e) {\r
 791       System.err.println("Exception\n" + e);\r
 792       e.printStackTrace();\r
 793     }\r
 794   }\r
 795 \r
 796   /**\r
 797    * Search for leaf nodes.\r
 798    * \r
 799    * @param node\r
 800    *          root node to search from\r
 801    * @param leaves\r
 802    *          Vector of leaves to add leaf node objects too.\r
 803    * \r
 804    * @return Vector of leaf nodes on binary tree\r
 805    */\r
 806   public Vector findLeaves(SequenceNode node, Vector leaves) {\r
 807     if (node == null) {\r
 808       return leaves;\r
 809     }\r
 810 \r
 811     if ((node.left() == null) && (node.right() == null)) // Interior node\r
 812                                                          // detection\r
 813     {\r
 814       leaves.addElement(node);\r
 815 \r
 816       return leaves;\r
 817     } else {\r
 818       /*\r
 819        * TODO: Identify internal nodes... if (node.isSequenceLabel()) {\r
 820        * leaves.addElement(node); }\r
 821        */\r
 822       findLeaves((SequenceNode) node.left(), leaves);\r
 823       findLeaves((SequenceNode) node.right(), leaves);\r
 824     }\r
 825 \r
 826     return leaves;\r
 827   }\r
 828 \r
 829   /**\r
 830    * make tree node vector from a newick tree structure with associated vamsas\r
 831    * objects\r
 832    * \r
 833    * @param ntree\r
 834    * @return Treenode definitions for nodes with associated objects\r
 835    */\r
 836   public Treenode[] makeTreeNodes() {\r
 837     return makeTreeNodes(true);\r
 838   }\r
 839 \r
 840   /**\r
 841    * make treenode vector for a parsed tree with/out leaf node associations\r
 842    * \r
 843    * @param ignoreplaceholders\r
 844    *          if true means only associated nodes are returned\r
 845    * @return treenode vector for associated or all leaves\r
 846    */\r
 847   public Treenode[] makeTreeNodes(boolean ignoreplaceholders) {\r
 848     Vector leaves = new Vector();\r
 849     findLeaves(root, leaves);\r
 850     Vector tnv = new Vector();\r
 851     Enumeration l = leaves.elements();\r
 852     Hashtable nodespecs = new Hashtable();\r
 853     while (l.hasMoreElements()) {\r
 854       BinaryNode tnode = (BinaryNode) l.nextElement();\r
 855       if (tnode instanceof SequenceNode) {\r
 856         if (!(ignoreplaceholders && ((SequenceNode) tnode).isPlaceholder())) {\r
 857           Object assocseq = ((SequenceNode) tnode).element();\r
 858           if (assocseq instanceof Vobject) {\r
 859             Vobject vobj = (Vobject) assocseq;\r
 860             if (vobj != null) {\r
 861               Treenode node = new Treenode();\r
 862               node.setNodespec(makeNodeSpec(nodespecs, tnode));\r
 863               node.setName(tnode.getName());\r
 864               Vref vr = new Vref();\r
 865               vr.addRefs(vobj);\r
 866               node.addVref(vr);\r
 867               tnv.addElement(node);\r
 868             } else {\r
 869               System.err.println("WARNING: Unassociated treeNode "\r
 870                   + tnode.element().toString()\r
 871                   + " "\r
 872                   + ((tnode.getName() != null) ? " label " + tnode.getName()\r
 873                       : ""));\r
 874             }\r
 875           }\r
 876         }\r
 877       }\r
 878     }\r
 879     if (tnv.size() > 0) {\r
 880       Treenode[] tn = new Treenode[tnv.size()];\r
 881       tnv.copyInto(tn);\r
 882       return tn;\r
 883     }\r
 884     return new Treenode[] {};\r
 885   }\r
 886 \r
 887   private String makeNodeSpec(Hashtable nodespecs, BinaryNode tnode) {\r
 888     String nname = new String(tnode.getName());\r
 889     Integer nindx = (Integer) nodespecs.get(nname);\r
 890     if (nindx == null) {\r
 891       nindx = new Integer(1);\r
 892     }\r
 893     nname = nindx.toString() + " " + nname;\r
 894     return nname;\r
 895   }\r
 896 \r
 897   /**\r
 898    * call to match up Treenode specs to NJTree parsed from document object.\r
 899    * \r
 900    * @param nodespec\r
 901    * @param leaves\r
 902    *          as returned from NJTree.findLeaves( .., ..) ..\r
 903    * @return\r
 904    */\r
 905   private BinaryNode findNodeSpec(String nodespec, Vector leaves) {\r
 906     int occurence = -1;\r
 907     String nspec = nodespec.substring(nodespec.indexOf(' ') + 1);\r
 908     String oval = nodespec.substring(0, nodespec.indexOf(' '));\r
 909     try {\r
 910       occurence = new Integer(oval).intValue();\r
 911     } catch (Exception e) {\r
 912       System.err.println("Invalid nodespec '" + nodespec + "'");\r
 913       return null;\r
 914     }\r
 915     BinaryNode bn = null;\r
 916 \r
 917     int nocc = 0;\r
 918     Enumeration en = leaves.elements();\r
 919     while (en.hasMoreElements() && nocc < occurence) {\r
 920       bn = (BinaryNode) en.nextElement();\r
 921       if (bn instanceof SequenceNode && bn.getName().equals(nspec)) {\r
 922         --occurence;\r
 923       } else\r
 924         bn = null;\r
 925     }\r
 926     return bn;\r
 927   }\r
 928 \r
 929   /**\r
 930    * \r
 931    * re-decorate the newick node representation with the VorbaId of an object\r
 932    * mapped by its corresponding TreeNode. Note: this only takes the first\r
 933    * object in the first set of references.\r
 934    * \r
 935    * @param tn\r
 936    * @return vector of mappings { treenode, SequenceNode, Vobject for VorbaId on\r
 937    *         sequence node }\r
 938    */\r
 939   public Vector attachTreeMap(Treenode[] tn) {\r
 940     if (root != null || tn == null)\r
 941       return null;\r
 942     Vector leaves = new Vector();\r
 943     Vector nodemap = new Vector();\r
 944     findLeaves(root, leaves);\r
 945     int sz = tn.length;\r
 946     int i = 0;\r
 947 \r
 948     while (i < sz) {\r
 949       Treenode node = tn[i++];\r
 950       BinaryNode mappednode = findNodeSpec(node.getNodespec(), leaves);\r
 951       if (mappednode != null && mappednode instanceof SequenceNode) {\r
 952         SequenceNode leaf = (SequenceNode) leaves.elementAt(i++);\r
 953         // check if we can make the specified association\r
 954         Vobject noderef = null;\r
 955         int vrf = 0, refv = 0;\r
 956         while (noderef == null && vrf < node.getVrefCount()) {\r
 957           if (refv < node.getVref(vrf).getRefsCount()) {\r
 958             Object ref = node.getVref(vrf).getRefs(refv++);\r
 959             if (ref instanceof Vobject) {\r
 960               noderef = (Vobject) ref;\r
 961             }\r
 962           } else {\r
 963             refv = 0;\r
 964             vrf++;\r
 965           }\r
 966         }\r
 967         if (noderef != null) {\r
 968           nodemap.addElement(new Object[] { node, leaf, noderef });\r
 969           leaf.setElement(noderef);\r
 970           leaf.setPlaceholder(false);\r
 971         } else {\r
 972           leaf.setPlaceholder(true);\r
 973         }\r
 974       }\r
 975     }\r
 976     return nodemap;\r
 977   }\r
 978 \r
 979 }\r