Clover icon

Coverage Report

  1. Project Clover database Thu Dec 4 2025 16:11:35 GMT
  2. Package jalview.analysis

File Finder.java

 

Coverage histogram

../../img/srcFileCovDistChart10.png
0% of files have more coverage

Code metrics

78
177
20
1
744
393
73
0.41
8.85
20
3.65

Classes

Class Line # Actions
Finder 49 177 73
0.9636363496.4%
 

Contributing tests

This file is covered by 18 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 java.util.ArrayList;
24    import java.util.Arrays;
25    import java.util.Iterator;
26    import java.util.List;
27    import java.util.Locale;
28   
29    import com.stevesoft.pat.Regex;
30   
31    import jalview.api.AlignViewportI;
32    import jalview.api.FeatureRenderer;
33    import jalview.api.FinderI;
34    import jalview.datamodel.AlignmentI;
35    import jalview.datamodel.SearchResultMatchI;
36    import jalview.datamodel.SearchResults;
37    import jalview.datamodel.SearchResultsI;
38    import jalview.datamodel.SequenceFeature;
39    import jalview.datamodel.SequenceGroup;
40    import jalview.datamodel.SequenceI;
41    import jalview.datamodel.features.SequenceFeaturesI;
42    import jalview.util.Comparison;
43    import jalview.util.Platform;
44    import jalview.util.MapList;
45   
46    /**
47    * Implements the search algorithm for the Find dialog
48    */
 
