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