Clover icon

Coverage Report

  1. Project Clover database Thu Nov 7 2024 17:01:39 GMT
  2. Package jalview.analysis

File Finder.java

 

Coverage histogram

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

Code metrics

78
177
20
1
743
392
73
0.41
8.85
20
3.65

Classes

Class Line # Actions
Finder 48 177 73
0.00%
 

Contributing tests

No tests hitting this source file were found.

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