*/
package jalview.analysis;
+import java.util.Locale;
+
+import jalview.api.AlignViewportI;
+import jalview.api.FinderI;
import jalview.datamodel.AlignmentI;
import jalview.datamodel.SearchResultMatchI;
import jalview.datamodel.SearchResults;
import jalview.datamodel.SearchResultsI;
import jalview.datamodel.SequenceGroup;
import jalview.datamodel.SequenceI;
-import jalview.datamodel.VisibleContigsIterator;
import jalview.util.Comparison;
+import jalview.util.MapList;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Iterator;
import java.util.List;
-import java.util.Vector;
import com.stevesoft.pat.Regex;
/**
* Implements the search algorithm for the Find dialog
*/
-public class Finder
+public class Finder implements FinderI
{
/*
* matched residue locations
/*
* sequences matched by id or description
*/
- private Vector<SequenceI> idMatch;
-
- /*
- * the alignment to search over
- */
- private AlignmentI alignment;
+ private List<SequenceI> idMatches;
/*
- * (optional) selection to restrict search to
+ * the viewport to search over
*/
- private SequenceGroup selection;
+ private AlignViewportI viewport;
/*
- * set true for case-sensitive search (default is false)
+ * sequence index in alignment to search from
*/
- private boolean caseSensitive;
+ private int sequenceIndex;
/*
- * set true to search sequence description (default is false)
+ * position offset in sequence to search from, base 0
+ * (position after start of last match for a 'find next')
*/
- private boolean includeDescription;
+ private int residueIndex;
/*
- * set true to return all matches (default is next match only)
+ * the true sequence position of the start of the
+ * last sequence searched (when 'ignore hidden regions' does not apply)
*/
- private boolean findAll;
+ private int searchedSequenceStartPosition;
/*
- * sequence index in alignment to search from
+ * when 'ignore hidden regions' applies, this holds the mapping from
+ * the visible sequence positions (1, 2, ...) to true sequence positions
*/
- private int sequenceIndex;
+ private MapList searchedSequenceMap;
- /*
- * column position in sequence to search from, base 0
- * - absolute column number including any hidden columns
- * (position of last match for a repeat search)
- */
- private int columnIndex;
+ private String seqToSearch;
/**
- * Constructor to start searching an alignment, optionally restricting results
- * to a selection
+ * Constructor for searching a viewport
*
- * @param al
- * @param sel
+ * @param av
*/
- public Finder(AlignmentI al, SequenceGroup sel)
+ public Finder(AlignViewportI av)
{
- this(al, sel, 0, -1);
+ this.viewport = av;
+ this.sequenceIndex = 0;
+ this.residueIndex = -1;
}
- /**
- * Constructor to resume search at given sequence and residue on alignment and
- * (optionally) restricted to a selection
- *
- * @param al
- * @param sel
- * @param seqindex
- * @param colindex
- */
- public Finder(AlignmentI al, SequenceGroup sel, int seqindex,
- int colindex)
+ @Override
+ public void findAll(String theSearchString, boolean matchCase,
+ boolean searchDescription, boolean ignoreHidden)
+ {
+ /*
+ * search from the start
+ */
+ sequenceIndex = 0;
+ residueIndex = -1;
+
+ doFind(theSearchString, matchCase, searchDescription, true,
+ ignoreHidden);
+
+ /*
+ * reset to start for next search
+ */
+ sequenceIndex = 0;
+ residueIndex = -1;
+ }
+
+ @Override
+ public void findNext(String theSearchString, boolean matchCase,
+ boolean searchDescription, boolean ignoreHidden)
{
- this.alignment = al;
- this.selection = sel;
- this.sequenceIndex = seqindex;
- this.columnIndex = colindex;
+ doFind(theSearchString, matchCase, searchDescription, false,
+ ignoreHidden);
+
+ if (searchResults.isEmpty() && idMatches.isEmpty())
+ {
+ /*
+ * search failed - reset to start for next search
+ */
+ sequenceIndex = 0;
+ residueIndex = -1;
+ }
}
/**
- * Performs a find for the given search string. By default the next match is
- * found, but if setFindAll(true) has been called, then all matches are found.
- * Sequences matched by id or description can be retrieved by getIdMatch(),
- * and matched residue patterns by getSearchResults().
+ * Performs a 'find next' or 'find all'
*
* @param theSearchString
- * @return
+ * @param matchCase
+ * @param searchDescription
+ * @param findAll
+ * @param ignoreHidden
*/
- public void find(String theSearchString)
+ protected void doFind(String theSearchString, boolean matchCase,
+ boolean searchDescription, boolean findAll, boolean ignoreHidden)
{
- if (findAll)
- {
- sequenceIndex = 0;
- columnIndex = -1;
- }
+ searchResults = new SearchResults();
+ idMatches = new ArrayList<>();
- String searchString = caseSensitive ? theSearchString
- : theSearchString.toUpperCase();
+ String searchString = matchCase ? theSearchString
+ : theSearchString.toUpperCase(Locale.ROOT);
Regex searchPattern = new Regex(searchString);
- searchPattern.setIgnoreCase(!caseSensitive);
- searchResults = new SearchResults();
- idMatch = new Vector<>();
+ searchPattern.setIgnoreCase(!matchCase);
+ SequenceGroup selection = viewport.getSelectionGroup();
if (selection != null && selection.getSize() < 1)
{
selection = null; // ? ignore column-only selection
}
+ AlignmentI alignment = viewport.getAlignment();
int end = alignment.getHeight();
- while (sequenceIndex < end)
+ getSequence(ignoreHidden);
+
+ boolean found = false;
+ while ((!found || findAll) && sequenceIndex < end)
{
- SequenceI seq = alignment.getSequenceAt(sequenceIndex);
- boolean found = findNext(seq, searchString, searchPattern);
- if (found && !findAll)
- {
- return;
- }
- if (!found)
- {
- sequenceIndex++;
- columnIndex = -1;
- }
+ found = findNextMatch(searchString, searchPattern, searchDescription,
+ ignoreHidden);
}
}
/**
- * Answers the start-end column range of the visible region starting at or
- * after the given column. if there are no hidden columns, this just returns
- * the remaining width of the alignment. Answers null if there are no visible
- * columns at or after <code>column</code>.
- */
- protected int[] getNextVisibleRegion(int column)
- {
- VisibleContigsIterator visibleRegions = alignment.getHiddenColumns()
- .getVisContigsIterator(column, alignment.getWidth(),
- false);
- return visibleRegions.hasNext() ? visibleRegions.next() : null;
- }
-
- /**
- * Finds the next match in the given sequence, starting at column at
- * <code>columnIndex</code>. Answers true if a match is found, else false. If
- * a match is found, <code>columnIndex</code> is advanced to the column after
- * the start of the matched region, ready for a search from the next position.
+ * Calculates and saves the sequence string to search. The string is restricted
+ * to the current selection region if there is one, and is saved with all gaps
+ * removed.
+ * <p>
+ * If there are hidden columns, and option {@ignoreHidden} is selected, then
+ * only visible positions of the sequence are included, and a mapping is also
+ * constructed from the returned string positions to the true sequence
+ * positions.
+ * <p>
+ * Note we have to do this each time {@code findNext} or {@code findAll} is
+ * called, in case the alignment, selection group or hidden columns have
+ * changed. In particular, if the sequence at offset {@code sequenceIndex} in
+ * the alignment is (no longer) in the selection group, search is advanced to
+ * the next sequence that is.
+ * <p>
+ * Sets sequence string to the empty string if there are no more sequences (in
+ * selection group if any) at or after {@code sequenceIndex}.
+ * <p>
+ * Returns true if a sequence could be found, false if end of alignment was
+ * reached
*
- * @param seq
- * @param searchString
- * @param searchPattern
+ * @param ignoreHidden
* @return
*/
- protected boolean findNext(SequenceI seq, String searchString,
- Regex searchPattern)
+ private boolean getSequence(boolean ignoreHidden)
{
- if (selection != null && !selection.contains(seq))
+ AlignmentI alignment = viewport.getAlignment();
+ if (sequenceIndex >= alignment.getHeight())
{
- /*
- * this sequence is not in the selection - advance to next sequence
- */
+ seqToSearch = "";
return false;
}
-
- if (columnIndex < 0)
+ SequenceI seq = alignment.getSequenceAt(sequenceIndex);
+ SequenceGroup selection = viewport.getSelectionGroup();
+ if (selection != null && !selection.contains(seq))
{
- /*
- * at start of sequence; try find by residue number, in sequence id,
- * or (optionally) in sequence description
- */
- if (doNonMotifSearches(seq, searchString, searchPattern))
+ if (!nextSequence(ignoreHidden))
{
- return true;
+ return false;
}
+ seq = alignment.getSequenceAt(sequenceIndex);
}
- /*
- * search for next match in sequence string
- */
- int end = seq.getLength();
- while (columnIndex < end)
+ String seqString = null;
+ if (ignoreHidden)
+ {
+ seqString = getVisibleSequence(seq);
+ this.searchedSequenceStartPosition = 1;
+ }
+ else
{
- if (searchNextVisibleRegion(seq, searchPattern))
+ int startCol = 0;
+ int endCol = seq.getLength() - 1;
+ this.searchedSequenceStartPosition = seq.getStart();
+ if (selection != null)
{
- return true;
+ startCol = selection.getStartRes();
+ endCol = Math.min(endCol, selection.getEndRes());
+ this.searchedSequenceStartPosition = seq.findPosition(startCol);
}
+ seqString = seq.getSequenceAsString(startCol, endCol + 1);
}
- return false;
+
+ /*
+ * remove gaps; note that even if this leaves an empty string, we 'search'
+ * the sequence anyway (for possible match on name or description)
+ */
+ String ungapped = AlignSeq.extractGaps(Comparison.GapChars, seqString);
+ this.seqToSearch = ungapped;
+
+ return true;
}
/**
- * Searches the sequence, starting from <code>columnIndex</code>, and adds the
- * next match (if any) to <code>searchResults</code>. The search is restricted
- * to the next visible column region, and to the <code>selection</code> region
- * if there is one. Answers true if a match is added, else false.
+ * Returns a string consisting of only the visible residues of {@code seq} from
+ * alignment column {@ fromColumn}, restricted to the current selection region
+ * if there is one.
+ * <p>
+ * As a side-effect, also computes the mapping from the true sequence positions
+ * to the positions (1, 2, ...) of the returned sequence. This is to allow
+ * search matches in the visible sequence to be converted to sequence positions.
*
* @param seq
- * @param searchPattern
* @return
*/
- protected boolean searchNextVisibleRegion(SequenceI seq, Regex searchPattern)
+ private String getVisibleSequence(SequenceI seq)
{
/*
- * sequence columns to search (working in absolute column
- * positions, base 0, including any hidden columns)
+ * get start / end columns of sequence and convert to base 0
+ * (so as to match the visible column ranges)
*/
- int seqColStart = columnIndex;
- int seqColEnd = seq.getLength() - 1;
+ int seqStartCol = seq.findIndex(seq.getStart()) - 1;
+ int seqEndCol = seq.findIndex(seq.getStart() + seq.getLength() - 1) - 1;
+ Iterator<int[]> visibleColumns = viewport.getViewAsVisibleContigs(true);
+ StringBuilder visibleSeq = new StringBuilder(seqEndCol - seqStartCol);
+ List<int[]> fromRanges = new ArrayList<>();
- /*
- * restrict search to (next) visible column region,
- * in case there are hidden columns
- */
- int[] visible = getNextVisibleRegion(columnIndex);
- if (visible != null)
+ while (visibleColumns.hasNext())
{
- seqColStart = Math.max(seqColStart, visible[0]);
- seqColEnd = Math.min(seqColEnd, visible[1]);
- }
- else
- {
- columnIndex = seqColEnd + 1;
- return false;
- }
-
- /*
- * restrict search to selected region if there is one
- */
- if (selection != null)
- {
- int selectionStart = selection.getStartRes();
- int selectionEnd = selection.getEndRes();
- if (selectionStart > seqColEnd || selectionEnd < seqColStart)
+ int[] range = visibleColumns.next();
+ if (range[0] > seqEndCol)
+ {
+ // beyond the end of the sequence
+ break;
+ }
+ if (range[1] < seqStartCol)
+ {
+ // before the start of the sequence
+ continue;
+ }
+ String subseq = seq.getSequenceAsString(range[0], range[1] + 1);
+ String ungapped = AlignSeq.extractGaps(Comparison.GapChars, subseq);
+ visibleSeq.append(ungapped);
+ if (!ungapped.isEmpty())
{
/*
- * sequence region doesn't overlap selection region -
- * no match, advance to next visible region
+ * visible region includes at least one non-gap character,
+ * so add the range to the mapping being constructed
*/
- columnIndex = seqColEnd + 1;
- return false;
+ int seqResFrom = seq.findPosition(range[0]);
+ int seqResTo = seqResFrom + ungapped.length() - 1;
+ fromRanges.add(new int[] { seqResFrom, seqResTo });
}
- seqColStart = Math.max(seqColStart, selectionStart);
- seqColEnd = Math.min(seqColEnd, selectionEnd);
}
- String seqString = seq.getSequenceAsString(seqColStart, seqColEnd + 1);
- String noGaps = AlignSeq.extractGaps(Comparison.GapChars, seqString);
+ /*
+ * construct the mapping
+ * from: visible sequence positions 1..length
+ * to: true residue positions of the alignment sequence
+ */
+ List<int[]> toRange = Arrays
+ .asList(new int[]
+ { 1, visibleSeq.length() });
+ searchedSequenceMap = new MapList(fromRanges, toRange, 1, 1);
- if (searchPattern.search(noGaps))
- {
- int sequenceStartPosition = seq.findPosition(seqColStart);
- recordMatch(seq, searchPattern, sequenceStartPosition);
- return true;
- }
- else
+ return visibleSeq.toString();
+ }
+
+ /**
+ * Advances the search to the next sequence in the alignment. Sequences not in
+ * the current selection group (if there is one) are skipped. The (sub-)sequence
+ * to be searched is extracted, gaps removed, and saved, or set to null if there
+ * are no more sequences to search.
+ * <p>
+ * Returns true if a sequence could be found, false if end of alignment was
+ * reached
+ *
+ * @param ignoreHidden
+ */
+ private boolean nextSequence(boolean ignoreHidden)
+ {
+ sequenceIndex++;
+ residueIndex = -1;
+
+ return getSequence(ignoreHidden);
+ }
+
+ /**
+ * Finds the next match in the given sequence, starting at offset
+ * {@code residueIndex}. Answers true if a match is found, else false.
+ * <p>
+ * If a match is found, {@code residueIndex} is advanced to the position after
+ * the start of the matched region, ready for the next search.
+ * <p>
+ * If no match is found, {@code sequenceIndex} is advanced ready to search the
+ * next sequence.
+ *
+ * @param seqToSearch
+ * @param searchString
+ * @param searchPattern
+ * @param matchDescription
+ * @param ignoreHidden
+ * @return
+ */
+ protected boolean findNextMatch(String searchString,
+ Regex searchPattern, boolean matchDescription,
+ boolean ignoreHidden)
+ {
+ if (residueIndex < 0)
{
/*
- * no match - advance columnIndex past this visible region
- * so the next visible region (if any) is searched next
+ * at start of sequence; try find by residue number, in sequence id,
+ * or (optionally) in sequence description
*/
- columnIndex = seqColEnd + 1;
+ if (doNonMotifSearches(searchString, searchPattern,
+ matchDescription))
+ {
+ return true;
+ }
+ }
+
+ /*
+ * search for next match in sequence string
+ */
+ int end = seqToSearch.length();
+ while (residueIndex < end)
+ {
+ boolean matched = searchPattern.searchFrom(seqToSearch, residueIndex);
+ if (matched)
+ {
+ if (recordMatch(searchPattern, ignoreHidden))
+ {
+ return true;
+ }
+ }
+ else
+ {
+ residueIndex = Integer.MAX_VALUE;
+ }
}
+ nextSequence(ignoreHidden);
return false;
}
/**
* Adds the match held in the <code>searchPattern</code> Regex to the
* <code>searchResults</code>, unless it is a subregion of the last match
- * recorded. <code>columnIndex</code> is advanced to the position after the
+ * recorded. <code>residueIndex</code> is advanced to the position after the
* start of the matched region, ready for the next search. Answers true if a
* match was added, else false.
+ * <p>
+ * Matches that lie entirely within hidden regions of the alignment are not
+ * added.
*
- * @param seq
* @param searchPattern
- * @param firstResiduePosition
+ * @param ignoreHidden
* @return
*/
- protected boolean recordMatch(SequenceI seq, Regex searchPattern,
- int firstResiduePosition)
+ protected boolean recordMatch(Regex searchPattern, boolean ignoreHidden)
{
+ SequenceI seq = viewport.getAlignment().getSequenceAt(sequenceIndex);
+
/*
- * get start/end of the match in sequence coordinates
+ * convert start/end of the match to sequence coordinates
*/
int offset = searchPattern.matchedFrom();
- int matchStartPosition = firstResiduePosition + offset;
+ int matchStartPosition = this.searchedSequenceStartPosition + offset;
int matchEndPosition = matchStartPosition
+ searchPattern.charsMatched() - 1;
/*
- * update columnIndex to next column after the start of the match
+ * update residueIndex to next position after the start of the match
* (findIndex returns a value base 1, columnIndex is held base 0)
*/
- columnIndex = seq.findIndex(matchStartPosition);
+ residueIndex = searchPattern.matchedFrom()+1;
+
+ /*
+ * return false if the match is entirely in a hidden region
+ */
+ if (allHidden(seq, matchStartPosition, matchEndPosition))
+ {
+ return false;
+ }
/*
* check that this match is not a subset of the previous one (JAL-2302)
if (lastMatch == null || !lastMatch.contains(seq, matchStartPosition,
matchEndPosition))
{
- searchResults.addResult(seq, matchStartPosition, matchEndPosition);
+ addMatch(seq, matchStartPosition, matchEndPosition, ignoreHidden);
return true;
}
}
/**
+ * Adds one match to the stored list. If hidden residues are being skipped, then
+ * the match may need to be split into contiguous positions of the sequence (so
+ * it does not include skipped residues).
+ *
+ * @param seq
+ * @param matchStartPosition
+ * @param matchEndPosition
+ * @param ignoreHidden
+ */
+ private void addMatch(SequenceI seq, int matchStartPosition,
+ int matchEndPosition, boolean ignoreHidden)
+ {
+ if (!ignoreHidden)
+ {
+ /*
+ * simple case
+ */
+ searchResults.addResult(seq, matchStartPosition, matchEndPosition);
+ return;
+ }
+
+ /*
+ * get start-end contiguous ranges in underlying sequence
+ */
+ int[] truePositions = searchedSequenceMap
+ .locateInFrom(matchStartPosition, matchEndPosition);
+ searchResults.addResult(seq, truePositions);
+ }
+
+ /**
+ * Returns true if all residues are hidden, else false
+ *
+ * @param seq
+ * @param fromPos
+ * @param toPos
+ * @return
+ */
+ private boolean allHidden(SequenceI seq, int fromPos, int toPos)
+ {
+ if (!viewport.hasHiddenColumns())
+ {
+ return false;
+ }
+ for (int res = fromPos; res <= toPos; res++)
+ {
+ if (isVisible(seq, res))
+ {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
* Does searches other than for residue patterns. Currently this includes
* <ul>
* <li>find residue by position (if search string is a number)</li>
* </ul>
* Answers true if a match is found, else false.
*
- * @param seq
* @param searchString
* @param searchPattern
+ * @param includeDescription
* @return
*/
- protected boolean doNonMotifSearches(SequenceI seq, String searchString,
- Regex searchPattern)
+ protected boolean doNonMotifSearches(String searchString,
+ Regex searchPattern, boolean includeDescription)
{
+ SequenceI seq = viewport.getAlignment().getSequenceAt(sequenceIndex);
+
/*
* position sequence search to start of sequence
*/
- columnIndex = 0;
-
- if (searchForResidueNumber(seq, searchString))
+ residueIndex = 0;
+ try
{
- return true;
+ int res = Integer.parseInt(searchString);
+ return searchForResidueNumber(seq, res);
+ } catch (NumberFormatException ex)
+ {
+ // search pattern is not a number
}
+
if (searchSequenceName(seq, searchPattern))
{
return true;
protected boolean searchSequenceDescription(SequenceI seq, Regex searchPattern)
{
String desc = seq.getDescription();
- if (desc != null && searchPattern.search(desc) && !idMatch.contains(seq))
+ if (desc != null && searchPattern.search(desc) && !idMatches.contains(seq))
{
- idMatch.addElement(seq);
+ idMatches.add(seq);
return true;
}
return false;
*/
protected boolean searchSequenceName(SequenceI seq, Regex searchPattern)
{
- if (searchPattern.search(seq.getName()) && !idMatch.contains(seq))
+ if (searchPattern.search(seq.getName()) && !idMatches.contains(seq))
{
- idMatch.addElement(seq);
+ idMatches.add(seq);
return true;
}
return false;
}
/**
- * Tries to interpret the search string as a residue position, and if valid,
- * adds the position to the search results and returns true, else answers
- * false
+ * If the residue position is valid for the sequence, and in a visible column,
+ * adds the position to the search results and returns true, else answers false.
+ *
+ * @param seq
+ * @param resNo
+ * @return
*/
- protected boolean searchForResidueNumber(SequenceI seq, String searchString)
+ protected boolean searchForResidueNumber(SequenceI seq, int resNo)
{
- try
+ if (seq.getStart() <= resNo && seq.getEnd() >= resNo)
{
- int res = Integer.parseInt(searchString);
- if (seq.getStart() <= res && seq.getEnd() >= res)
+ if (isVisible(seq, resNo))
{
- searchResults.addResult(seq, res, res);
+ searchResults.addResult(seq, resNo, resNo);
return true;
}
- } catch (NumberFormatException ex)
- {
}
return false;
}
/**
- * Sets whether the search is case sensitive (default is no)
- *
- * @param value
- */
- public void setCaseSensitive(boolean value)
- {
- this.caseSensitive = value;
- }
-
- /**
- * Sets whether search returns all matches. Default is to return the next
- * match only.
+ * Returns true if the residue is in a visible column, else false
*
- * @param value
+ * @param seq
+ * @param res
+ * @return
*/
- public void setFindAll(boolean value)
+ private boolean isVisible(SequenceI seq, int res)
{
- this.findAll = value;
+ if (!viewport.hasHiddenColumns())
+ {
+ return true;
+ }
+ int col = seq.findIndex(res); // base 1
+ return viewport.getAlignment().getHiddenColumns().isVisible(col - 1); // base 0
}
- /**
- * Returns the (possibly empty) list of sequences matched on sequence name or
- * description
- *
- * @return
- */
- public Vector<SequenceI> getIdMatch()
+ @Override
+ public List<SequenceI> getIdMatches()
{
- return idMatch;
+ return idMatches;
}
- /**
- * Answers the search results (possibly empty) from the last search
- *
- * @return
- */
+ @Override
public SearchResultsI getSearchResults()
{
return searchResults;
}
-
- /**
- * Answers the absolute column position (base 0, including any hidden columns)
- * of the start of the last sequence motif (residue pattern) match found. A
- * 'Find next' will search from the next position.
- *
- * @return
- */
- public int getColumnIndex()
- {
- return columnIndex;
- }
-
- /**
- * Answers the offset in the alignment (0..) of the sequence in which the last
- * match was found (if any)
- *
- * @return
- */
- public int getSequenceIndex()
- {
- return sequenceIndex;
- }
-
- /**
- * Sets whether search also searches in sequence description text (default is
- * no)
- *
- * @param value
- */
- public void setIncludeDescription(boolean value)
- {
- this.includeDescription = value;
- }
}