Clover icon

Coverage Report

  1. Project Clover database Wed Sep 17 2025 10:52:37 BST
  2. Package jalview.analysis

File TreeModel.java

 

Coverage histogram

../../img/srcFileCovDistChart6.png
37% of files have more coverage

Code metrics

72
158
28
1
710
406
70
0.44
5.64
28
2.5

Classes

Class Line # Actions
TreeModel 41 158 70
0.511627951.2%
 

Contributing tests

This file is covered by 13 tests. .

Source view

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.datamodel.AlignmentAnnotation;
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    BinaryNode top;
55   
56    double maxDistValue;
57   
58    double maxheight;
59   
60    int ycount;
61   
62    Vector<BinaryNode> 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    * @param leafAnnotations
81    * Set of annotations that might also be mappable to leaves of the tree
82    */
 
83  23 toggle public TreeModel(SequenceI[] seqs, AlignmentView odata,
84    NewickFile treefile, AlignmentAnnotation[] leafAnnotations)
85    {
86  23 this(seqs, treefile.getTree(), treefile.HasDistances(),
87    treefile.HasBootstrap(), treefile.HasRootDistance());
88  23 seqData = odata;
89  23 if (leafAnnotations != null)
90    {
91    // TODO
92    // leaf names are seuqence ID + annotation for display
93    // leaf links are annotationId <> annotation object for import from
94    // project
95    // --> need to resolve before passing for display
96    // ==> do leafs need to be renamed after import ?
97    // ==> implies the 'nodeLabel' business needs to be callable independently
98    // of score function
99    }
100    else
101    {
102  23 associateLeavesToSequences(seqs);
103    }
104    }
105   
106    /**
107    * Constructor given a calculated tree
108    *
109    * @param tree
110    */
 
111  1 toggle public TreeModel(TreeBuilder tree)
112    {
113  1 this(tree.getSequences(), tree.getTopNode(), tree.hasDistances(),
114    tree.hasBootstrap(), tree.hasRootDistance());
115  1 seqData = tree.getOriginalData();
116    }
117   
118    /**
119    * Constructor given sequences, root node and tree property flags
120    *
121    * @param seqs
122    * @param root
123    * @param hasDist
124    * @param hasBoot
125    * @param hasRootDist
126    */
 
127  24 toggle public TreeModel(SequenceI[] seqs, BinaryNode root, boolean hasDist,
128    boolean hasBoot, boolean hasRootDist)
129    {
130  24 this.sequences = seqs;
131  24 top = root;
132   
133  24 hasDistances = hasDist;
134  24 hasBootstrap = hasBoot;
135  24 hasRootDistance = hasRootDist;
136   
137  24 maxheight = findHeight(top);
138    }
139   
140    /**
141    * @param seqs
142    */
 
143  23 toggle public void associateLeavesToSequences(SequenceI[] seqs)
144    {
145  23 SequenceIdMatcher algnIds = new SequenceIdMatcher(seqs);
146   
147  23 Vector<BinaryNode> leaves = findLeaves(top);
148   
149  23 int i = 0;
150  23 int namesleft = seqs.length;
151   
152  23 SequenceNode j;
153  23 SequenceI nam;
154  23 String realnam;
155  23 Vector<SequenceI> one2many = new Vector<SequenceI>();
156    // int countOne2Many = 0;
157  295 while (i < leaves.size())
158    {
159    // TODO - decide if we get rid of the polymorphism here ?
160  272 j = (SequenceNode) leaves.elementAt(i++);
161  272 realnam = j.getName();
162  272 nam = null;
163   
164  272 if (namesleft > -1)
165    {
166  272 nam = algnIds.findIdMatch(realnam);
167    }
168   
169  272 if (nam != null)
170    {
171  198 j.setElement(nam);
172  198 if (one2many.contains(nam))
173    {
174    // countOne2Many++;
175    // if (Cache.isDebugEnabled())
176    // Cache.debug("One 2 many relationship for
177    // "+nam.getName());
178    }
179    else
180    {
181  198 one2many.addElement(nam);
182  198 namesleft--;
183    }
184    }
185    else
186    {
187  74 j.setElement(new Sequence(realnam, "THISISAPLACEHLDER"));
188  74 j.setPlaceholder(true);
189    }
190    }
191    // if (Cache.isDebugEnabled() && countOne2Many>0) {
192    // Cache.debug("There were "+countOne2Many+" alignment
193    // sequence ids (out of "+one2many.size()+" unique ids) linked to two or
194    // more leaves.");
195    // }
196    // one2many.clear();
197    }
198   
199    /**
200    * Generate a string representation of the Tree
201    *
202    * @return Newick File with all tree data available
203    */
 
