JAL-3949 fixed failing commandlinetests due to more output and line count limit
[jalview.git] / src / jalview / analysis / TreeModel.java
1 /*
2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
4  * 
5  * This file is part of Jalview.
6  * 
7  * Jalview is free software: you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License 
9  * as published by the Free Software Foundation, either version 3
10  * of the License, or (at your option) any later version.
11  *  
12  * Jalview is distributed in the hope that it will be useful, but 
13  * WITHOUT ANY WARRANTY; without even the implied warranty 
14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
15  * PURPOSE.  See the GNU General Public License for more details.
16  * 
17  * You should have received a copy of the GNU General Public License
18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
19  * The Jalview Authors are detailed in the 'AUTHORS' file.
20  */
21 package jalview.analysis;
22
23 import jalview.bin.Cache;
24 import jalview.datamodel.AlignmentView;
25 import jalview.datamodel.BinaryNode;
26 import jalview.datamodel.NodeTransformI;
27 import jalview.datamodel.Sequence;
28 import jalview.datamodel.SequenceI;
29 import jalview.datamodel.SequenceNode;
30 import jalview.io.NewickFile;
31
32 import java.util.ArrayList;
33 import java.util.Enumeration;
34 import java.util.List;
35 import java.util.Vector;
36
37 /**
38  * A model of a tree, either computed by Jalview or loaded from a file or other
39  * resource or service
40  */
41 public class TreeModel
42 {
43
44   SequenceI[] sequences;
45
46   /* 
47    * SequenceData is a string representation of what the user
48    * sees. The display may contain hidden columns.
49    */
50   private AlignmentView seqData;
51
52   int noseqs;
53
54   SequenceNode top;
55
56   double maxDistValue;
57
58   double maxheight;
59
60   int ycount;
61
62   Vector<SequenceNode> node;
63
64   boolean hasDistances = true; // normal case for jalview trees
65
66   boolean hasBootstrap = false; // normal case for jalview trees
67
68   private boolean hasRootDistance = true;
69
70   /**
71    * Create a new TreeModel object with leaves associated with sequences in
72    * seqs, and (optionally) original alignment data represented by Cigar strings
73    * 
74    * @param seqs
75    *          SequenceI[]
76    * @param odata
77    *          Cigar[]
78    * @param treefile
79    *          NewickFile
80    */
81   public TreeModel(SequenceI[] seqs, AlignmentView odata,
82           NewickFile treefile)
83   {
84     this(seqs, treefile.getTree(), treefile.HasDistances(),
85             treefile.HasBootstrap(), treefile.HasRootDistance());
86     seqData = odata;
87
88     associateLeavesToSequences(seqs);
89   }
90
91   /**
92    * Constructor given a calculated tree
93    * 
94    * @param tree
95    */
96   public TreeModel(TreeBuilder tree)
97   {
98     this(tree.getSequences(), tree.getTopNode(), tree.hasDistances(),
99             tree.hasBootstrap(), tree.hasRootDistance());
100     seqData = tree.getOriginalData();
101   }
102
103   /**
104    * Constructor given sequences, root node and tree property flags
105    * 
106    * @param seqs
107    * @param root
108    * @param hasDist
109    * @param hasBoot
110    * @param hasRootDist
111    */
112   public TreeModel(SequenceI[] seqs, SequenceNode root, boolean hasDist,
113           boolean hasBoot, boolean hasRootDist)
114   {
115     this.sequences = seqs;
116     top = root;
117
118     hasDistances = hasDist;
119     hasBootstrap = hasBoot;
120     hasRootDistance = hasRootDist;
121
122     maxheight = findHeight(top);
123   }
124
125   /**
126    * @param seqs
127    */
128   public void associateLeavesToSequences(SequenceI[] seqs)
129   {
130     SequenceIdMatcher algnIds = new SequenceIdMatcher(seqs);
131
132     Vector<SequenceNode> leaves = findLeaves(top);
133
134     int i = 0;
135     int namesleft = seqs.length;
136
137     SequenceNode j;
138     SequenceI nam;
139     String realnam;
140     Vector<SequenceI> one2many = new Vector<SequenceI>();
141     // int countOne2Many = 0;
142     while (i < leaves.size())
143     {
144       j = leaves.elementAt(i++);
145       realnam = j.getName();
146       nam = null;
147
148       if (namesleft > -1)
149       {
150         nam = algnIds.findIdMatch(realnam);
151       }
152
153       if (nam != null)
154       {
155         j.setElement(nam);
156         if (one2many.contains(nam))
157         {
158           // countOne2Many++;
159           // if (Cache.isDebugEnabled())
160           // Cache.debug("One 2 many relationship for
161           // "+nam.getName());
162         }
163         else
164         {
165           one2many.addElement(nam);
166           namesleft--;
167         }
168       }
169       else
170       {
171         j.setElement(new Sequence(realnam, "THISISAPLACEHLDER"));
172         j.setPlaceholder(true);
173       }
174     }
175     // if (Cache.isDebugEnabled() && countOne2Many>0) {
176     // Cache.debug("There were "+countOne2Many+" alignment
177     // sequence ids (out of "+one2many.size()+" unique ids) linked to two or
178     // more leaves.");
179     // }
180     // one2many.clear();
181   }
182
183   /**
184    * Generate a string representation of the Tree
185    * 
186    * @return Newick File with all tree data available
187    */
188   public String print()
189   {
190     NewickFile fout = new NewickFile(getTopNode());
191
192     return fout.print(hasBootstrap(), hasDistances(), hasRootDistance()); // output
193                                                                           // all
194                                                                           // data
195                                                                           // available
196                                                                           // for
197                                                                           // tree
198   }
199
200   /**
201    * 
202    * used when the alignment associated to a tree has changed.
203    * 
204    * @param list
205    *          Sequence set to be associated with tree nodes
206    */
207   public void updatePlaceHolders(List<SequenceI> list)
208   {
209     Vector<SequenceNode> leaves = findLeaves(top);
210
211     int sz = leaves.size();
212     SequenceIdMatcher seqmatcher = null;
213     int i = 0;
214
215     while (i < sz)
216     {
217       SequenceNode leaf = leaves.elementAt(i++);
218
219       if (list.contains(leaf.element()))
220       {
221         leaf.setPlaceholder(false);
222       }
223       else
224       {
225         if (seqmatcher == null)
226         {
227           // Only create this the first time we need it
228           SequenceI[] seqs = new SequenceI[list.size()];
229
230           for (int j = 0; j < seqs.length; j++)
231           {
232             seqs[j] = list.get(j);
233           }
234
235           seqmatcher = new SequenceIdMatcher(seqs);
236         }
237
238         SequenceI nam = seqmatcher.findIdMatch(leaf.getName());
239
240         if (nam != null)
241         {
242           if (!leaf.isPlaceholder())
243           {
244             // remapping the node to a new sequenceI - should remove any refs to
245             // old one.
246             // TODO - make many sequenceI to one leaf mappings possible!
247             // (JBPNote)
248           }
249           leaf.setPlaceholder(false);
250           leaf.setElement(nam);
251         }
252         else
253         {
254           if (!leaf.isPlaceholder())
255           {
256             // Construct a new placeholder sequence object for this leaf
257             leaf.setElement(
258                     new Sequence(leaf.getName(), "THISISAPLACEHLDER"));
259           }
260           leaf.setPlaceholder(true);
261
262         }
263       }
264     }
265   }
266
267   /**
268    * rename any nodes according to their associated sequence. This will modify
269    * the tree's metadata! (ie the original NewickFile or newly generated
270    * BinaryTree's label data)
271    */
272   public void renameAssociatedNodes()
273   {
274     applyToNodes(new NodeTransformI()
275     {
276
277       @Override
278       public void transform(BinaryNode nd)
279       {
280         Object el = nd.element();
281         if (el != null && el instanceof SequenceI)
282         {
283           nd.setName(((SequenceI) el).getName());
284         }
285       }
286     });
287   }
288
289   /**
290    * Search for leaf nodes below (or at) the given node
291    * 
292    * @param nd
293    *          root node to search from
294    * 
295    * @return
296    */
297   public Vector<SequenceNode> findLeaves(SequenceNode nd)
298   {
299     Vector<SequenceNode> leaves = new Vector<SequenceNode>();
300     findLeaves(nd, leaves);
301     return leaves;
302   }
303
304   /**
305    * Search for leaf nodes.
306    * 
307    * @param nd
308    *          root node to search from
309    * @param leaves
310    *          Vector of leaves to add leaf node objects too.
311    * 
312    * @return Vector of leaf nodes on binary tree
313    */
314   Vector<SequenceNode> findLeaves(SequenceNode nd,
315           Vector<SequenceNode> leaves)
316   {
317     if (nd == null)
318     {
319       return leaves;
320     }
321
322     if ((nd.left() == null) && (nd.right() == null)) // Interior node
323     // detection
324     {
325       leaves.addElement(nd);
326
327       return leaves;
328     }
329     else
330     {
331       /*
332        * TODO: Identify internal nodes... if (node.isSequenceLabel()) {
333        * leaves.addElement(node); }
334        */
335       findLeaves((SequenceNode) nd.left(), leaves);
336       findLeaves((SequenceNode) nd.right(), leaves);
337     }
338
339     return leaves;
340   }
341
342   /**
343    * printNode is mainly for debugging purposes.
344    * 
345    * @param nd
346    *          SequenceNode
347    */
348   void printNode(SequenceNode nd)
349   {
350     if (nd == null)
351     {
352       return;
353     }
354
355     if ((nd.left() == null) && (nd.right() == null))
356     {
357       System.out.println("Leaf = " + ((SequenceI) nd.element()).getName());
358       System.out.println("Dist " + nd.dist);
359       System.out.println("Boot " + nd.getBootstrap());
360     }
361     else
362     {
363       System.out.println("Dist " + nd.dist);
364       printNode((SequenceNode) nd.left());
365       printNode((SequenceNode) nd.right());
366     }
367   }
368
369   /**
370    * DOCUMENT ME!
371    * 
372    * @return DOCUMENT ME!
373    */
374   public double getMaxHeight()
375   {
376     return maxheight;
377   }
378
379   /**
380    * Makes a list of groups, where each group is represented by a node whose
381    * height (distance from the root node), as a fraction of the height of the
382    * whole tree, is greater than the given threshold. This corresponds to
383    * selecting the nodes immediately to the right of a vertical line
384    * partitioning the tree (if the tree is drawn with root to the left). Each
385    * such node represents a group that contains all of the sequences linked to
386    * the child leaf nodes.
387    * 
388    * @param threshold
389    * @see #getGroups()
390    */
391   public List<SequenceNode> groupNodes(float threshold)
392   {
393     List<SequenceNode> groups = new ArrayList<SequenceNode>();
394     _groupNodes(groups, getTopNode(), threshold);
395     return groups;
396   }
397
398   protected void _groupNodes(List<SequenceNode> groups, SequenceNode nd,
399           float threshold)
400   {
401     if (nd == null)
402     {
403       return;
404     }
405
406     if ((nd.height / maxheight) > threshold)
407     {
408       groups.add(nd);
409     }
410     else
411     {
412       _groupNodes(groups, (SequenceNode) nd.left(), threshold);
413       _groupNodes(groups, (SequenceNode) nd.right(), threshold);
414     }
415   }
416
417   /**
418    * DOCUMENT ME!
419    * 
420    * @param nd
421    *          DOCUMENT ME!
422    * 
423    * @return DOCUMENT ME!
424    */
425   public double findHeight(SequenceNode nd)
426   {
427     if (nd == null)
428     {
429       return maxheight;
430     }
431
432     if ((nd.left() == null) && (nd.right() == null))
433     {
434       nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
435
436       if (nd.height > maxheight)
437       {
438         return nd.height;
439       }
440       else
441       {
442         return maxheight;
443       }
444     }
445     else
446     {
447       if (nd.parent() != null)
448       {
449         nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
450       }
451       else
452       {
453         maxheight = 0;
454         nd.height = (float) 0.0;
455       }
456
457       maxheight = findHeight((SequenceNode) (nd.left()));
458       maxheight = findHeight((SequenceNode) (nd.right()));
459     }
460
461     return maxheight;
462   }
463
464   /**
465    * DOCUMENT ME!
466    * 
467    * @param nd
468    *          DOCUMENT ME!
469    */
470   void printN(SequenceNode nd)
471   {
472     if (nd == null)
473     {
474       return;
475     }
476
477     if ((nd.left() != null) && (nd.right() != null))
478     {
479       printN((SequenceNode) nd.left());
480       printN((SequenceNode) nd.right());
481     }
482     else
483     {
484       System.out.println(" name = " + ((SequenceI) nd.element()).getName());
485     }
486
487     System.out.println(
488             " dist = " + nd.dist + " " + nd.count + " " + nd.height);
489   }
490
491   /**
492    * DOCUMENT ME!
493    * 
494    * @param nd
495    *          DOCUMENT ME!
496    */
497   public void reCount(SequenceNode nd)
498   {
499     ycount = 0;
500     // _lycount = 0;
501     // _lylimit = this.node.size();
502     _reCount(nd);
503   }
504
505   // private long _lycount = 0, _lylimit = 0;
506
507   /**
508    * DOCUMENT ME!
509    * 
510    * @param nd
511    *          DOCUMENT ME!
512    */
513   void _reCount(SequenceNode nd)
514   {
515     // if (_lycount<_lylimit)
516     // {
517     // System.err.println("Warning: depth of _recount greater than number of
518     // nodes.");
519     // }
520     if (nd == null)
521     {
522       return;
523     }
524     // _lycount++;
525
526     if ((nd.left() != null) && (nd.right() != null))
527     {
528
529       _reCount((SequenceNode) nd.left());
530       _reCount((SequenceNode) nd.right());
531
532       SequenceNode l = (SequenceNode) nd.left();
533       SequenceNode r = (SequenceNode) nd.right();
534
535       nd.count = l.count + r.count;
536       nd.ycount = (l.ycount + r.ycount) / 2;
537     }
538     else
539     {
540       nd.count = 1;
541       nd.ycount = ycount++;
542     }
543     // _lycount--;
544   }
545
546   /**
547    * DOCUMENT ME!
548    * 
549    * @param nd
550    *          DOCUMENT ME!
551    */
552   public void swapNodes(SequenceNode nd)
553   {
554     if (nd == null)
555     {
556       return;
557     }
558
559     SequenceNode tmp = (SequenceNode) nd.left();
560
561     nd.setLeft(nd.right());
562     nd.setRight(tmp);
563   }
564
565   /**
566    * DOCUMENT ME!
567    * 
568    * @param nd
569    *          DOCUMENT ME!
570    * @param dir
571    *          DOCUMENT ME!
572    */
573   void changeDirection(SequenceNode nd, SequenceNode dir)
574   {
575     if (nd == null)
576     {
577       return;
578     }
579
580     if (nd.parent() != top)
581     {
582       changeDirection((SequenceNode) nd.parent(), nd);
583
584       SequenceNode tmp = (SequenceNode) nd.parent();
585
586       if (dir == nd.left())
587       {
588         nd.setParent(dir);
589         nd.setLeft(tmp);
590       }
591       else if (dir == nd.right())
592       {
593         nd.setParent(dir);
594         nd.setRight(tmp);
595       }
596     }
597     else
598     {
599       if (dir == nd.left())
600       {
601         nd.setParent(nd.left());
602
603         if (top.left() == nd)
604         {
605           nd.setRight(top.right());
606         }
607         else
608         {
609           nd.setRight(top.left());
610         }
611       }
612       else
613       {
614         nd.setParent(nd.right());
615
616         if (top.left() == nd)
617         {
618           nd.setLeft(top.right());
619         }
620         else
621         {
622           nd.setLeft(top.left());
623         }
624       }
625     }
626   }
627
628   /**
629    * DOCUMENT ME!
630    * 
631    * @return DOCUMENT ME!
632    */
633   public SequenceNode getTopNode()
634   {
635     return top;
636   }
637
638   /**
639    * 
640    * @return true if tree has real distances
641    */
642   public boolean hasDistances()
643   {
644     return hasDistances;
645   }
646
647   /**
648    * 
649    * @return true if tree has real bootstrap values
650    */
651   public boolean hasBootstrap()
652   {
653     return hasBootstrap;
654   }
655
656   public boolean hasRootDistance()
657   {
658     return hasRootDistance;
659   }
660
661   /**
662    * apply the given transform to all the nodes in the tree.
663    * 
664    * @param nodeTransformI
665    */
666   public void applyToNodes(NodeTransformI nodeTransformI)
667   {
668     for (Enumeration<SequenceNode> nodes = node.elements(); nodes
669             .hasMoreElements(); nodeTransformI
670                     .transform(nodes.nextElement()))
671     {
672       ;
673     }
674   }
675
676   public AlignmentView getOriginalData()
677   {
678     return seqData;
679   }
680 }