ensure lastSeq is refreshed if new feature added
[jalview.git] / src / jalview / analysis / NJTree.java
1 /*
2 * Jalview - A Sequence Alignment Editor and Viewer
3 * Copyright (C) 2006 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License
7 * as published by the Free Software Foundation; either version 2
8 * of the License, or (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
18 */
19 package jalview.analysis;
20
21 import jalview.datamodel.*;
22
23 import jalview.io.NewickFile;
24
25 import jalview.schemes.ResidueProperties;
26 import jalview.schemes.ScoreMatrix;
27
28 import jalview.util.*;
29
30 import java.util.*;
31
32
33 /**
34  * DOCUMENT ME!
35  *
36  * @author $author$
37  * @version $Revision$
38  */
39 public class NJTree
40 {
41     Vector cluster;
42     SequenceI[] sequence;
43
44     //SequenceData is a string representation of what the user
45     //sees. The display may contain hidden columns.
46     public AlignmentView seqData=null;
47
48     int[] done;
49     int noseqs;
50     int noClus;
51     float[][] distance;
52     int mini;
53     int minj;
54     float ri;
55     float rj;
56     Vector groups = new Vector();
57     SequenceNode maxdist;
58     SequenceNode top;
59     float maxDistValue;
60     float maxheight;
61     int ycount;
62     Vector node;
63     String type;
64     String pwtype;
65     Object found = null;
66     Object leaves = null;
67
68     boolean hasDistances = true; // normal case for jalview trees
69     boolean hasBootstrap = false; // normal case for jalview trees
70
71     private boolean hasRootDistance = true;
72
73     /**
74      * Create a new NJTree object with leaves associated with sequences in seqs,
75      * and original alignment data represented by Cigar strings.
76      * @param seqs SequenceI[]
77      * @param odata Cigar[]
78      * @param treefile NewickFile
79      */
80     public NJTree(SequenceI[] seqs, AlignmentView odata, NewickFile treefile) {
81       this(seqs, treefile);
82       if (odata!=null)
83         seqData = odata;
84       /*
85       sequenceString = new String[odata.length];
86       char gapChar = jalview.util.Comparison.GapChars.charAt(0);
87       for (int i = 0; i < odata.length; i++)
88       {
89         SequenceI oseq_aligned = odata[i].getSeq(gapChar);
90           sequenceString[i] = oseq_aligned.getSequence();
91       } */
92     }
93
94     /**
95      * Creates a new NJTree object from a tree from an external source
96      *
97      * @param seqs SequenceI which should be associated with leafs of treefile
98      * @param treefile A parsed tree
99      */
100     public NJTree(SequenceI[] seqs,  NewickFile treefile)
101     {
102         this.sequence = seqs;
103         top = treefile.getTree();
104
105         /**
106          * There is no dependent alignment to be recovered from an
107          * imported tree.
108          *
109         if (sequenceString == null)
110         {
111           sequenceString = new String[seqs.length];
112           for (int i = 0; i < seqs.length; i++)
113           {
114             sequenceString[i] = seqs[i].getSequence();
115           }
116         }
117         */
118
119         hasDistances = treefile.HasDistances();
120         hasBootstrap = treefile.HasBootstrap();
121         hasRootDistance = treefile.HasRootDistance();
122
123         maxheight = findHeight(top);
124
125         SequenceIdMatcher algnIds = new SequenceIdMatcher(seqs);
126
127         Vector leaves = new Vector();
128         findLeaves(top, leaves);
129
130         int i = 0;
131         int namesleft = seqs.length;
132
133         SequenceNode j;
134         SequenceI nam;
135         String realnam;
136         Vector one2many=new Vector();
137         int countOne2Many=0;
138         while (i < leaves.size())
139         {
140             j = (SequenceNode) leaves.elementAt(i++);
141             realnam = j.getName();
142             nam = null;
143
144             if (namesleft > -1)
145             {
146                 nam = algnIds.findIdMatch(realnam);
147             }
148
149             if (nam != null)
150             {
151                 j.setElement(nam);
152                 if (one2many.contains(nam)) {
153                   countOne2Many++;
154                 //  if (jalview.bin.Cache.log.isDebugEnabled())
155                 //    jalview.bin.Cache.log.debug("One 2 many relationship for "+nam.getName());
156                 } else {
157                   one2many.addElement(nam);
158                   namesleft--;
159                 }
160             }
161             else
162             {
163                 j.setElement(new Sequence(realnam, "THISISAPLACEHLDER"));
164                 j.setPlaceholder(true);
165             }
166         }
167       //  if (jalview.bin.Cache.log.isDebugEnabled() && countOne2Many>0) {
168       //    jalview.bin.Cache.log.debug("There were "+countOne2Many+" alignment sequence ids (out of "+one2many.size()+" unique ids) linked to two or more leaves.");
169       //  }
170       //  one2many.clear();
171     }
172
173     /**
174      * Creates a new NJTree object.
175      *
176      * @param sequence DOCUMENT ME!
177      * @param type DOCUMENT ME!
178      * @param pwtype DOCUMENT ME!
179      * @param start DOCUMENT ME!
180      * @param end DOCUMENT ME!
181      */
182     public NJTree(SequenceI[] sequence,
183                   AlignmentView seqData,
184                   String type,
185                   String pwtype,
186                   int start, int end)
187     {
188         this.sequence = sequence;
189         this.node = new Vector();
190         this.type = type;
191         this.pwtype = pwtype;
192         if (seqData!=null) {
193           this.seqData = seqData;
194         } else {
195           SeqCigar[] seqs = new SeqCigar[sequence.length];
196           for(int i=0; i<sequence.length; i++)
197             {
198               seqs[i] = new SeqCigar(sequence[i], start, end);
199             }
200             CigarArray sdata = new CigarArray(seqs);
201             sdata.addOperation(CigarArray.M, end-start+1);
202             this.seqData = new AlignmentView(sdata, start);
203         }
204
205         if (!(type.equals("NJ")))
206         {
207             type = "AV";
208         }
209
210         if (!(pwtype.equals("PID")))
211         {
212           if (ResidueProperties.getScoreMatrix(pwtype)==null) {
213             type = "BLOSUM62";
214           }
215         }
216
217         int i = 0;
218
219         done = new int[sequence.length];
220
221         while ((i < sequence.length) && (sequence[i] != null))
222         {
223             done[i] = 0;
224             i++;
225         }
226
227         noseqs = i++;
228
229         distance = findDistances(this.seqData.getSequenceStrings(Comparison.GapChars.charAt(0)));
230
231         makeLeaves();
232
233         noClus = cluster.size();
234
235         cluster();
236     }
237
238     /**
239      * DOCUMENT ME!
240      *
241      * @return DOCUMENT ME!
242      */
243     public String toString()
244     {
245         jalview.io.NewickFile fout = new jalview.io.NewickFile(getTopNode());
246
247         return fout.print(false, true); // distances only
248     }
249
250     /**
251      *
252      * used when the alignment associated to a tree has changed.
253      *
254      * @param alignment Vector
255      */
256     public void UpdatePlaceHolders(Vector alignment)
257     {
258         Vector leaves = new Vector();
259         findLeaves(top, leaves);
260
261         int sz = leaves.size();
262         SequenceIdMatcher seqmatcher = null;
263         int i = 0;
264
265         while (i < sz)
266         {
267             SequenceNode leaf = (SequenceNode) leaves.elementAt(i++);
268
269             if (alignment.contains(leaf.element()))
270             {
271                 leaf.setPlaceholder(false);
272             }
273             else
274             {
275                 if (seqmatcher == null)
276                 {
277                     // Only create this the first time we need it
278                     SequenceI[] seqs = new SequenceI[alignment.size()];
279
280                     for (int j = 0; j < seqs.length; j++)
281                         seqs[j] = (SequenceI) alignment.elementAt(j);
282
283                     seqmatcher = new SequenceIdMatcher(seqs);
284                 }
285
286                 SequenceI nam = seqmatcher.findIdMatch(leaf.getName());
287
288                 if (nam != null)
289                 {
290                     if (!leaf.isPlaceholder()) {
291                       // remapping the node to a new sequenceI - should remove any refs to old one.
292                       // TODO - make many sequenceI to one leaf mappings possible! (JBPNote)
293                     }
294                     leaf.setPlaceholder(false);
295                     leaf.setElement(nam);
296                 }
297                 else
298                 {
299                     if (!leaf.isPlaceholder()) {
300                         // Construct a new placeholder sequence object for this leaf
301                         leaf.setElement(new Sequence(leaf.getName(), "THISISAPLACEHLDER"));
302                     }
303                     leaf.setPlaceholder(true);
304                     
305                 }
306             }
307         }
308     }
309
310     /**
311      * DOCUMENT ME!
312      */
313     public void cluster()
314     {
315         while (noClus > 2)
316         {
317             if (type.equals("NJ"))
318             {
319                 findMinNJDistance();
320             }
321             else
322             {
323                 findMinDistance();
324             }
325
326             Cluster c = joinClusters(mini, minj);
327
328             done[minj] = 1;
329
330             cluster.setElementAt(null, minj);
331             cluster.setElementAt(c, mini);
332
333             noClus--;
334         }
335
336         boolean onefound = false;
337
338         int one = -1;
339         int two = -1;
340
341         for (int i = 0; i < noseqs; i++)
342         {
343             if (done[i] != 1)
344             {
345                 if (onefound == false)
346                 {
347                     two = i;
348                     onefound = true;
349                 }
350                 else
351                 {
352                     one = i;
353                 }
354             }
355         }
356
357         joinClusters(one, two);
358         top = (SequenceNode) (node.elementAt(one));
359
360         reCount(top);
361         findHeight(top);
362         findMaxDist(top);
363     }
364
365     /**
366      * DOCUMENT ME!
367      *
368      * @param i DOCUMENT ME!
369      * @param j DOCUMENT ME!
370      *
371      * @return DOCUMENT ME!
372      */
373     public Cluster joinClusters(int i, int j)
374     {
375         float dist = distance[i][j];
376
377         int noi = ((Cluster) cluster.elementAt(i)).value.length;
378         int noj = ((Cluster) cluster.elementAt(j)).value.length;
379
380         int[] value = new int[noi + noj];
381
382         for (int ii = 0; ii < noi; ii++)
383         {
384             value[ii] = ((Cluster) cluster.elementAt(i)).value[ii];
385         }
386
387         for (int ii = noi; ii < (noi + noj); ii++)
388         {
389             value[ii] = ((Cluster) cluster.elementAt(j)).value[ii - noi];
390         }
391
392         Cluster c = new Cluster(value);
393
394         ri = findr(i, j);
395         rj = findr(j, i);
396
397         if (type.equals("NJ"))
398         {
399             findClusterNJDistance(i, j);
400         }
401         else
402         {
403             findClusterDistance(i, j);
404         }
405
406         SequenceNode sn = new SequenceNode();
407
408         sn.setLeft((SequenceNode) (node.elementAt(i)));
409         sn.setRight((SequenceNode) (node.elementAt(j)));
410
411         SequenceNode tmpi = (SequenceNode) (node.elementAt(i));
412         SequenceNode tmpj = (SequenceNode) (node.elementAt(j));
413
414         if (type.equals("NJ"))
415         {
416             findNewNJDistances(tmpi, tmpj, dist);
417         }
418         else
419         {
420             findNewDistances(tmpi, tmpj, dist);
421         }
422
423         tmpi.setParent(sn);
424         tmpj.setParent(sn);
425
426         node.setElementAt(sn, i);
427
428         return c;
429     }
430
431     /**
432      * DOCUMENT ME!
433      *
434      * @param tmpi DOCUMENT ME!
435      * @param tmpj DOCUMENT ME!
436      * @param dist DOCUMENT ME!
437      */
438     public void findNewNJDistances(SequenceNode tmpi, SequenceNode tmpj,
439         float dist)
440     {
441
442         tmpi.dist = ((dist + ri) - rj) / 2;
443         tmpj.dist = (dist - tmpi.dist);
444
445         if (tmpi.dist < 0)
446         {
447             tmpi.dist = 0;
448         }
449
450         if (tmpj.dist < 0)
451         {
452             tmpj.dist = 0;
453         }
454     }
455
456     /**
457      * DOCUMENT ME!
458      *
459      * @param tmpi DOCUMENT ME!
460      * @param tmpj DOCUMENT ME!
461      * @param dist DOCUMENT ME!
462      */
463     public void findNewDistances(SequenceNode tmpi, SequenceNode tmpj,
464         float dist)
465     {
466         float ih = 0;
467         float jh = 0;
468
469         SequenceNode sni = tmpi;
470         SequenceNode snj = tmpj;
471
472         while (sni != null)
473         {
474             ih = ih + sni.dist;
475             sni = (SequenceNode) sni.left();
476         }
477
478         while (snj != null)
479         {
480             jh = jh + snj.dist;
481             snj = (SequenceNode) snj.left();
482         }
483
484         tmpi.dist = ((dist / 2) - ih);
485         tmpj.dist = ((dist / 2) - jh);
486     }
487
488     /**
489      * DOCUMENT ME!
490      *
491      * @param i DOCUMENT ME!
492      * @param j DOCUMENT ME!
493      */
494     public void findClusterDistance(int i, int j)
495     {
496         int noi = ((Cluster) cluster.elementAt(i)).value.length;
497         int noj = ((Cluster) cluster.elementAt(j)).value.length;
498
499         // New distances from cluster to others
500         float[] newdist = new float[noseqs];
501
502         for (int l = 0; l < noseqs; l++)
503         {
504             if ((l != i) && (l != j))
505             {
506                 newdist[l] = ((distance[i][l] * noi) + (distance[j][l] * noj)) / (noi +
507                     noj);
508             }
509             else
510             {
511                 newdist[l] = 0;
512             }
513         }
514
515         for (int ii = 0; ii < noseqs; ii++)
516         {
517             distance[i][ii] = newdist[ii];
518             distance[ii][i] = newdist[ii];
519         }
520     }
521
522     /**
523      * DOCUMENT ME!
524      *
525      * @param i DOCUMENT ME!
526      * @param j DOCUMENT ME!
527      */
528     public void findClusterNJDistance(int i, int j)
529     {
530
531         // New distances from cluster to others
532         float[] newdist = new float[noseqs];
533
534         for (int l = 0; l < noseqs; l++)
535         {
536             if ((l != i) && (l != j))
537             {
538                 newdist[l] = ((distance[i][l] + distance[j][l]) -
539                     distance[i][j]) / 2;
540             }
541             else
542             {
543                 newdist[l] = 0;
544             }
545         }
546
547         for (int ii = 0; ii < noseqs; ii++)
548         {
549             distance[i][ii] = newdist[ii];
550             distance[ii][i] = newdist[ii];
551         }
552     }
553
554     /**
555      * DOCUMENT ME!
556      *
557      * @param i DOCUMENT ME!
558      * @param j DOCUMENT ME!
559      *
560      * @return DOCUMENT ME!
561      */
562     public float findr(int i, int j)
563     {
564         float tmp = 1;
565
566         for (int k = 0; k < noseqs; k++)
567         {
568             if ((k != i) && (k != j) && (done[k] != 1))
569             {
570                 tmp = tmp + distance[i][k];
571             }
572         }
573
574         if (noClus > 2)
575         {
576             tmp = tmp / (noClus - 2);
577         }
578
579         return tmp;
580     }
581
582     /**
583      * DOCUMENT ME!
584      *
585      * @return DOCUMENT ME!
586      */
587     public float findMinNJDistance()
588     {
589         float min = 100000;
590
591         for (int i = 0; i < (noseqs - 1); i++)
592         {
593             for (int j = i + 1; j < noseqs; j++)
594             {
595                 if ((done[i] != 1) && (done[j] != 1))
596                 {
597                     float tmp = distance[i][j] - (findr(i, j) + findr(j, i));
598
599                     if (tmp < min)
600                     {
601                         mini = i;
602                         minj = j;
603
604                         min = tmp;
605                     }
606                 }
607             }
608         }
609
610         return min;
611     }
612
613     /**
614      * DOCUMENT ME!
615      *
616      * @return DOCUMENT ME!
617      */
618     public float findMinDistance()
619     {
620         float min = 100000;
621
622         for (int i = 0; i < (noseqs - 1); i++)
623         {
624             for (int j = i + 1; j < noseqs; j++)
625             {
626                 if ((done[i] != 1) && (done[j] != 1))
627                 {
628                     if (distance[i][j] < min)
629                     {
630                         mini = i;
631                         minj = j;
632
633                         min = distance[i][j];
634                     }
635                 }
636             }
637         }
638
639         return min;
640     }
641
642     /**
643      * DOCUMENT ME!
644      *
645      * @return DOCUMENT ME!
646      */
647     public float[][] findDistances(String[] sequenceString)
648     {
649         float[][] distance = new float[noseqs][noseqs];
650
651         if (pwtype.equals("PID"))
652         {
653             for (int i = 0; i < (noseqs - 1); i++)
654             {
655                 for (int j = i; j < noseqs; j++)
656                 {
657                     if (j == i)
658                     {
659                         distance[i][i] = 0;
660                     }
661                     else
662                     {
663                         distance[i][j] = 100 -
664                              Comparison.PID(sequenceString[i], sequenceString[j]);
665
666                         distance[j][i] = distance[i][j];
667                     }
668                 }
669             }
670         }
671         else {
672           // Pairwise substitution score (with no gap penalties)
673           ScoreMatrix pwmatrix=ResidueProperties.getScoreMatrix(pwtype);
674           if (pwmatrix==null) {
675             pwmatrix=ResidueProperties.getScoreMatrix("BLOSUM62");
676           }
677           int maxscore = 0;
678           int end = sequenceString[0].length();
679           for (int i = 0; i < (noseqs - 1); i++)
680           {
681             for (int j = i; j < noseqs; j++)
682             {
683               int score = 0;
684               
685               for (int k = 0; k < end; k++)
686               {
687                 try
688                 {
689                   score += pwmatrix.getPairwiseScore(sequenceString[i].charAt(k),
690                       sequenceString[j].charAt(k));
691                 }
692                 catch (Exception ex)
693                 {
694                   System.err.println("err creating BLOSUM62 tree");
695                   ex.printStackTrace();
696                 }
697               }
698               
699               distance[i][j] = (float) score;
700               
701               if (score > maxscore)
702               {
703                 maxscore = score;
704               }
705             }
706           }
707           
708           for (int i = 0; i < (noseqs - 1); i++)
709           {
710             for (int j = i; j < noseqs; j++)
711             {
712               distance[i][j] = (float) maxscore - distance[i][j];
713               distance[j][i] = distance[i][j];
714             }
715           }
716           
717         }
718         return distance;
719     
720           //   else
721       /*  else if (pwtype.equals("SW"))
722         {
723             float max = -1;
724
725             for (int i = 0; i < (noseqs - 1); i++)
726             {
727                 for (int j = i; j < noseqs; j++)
728                 {
729                     AlignSeq as = new AlignSeq(sequence[i], sequence[j], "pep");
730                     as.calcScoreMatrix();
731                     as.traceAlignment();
732                     as.printAlignment(System.out);
733                     distance[i][j] = (float) as.maxscore;
734
735                     if (max < distance[i][j])
736                     {
737                         max = distance[i][j];
738                     }
739                 }
740             }
741
742             for (int i = 0; i < (noseqs - 1); i++)
743             {
744                 for (int j = i; j < noseqs; j++)
745                 {
746                     distance[i][j] = max - distance[i][j];
747                     distance[j][i] = distance[i][j];
748                 }
749             }
750         }/*/
751     }
752
753     /**
754      * DOCUMENT ME!
755      */
756     public void makeLeaves()
757     {
758         cluster = new Vector();
759
760         for (int i = 0; i < noseqs; i++)
761         {
762             SequenceNode sn = new SequenceNode();
763
764             sn.setElement(sequence[i]);
765             sn.setName(sequence[i].getName());
766             node.addElement(sn);
767
768             int[] value = new int[1];
769             value[0] = i;
770
771             Cluster c = new Cluster(value);
772             cluster.addElement(c);
773         }
774     }
775
776     /**
777      * DOCUMENT ME!
778      *
779      * @param node DOCUMENT ME!
780      * @param leaves DOCUMENT ME!
781      *
782      * @return DOCUMENT ME!
783      */
784     public Vector findLeaves(SequenceNode node, Vector leaves)
785     {
786         if (node == null)
787         {
788             return leaves;
789         }
790
791         if ((node.left() == null) && (node.right() == null))
792         {
793             leaves.addElement(node);
794
795             return leaves;
796         }
797         else
798         {
799             findLeaves((SequenceNode) node.left(), leaves);
800             findLeaves((SequenceNode) node.right(), leaves);
801         }
802
803         return leaves;
804     }
805
806     /**
807      * DOCUMENT ME!
808      *
809      * @param node DOCUMENT ME!
810      * @param count DOCUMENT ME!
811      *
812      * @return DOCUMENT ME!
813      */
814     public Object findLeaf(SequenceNode node, int count)
815     {
816         found = _findLeaf(node, count);
817
818         return found;
819     }
820
821     /**
822      * DOCUMENT ME!
823      *
824      * @param node DOCUMENT ME!
825      * @param count DOCUMENT ME!
826      *
827      * @return DOCUMENT ME!
828      */
829     public Object _findLeaf(SequenceNode node, int count)
830     {
831         if (node == null)
832         {
833             return null;
834         }
835
836         if (node.ycount == count)
837         {
838             found = node.element();
839
840             return found;
841         }
842         else
843         {
844             _findLeaf((SequenceNode) node.left(), count);
845             _findLeaf((SequenceNode) node.right(), count);
846         }
847
848         return found;
849     }
850
851     /**
852      * printNode is mainly for debugging purposes.
853      *
854      * @param node SequenceNode
855      */
856     public void printNode(SequenceNode node)
857     {
858         if (node == null)
859         {
860             return;
861         }
862
863         if ((node.left() == null) && (node.right() == null))
864         {
865             System.out.println("Leaf = " +
866                 ((SequenceI) node.element()).getName());
867             System.out.println("Dist " + ((SequenceNode) node).dist);
868             System.out.println("Boot " + node.getBootstrap());
869         }
870         else
871         {
872             System.out.println("Dist " + ((SequenceNode) node).dist);
873             printNode((SequenceNode) node.left());
874             printNode((SequenceNode) node.right());
875         }
876     }
877
878     /**
879      * DOCUMENT ME!
880      *
881      * @param node DOCUMENT ME!
882      */
883     public void findMaxDist(SequenceNode node)
884     {
885         if (node == null)
886         {
887             return;
888         }
889
890         if ((node.left() == null) && (node.right() == null))
891         {
892             float dist = ((SequenceNode) node).dist;
893
894             if (dist > maxDistValue)
895             {
896                 maxdist = (SequenceNode) node;
897                 maxDistValue = dist;
898             }
899         }
900         else
901         {
902             findMaxDist((SequenceNode) node.left());
903             findMaxDist((SequenceNode) node.right());
904         }
905     }
906
907     /**
908      * DOCUMENT ME!
909      *
910      * @return DOCUMENT ME!
911      */
912     public Vector getGroups()
913     {
914         return groups;
915     }
916
917     /**
918      * DOCUMENT ME!
919      *
920      * @return DOCUMENT ME!
921      */
922     public float getMaxHeight()
923     {
924         return maxheight;
925     }
926
927     /**
928      * DOCUMENT ME!
929      *
930      * @param node DOCUMENT ME!
931      * @param threshold DOCUMENT ME!
932      */
933     public void groupNodes(SequenceNode node, float threshold)
934     {
935         if (node == null)
936         {
937             return;
938         }
939
940         if ((node.height / maxheight) > threshold)
941         {
942             groups.addElement(node);
943         }
944         else
945         {
946             groupNodes((SequenceNode) node.left(), threshold);
947             groupNodes((SequenceNode) node.right(), threshold);
948         }
949     }
950
951     /**
952      * DOCUMENT ME!
953      *
954      * @param node DOCUMENT ME!
955      *
956      * @return DOCUMENT ME!
957      */
958     public float findHeight(SequenceNode node)
959     {
960         if (node == null)
961         {
962             return maxheight;
963         }
964
965         if ((node.left() == null) && (node.right() == null))
966         {
967             node.height = ((SequenceNode) node.parent()).height + node.dist;
968
969             if (node.height > maxheight)
970             {
971                 return node.height;
972             }
973             else
974             {
975                 return maxheight;
976             }
977         }
978         else
979         {
980             if (node.parent() != null)
981             {
982                 node.height = ((SequenceNode) node.parent()).height +
983                     node.dist;
984             }
985             else
986             {
987                 maxheight = 0;
988                 node.height = (float) 0.0;
989             }
990
991             maxheight = findHeight((SequenceNode) (node.left()));
992             maxheight = findHeight((SequenceNode) (node.right()));
993         }
994
995         return maxheight;
996     }
997
998     /**
999      * DOCUMENT ME!
1000      *
1001      * @return DOCUMENT ME!
1002      */
1003     public SequenceNode reRoot()
1004     {
1005         if (maxdist != null)
1006         {
1007             ycount = 0;
1008
1009             float tmpdist = maxdist.dist;
1010
1011             // New top
1012             SequenceNode sn = new SequenceNode();
1013             sn.setParent(null);
1014
1015             // New right hand of top
1016             SequenceNode snr = (SequenceNode) maxdist.parent();
1017             changeDirection(snr, maxdist);
1018             System.out.println("Printing reversed tree");
1019             printN(snr);
1020             snr.dist = tmpdist / 2;
1021             maxdist.dist = tmpdist / 2;
1022
1023             snr.setParent(sn);
1024             maxdist.setParent(sn);
1025
1026             sn.setRight(snr);
1027             sn.setLeft(maxdist);
1028
1029             top = sn;
1030
1031             ycount = 0;
1032             reCount(top);
1033             findHeight(top);
1034         }
1035
1036         return top;
1037     }
1038     /**
1039      *
1040      * @return true if original sequence data can be recovered
1041      */
1042     public boolean hasOriginalSequenceData() {
1043       return seqData!=null;
1044     }
1045     /**
1046      * Returns original alignment data used for calculation - or null where
1047      * not available.
1048      *
1049      * @return null or cut'n'pasteable alignment
1050      */
1051     public String printOriginalSequenceData(char gapChar)
1052     {
1053       if (seqData==null)
1054         return null;
1055
1056       StringBuffer sb = new StringBuffer();
1057       String[] seqdatas = seqData.getSequenceStrings(gapChar);
1058       for(int i=0; i<seqdatas.length; i++)
1059       {
1060         sb.append(new jalview.util.Format("%-" + 15 + "s").form(
1061             sequence[i].getName()));
1062         sb.append(" "+seqdatas[i]+"\n");
1063       }
1064       return sb.toString();
1065     }
1066     /**
1067      * DOCUMENT ME!
1068      *
1069      * @param node DOCUMENT ME!
1070      */
1071     public void printN(SequenceNode node)
1072     {
1073         if (node == null)
1074         {
1075             return;
1076         }
1077
1078         if ((node.left() != null) && (node.right() != null))
1079         {
1080             printN((SequenceNode) node.left());
1081             printN((SequenceNode) node.right());
1082         }
1083         else
1084         {
1085             System.out.println(" name = " +
1086                 ((SequenceI) node.element()).getName());
1087         }
1088
1089         System.out.println(" dist = " + ((SequenceNode) node).dist + " " +
1090             ((SequenceNode) node).count + " " + ((SequenceNode) node).height);
1091     }
1092
1093     /**
1094      * DOCUMENT ME!
1095      *
1096      * @param node DOCUMENT ME!
1097      */
1098     public void reCount(SequenceNode node)
1099     {
1100         ycount = 0;
1101         _reCount(node);
1102     }
1103
1104     /**
1105      * DOCUMENT ME!
1106      *
1107      * @param node DOCUMENT ME!
1108      */
1109     public void _reCount(SequenceNode node)
1110     {
1111         if (node == null)
1112         {
1113             return;
1114         }
1115
1116         if ((node.left() != null) && (node.right() != null))
1117         {
1118             _reCount((SequenceNode) node.left());
1119             _reCount((SequenceNode) node.right());
1120
1121             SequenceNode l = (SequenceNode) node.left();
1122             SequenceNode r = (SequenceNode) node.right();
1123
1124             ((SequenceNode) node).count = l.count + r.count;
1125             ((SequenceNode) node).ycount = (l.ycount + r.ycount) / 2;
1126         }
1127         else
1128         {
1129             ((SequenceNode) node).count = 1;
1130             ((SequenceNode) node).ycount = ycount++;
1131         }
1132     }
1133
1134     /**
1135      * DOCUMENT ME!
1136      *
1137      * @param node DOCUMENT ME!
1138      */
1139     public void swapNodes(SequenceNode node)
1140     {
1141         if (node == null)
1142         {
1143             return;
1144         }
1145
1146         SequenceNode tmp = (SequenceNode) node.left();
1147
1148         node.setLeft(node.right());
1149         node.setRight(tmp);
1150     }
1151
1152     /**
1153      * DOCUMENT ME!
1154      *
1155      * @param node DOCUMENT ME!
1156      * @param dir DOCUMENT ME!
1157      */
1158     public void changeDirection(SequenceNode node, SequenceNode dir)
1159     {
1160         if (node == null)
1161         {
1162             return;
1163         }
1164
1165         if (node.parent() != top)
1166         {
1167             changeDirection((SequenceNode) node.parent(), node);
1168
1169             SequenceNode tmp = (SequenceNode) node.parent();
1170
1171             if (dir == node.left())
1172             {
1173                 node.setParent(dir);
1174                 node.setLeft(tmp);
1175             }
1176             else if (dir == node.right())
1177             {
1178                 node.setParent(dir);
1179                 node.setRight(tmp);
1180             }
1181         }
1182         else
1183         {
1184             if (dir == node.left())
1185             {
1186                 node.setParent(node.left());
1187
1188                 if (top.left() == node)
1189                 {
1190                     node.setRight(top.right());
1191                 }
1192                 else
1193                 {
1194                     node.setRight(top.left());
1195                 }
1196             }
1197             else
1198             {
1199                 node.setParent(node.right());
1200
1201                 if (top.left() == node)
1202                 {
1203                     node.setLeft(top.right());
1204                 }
1205                 else
1206                 {
1207                     node.setLeft(top.left());
1208                 }
1209             }
1210         }
1211     }
1212
1213
1214     /**
1215      * DOCUMENT ME!
1216      *
1217      * @return DOCUMENT ME!
1218      */
1219     public SequenceNode getMaxDist()
1220     {
1221         return maxdist;
1222     }
1223
1224     /**
1225      * DOCUMENT ME!
1226      *
1227      * @return DOCUMENT ME!
1228      */
1229     public SequenceNode getTopNode()
1230     {
1231         return top;
1232     }
1233     /**
1234      *
1235      * @return true if tree has real distances
1236      */
1237     public boolean isHasDistances() {
1238       return hasDistances;
1239     }
1240
1241     /**
1242      *
1243      * @return true if tree has real bootstrap values
1244      */
1245     public boolean isHasBootstrap() {
1246       return hasBootstrap;
1247     }
1248
1249   public boolean isHasRootDistance()
1250   {
1251     return hasRootDistance;
1252   }
1253
1254 }
1255
1256
1257 /**
1258  * DOCUMENT ME!
1259  *
1260  * @author $author$
1261  * @version $Revision$
1262  */
1263 class Cluster
1264 {
1265     int[] value;
1266
1267     /**
1268      * Creates a new Cluster object.
1269      *
1270      * @param value DOCUMENT ME!
1271      */
1272     public Cluster(int[] value)
1273     {
1274         this.value = value;
1275     }
1276 }
1277