204  4 toggle public String print()
205    {
206  4 NewickFile fout = new NewickFile(getTopNode());
207   
208  4 return fout.print(hasBootstrap(), hasDistances(), hasRootDistance()); // output
209    // all
210    // data
211    // available
212    // for
213    // tree
214    }
215   
216    /**
217    *
218    * used when the alignment associated to a tree has changed.
219    *
220    * @param list
221    * Sequence set to be associated with tree nodes
222    */
 
223  0 toggle public void updatePlaceHolders(List<SequenceI> list)
224    {
225  0 Vector<BinaryNode> leaves = findLeaves(top);
226   
227  0 int sz = leaves.size();
228  0 SequenceIdMatcher seqmatcher = null;
229  0 int i = 0;
230   
231  0 while (i < sz)
232    {
233  0 SequenceNode leaf = (SequenceNode) leaves.elementAt(i++);
234   
235  0 if (list.contains(leaf.element()))
236    {
237  0 leaf.setPlaceholder(false);
238    }
239    else
240    {
241  0 if (seqmatcher == null)
242    {
243    // Only create this the first time we need it
244  0 SequenceI[] seqs = new SequenceI[list.size()];
245   
246  0 for (int j = 0; j < seqs.length; j++)
247    {
248  0 seqs[j] = list.get(j);
249    }
250   
251  0 seqmatcher = new SequenceIdMatcher(seqs);
252    }
253   
254  0 SequenceI nam = seqmatcher.findIdMatch(leaf.getName());
255   
256  0 if (nam != null)
257    {
258  0 if (!leaf.isPlaceholder())
259    {
260    // remapping the node to a new sequenceI - should remove any refs to
261    // old one.
262    // TODO - make many sequenceI to one leaf mappings possible!
263    // (JBPNote)
264    }
265  0 leaf.setPlaceholder(false);
266  0 leaf.setElement(nam);
267    }
268    else
269    {
270  0 if (!leaf.isPlaceholder())
271    {
272    // Construct a new placeholder sequence object for this leaf
273  0 leaf.setElement(
274    new Sequence(leaf.getName(), "THISISAPLACEHLDER"));
275    }
276  0 leaf.setPlaceholder(true);
277   
278    }
279    }
280    }
281    }
282   
283    /**
284    * rename any nodes according to their associated sequence. This will modify
285    * the tree's metadata! (ie the original NewickFile or newly generated
286    * BinaryTree's label data)
287    */
 
288  0 toggle public void renameAssociatedNodes()
289    {
290  0 applyToNodes(new NodeTransformI()
291    {
292   
 
293  0 toggle @Override
294    public void transform(BinaryNode nd)
295    {
296  0 Object el = nd.element();
297  0 if (el != null && el instanceof SequenceI)
298    {
299  0 nd.setName(((SequenceI) el).getName());
300    }
301    }
302    });
303    }
304   
305    /**
306    * Search for leaf nodes below (or at) the given node
307    *
308    * @param top2
309    * root node to search from
310    *
311    * @return
312    */
 
313  54 toggle public Vector<BinaryNode> findLeaves(BinaryNode top2)
314    {
315  54 Vector<BinaryNode> leaves = new Vector<BinaryNode>();
316  54 findLeaves(top2, leaves);
317  54 return leaves;
318    }
319   
320    /**
321    * Search for leaf nodes.
322    *
323    * @param nd
324    * root node to search from
325    * @param leaves
326    * Vector of leaves to add leaf node objects too.
327    *
328    * @return Vector of leaf nodes on binary tree
329    */
 
330  1306 toggle Vector<BinaryNode> findLeaves(BinaryNode nd, Vector<BinaryNode> leaves)
331    {
332  1306 if (nd == null)
333    {
334  0 return leaves;
335    }
336   
337  1306 if ((nd.left() == null) && (nd.right() == null)) // Interior node
338    // detection
339    {
340  680 leaves.addElement(nd);
341   
342  680 return leaves;
343    }
344    else
345    {
346    /*
347    * TODO: Identify internal nodes... if (node.isSequenceLabel()) {
348    * leaves.addElement(node); }
349    */
350  626 findLeaves(nd.left(), leaves);
351  626 findLeaves(nd.right(), leaves);
352    }
353   
354  626 return leaves;
355    }
356   
357    /**
358    * printNode is mainly for debugging purposes.
359    *
360    * @param nd
361    * SequenceNode
362    */
 