49    public class Finder implements FinderI
50    {
51    /*
52    * matched residue locations
53    */
54    private SearchResultsI searchResults;
55   
56    /*
57    * sequences matched by id or description
58    */
59    private List<SequenceI> idMatches;
60   
61    /*
62    * the viewport to search over
63    */
64    private AlignViewportI viewport;
65   
66    /*
67    * feature renderer model - if available
68    */
69    FeatureRenderer frm = null;
70   
71    /*
72    * sequence index in alignment to search from
73    */
74    private int sequenceIndex;
75   
76    /*
77    * position offset in sequence to search from, base 0
78    * (position after start of last match for a 'find next')
79    */
80    private int residueIndex;
81   
82    /*
83    * last feature matched when incrementally searching sequence features
84    */
85    private SequenceFeature lastFeature;
86   
87    /*
88    * last sequenceIndex used when lastFeature was discovered
89    */
90    private int lastFeatureSequenceIndex;
91   
92    /*
93    * the true sequence position of the start of the
94    * last sequence searched (when 'ignore hidden regions' does not apply)
95    */
96    private int searchedSequenceStartPosition;
97   
98    /*
99    * when 'ignore hidden regions' applies, this holds the mapping from
100    * the visible sequence positions (1, 2, ...) to true sequence positions
101    */
102    private MapList searchedSequenceMap;
103   
104    private String seqToSearch;
105   
106    /**
107    * Constructor for searching a viewport
108    *
109    * @param av
110    */
 
111  38 toggle public Finder(AlignViewportI av)
112    {
113  38 this.viewport = av;
114  38 this.sequenceIndex = 0;
115  38 this.residueIndex = -1;
116    }
117   
 
118  32 toggle @Override
119    public void findAll(String theSearchString, boolean matchCase,
120    boolean searchDescription, boolean searchFeatureDesc,
121    boolean ignoreHidden)
122    {
123    /*
124    * search from the start
125    */
126  32 lastFeature = null;
127  32 lastFeatureSequenceIndex = 0;
128  32 sequenceIndex = 0;
129  32 residueIndex = -1;
130   
131  32 doFind(theSearchString, matchCase, searchDescription, searchFeatureDesc,
132    true, ignoreHidden);
133   
134    /*
135    * reset to start for next search
136    */
137  32 sequenceIndex = 0;
138  32 residueIndex = -1;
139  32 lastFeature = null;
140  32 lastFeatureSequenceIndex = 0;
141    }
142   
 
143  23 toggle @Override
144    public void findNext(String theSearchString, boolean matchCase,
145    boolean searchDescription, boolean searchFeatureDesc,
146    boolean ignoreHidden)
147    {
148  23 doFind(theSearchString, matchCase, searchDescription, searchFeatureDesc,
149    false, ignoreHidden);
150   
151  23 if (searchResults.isEmpty() && idMatches.isEmpty())
152    {
153    /*
154    * search failed - reset to start for next search
155    */
156  3 sequenceIndex = 0;
157  3 residueIndex = -1;
158  3 lastFeature = null;
159  3 lastFeatureSequenceIndex = 0;
160    }
161    }
162   
163    /**
164    * Performs a 'find next' or 'find all'
165    *
166    * @param theSearchString
167    * @param matchCase
168    * @param searchDescription
169    * @param findAll
170    * @param ignoreHidden
171    */
 
172  55 toggle protected void doFind(String theSearchString, boolean matchCase,
173    boolean searchDescription, boolean searchFeatureDesc,
174    boolean findAll, boolean ignoreHidden)
175    {
176  55 searchResults = new SearchResults();
177  55 idMatches = new ArrayList<>();
178   
179  55 String searchString = matchCase ? theSearchString
180    : theSearchString.toUpperCase(Locale.ROOT);
181  55 Regex searchPattern = Platform.newRegex(searchString);
182  55 searchPattern.setIgnoreCase(!matchCase);
183   
184  55 SequenceGroup selection = viewport.getSelectionGroup();
185  55 if (selection != null && selection.getSize() < 1)
186    {
187  0 selection = null; // ? ignore column-only selection
188    }
189   
190  55 AlignmentI alignment = viewport.getAlignment();
191  55 int end = alignment.getHeight();
192   
193  55 getSequence(ignoreHidden);
194   
195  55 boolean found = false;
196  272 while ((!found || findAll) && sequenceIndex < end)
197    {
198  217 found = findNextMatch(searchString, searchPattern, searchDescription,
199    searchFeatureDesc, ignoreHidden);
200    }
201    }
202   
203    /**
204    * Calculates and saves the sequence string to search. The string is
205    * restricted to the current selection region if there is one, and is saved
206    * with all gaps removed.
207    * <p>
208    * If there are hidden columns, and option {@ignoreHidden} is selected, then
209    * only visible positions of the sequence are included, and a mapping is also
210    * constructed from the returned string positions to the true sequence
211    * positions.
212    * <p>
213    * Note we have to do this each time {@code findNext} or {@code findAll} is
214    * called, in case the alignment, selection group or hidden columns have
215    * changed. In particular, if the sequence at offset {@code sequenceIndex} in
216    * the alignment is (no longer) in the selection group, search is advanced to
217    * the next sequence that is.
218    * <p>
219    * Sets sequence string to the empty string if there are no more sequences (in
220    * selection group if any) at or after {@code sequenceIndex}.
221    * <p>
222    * Returns true if a sequence could be found, false if end of alignment was
223    * reached
224    *
225    * @param ignoreHidden
226    * @return
227    */
 
228  207 toggle private boolean getSequence(boolean ignoreHidden)
229    {
230  207 AlignmentI alignment = viewport.getAlignment();
231  207 if (sequenceIndex >= alignment.getHeight())
232    {
233  35 seqToSearch = "";
234  35 return false;
235    }
236  172 SequenceI seq = alignment.getSequenceAt(sequenceIndex);
237  172 SequenceGroup selection = viewport.getSelectionGroup();
238  172 if (selection != null && !selection.contains(seq))
239    {
240  9 if (!nextSequence(ignoreHidden))
241    {
242  4 return false;
243    }
244  5 seq = alignment.getSequenceAt(sequenceIndex);
245    }
246   
247  168 String seqString = null;
248  168 if (ignoreHidden)
249    {
250  33 seqString = getVisibleSequence(seq);
251  33 this.searchedSequenceStartPosition = 1;
252    }
253    else
254    {
255  135 int startCol = 0;
256  135 int endCol = seq.getLength() - 1;
257  135 this.searchedSequenceStartPosition = seq.getStart();
258  135 if (selection != null)
259    {
260  21 startCol = selection.getStartRes();
261  21 endCol = Math.min(endCol, selection.getEndRes());
262  21 this.searchedSequenceStartPosition = seq.findPosition(startCol);
263    }
264  135 seqString = seq.getSequenceAsString(startCol, endCol + 1);
265    }
266   
267    /*
268    * remove gaps; note that even if this leaves an empty string, we 'search'
269    * the sequence anyway (for possible match on name or description)
270    */
271  168 String ungapped = AlignSeq.extractGaps(Comparison.GapChars, seqString);
272  168 this.seqToSearch = ungapped;
273   
274  168 return true;
275    }
276   
277    /**
278    * Returns a string consisting of only the visible residues of {@code seq}
279    * from alignment column {@ fromColumn}, restricted to the current selection
280    * region if there is one.
281    * <p>
282    * As a side-effect, also computes the mapping from the true sequence
283    * positions to the positions (1, 2, ...) of the returned sequence. This is to
284    * allow search matches in the visible sequence to be converted to sequence
285    * positions.
286    *
287    * @param seq
288    * @return
289    */
 
290  33 toggle private String getVisibleSequence(SequenceI seq)
291    {
292    /*
293    * get start / end columns of sequence and convert to base 0
294    * (so as to match the visible column ranges)
295    */
296  33 int seqStartCol = seq.findIndex(seq.getStart()) - 1;
297  33 int seqEndCol = seq.findIndex(seq.getStart() + seq.getLength() - 1) - 1;
298  33 Iterator<int[]> visibleColumns = viewport.getViewAsVisibleContigs(true);
299  33 StringBuilder visibleSeq = new StringBuilder(seqEndCol - seqStartCol);
300  33 List<int[]> fromRanges = new ArrayList<>();
301   
302  93 while (visibleColumns.hasNext())
303    {
304  63 int[] range = visibleColumns.next();
305  63 if (range[0] > seqEndCol)
306    {
307    // beyond the end of the sequence
308  3 break;
309    }
310  60 if (range[1] < seqStartCol)
311    {
312    // before the start of the sequence
313  3 continue;
314    }
315  57 String subseq = seq.getSequenceAsString(range[0], range[1] + 1);
316  57 String ungapped = AlignSeq.extractGaps(Comparison.GapChars, subseq);
317  57 visibleSeq.append(ungapped);
318  57 if (!ungapped.isEmpty())
319    {
320    /*
321    * visible region includes at least one non-gap character,
322    * so add the range to the mapping being constructed
323    */
324  57 int seqResFrom = seq.findPosition(range[0]);
325  57 int seqResTo = seqResFrom + ungapped.length() - 1;
326  57 fromRanges.add(new int[] { seqResFrom, seqResTo });
327    }
328    }
329   
330    /*
331    * construct the mapping
332    * from: visible sequence positions 1..length
333    * to: true residue positions of the alignment sequence
334    */
335  33 List<int[]> toRange = Arrays
336    .asList(new int[]
337    { 1, visibleSeq.length() });
338  33 searchedSequenceMap = new MapList(fromRanges, toRange, 1, 1);
339   
340  33 return visibleSeq.toString();
341    }
342   
343    /**
344    * Advances the search to the next sequence in the alignment. Sequences not in
345    * the current selection group (if there is one) are skipped. The
346    * (sub-)sequence to be searched is extracted, gaps removed, and saved, or set
347    * to null if there are no more sequences to search.
348    * <p>
349    * Returns true if a sequence could be found, false if end of alignment was
350    * reached
351    *
352    * @param ignoreHidden
353    */
 
354  152 toggle private boolean nextSequence(boolean ignoreHidden)
355    {
356  152 sequenceIndex++;
357  152 residueIndex = -1;
358   
359  152 return getSequence(ignoreHidden);
360    }
361   
362    /**
363    * Finds the next match in the given sequence, starting at offset
364    * {@code residueIndex}. Answers true if a match is found, else false.
365    * <p>
366    * If a match is found, {@code residueIndex} is advanced to the position after
367    * the start of the matched region, ready for the next search.
368    * <p>
369    * If no match is found, {@code sequenceIndex} is advanced ready to search the
370    * next sequence.
371    *
372    * @param seqToSearch
373    * @param searchString
374    * @param searchPattern
375    * @param matchDescription
376    * @param ignoreHidden
377    * @return
378    */
 
379  217 toggle protected boolean findNextMatch(String searchString, Regex searchPattern,
380    boolean matchDescription, boolean matchFeatureDesc,
381    boolean ignoreHidden)
382    {
383  217 if (residueIndex < 0)
384    {
385    /*
386    * at start of sequence; try find by residue number, in sequence id,
387    * or (optionally) in sequence description
388    */
389  153 if (doNonMotifSearches(searchString, searchPattern, matchDescription))
390    {
391  17 return true;
392    }
393    }
394   
395    /*
396    * search for next match in sequence string
397    */
398  200 int end = seqToSearch.length();
399  354 while (residueIndex < end)
400    {
401  211 boolean matched = searchPattern.searchFrom(seqToSearch, residueIndex);
402  211 if (matched)
403    {
404  72 if (recordMatch(searchPattern, ignoreHidden))
405    {
406  51 return true;
407    }
408    }
409    else
410    {
411  139 if (matchFeatureDesc)
412    {
413  17 matched = searchSequenceFeatures(residueIndex, searchPattern);
414  17 if (matched)
415    {
416  6 return true;
417    }
418  11 lastFeature = null;
419    }
420  133 residueIndex = Integer.MAX_VALUE;
421    }
422    }
423   
424  143 nextSequence(ignoreHidden);
425  143 return false;
426    }
427   
428    /**
429    * Adds the match held in the <code>searchPattern</code> Regex to the
430    * <code>searchResults</code>, unless it is a subregion of the last match
431    * recorded. <code>residueIndex</code> is advanced to the position after the
432    * start of the matched region, ready for the next search. Answers true if a
433    * match was added, else false.
434    * <p>
435    * Matches that lie entirely within hidden regions of the alignment are not
436    * added.
437    *
438    * @param searchPattern
439    * @param ignoreHidden
440    * @return
441    */
 
442  72 toggle protected boolean recordMatch(Regex searchPattern, boolean ignoreHidden)
443    {
444  72 SequenceI seq = viewport.getAlignment().getSequenceAt(sequenceIndex);
445   
446    /*
447    * convert start/end of the match to sequence coordinates
448    */
449  72 int offset = searchPattern.matchedFrom();
450  72 int matchStartPosition = this.searchedSequenceStartPosition + offset;
451  72 int matchEndPosition = matchStartPosition + searchPattern.charsMatched()
452    - 1;
453   
454    /*
455    * update residueIndex to next position after the start of the match
456    * (findIndex returns a value base 1, columnIndex is held base 0)
457    */
458  72 residueIndex = searchPattern.matchedFrom() + 1;
459   
460    /*
461    * return false if the match is entirely in a hidden region
462    */
463  72 if (allHidden(seq, matchStartPosition, matchEndPosition))
464    {
465  5 return false;
466    }
467   
468    /*
469    * check that this match is not a subset of the previous one (JAL-2302)
470    */
471  67 List<SearchResultMatchI> matches = searchResults.getResults();
472  67 SearchResultMatchI lastMatch = matches.isEmpty() ? null
473    : matches.get(matches.size() - 1);
474   
475  67 if (lastMatch == null || !lastMatch.contains(seq, matchStartPosition,
476    matchEndPosition))
477    {
478  51 addMatch(seq, matchStartPosition, matchEndPosition, ignoreHidden);
479  51 return true;
480    }
481   
482  16 return false;
483    }
484   
485    /**
486    * Adds one match to the stored list. If hidden residues are being skipped,
487    * then the match may need to be split into contiguous positions of the
488    * sequence (so it does not include skipped residues).
489    *
490    * @param seq
491    * @param matchStartPosition
492    * @param matchEndPosition
493    * @param ignoreHidden
494    */
 
495  51 toggle private void addMatch(SequenceI seq, int matchStartPosition,
496    int matchEndPosition, boolean ignoreHidden)
497    {
498  51 if (!ignoreHidden)
499    {
500    /*
501    * simple case
502    */
503  46 searchResults.addResult(seq, matchStartPosition, matchEndPosition);
504  46 return;
505    }
506   
507    /*
508    * get start-end contiguous ranges in underlying sequence
509    */
510  5 int[] truePositions = searchedSequenceMap
511    .locateInFrom(matchStartPosition, matchEndPosition);
512  5 searchResults.addResult(seq, truePositions);
513    }
514   
515    /**
516    * Returns true if all residues are hidden, else false
517    *
518    * @param seq
519    * @param fromPos
520    * @param toPos
521    * @return
522    */
 
523  72 toggle private boolean allHidden(SequenceI seq, int fromPos, int toPos)
524    {
525  72 if (!viewport.hasHiddenColumns())
526    {
527  49 return false;
528    }
529  28 for (int res = fromPos; res <= toPos; res++)
530    {
531  23 if (isVisible(seq, res))
532    {
533  18 return false;
534    }
535    }
536  5 return true;
537    }
538   
539    /**
540    * Does searches other than for residue patterns. Currently this includes
541    * <ul>
542    * <li>find residue by position (if search string is a number)</li>
543    * <li>match search string to sequence id</li>
544    * <li>match search string to sequence description (optional)</li>
545    * </ul>
546    * Answers true if a match is found, else false.
547    *
548    * @param searchString
549    * @param searchPattern
550    * @param includeDescription
551    * @return
552    */
 
553  153 toggle protected boolean doNonMotifSearches(String searchString,
554    Regex searchPattern, boolean includeDescription)
555    {
556  153 SequenceI seq = viewport.getAlignment().getSequenceAt(sequenceIndex);
557   
558    /*
559    * position sequence search to start of sequence
560    */
561  153 residueIndex = 0;
562  153 try
563    {
564  153 int res = Integer.parseInt(searchString);
565  5 return searchForResidueNumber(seq, res);
566    } catch (NumberFormatException ex)
567    {
568    // search pattern is not a number
569    }
570   
571  148 if (searchSequenceName(seq, searchPattern))
572    {
573  10 return true;
574    }
575  138 if (includeDescription && searchSequenceDescription(seq, searchPattern))
576    {
577  4 return true;
578    }
579  134 return false;
580    }
581   
582    /**
583    * Searches for a match with the sequence features, and if found, adds the
584    * sequence to the list of match ids, (but not as a duplicate). Answers true
585    * if a match was added, else false.
586    *
587    * @param seq
588    * @param searchPattern
589    * @return
590    */
 
591  17 toggle protected boolean searchSequenceFeatures(int from, Regex searchPattern)
592    {
593  17 if (lastFeatureSequenceIndex != sequenceIndex)
594    {
595  9 lastFeatureSequenceIndex = sequenceIndex;
596  9 lastFeature = null;
597    }
598  17 SequenceI seq = viewport.getAlignment().getSequenceAt(sequenceIndex);
599  17 SequenceFeaturesI sf = seq.getFeatures();
600   
601    // TODO - stash feature list and search incrementally
602  17 List<SequenceFeature> allFeatures = null;
603  17 if (frm != null)
604    {
605  0 allFeatures = frm.findFeaturesAtResidue(seq, seq.getStart(),
606    seq.getEnd());
607    }
608    else
609    {
610    // allFeatures = sf.getAllFeatures(null);
611  17 allFeatures = sf.getAllFeatures();
612    }
613    // so we can check we are advancing when debugging
614  17 long fpos = 0;
615   
616  17 for (SequenceFeature feature : allFeatures)
617    {
618  15 fpos++;
619  15 if (lastFeature != null)
620    {
621    // iterate till we find last feature matched
622  6 if (lastFeature != feature)
623    {
624  1 continue;
625    }
626    else
627    {
628  5 lastFeature = null;
629  5 continue;
630    }
631    }
632   
633  9 if (searchPattern.search(feature.type) || (feature.description != null
634    && searchPattern.search(feature.description)))
635    {
636  6 searchResults.addResult(seq, feature.getBegin(), feature.getEnd());
637  6 lastFeature = feature;
638  6 return true;
639    }
640    }
641  11 residueIndex = Integer.MAX_VALUE;
642  11 lastFeature = null;
643  11 return false;
644    }
645   
646    /**
647    * Searches for a match with the sequence description, and if found, adds the
648    * sequence to the list of match ids (but not as a duplicate). Answers true if
649    * a match was added, else false.
650    *
651    * @param seq
652    * @param searchPattern
653    * @return
654    */
 
655  11 toggle protected boolean searchSequenceDescription(SequenceI seq,
656    Regex searchPattern)
657    {
658  11 String desc = seq.getDescription();
659  11 if (desc != null && searchPattern.search(desc)
660    && !idMatches.contains(seq))
661    {
662  4 idMatches.add(seq);
663  4 return true;
664    }
665  7 return false;
666    }
667   
668    /**
669    * Searches for a match with the sequence name, and if found, adds the
670    * sequence to the list of match ids (but not as a duplicate). Answers true if
671    * a match was added, else false.
672    *
673    * @param seq
674    * @param searchPattern
675    * @return
676    */
 
677  148 toggle protected boolean searchSequenceName(SequenceI seq, Regex searchPattern)
678    {
679  148 if (searchPattern.search(seq.getName()) && !idMatches.contains(seq))
680    {
681  10 idMatches.add(seq);
682  10 return true;
683    }
684  138 return false;
685    }
686   
687    /**
688    * If the residue position is valid for the sequence, and in a visible column,
689    * adds the position to the search results and returns true, else answers
690    * false.
691    *
692    * @param seq
693    * @param resNo
694    * @return
695    */
 
696  5 toggle protected boolean searchForResidueNumber(SequenceI seq, int resNo)
697    {
698  5 if (seq.getStart() <= resNo && seq.getEnd() >= resNo)
699    {
700  3 if (isVisible(seq, resNo))
701    {
702  3 searchResults.addResult(seq, resNo, resNo);
703  3 return true;
704    }
705    }
706  2 return false;
707    }
708   
709    /**
710    * Returns true if the residue is in a visible column, else false
711    *
712    * @param seq
713    * @param res
714    * @return
715    */
 
716  26 toggle private boolean isVisible(SequenceI seq, int res)
717    {
718  26 if (!viewport.hasHiddenColumns())
719    {
720  0 return true;
721    }
722  26 int col = seq.findIndex(res); // base 1
723  26 return viewport.getAlignment().getHiddenColumns().isVisible(col - 1); // base
724    // 0
725    }
726   
 
727  30 toggle @Override
728    public List<SequenceI> getIdMatches()
729    {
730  30 return idMatches;
731    }
732   
 
733  62 toggle @Override
734    public SearchResultsI getSearchResults()
735    {
736  62 return searchResults;
737    }
738   
 
739  0 toggle @Override
740    public void setFeatureRenderer(FeatureRenderer featureRenderer)
741    {
742  0 frm = featureRenderer;
743    }
744    }
  • Report generated by OpenClover v 4.4.1 on Thu Dec 4 2025 16:21:53 GMT using coverage data from Thu Dec 4 2025 16:21:39 GMT.
  • OpenClover is free and open-source software.