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