363  0 toggle void printNode(BinaryNode nd)
364    {
365  0 if (nd == null)
366    {
367  0 return;
368    }
369   
370  0 if ((nd.left() == null) && (nd.right() == null))
371    {
372    // TODO FIX FOR COLUMN TREES
373  0 jalview.bin.Console
374    .outPrintln("Leaf = " + ((SequenceI) nd.element()).getName());
375  0 jalview.bin.Console.outPrintln("Dist " + nd.dist);
376  0 jalview.bin.Console.outPrintln("Boot " + nd.getBootstrap());
377    }
378    else
379    {
380  0 jalview.bin.Console.outPrintln("Dist " + nd.dist);
381  0 printNode((BinaryNode) nd.left());
382  0 printNode((BinaryNode) nd.right());
383    }
384    }
385   
386   
 
387  0 toggle public Vector<BinaryNode> getNode()
388    {
389  0 return node;
390    }
391   
 
392  3 toggle public void setNode(Vector<BinaryNode> node)
393    {
394  3 this.node = node;
395    }
396   
397    /**
398    * DOCUMENT ME!
399    *
400    * @return DOCUMENT ME!
401    */
 
402  1 toggle public double getMaxHeight()
403    {
404  1 return maxheight;
405    }
406   
407    /**
408    * Makes a list of groups, where each group is represented by a node whose
409    * height (distance from the root node), as a fraction of the height of the
410    * whole tree, is greater than the given threshold. This corresponds to
411    * selecting the nodes immediately to the right of a vertical line
412    * partitioning the tree (if the tree is drawn with root to the left). Each
413    * such node represents a group that contains all of the sequences linked to
414    * the child leaf nodes.
415    *
416    * @param threshold
417    * @see #getGroups()
418    */
 
419  1 toggle public List<BinaryNode> groupNodes(float threshold)
420    {
421  1 List<BinaryNode> groups = new ArrayList<BinaryNode>();
422  1 _groupNodes(groups, getTopNode(), threshold);
423  1 return groups;
424    }
425   
 
426  3 toggle protected void _groupNodes(List<BinaryNode> groups, BinaryNode nd,
427    float threshold)
428    {
429  3 if (nd == null)
430    {
431  0 return;
432    }
433   
434  3 if ((nd.height / maxheight) > threshold)
435    {
436  2 groups.add(nd);
437    }
438    else
439    {
440  1 _groupNodes(groups, nd.left(), threshold);
441  1 _groupNodes(groups, nd.right(), threshold);
442    }
443    }
444   
445    /**
446    * DOCUMENT ME!
447    *
448    * @param nd
449    * DOCUMENT ME!
450    *
451    * @return DOCUMENT ME!
452    */
 
453  1528 toggle public double findHeight(BinaryNode nd)
454    {
455  1528 if (nd == null)
456    {
457  0 return maxheight;
458    }
459   
460  1528 if ((nd.left() == null) && (nd.right() == null))
461    {
462  794 nd.height = nd.parent().height + nd.dist;
463   
464  794 if (nd.height > maxheight)
465    {
466  94 return nd.height;
467    }
468    else
469    {
470  700 return maxheight;
471    }
472    }
473    else
474    {
475  734 if (nd.parent() != null)
476    {
477  674 nd.height = nd.parent().height + nd.dist;
478    }
479    else
480    {
481  60 maxheight = 0;
482  60 nd.height = (float) 0.0;
483    }
484   
485  734 maxheight = findHeight((BinaryNode) (nd.left()));
486  734 maxheight = findHeight((BinaryNode) (nd.right()));
487    }
488   
489  734 return maxheight;
490    }
491   
492    /**
493    * DOCUMENT ME!
494    *
495    * @param nd
496    * DOCUMENT ME!
497    */
 
498  0 toggle void printN(BinaryNode nd)
499    {
500  0 if (nd == null)
501    {
502  0 return;
503    }
504   
505  0 if ((nd.left() != null) && (nd.right() != null))
506    {
507  0 printN((BinaryNode) nd.left());
508  0 printN((BinaryNode) nd.right());
509    }
510    else
511    {
512  0 jalview.bin.Console.outPrintln(
513    " name = " + ((SequenceI) nd.element()).getName());
514    }
515   
516  0 jalview.bin.Console.outPrintln(
517    " dist = " + nd.dist + " " + nd.count + " " + nd.height);
518    }
519   
520    /**
521    * DOCUMENT ME!
522    *
523    * @param nd
524    * DOCUMENT ME!
525    */
 
