src/jalview/analysis/Finder.java

   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   public Finder(AlignViewportI av)
  78   {
  79     this.viewport = av;
  80     this.sequenceIndex = 0;
  81     this.columnIndex = -1;
  82   }
  83
  84   @Override
  85   public void findAll(String theSearchString, boolean matchCase,
  86           boolean searchDescription)
  87   {
  88     /*
  89      * search from the start
  90      */
  91     sequenceIndex = 0;
  92     columnIndex = -1;
  93
  94     doFind(theSearchString, matchCase, searchDescription, true);
  95
  96     /*
  97      * reset to start for next search
  98      */
  99     sequenceIndex = 0;
 100     columnIndex = -1;
 101   }
 102
 103   @Override
 104   public void findNext(String theSearchString, boolean matchCase,
 105           boolean searchDescription)
 106   {
 107     doFind(theSearchString, matchCase, searchDescription, false);
 108
 109     if (searchResults.isEmpty() && idMatches.isEmpty())
 110     {
 111       /*
 112        * search failed - reset to start for next search
 113        */
 114       sequenceIndex = 0;
 115       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   protected void doFind(String theSearchString, boolean matchCase,
 128           boolean searchDescription, boolean findAll)
 129   {
 130     String searchString = matchCase ? theSearchString
 131             : theSearchString.toUpperCase();
 132     Regex searchPattern = new Regex(searchString);
 133     searchPattern.setIgnoreCase(!matchCase);
 134
 135     searchResults = new SearchResults();
 136     idMatches = new Vector<>();
 137
 138     SequenceGroup selection = viewport.getSelectionGroup();
 139     if (selection != null && selection.getSize() < 1)
 140     {
 141       selection = null; // ? ignore column-only selection
 142     }
 143
 144     AlignmentI alignment = viewport.getAlignment();
 145     int end = alignment.getHeight();
 146
 147     while (sequenceIndex < end)
 148     {
 149       SequenceI seq = alignment.getSequenceAt(sequenceIndex);
 150       boolean found = findNextMatch(seq, searchString, searchPattern,
 151               searchDescription);
 152       if (found && !findAll)
 153       {
 154         return;
 155       }
 156       if (!found)
 157       {
 158         sequenceIndex++;
 159         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   protected Range getNextVisibleSequenceRegion(SequenceI sequence,
 173           int column)
 174   {
 175     int seqColStart = column;
 176     int seqColEnd = sequence.getLength() - 1;
 177
 178     /*
 179      * restrict search to (next) visible column region,
 180      * in case there are hidden columns
 181      */
 182     AlignmentI alignment = viewport.getAlignment();
 183     VisibleContigsIterator visibleRegions = alignment.getHiddenColumns()
 184             .getVisContigsIterator(column, alignment.getWidth(),
 185                     false);
 186     int[] visible = visibleRegions.hasNext() ? visibleRegions.next() : null;
 187     if (visible == null)
 188     {
 189       columnIndex = seqColEnd + 1;
 190       return null;
 191     }
 192     seqColStart = Math.max(seqColStart, visible[0]);
 193     seqColEnd = Math.min(seqColEnd, visible[1]);
 194
 195     /*
 196      * restrict search to selected region if there is one
 197      */
 198     SequenceGroup selection = viewport.getSelectionGroup();
 199     if (selection != null)
 200     {
 201       int selectionStart = selection.getStartRes();
 202       int selectionEnd = selection.getEndRes();
 203       if (selectionStart > seqColEnd || selectionEnd < seqColStart)
 204       {
 205         /*
 206          * sequence region doesn't overlap selection region
 207          */
 208         columnIndex = seqColEnd + 1;
 209         return null;
 210       }
 211       seqColStart = Math.max(seqColStart, selectionStart);
 212       seqColEnd = Math.min(seqColEnd, selectionEnd);
 213     }
 214
 215     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   protected boolean findNextMatch(SequenceI seq, String searchString,
 231           Regex searchPattern, boolean matchDescription)
 232   {
 233     SequenceGroup selection = viewport.getSelectionGroup();
 234     if (selection != null && !selection.contains(seq))
 235     {
 236       /*
 237        * this sequence is not in the selection - advance to next sequence
 238        */
 239       return false;
 240     }
 241
 242     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       if (doNonMotifSearches(seq, searchString, searchPattern,
 249               matchDescription))
 250       {
 251         return true;
 252       }
 253     }
 254
 255     /*
 256      * search for next match in sequence string
 257      */
 258     int end = seq.getLength();
 259     while (columnIndex < end)
 260     {
 261       if (searchNextVisibleRegion(seq, searchPattern))
 262       {
 263         return true;
 264       }
 265     }
 266     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   protected boolean searchNextVisibleRegion(SequenceI seq, Regex searchPattern)
 280   {
 281     Range visible = getNextVisibleSequenceRegion(seq, columnIndex);
 282     if (visible == null)
 283     {
 284       return false;
 285     }
 286     String seqString = seq.getSequenceAsString(visible.start, visible.end + 1);
 287     String noGaps = AlignSeq.extractGaps(Comparison.GapChars, seqString);
 288
 289     if (searchPattern.search(noGaps))
 290     {
 291       int sequenceStartPosition = seq.findPosition(visible.start);
 292       recordMatch(seq, searchPattern, sequenceStartPosition);
 293       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       columnIndex = visible.end + 1;
 302     }
 303
 304     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   protected boolean recordMatch(SequenceI seq, Regex searchPattern,
 320           int firstResiduePosition)
 321   {
 322     /*
 323      * get start/end of the match in sequence coordinates
 324      */
 325     int offset = searchPattern.matchedFrom();
 326     int matchStartPosition = firstResiduePosition + offset;
 327     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     columnIndex = seq.findIndex(matchStartPosition);
 335
 336     /*
 337      * check that this match is not a subset of the previous one (JAL-2302)
 338      */
 339     List<SearchResultMatchI> matches = searchResults.getResults();
 340     SearchResultMatchI lastMatch = matches.isEmpty() ? null
 341             : matches.get(matches.size() - 1);
 342
 343     if (lastMatch == null || !lastMatch.contains(seq, matchStartPosition,
 344             matchEndPosition))
 345     {
 346       searchResults.addResult(seq, matchStartPosition, matchEndPosition);
 347       return true;
 348     }
 349
 350     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   protected boolean doNonMotifSearches(SequenceI seq, String searchString,
 369           Regex searchPattern, boolean includeDescription)
 370   {
 371     /*
 372      * position sequence search to start of sequence
 373      */
 374     columnIndex = 0;
 375
 376     if (searchForResidueNumber(seq, searchString))
 377     {
 378       return true;
 379     }
 380     if (searchSequenceName(seq, searchPattern))
 381     {
 382       return true;
 383     }
 384     if (includeDescription && searchSequenceDescription(seq, searchPattern))
 385     {
 386       return true;
 387     }
 388     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   protected boolean searchSequenceDescription(SequenceI seq, Regex searchPattern)
 401   {
 402     String desc = seq.getDescription();
 403     if (desc != null && searchPattern.search(desc) && !idMatches.contains(seq))
 404     {
 405       idMatches.addElement(seq);
 406       return true;
 407     }
 408     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   protected boolean searchSequenceName(SequenceI seq, Regex searchPattern)
 421   {
 422     if (searchPattern.search(seq.getName()) && !idMatches.contains(seq))
 423     {
 424       idMatches.addElement(seq);
 425       return true;
 426     }
 427     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   protected boolean searchForResidueNumber(SequenceI seq, String searchString)
 436   {
 437     try
 438     {
 439       int res = Integer.parseInt(searchString);
 440       if (seq.getStart() <= res && seq.getEnd() >= res)
 441       {
 442         searchResults.addResult(seq, res, res);
 443         return true;
 444       }
 445     } catch (NumberFormatException ex)
 446     {
 447     }
 448     return false;
 449   }
 450
 451   /* (non-Javadoc)
 452    * @see jalview.analysis.FinderI#getIdMatch()
 453    */
 454   @Override
 455   public Vector<SequenceI> getIdMatches()
 456   {
 457     return idMatches;
 458   }
 459
 460   /* (non-Javadoc)
 461    * @see jalview.analysis.FinderI#getSearchResults()
 462    */
 463   @Override
 464   public SearchResultsI getSearchResults()
 465   {
 466     return searchResults;
 467   }
 468 }