2 * Jalview - A Sequence Alignment Editor and Viewer
\r
3 * Copyright (C) 2007 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle
\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
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
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
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
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
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
45 * @version $Revision: 1.12 $
\r
47 public class NewickFile {
\r
48 public class BinaryNode {
\r
59 /** DOCUMENT ME!! */
\r
60 public int bootstrap;
\r
63 * Creates a new BinaryNode object.
\r
65 public BinaryNode() {
\r
66 left = right = parent = null;
\r
71 * Creates a new BinaryNode object.
\r
80 public BinaryNode(VorbaId element, BinaryNode parent, String name) {
\r
81 this.element = element;
\r
82 this.parent = parent;
\r
85 left = right = null;
\r
91 * @return DOCUMENT ME!
\r
93 public VorbaId element() {
\r
103 * @return DOCUMENT ME!
\r
105 public VorbaId setElement(VorbaId v) {
\r
106 return element = v;
\r
112 * @return DOCUMENT ME!
\r
114 public BinaryNode left() {
\r
124 * @return DOCUMENT ME!
\r
126 public BinaryNode setLeft(BinaryNode n) {
\r
133 * @return DOCUMENT ME!
\r
135 public BinaryNode right() {
\r
145 * @return DOCUMENT ME!
\r
147 public BinaryNode setRight(BinaryNode n) {
\r
154 * @return DOCUMENT ME!
\r
156 public BinaryNode parent() {
\r
166 * @return DOCUMENT ME!
\r
168 public BinaryNode setParent(BinaryNode n) {
\r
175 * @return DOCUMENT ME!
\r
177 public boolean isLeaf() {
\r
178 return (left == null) && (right == null);
\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
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
195 if (rightchild != null) {
\r
196 this.setRight(rightchild);
\r
197 rightchild.detach();
\r
198 rightchild.setParent(this);
\r
203 * Detaches the node from the binary tree, along with all its child nodes.
\r
205 * @return BinaryNode The detached node.
\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
212 if (this.parent.right == this) {
\r
213 this.parent.right = null;
\r
218 this.parent = null;
\r
224 * Traverses up through the tree until a node with a free leftchild is
\r
227 * @return BinaryNode
\r
229 public BinaryNode ascendLeft() {
\r
230 BinaryNode c = this;
\r
234 } while ((c != null) && (c.left() != null) && !c.left().isLeaf());
\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
244 * @return BinaryNode
\r
246 public BinaryNode ascendRight() {
\r
247 BinaryNode c = this;
\r
251 } while ((c != null) && (c.right() != null) && !c.right().isLeaf());
\r
262 public void setName(String name) {
\r
269 * @return DOCUMENT ME!
\r
271 public String getName() {
\r
281 public void setBootstrap(int boot) {
\r
282 this.bootstrap = boot;
\r
288 * @return DOCUMENT ME!
\r
290 public int getBootstrap() {
\r
295 * @return unquoted string of form VorbaId|v|node name string
\r
297 public String getNewickNodeName() {
\r
298 if (element!=null || name!=null)
\r
300 return ((element!=null) ? element.getId()+"|v|" : "")
\r
301 + ((name == null) ? "" : name);
\r
305 public boolean parseNodeNameString(uk.ac.vamsas.client.ClientDocument binder)
\r
308 if (element==null && name!=null && name.indexOf("|v|")>-1)
\r
310 element = binder.getObject(null).getVorbaId(); // TODO: fix THIS ! name.substring(0, name.indexOf("|v")));
\r
317 public class SequenceNode extends BinaryNode {
\r
318 /** DOCUMENT ME!! */
\r
321 /** DOCUMENT ME!! */
\r
322 public boolean dummy = false;
\r
324 private boolean placeholder = false;
\r
327 * Creates a new SequenceNode object.
\r
329 public SequenceNode() {
\r
334 * Creates a new SequenceNode object.
\r
345 public SequenceNode(VorbaId val, SequenceNode parent, float dist, String name) {
\r
346 super(val, parent, name);
\r
349 public SequenceNode(Vobject val, SequenceNode parent, float dist, String name) {
\r
350 super(val.getVorbaId(), parent, name);
\r
355 * Creates a new SequenceNode object.
\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
374 this.bootstrap = bootstrap;
\r
375 this.dummy = dummy;
\r
380 * true if node is created for the representation of polytomous
\r
383 public boolean isDummy() {
\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
391 public boolean isPlaceholder() {
\r
392 return placeholder;
\r
401 * @return DOCUMENT ME!
\r
403 public boolean setDummy(boolean newstate) {
\r
404 boolean oldstate = dummy;
\r
413 * @param Placeholder
\r
416 public void setPlaceholder(boolean Placeholder) {
\r
417 this.placeholder = Placeholder;
\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
425 public SequenceNode AscendTree() {
\r
426 SequenceNode c = this;
\r
429 c = (SequenceNode) c.parent();
\r
430 } while ((c != null) && c.dummy);
\r
439 private boolean HasBootstrap = false;
\r
441 private boolean HasDistances = false;
\r
443 private boolean RootHasDistance = false;
\r
446 boolean ReplaceUnderscores = false;
\r
448 boolean printRootInfo = false;
\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
456 char QuoteChar = '\'';
\r
458 String newickFile = null;
\r
461 * Creates a new NewickFile object.
\r
466 * @throws IOException
\r
469 public NewickFile(String inStr) throws IOException {
\r
470 newickFile = inStr;
\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
479 * Creates a new NewickFile object.
\r
484 public NewickFile(SequenceNode newtree) {
\r
489 * Creates a new NewickFile object.
\r
496 public NewickFile(SequenceNode newtree, boolean bootstrap) {
\r
497 HasBootstrap = bootstrap;
\r
502 * Creates a new NewickFile object.
\r
511 public NewickFile(SequenceNode newtree, boolean bootstrap, boolean distances) {
\r
513 HasBootstrap = bootstrap;
\r
514 HasDistances = distances;
\r
518 * Creates a new NewickFile object.
\r
526 * @param rootdistance
\r
529 public NewickFile(SequenceNode newtree, boolean bootstrap, boolean distances,
\r
530 boolean rootdistance) {
\r
532 HasBootstrap = bootstrap;
\r
533 HasDistances = distances;
\r
534 RootHasDistance = rootdistance;
\r
543 * Message qualifier (ie the incorrect data)
\r
545 * range of characters either side to dump
\r
547 * character position
\r
549 * newick string being parsed
\r
551 * @return composed error message
\r
553 private String ErrorStringrange(String Error, String Er, int r, int p,
\r
555 return ((Error == null) ? "" : Error)
\r
560 + s.substring(((p - r) < 0) ? 0 : (p - r), ((p + r) > s.length()) ? s
\r
561 .length() : (p + r)) + " )\n";
\r
566 * @return true if tree has bootstrap values
\r
568 public boolean HasBootstrap() {
\r
569 return HasBootstrap;
\r
574 * @return true if tree has distances on branches
\r
576 public boolean HasDistances() {
\r
577 return HasDistances;
\r
582 * @return true if root has a stem distance
\r
584 public boolean HasRootDistance() {
\r
585 return RootHasDistance;
\r
588 * hacked out of jalview code
\r
591 String errormessage;
\r
592 java.io.BufferedReader dataIn=null;
\r
593 public String nextLine() throws IOException {
\r
596 dataIn = new BufferedReader(new StringReader(newickFile));
\r
600 throw new IOException("IMPLEMENTATION ERROR: NewickFile has not been initialised for reading a newick string.");
\r
602 return dataIn.readLine();
\r
603 throw new IOException("Invalid Source Stream:" + errormessage);
\r
606 * call this to convert the newick string into a binary node linked tree
\r
608 * @throws IOException
\r
609 * if the newick string cannot be parsed.
\r
611 public void parse() throws IOException {
\r
613 if (newickFile==null)
\r
615 // fill nf with complete tree file
\r
617 StringBuffer file = new StringBuffer();
\r
619 while ((nf = nextLine()) != null) {
\r
623 nf = file.toString();
\r
630 root = new SequenceNode();
\r
632 SequenceNode realroot = null;
\r
633 SequenceNode c = root;
\r
637 // int flen = nf.length();
\r
639 String Error = null;
\r
640 String nodename = null;
\r
642 float DefDistance = (float) 0.001; // @param Default distance for a node -
\r
644 int DefBootstrap = 0; // @param Default bootstrap for a node
\r
646 float distance = DefDistance;
\r
647 int bootstrap = DefBootstrap;
\r
649 boolean ascending = false; // flag indicating that we are leaving the
\r
652 Pattern majorsyms = Pattern.compile(
\r
655 Matcher mjsyms = majorsyms.matcher(nf);
\r
656 while (mjsyms.find(cp) && (Error == null)) {
\r
657 int fcp = mjsyms.start();
\r
659 switch (nf.charAt(fcp)) {
\r
660 case '[': // Comment or structured/extended NH format info
\r
663 if (nf.indexOf(']',fcp)>-1) {
\r
664 // Skip the comment field
\r
665 cp = nf.indexOf(']',fcp);
\r
667 Error = ErrorStringrange(Error, "Unterminated comment", 3, fcp, nf);
\r
676 // ascending should not be set
\r
677 // New Internal node
\r
679 Error = ErrorStringrange(Error, "Unexpected '('", 7, fcp, nf);
\r
687 if (c.right() == null) {
\r
688 c.setRight(new SequenceNode(null, c, null, DefDistance, DefBootstrap,
\r
690 c = (SequenceNode) c.right();
\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
699 c.setLeft(new SequenceNode(null, c, null, DefDistance, DefBootstrap,
\r
701 c = (SequenceNode) c.left();
\r
704 if (realroot == null) {
\r
709 distance = DefDistance;
\r
710 bootstrap = DefBootstrap;
\r
715 // Deal with quoted fields
\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
723 Error = ErrorStringrange(Error, "Unterminated quotes for nodename",
\r
732 Error = ErrorStringrange(Error,
\r
733 "Wayward semicolon (depth=" + d + ")", 7, fcp, nf);
\r
736 // cp advanced at the end of default
\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
746 if (nodename == null) {
\r
747 if (ReplaceUnderscores) {
\r
748 nodename = uqnodename.group(1).replace('_', ' ');
\r
750 nodename = uqnodename.group(1);
\r
753 Error = ErrorStringrange(Error,
\r
754 "File has broken algorithm - overwritten nodename", 10, fcp, nf);
\r
758 Matcher nbootstrap = Pattern.compile("\\S+([0-9+]+)\\S*:").matcher(fstring);
\r
761 if (nbootstrap.matches()
\r
762 && (nbootstrap.start(1) > uqnodename.end(1))) {
\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
772 Matcher ndist = Pattern.compile(
\r
773 ":([-0-9Ee.+]+)").matcher(fstring);
\r
774 boolean nodehasdistance = false;
\r
776 if (ndist.matches()) {
\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
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
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
805 if (c.right() == null) {
\r
806 c.setRight(newnode);
\r
808 if (c.left() == null) {
\r
809 c.setLeft(newnode);
\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
822 // move back up the tree from preceding closure
\r
823 c = c.AscendTree();
\r
825 if ((d > -1) && (c == null)) {
\r
826 Error = ErrorStringrange(
\r
828 "File broke algorithm: Lost place in tree (is there an extra ')' ?)",
\r
833 if (nf.charAt(fcp) == ')') {
\r
837 if (nf.charAt(fcp) == ',') {
\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
848 // else : We do nothing if ';' is encountered.
\r
851 // Reset new node properties to obvious fakes
\r
853 distance = DefDistance;
\r
854 bootstrap = DefBootstrap;
\r
860 if (Error != null) {
\r
861 throw (new IOException("NewickFile: " + Error + "\n"));
\r
864 root = (SequenceNode) root.right().detach(); // remove the imaginary root.
\r
866 if (!RootHasDistance) {
\r
867 root.dist = (HasDistances) ? 0 : DefDistance;
\r
874 * @return DOCUMENT ME!
\r
876 public SequenceNode getTree() {
\r
879 public uk.ac.vamsas.objects.core.Treenode[] matchTreeNodeNames(String[] names, Vobject[] boundObjects)
\r
882 // also - need to reconstruct a names object id mapping (or BInaryNode) mapping for the parsed tree file
\r
886 * Generate a newick format tree according to internal flags for bootstraps,
\r
887 * distances and root distances.
\r
889 * @return new hampshire tree in a single line
\r
891 public String print() {
\r
892 synchronized (this) {
\r
893 StringBuffer tf = new StringBuffer();
\r
896 return (tf.append(";").toString());
\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
906 * @param withbootstraps
\r
907 * controls if bootstrap values are explicitly written.
\r
909 * @return new hampshire tree in a single line
\r
911 public String print(boolean withbootstraps) {
\r
912 synchronized (this) {
\r
913 boolean boots = this.HasBootstrap;
\r
914 this.HasBootstrap = withbootstraps;
\r
916 String rv = print();
\r
917 this.HasBootstrap = boots;
\r
925 * Generate newick format tree according to internal flags for writing root
\r
928 * @param withbootstraps
\r
929 * explicitly write bootstrap values
\r
931 * explicitly write distances
\r
933 * @return new hampshire tree in a single line
\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
940 String rv = print(withbootstraps);
\r
941 this.HasDistances = dists;
\r
948 * Generate newick format tree according to user specified flags
\r
950 * @param withbootstraps
\r
951 * explicitly write bootstrap values
\r
953 * explicitly write distances
\r
954 * @param printRootInfo
\r
955 * explicitly write root distance
\r
957 * @return new hampshire tree in a single line
\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
965 String rv = print(withbootstraps, withdists);
\r
966 this.printRootInfo = rootinfo;
\r
975 * @return DOCUMENT ME!
\r
977 char getQuoteChar() {
\r
987 * @return DOCUMENT ME!
\r
989 char setQuoteChar(char c) {
\r
990 char old = QuoteChar;
\r
1002 * @return DOCUMENT ME!
\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
1008 return NodeSafeName[2].matcher(name).replaceAll("_"); // whitespace
\r
1018 * @return DOCUMENT ME!
\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
1032 * @return DOCUMENT ME!
\r
1034 private String printRootField(SequenceNode root) {
\r
1035 return (printRootInfo) ? (((root.getName() == null) ? "" : nodeName(root
\r
1037 + ((HasBootstrap) ? ((root.getBootstrap() > -1) ? (" " + root
\r
1038 .getBootstrap()) : "") : "") + ((RootHasDistance) ? (":" + root.dist)
\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
1049 if (root.isDummy()) {
\r
1050 _print(tf, (SequenceNode) root.right());
\r
1051 _print(tf, (SequenceNode) root.left());
\r
1054 _print(tf, (SequenceNode) root.right());
\r
1056 if (root.left() != null) {
\r
1060 _print(tf, (SequenceNode) root.left());
\r
1061 tf.append(")" + printRootField(root));
\r
1067 // Recursive call for non-root nodes
\r
1068 public void _print(StringBuffer tf, SequenceNode c) {
\r
1071 tf.append(printNodeField(c));
\r
1073 if (c.isDummy()) {
\r
1074 _print(tf, (SequenceNode) c.left());
\r
1075 if (c.left() != null) {
\r
1078 _print(tf, (SequenceNode) c.right());
\r
1081 _print(tf, (SequenceNode) c.right());
\r
1083 if (c.left() != null) {
\r
1087 _print(tf, (SequenceNode) c.left());
\r
1088 tf.append(")" + printNodeField(c));
\r
1095 public static void main(String[] args) {
\r
1097 if (args == null || args.length != 1) {
\r
1099 .println("Takes one argument - file name of a newick tree file.");
\r
1103 File fn = new File(args[0]);
\r
1105 StringBuffer newickfile = new StringBuffer();
\r
1106 BufferedReader treefile = new BufferedReader(new FileReader(fn));
\r
1109 while ((l = treefile.readLine()) != null) {
\r
1110 newickfile.append(l);
\r
1114 System.out.println("Read file :\n");
\r
1115 NewickFile trf = new NewickFile(fn);
\r
1117 System.out.println("Original file :\n");
\r
1119 System.out.println(Pattern.compile("\n+").matcher(newickfile.toString()).replaceAll("") + "\n");
\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
1140 * Search for leaf nodes.
\r
1142 * @param node root node to search from
\r
1143 * @param leaves Vector of leaves to add leaf node objects too.
\r
1145 * @return Vector of leaf nodes on binary tree
\r
1147 public Vector findLeaves(SequenceNode node, Vector leaves)
\r
1154 if ( (node.left() == null) && (node.right() == null)) // Interior node detection
\r
1156 leaves.addElement(node);
\r
1162 /* TODO: Identify internal nodes... if (node.isSequenceLabel())
\r
1164 leaves.addElement(node);
\r
1166 findLeaves( (SequenceNode) node.left(), leaves);
\r
1167 findLeaves( (SequenceNode) node.right(), leaves);
\r
1174 * make tree node vector from a newick tree structure with associated vamsas objects
\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
1184 Hashtable nodespecs = new Hashtable();
\r
1185 while (l.hasMoreElements())
\r
1187 BinaryNode tnode = (BinaryNode) l.nextElement();
\r
1188 if (tnode instanceof SequenceNode)
\r
1190 if (!((SequenceNode) tnode).isPlaceholder())
\r
1192 Object assocseq = ((SequenceNode) tnode).element();
\r
1193 if (assocseq instanceof Vobject)
\r
1195 Vobject vobj = (Vobject) assocseq;
\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
1204 tnv.addElement(node);
\r
1208 System.err.println("WARNING: Unassociated treeNode "+tnode.element().toString()+" "
\r
1209 +((tnode.getName()!=null) ? " label "+tnode.getName() : ""));
\r
1217 Treenode[] tn = new Treenode[tnv.size()];
\r
1218 tnv.copyInto(tn);
\r
1221 return new Treenode[] {};
\r
1223 private String makeNodeSpec(Hashtable nodespecs, BinaryNode tnode)
\r
1225 String nname = new String(tnode.getName());
\r
1226 Integer nindx = (Integer) nodespecs.get(nname);
\r
1229 nindx = new Integer(1);
\r
1231 nname = nindx.toString()+" "+nname;
\r
1235 * call to match up Treenode specs to NJTree parsed from document object.
\r
1239 * as returned from NJTree.findLeaves( .., ..) ..
\r
1242 private BinaryNode findNodeSpec(String nodespec, Vector leaves)
\r
1245 String nspec = nodespec.substring(nodespec.indexOf(' ')+1);
\r
1246 String oval = nodespec.substring(0, nodespec.indexOf(' '));
\r
1248 occurence = new Integer(oval).intValue();
\r
1250 catch (Exception e)
\r
1252 System.err.println("Invalid nodespec '"+nodespec+"'");
\r
1255 BinaryNode bn = null;
\r
1258 Enumeration en = leaves.elements();
\r
1259 while (en.hasMoreElements() && nocc<occurence)
\r
1261 bn = (BinaryNode) en.nextElement();
\r
1262 if (bn instanceof SequenceNode && bn.getName().equals(nspec))
\r