/* * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$) * Copyright (C) $$Year-Rel$$ The Jalview Authors * * This file is part of Jalview. * * Jalview is free software: you can redistribute it and/or * modify it under the terms of the GNU General Public License * as published by the Free Software Foundation, either version 3 * of the License, or (at your option) any later version. * * Jalview is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty * of MERCHANTABILITY or FITNESS FOR A PARTICULAR * PURPOSE. See the GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with Jalview. If not, see . * The Jalview Authors are detailed in the 'AUTHORS' file. */ package jalview.analysis; import jalview.api.AlignViewportI; import jalview.api.FinderI; import jalview.datamodel.AlignmentI; import jalview.datamodel.Range; 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 java.util.List; import java.util.Vector; import com.stevesoft.pat.Regex; /** * Implements the search algorithm for the Find dialog */ public class Finder implements FinderI { /* * matched residue locations */ private SearchResultsI searchResults; /* * sequences matched by id or description */ private Vector idMatches; /* * the viewport to search over */ private AlignViewportI viewport; /* * sequence index in alignment to search from */ private int sequenceIndex; /* * column position in sequence to search from, base 0 * - absolute column number including any hidden columns * (position after start of last match for a repeat search) */ private int columnIndex; /** * Constructor for searching a viewport * * @param av */ public Finder(AlignViewportI av) { this.viewport = av; this.sequenceIndex = 0; this.columnIndex = -1; } @Override public void findAll(String theSearchString, boolean matchCase, boolean searchDescription) { /* * search from the start */ sequenceIndex = 0; columnIndex = -1; doFind(theSearchString, matchCase, searchDescription, true); /* * reset to start for next search */ sequenceIndex = 0; columnIndex = -1; } @Override public void findNext(String theSearchString, boolean matchCase, boolean searchDescription) { doFind(theSearchString, matchCase, searchDescription, false); if (searchResults.isEmpty() && idMatches.isEmpty()) { /* * search failed - reset to start for next search */ sequenceIndex = 0; columnIndex = -1; } } /** * Performs a 'find next' or 'find all' * * @param theSearchString * @param matchCase * @param searchDescription * @param findAll */ protected void doFind(String theSearchString, boolean matchCase, boolean searchDescription, boolean findAll) { String searchString = matchCase ? theSearchString : theSearchString.toUpperCase(); Regex searchPattern = new Regex(searchString); searchPattern.setIgnoreCase(!matchCase); searchResults = new SearchResults(); idMatches = new Vector<>(); 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) { SequenceI seq = alignment.getSequenceAt(sequenceIndex); boolean found = findNextMatch(seq, searchString, searchPattern, searchDescription); if (found && !findAll) { return; } if (!found) { sequenceIndex++; columnIndex = -1; } } } /** * Answers the start-end column range of the visible region of * sequence starting at or after the given column. * If there are no hidden columns, this just returns the remaining width of * the sequence. The range is restricted to the current selection * if there is one. Answers null if there are no visible columns at or after * column. */ protected Range getNextVisibleSequenceRegion(SequenceI sequence, int column) { int seqColStart = column; int seqColEnd = sequence.getLength() - 1; /* * restrict search to (next) visible column region, * in case there are hidden columns */ AlignmentI alignment = viewport.getAlignment(); VisibleContigsIterator visibleRegions = alignment.getHiddenColumns() .getVisContigsIterator(column, alignment.getWidth(), false); int[] visible = visibleRegions.hasNext() ? visibleRegions.next() : null; if (visible == null) { columnIndex = seqColEnd + 1; return null; } seqColStart = Math.max(seqColStart, visible[0]); seqColEnd = Math.min(seqColEnd, visible[1]); /* * restrict search to selected region if there is one */ SequenceGroup selection = viewport.getSelectionGroup(); if (selection != null) { int selectionStart = selection.getStartRes(); int selectionEnd = selection.getEndRes(); if (selectionStart > seqColEnd || selectionEnd < seqColStart) { /* * sequence region doesn't overlap selection region */ columnIndex = seqColEnd + 1; return null; } seqColStart = Math.max(seqColStart, selectionStart); seqColEnd = Math.min(seqColEnd, selectionEnd); } return new Range(seqColStart, seqColEnd); } /** * Finds the next match in the given sequence, starting at column at * columnIndex. Answers true if a match is found, else false. If * a match is found, columnIndex is advanced to the column after * the start of the matched region, ready for a search from the next position. * * @param seq * @param searchString * @param searchPattern * @param matchDescription * @return */ protected boolean findNextMatch(SequenceI seq, String searchString, Regex searchPattern, boolean matchDescription) { SequenceGroup selection = viewport.getSelectionGroup(); if (selection != null && !selection.contains(seq)) { /* * this sequence is not in the selection - advance to next sequence */ return false; } if (columnIndex < 0) { /* * at start of sequence; try find by residue number, in sequence id, * or (optionally) in sequence description */ if (doNonMotifSearches(seq, searchString, searchPattern, matchDescription)) { return true; } } /* * search for next match in sequence string */ int end = seq.getLength(); while (columnIndex < end) { if (searchNextVisibleRegion(seq, searchPattern)) { return true; } } return false; } /** * Searches the sequence, starting from columnIndex, and adds the * next match (if any) to searchResults. The search is restricted * to the next visible column region, and to the selection region * if there is one. Answers true if a match is added, else false. * * @param seq * @param searchPattern * @return */ protected boolean searchNextVisibleRegion(SequenceI seq, Regex searchPattern) { Range visible = getNextVisibleSequenceRegion(seq, columnIndex); if (visible == null) { return false; } String seqString = seq.getSequenceAsString(visible.start, visible.end + 1); String noGaps = AlignSeq.extractGaps(Comparison.GapChars, seqString); if (searchPattern.search(noGaps)) { int sequenceStartPosition = seq.findPosition(visible.start); recordMatch(seq, searchPattern, sequenceStartPosition); return true; } else { /* * no match - advance columnIndex past this visible region * so the next visible region (if any) is searched next */ columnIndex = visible.end + 1; } return false; } /** * Adds the match held in the searchPattern Regex to the * searchResults, unless it is a subregion of the last match * recorded. columnIndex 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. * * @param seq * @param searchPattern * @param firstResiduePosition * @return */ protected boolean recordMatch(SequenceI seq, Regex searchPattern, int firstResiduePosition) { /* * get start/end of the match in sequence coordinates */ int offset = searchPattern.matchedFrom(); int matchStartPosition = firstResiduePosition + offset; int matchEndPosition = matchStartPosition + searchPattern.charsMatched() - 1; /* * update columnIndex to next column after the start of the match * (findIndex returns a value base 1, columnIndex is held base 0) */ columnIndex = seq.findIndex(matchStartPosition); /* * check that this match is not a subset of the previous one (JAL-2302) */ List matches = searchResults.getResults(); SearchResultMatchI lastMatch = matches.isEmpty() ? null : matches.get(matches.size() - 1); if (lastMatch == null || !lastMatch.contains(seq, matchStartPosition, matchEndPosition)) { searchResults.addResult(seq, matchStartPosition, matchEndPosition); return true; } return false; } /** * Does searches other than for residue patterns. Currently this includes *
    *
  • find residue by position (if search string is a number)
  • *
  • match search string to sequence id
  • *
  • match search string to sequence description (optional)
  • *
* 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, boolean includeDescription) { /* * position sequence search to start of sequence */ columnIndex = 0; if (searchForResidueNumber(seq, searchString)) { return true; } if (searchSequenceName(seq, searchPattern)) { return true; } if (includeDescription && searchSequenceDescription(seq, searchPattern)) { return true; } return false; } /** * Searches for a match with the sequence description, and if found, adds the * sequence to the list of match ids (but not as a duplicate). Answers true if * a match was added, else false. * * @param seq * @param searchPattern * @return */ protected boolean searchSequenceDescription(SequenceI seq, Regex searchPattern) { String desc = seq.getDescription(); if (desc != null && searchPattern.search(desc) && !idMatches.contains(seq)) { idMatches.addElement(seq); return true; } return false; } /** * Searches for a match with the sequence name, and if found, adds the * sequence to the list of match ids (but not as a duplicate). Answers true if * a match was added, else false. * * @param seq * @param searchPattern * @return */ protected boolean searchSequenceName(SequenceI seq, Regex searchPattern) { if (searchPattern.search(seq.getName()) && !idMatches.contains(seq)) { idMatches.addElement(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 */ protected boolean searchForResidueNumber(SequenceI seq, String searchString) { try { int res = Integer.parseInt(searchString); if (seq.getStart() <= res && seq.getEnd() >= res) { searchResults.addResult(seq, res, res); return true; } } catch (NumberFormatException ex) { } return false; } /* (non-Javadoc) * @see jalview.analysis.FinderI#getIdMatch() */ @Override public Vector getIdMatches() { return idMatches; } /* (non-Javadoc) * @see jalview.analysis.FinderI#getSearchResults() */ @Override public SearchResultsI getSearchResults() { return searchResults; } }