Clover icon

Coverage Report

  1. Project Clover database Thu Aug 13 2020 12:04:21 BST
  2. Package jalview.analysis

File Finder.java

 

Coverage histogram

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

Code metrics

50
107
14
1
468
242
51
0.48
7.64
14
3.64

Classes

Class Line # Actions
Finder 43 107 51
0.988304198.8%
 

Contributing tests

This file is covered by 15 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.api.AlignViewportI;
24    import jalview.api.FinderI;
25    import jalview.datamodel.AlignmentI;
26    import jalview.datamodel.Range;
27    import jalview.datamodel.SearchResultMatchI;
28    import jalview.datamodel.SearchResults;
29    import jalview.datamodel.SearchResultsI;
30    import jalview.datamodel.SequenceGroup;
31    import jalview.datamodel.SequenceI;
32    import jalview.datamodel.VisibleContigsIterator;
33    import jalview.util.Comparison;
34   
35    import java.util.List;
36    import java.util.Vector;
37   
38    import com.stevesoft.pat.Regex;
39   
40    /**
41    * Implements the search algorithm for the Find dialog
42    */
 
43    public class Finder implements FinderI
44    {
45    /*
46    * matched residue locations
47    */
48    private SearchResultsI searchResults;
49   
50    /*
51    * sequences matched by id or description
52    */
53    private Vector<SequenceI> idMatches;
54   
55    /*
56    * the viewport to search over
57    */
58    private AlignViewportI viewport;
59   
60    /*
61    * sequence index in alignment to search from
62    */
63    private int sequenceIndex;
64   
65    /*
66    * column position in sequence to search from, base 0
67    * - absolute column number including any hidden columns
68    * (position after start of last match for a repeat search)
69    */
70    private int columnIndex;
71   
72    /**
73    * Constructor for searching a viewport
74    *
75    * @param av
76    */
 
77  31 toggle public Finder(AlignViewportI av)
78    {
79  31 this.viewport = av;
80  31 this.sequenceIndex = 0;
81  31 this.columnIndex = -1;
82    }
83   
 
84  22 toggle @Override
85    public void findAll(String theSearchString, boolean matchCase,
86    boolean searchDescription)
87    {
88    /*
89    * search from the start
90    */
91  22 sequenceIndex = 0;
92  22 columnIndex = -1;
93   
94  22 doFind(theSearchString, matchCase, searchDescription, true);
95   
96    /*
97    * reset to start for next search
98    */
99  22 sequenceIndex = 0;
100  22 columnIndex = -1;
101    }
102   
 
103  18 toggle @Override
104    public void findNext(String theSearchString, boolean matchCase,
105    boolean searchDescription)
106    {
107  18 doFind(theSearchString, matchCase, searchDescription, false);
108   
109  18 if (searchResults.isEmpty() && idMatches.isEmpty())
110    {
111    /*
112    * search failed - reset to start for next search
113    */
114  3 sequenceIndex = 0;
115  3 columnIndex = -1;
116    }
117    }
118   
119    /**
120    * Performs a 'find next' or 'find all'
121    *
122    * @param theSearchString
123    * @param matchCase
124    * @param searchDescription
125    * @param findAll
126    */
 
127  40 toggle protected void doFind(String theSearchString, boolean matchCase,
128    boolean searchDescription, boolean findAll)
129    {
130  40 String searchString = matchCase ? theSearchString
131    : theSearchString.toUpperCase();
132  40 Regex searchPattern = new Regex(searchString);
133  40 searchPattern.setIgnoreCase(!matchCase);
134   
135  40 searchResults = new SearchResults();
136  40 idMatches = new Vector<>();
137   
138  40 SequenceGroup selection = viewport.getSelectionGroup();
139  40 if (selection != null && selection.getSize() < 1)
140    {
141  0 selection = null; // ? ignore column-only selection
142    }
143   
144  40 AlignmentI alignment = viewport.getAlignment();
145  40 int end = alignment.getHeight();
146   
147  202 while (sequenceIndex < end)
148    {
149  177 SequenceI seq = alignment.getSequenceAt(sequenceIndex);
150  177 boolean found = findNextMatch(seq, searchString, searchPattern,
151    searchDescription);
152  177 if (found && !findAll)
153    {
154  15 return;
155    }
156  162 if (!found)
157    {
158  108 sequenceIndex++;
159  108 columnIndex = -1;
160    }
161    }
162    }
163   
164    /**
165    * Answers the start-end column range of the visible region of
166    * <code>sequence</code> starting at or after the given <code>column</code>.
167    * If there are no hidden columns, this just returns the remaining width of
168    * the sequence. The range is restricted to the current <code>selection</code>
169    * if there is one. Answers null if there are no visible columns at or after
170    * <code>column</code>.
171    */
 
172  170 toggle protected Range getNextVisibleSequenceRegion(SequenceI sequence,
173    int column)
174    {
175  170 int seqColStart = column;
176  170 int seqColEnd = sequence.getLength() - 1;
177   
178    /*
179    * restrict search to (next) visible column region,
180    * in case there are hidden columns
181    */
182  170 AlignmentI alignment = viewport.getAlignment();
183  170 VisibleContigsIterator visibleRegions = alignment.getHiddenColumns()
184    .getVisContigsIterator(column, alignment.getWidth(),
185    false);
186  170 int[] visible = visibleRegions.hasNext() ? visibleRegions.next() : null;
187  170 if (visible == null)
188    {
189  2 columnIndex = seqColEnd + 1;
190  2 return null;
191    }
192  168 seqColStart = Math.max(seqColStart, visible[0]);
193  168 seqColEnd = Math.min(seqColEnd, visible[1]);
194   
195    /*
196    * restrict search to selected region if there is one
197    */
198  168 SequenceGroup selection = viewport.getSelectionGroup();
199  168 if (selection != null)
200    {
201  30 int selectionStart = selection.getStartRes();
202  30 int selectionEnd = selection.getEndRes();
203  30 if (selectionStart > seqColEnd || selectionEnd < seqColStart)
204    {
205    /*
206    * sequence region doesn't overlap selection region
207    */
208  10 columnIndex = seqColEnd + 1;
209  10 return null;
210    }
211  20 seqColStart = Math.max(seqColStart, selectionStart);
212  20 seqColEnd = Math.min(seqColEnd, selectionEnd);
213    }
214   
215  158 return new Range(seqColStart, seqColEnd);
216    }
217   
218    /**
219    * Finds the next match in the given sequence, starting at column at
220    * <code>columnIndex</code>. Answers true if a match is found, else false. If
221    * a match is found, <code>columnIndex</code> is advanced to the column after
222    * the start of the matched region, ready for a search from the next position.
223    *
224    * @param seq
225    * @param searchString
226    * @param searchPattern
227    * @param matchDescription
228    * @return
229    */
 
230  177 toggle protected boolean findNextMatch(SequenceI seq, String searchString,
231    Regex searchPattern, boolean matchDescription)
232    {
233  177 SequenceGroup selection = viewport.getSelectionGroup();
234  177 if (selection != null && !selection.contains(seq))
235    {
236    /*
237    * this sequence is not in the selection - advance to next sequence
238    */
239  9 return false;
240    }
241   
242  168 if (columnIndex < 0)
243    {
244    /*
245    * at start of sequence; try find by residue number, in sequence id,
246    * or (optionally) in sequence description
247    */
248  107 if (doNonMotifSearches(seq, searchString, searchPattern,
249    matchDescription))
250    {
251  17 return true;
252    }
253    }
254   
255    /*
256    * search for next match in sequence string
257    */
258  151 int end = seq.getLength();
259  269 while (columnIndex < end)
260    {
261  170 if (searchNextVisibleRegion(seq, searchPattern))
262    {
263  52 return true;
264    }
265    }
266  99 return false;
267    }
268   
269    /**
270    * Searches the sequence, starting from <code>columnIndex</code>, and adds the
271    * next match (if any) to <code>searchResults</code>. The search is restricted
272    * to the next visible column region, and to the <code>selection</code> region
273    * if there is one. Answers true if a match is added, else false.
274    *
275    * @param seq
276    * @param searchPattern
277    * @return
278    */
 
279  170 toggle protected boolean searchNextVisibleRegion(SequenceI seq, Regex searchPattern)
280    {
281  170 Range visible = getNextVisibleSequenceRegion(seq, columnIndex);
282  170 if (visible == null)
283    {
284  12 return false;
285    }
286  158 String seqString = seq.getSequenceAsString(visible.start, visible.end + 1);
287  158 String noGaps = AlignSeq.extractGaps(Comparison.GapChars, seqString);
288   
289  158 if (searchPattern.search(noGaps))
290    {
291  52 int sequenceStartPosition = seq.findPosition(visible.start);
292  52 recordMatch(seq, searchPattern, sequenceStartPosition);
293  52 return true;
294    }
295    else
296    {
297    /*
298    * no match - advance columnIndex past this visible region
299    * so the next visible region (if any) is searched next
300    */
301  106 columnIndex = visible.end + 1;
302    }
303   
304  106 return false;
305    }
306   
307    /**
308    * Adds the match held in the <code>searchPattern</code> Regex to the
309    * <code>searchResults</code>, unless it is a subregion of the last match
310    * recorded. <code>columnIndex</code> is advanced to the position after the
311    * start of the matched region, ready for the next search. Answers true if a
312    * match was added, else false.
313    *
314    * @param seq
315    * @param searchPattern
316    * @param firstResiduePosition
317    * @return
318    */
 
319  52 toggle protected boolean recordMatch(SequenceI seq, Regex searchPattern,
320    int firstResiduePosition)
321    {
322    /*
323    * get start/end of the match in sequence coordinates
324    */
325  52 int offset = searchPattern.matchedFrom();
326  52 int matchStartPosition = firstResiduePosition + offset;
327  52 int matchEndPosition = matchStartPosition
328    + searchPattern.charsMatched() - 1;
329   
330    /*
331    * update columnIndex to next column after the start of the match
332    * (findIndex returns a value base 1, columnIndex is held base 0)
333    */
334  52 columnIndex = seq.findIndex(matchStartPosition);
335   
336    /*
337    * check that this match is not a subset of the previous one (JAL-2302)
338    */
339  52 List<SearchResultMatchI> matches = searchResults.getResults();
340  52 SearchResultMatchI lastMatch = matches.isEmpty() ? null
341    : matches.get(matches.size() - 1);
342   
343  52 if (lastMatch == null || !lastMatch.contains(seq, matchStartPosition,
344    matchEndPosition))
345    {
346  36 searchResults.addResult(seq, matchStartPosition, matchEndPosition);
347  36 return true;
348    }
349   
350  16 return false;
351    }
352   
353    /**
354    * Does searches other than for residue patterns. Currently this includes
355    * <ul>
356    * <li>find residue by position (if search string is a number)</li>
357    * <li>match search string to sequence id</li>
358    * <li>match search string to sequence description (optional)</li>
359    * </ul>
360    * Answers true if a match is found, else false.
361    *
362    * @param seq
363    * @param searchString
364    * @param searchPattern
365    * @param includeDescription
366    * @return
367    */
 
368  107 toggle protected boolean doNonMotifSearches(SequenceI seq, String searchString,
369    Regex searchPattern, boolean includeDescription)
370    {
371    /*
372    * position sequence search to start of sequence
373    */
374  107 columnIndex = 0;
375   
376  107 if (searchForResidueNumber(seq, searchString))
377    {
378  3 return true;
379    }
380  104 if (searchSequenceName(seq, searchPattern))
381    {
382  10 return true;
383    }
384  94 if (includeDescription && searchSequenceDescription(seq, searchPattern))
385    {
386  4 return true;
387    }
388  90 return false;
389    }
390   
391    /**
392    * Searches for a match with the sequence description, and if found, adds the
393    * sequence to the list of match ids (but not as a duplicate). Answers true if
394    * a match was added, else false.
395    *
396    * @param seq
397    * @param searchPattern
398    * @return
399    */
 
400  11 toggle protected boolean searchSequenceDescription(SequenceI seq, Regex searchPattern)
401    {
402  11 String desc = seq.getDescription();
403  11 if (desc != null && searchPattern.search(desc) && !idMatches.contains(seq))
404    {
405  4 idMatches.addElement(seq);
406  4 return true;
407    }
408  7 return false;
409    }
410   
411    /**
412    * Searches for a match with the sequence name, and if found, adds the
413    * sequence to the list of match ids (but not as a duplicate). Answers true if
414    * a match was added, else false.
415    *
416    * @param seq
417    * @param searchPattern
418    * @return
419    */
 
420  104 toggle protected boolean searchSequenceName(SequenceI seq, Regex searchPattern)
421    {
422  104 if (searchPattern.search(seq.getName()) && !idMatches.contains(seq))
423    {
424  10 idMatches.addElement(seq);
425  10 return true;
426    }
427  94 return false;
428    }
429   
430    /**
431    * Tries to interpret the search string as a residue position, and if valid,
432    * adds the position to the search results and returns true, else answers
433    * false
434    */
 
435  107 toggle protected boolean searchForResidueNumber(SequenceI seq, String searchString)
436    {
437  107 try
438    {
439  107 int res = Integer.parseInt(searchString);
440  5 if (seq.getStart() <= res && seq.getEnd() >= res)
441    {
442  3 searchResults.addResult(seq, res, res);
443  3 return true;
444    }
445    } catch (NumberFormatException ex)
446    {
447    }
448  104 return false;
449    }
450   
451    /* (non-Javadoc)
452    * @see jalview.analysis.FinderI#getIdMatch()
453    */
 
454  30 toggle @Override
455    public Vector<SequenceI> getIdMatches()
456    {
457  30 return idMatches;
458    }
459   
460    /* (non-Javadoc)
461    * @see jalview.analysis.FinderI#getSearchResults()
462    */
 
463  43 toggle @Override
464    public SearchResultsI getSearchResults()
465    {
466  43 return searchResults;
467    }
468    }