X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Fanalysis%2FFinder.java;h=3cbef6d89175201f0f9029cf3dfca2260bf0295c;hb=9b5106c49c8fa0a7269f38ad1825851eb8ba5b85;hp=e24a6c059c69119154e8e53bf1948954cc702f82;hpb=dbcfef03ad3d2853eda62c727978a160fc347f58;p=jalview.git diff --git a/src/jalview/analysis/Finder.java b/src/jalview/analysis/Finder.java index e24a6c0..3cbef6d 100644 --- a/src/jalview/analysis/Finder.java +++ b/src/jalview/analysis/Finder.java @@ -1,273 +1,468 @@ +/* + * 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 jalview.datamodel.*; +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; -public class Finder { - /** - * Implements the search algorithms for the Find dialog box. + /* + * 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 */ - SearchResults searchResults; - AlignmentI alignment; - jalview.datamodel.SequenceGroup selection=null; - Vector idMatch=null; - boolean caseSensitive=false; - boolean findAll=false; - com.stevesoft.pat.Regex regex=null; - /** - * hold's last-searched position between calles to find(false) + sequenceIndex = 0; + columnIndex = -1; + + doFind(theSearchString, matchCase, searchDescription, true); + + /* + * reset to start for next search */ - int seqIndex=0,resIndex=0; - public Finder(AlignmentI alignment, SequenceGroup selection) { - this.alignment=alignment; - this.selection = selection; - } + sequenceIndex = 0; + columnIndex = -1; + } + + @Override + public void findNext(String theSearchString, boolean matchCase, + boolean searchDescription) + { + doFind(theSearchString, matchCase, searchDescription, false); - public Finder(AlignmentI alignment, SequenceGroup selectionGroup, int seqIndex, int resIndex) { - this(alignment, selectionGroup); - this.seqIndex=seqIndex; - this.resIndex=resIndex; + if (searchResults.isEmpty() && idMatches.isEmpty()) + { + /* + * search failed - reset to start for next search + */ + sequenceIndex = 0; + columnIndex = -1; } + } - public boolean find(String searchString) { - boolean hasResults=false; - if(!caseSensitive) - searchString = searchString.toUpperCase(); - regex = new com.stevesoft.pat.Regex(searchString); - searchResults = new SearchResults(); - idMatch = new Vector(); - Sequence seq; - String item = null; - boolean found = false; - - ////// is the searchString a residue number? - try - { - int res = Integer.parseInt(searchString); - found = true; - if (selection == null || selection.getSize(false) < 1) - { - seq = (Sequence) alignment.getSequenceAt(0); - } - else - { - seq = (Sequence) (selection.getSequenceAt(0)); - } - - searchResults.addResult(seq, res, res); - hasResults=true; - } - catch (NumberFormatException ex) - { - } - - /////////////////////////////////////////////// - - int end = alignment.getHeight(); - - - if (selection != null) - { - if ((selection.getSize(false) < 1) || - ((selection.getEndRes() - selection.getStartRes()) < 2)) - { - selection = null; - } - } - - while (!found && (seqIndex < end)) - { - seq = (Sequence) alignment.getSequenceAt(seqIndex); - - if ((selection != null) && !selection.getSequences(false).contains(seq)) - { - seqIndex++; - resIndex = 0; - - continue; - } - - item = seq.getSequenceAsString(); - // JBPNote - check if this toUpper which is present in the application implementation makes a difference - //if(!caseSensitive) - // item = item.toUpperCase(); - - if ((selection != null) && - (selection.getEndRes() < alignment.getWidth()-1)) - { - item = item.substring(0, selection.getEndRes() + 1); - } - - ///Shall we ignore gaps???? - JBPNote: Add Flag for forcing this or not - StringBuffer noGapsSB = new StringBuffer(); - int insertCount = 0; - Vector spaces = new Vector(); - - for (int j = 0; j < item.length(); j++) - { - if (!jalview.util.Comparison.isGap(item.charAt(j))) - { - noGapsSB.append(item.charAt(j)); - spaces.add(new Integer(insertCount)); - } - else - { - insertCount++; - } - } - - String noGaps = noGapsSB.toString(); - - for (int r = resIndex; r < noGaps.length(); r++) - { - - if (regex.searchFrom(noGaps, r)) - { - resIndex = regex.matchedFrom(); - - if ((selection != null) && - ((resIndex + - Integer.parseInt(spaces.get(resIndex).toString())) < selection.getStartRes())) - { - continue; - } - - - int sres = seq.findPosition(resIndex + - Integer.parseInt(spaces.elementAt(resIndex) - .toString())); - int eres = seq.findPosition(regex.matchedTo() - 1 + - Integer.parseInt(spaces.elementAt(regex.matchedTo() - - 1).toString())); - - searchResults.addResult(seq, sres, eres); - hasResults=true; - if (!findAll) - { - // thats enough, break and display the result - found = true; - resIndex++; - - break; - } - - r = resIndex; - } - else - { - break; - } - } - - if (!found) - { - seqIndex++; - resIndex = 0; - } - } - - for (int id = 0; id < alignment.getHeight(); id++) - { - if (regex.search(alignment.getSequenceAt(id).getName())) - { - idMatch.add(alignment.getSequenceAt(id)); - hasResults=true; - } - } - return hasResults; + /** + * 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 } - /** - * @return the alignment - */ - public AlignmentI getAlignment() { - return alignment; + + 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; + } } - /** - * @param alignment the alignment to set + } + + /** + * 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 */ - public void setAlignment(AlignmentI alignment) { - this.alignment = alignment; + 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; } - /** - * @return the caseSensitive + seqColStart = Math.max(seqColStart, visible[0]); + seqColEnd = Math.min(seqColEnd, visible[1]); + + /* + * restrict search to selected region if there is one */ - public boolean isCaseSensitive() { - return caseSensitive; + 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); } - /** - * @param caseSensitive the caseSensitive to set - */ - public void setCaseSensitive(boolean caseSensitive) { - this.caseSensitive = caseSensitive; + + 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; } - /** - * @return the findAll - */ - public boolean isFindAll() { - return findAll; + + 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; + } } - /** - * @param findAll the findAll to set + + /* + * search for next match in sequence string */ - public void setFindAll(boolean findAll) { - this.findAll = findAll; + int end = seq.getLength(); + while (columnIndex < end) + { + if (searchNextVisibleRegion(seq, searchPattern)) + { + return true; + } } - /** - * @return the selection - */ - public jalview.datamodel.SequenceGroup getSelection() { - return selection; + 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; } - /** - * @param selection the selection to set - */ - public void setSelection(jalview.datamodel.SequenceGroup selection) { - this.selection = selection; + 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; } - /** - * @return the idMatch - */ - public Vector getIdMatch() { - return idMatch; + else + { + /* + * no match - advance columnIndex past this visible region + * so the next visible region (if any) is searched next + */ + columnIndex = visible.end + 1; } - /** - * @return the regex + + 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 */ - public com.stevesoft.pat.Regex getRegex() { - return regex; - } - /** - * @return the searchResults + 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) */ - public SearchResults getSearchResults() { - return searchResults; - } + columnIndex = seq.findIndex(matchStartPosition); - /** - * @return the resIndex + /* + * check that this match is not a subset of the previous one (JAL-2302) */ - public int getResIndex() { - return resIndex; + 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; } - /** - * @param resIndex the resIndex to set + 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 */ - public void setResIndex(int resIndex) { - this.resIndex = resIndex; + columnIndex = 0; + + if (searchForResidueNumber(seq, searchString)) + { + return true; } + if (searchSequenceName(seq, searchPattern)) + { + return true; + } + if (includeDescription && searchSequenceDescription(seq, searchPattern)) + { + return true; + } + return false; + } - /** - * @return the seqIndex - */ - public int getSeqIndex() { - return seqIndex; + /** + * 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; + } - /** - * @param seqIndex the seqIndex to set - */ - public void setSeqIndex(int seqIndex) { - this.seqIndex = seqIndex; + /** + * 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; + } }