526  18 toggle public void reCount(BinaryNode nd)
527    {
528  18 ycount = 0;
529    // _lycount = 0;
530    // _lylimit = this.node.size();
531  18 _reCount(nd);
532    }
533   
534    // private long _lycount = 0, _lylimit = 0;
535   
536    /**
537    * DOCUMENT ME!
538    *
539    * @param nd
540    * DOCUMENT ME!
541    */
 
542  486 toggle void _reCount(BinaryNode nd)
543    {
544    // if (_lycount<_lylimit)
545    // {
546    // jalview.bin.Console.errPrintln("Warning: depth of _recount greater than
547    // number of
548    // nodes.");
549    // }
550  486 if (nd == null)
551    {
552  0 return;
553    }
554    // _lycount++;
555   
556  486 if ((nd.left() != null) && (nd.right() != null))
557    {
558   
559  234 _reCount((BinaryNode) nd.left());
560  234 _reCount((BinaryNode) nd.right());
561   
562  234 BinaryNode l = (BinaryNode) nd.left();
563  234 BinaryNode r = (BinaryNode) nd.right();
564   
565  234 nd.count = l.count + r.count;
566  234 nd.ycount = (l.ycount + r.ycount) / 2;
567    }
568    else
569    {
570  252 nd.count = 1;
571  252 nd.ycount = ycount++;
572    }
573    // _lycount--;
574    }
575   
576    /**
577    * DOCUMENT ME!
578    *
579    * @param nd
580    * DOCUMENT ME!
581    */
 
582  0 toggle public void swapNodes(BinaryNode nd)
583    {
584  0 if (nd == null)
585    {
586  0 return;
587    }
588   
589  0 BinaryNode tmp = (BinaryNode) nd.left();
590   
591  0 nd.setLeft(nd.right());
592  0 nd.setRight(tmp);
593    }
594   
595    /**
596    * DOCUMENT ME!
597    *
598    * @param nd
599    * DOCUMENT ME!
600    * @param dir
601    * DOCUMENT ME!
602    */
 
603  0 toggle void changeDirection(BinaryNode nd, BinaryNode dir)
604    {
605  0 if (nd == null)
606    {
607  0 return;
608    }
609   
610  0 if (nd.parent() != top)
611    {
612  0 changeDirection((BinaryNode) nd.parent(), nd);
613   
614  0 BinaryNode tmp = (BinaryNode) nd.parent();
615   
616  0 if (dir == nd.left())
617    {
618  0 nd.setParent(dir);
619  0 nd.setLeft(tmp);
620    }
621  0 else if (dir == nd.right())
622    {
623  0 nd.setParent(dir);
624  0 nd.setRight(tmp);
625    }
626    }
627    else
628    {
629  0 if (dir == nd.left())
630    {
631  0 nd.setParent(nd.left());
632   
633  0 if (top.left() == nd)
634    {
635  0 nd.setRight(top.right());
636    }
637    else
638    {
639  0 nd.setRight(top.left());
640    }
641    }
642    else
643    {
644  0 nd.setParent(nd.right());
645   
646  0 if (top.left() == nd)
647    {
648  0 nd.setLeft(top.right());
649    }
650    else
651    {
652  0 nd.setLeft(top.left());
653    }
654    }
655    }
656    }
657   
658    /**
659    * DOCUMENT ME!
660    *
661    * @return DOCUMENT ME!
662    */
 
663  90 toggle public BinaryNode getTopNode()
664    {
665  90 return top;
666    }
667   
668    /**
669    *
670    * @return true if tree has real distances
671    */
 
672  4 toggle public boolean hasDistances()
673    {
674  4 return hasDistances;
675    }
676   
677    /**
678    *
679    * @return true if tree has real bootstrap values
680    */
 
681  4 toggle public boolean hasBootstrap()
682    {
683  4 return hasBootstrap;
684    }
685   
 
686  4 toggle public boolean hasRootDistance()
687    {
688  4 return hasRootDistance;
689    }
690   
691    /**
692    * apply the given transform to all the nodes in the tree.
693    *
694    * @param nodeTransformI
695    */
 
696  3 toggle public void applyToNodes(NodeTransformI nodeTransformI)
697    {
698  67 for (Enumeration<BinaryNode> nodes = node.elements(); nodes
699    .hasMoreElements(); nodeTransformI
700    .transform(nodes.nextElement()))
701    {
702  64 ;
703    }
704    }
705   
 
706  17 toggle public AlignmentView getOriginalData()
707    {
708  17 return seqData;
709    }
710    }
  • Report generated by OpenClover v 4.4.1 on Wed Sep 17 2025 11:01:30 BST using coverage data from Wed Sep 17 2025 11:01:17 BST.
  • OpenClover is free and open-source software.