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

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