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 contiguous visible regions of
 166    * {@code sequence} starting at or after the given {@code column}. If there are
 167    * no hidden columns, this just returns the remaining width of the sequence.
 168    * Otherwise, visible columns are added as long as they are contiguous on the
 169    * sequence (hidden regions only contain gaps). The range is restricted to the
 170    * current {@code selection} if there is one. Answers null if there are no
 171    * visible columns at or after {@code column}.
 172    *
 173    * @param sequence
 174    * @param column
 175    * @return
 176    */
 177   protected Range getNextVisibleSequenceRegion(SequenceI sequence,
 178           final int column)
 179   {
 180     AlignmentI alignment = viewport.getAlignment();
 181     VisibleContigsIterator visibleRegions = alignment.getHiddenColumns()
 182             .getVisContigsIterator(column, alignment.getWidth(),
 183                     false);
 184     if (!visibleRegions.hasNext())
 185     {
 186       // off the end of the sequence - force search to next sequence
 187       columnIndex = sequence.getLength();
 188       return null;
 189     }
 190
 191     int[] visible = visibleRegions.next();
 192     int seqColStart = Math.max(column, visible[0]);
 193     int seqColEnd = visible[1];
 194     // end residue of region (next residue if end position is gapped)
 195     int endSeqPos = sequence.findPosition(visible[1]);
 196     if (Comparison.isGap(sequence.getCharAt(visible[1])))
 197     {
 198       endSeqPos--;
 199     }
 200     while (visibleRegions.hasNext())
 201     {
 202       visible = visibleRegions.next();
 203       int startSeqPos = sequence.findPosition(visible[0]);
 204       if (startSeqPos - endSeqPos > 1)
 205       {
 206         // this visible region is not contiguous - ignore it
 207         break;
 208       }
 209       endSeqPos = sequence.findPosition(visible[1]);
 210       seqColEnd = visible[1];
 211     }
 212     seqColEnd = Math.min(sequence.getLength() - 1, seqColEnd);
 213
 214     /*
 215      * restrict search to selected region if there is one
 216      */
 217     SequenceGroup selection = viewport.getSelectionGroup();
 218     if (selection != null)
 219     {
 220       int selectionStart = selection.getStartRes();
 221       int selectionEnd = selection.getEndRes();
 222       if (selectionStart > seqColEnd || selectionEnd < seqColStart)
 223       {
 224         /*
 225          * sequence region doesn't overlap selection region
 226          */
 227         columnIndex = seqColEnd + 1;
 228         return null;
 229       }
 230       seqColStart = Math.max(seqColStart, selectionStart);
 231       seqColEnd = Math.min(seqColEnd, selectionEnd);
 232     }
 233
 234     return new Range(seqColStart, seqColEnd);
 235   }
 236
 237   /**
 238    * Finds the next match in the given sequence, starting at column at
 239    * <code>columnIndex</code>. Answers true if a match is found, else false. If
 240    * a match is found, <code>columnIndex</code> is advanced to the column after
 241    * the start of the matched region, ready for a search from the next position.
 242    *
 243    * @param seq
 244    * @param searchString
 245    * @param searchPattern
 246    * @param matchDescription
 247    * @return
 248    */
 249   protected boolean findNextMatch(SequenceI seq, String searchString,
 250           Regex searchPattern, boolean matchDescription)
 251   {
 252     SequenceGroup selection = viewport.getSelectionGroup();
 253     if (selection != null && !selection.contains(seq))
 254     {
 255       /*
 256        * this sequence is not in the selection - advance to next sequence
 257        */
 258       return false;
 259     }
 260
 261     if (columnIndex < 0)
 262     {
 263       /*
 264        * at start of sequence; try find by residue number, in sequence id,
 265        * or (optionally) in sequence description
 266        */
 267       if (doNonMotifSearches(seq, searchString, searchPattern,
 268               matchDescription))
 269       {
 270         return true;
 271       }
 272     }
 273
 274     /*
 275      * search for next match in sequence string
 276      */
 277     int end = seq.getLength();
 278     while (columnIndex < end)
 279     {
 280       if (searchNextVisibleRegion(seq, searchPattern))
 281       {
 282         return true;
 283       }
 284     }
 285     return false;
 286   }
 287
 288   /**
 289    * Searches the sequence, starting from <code>columnIndex</code>, and adds the
 290    * next match (if any) to <code>searchResults</code>. The search is restricted
 291    * to the next visible column region, and to the <code>selection</code> region
 292    * if there is one. Answers true if a match is added, else false.
 293    *
 294    * @param seq
 295    * @param searchPattern
 296    * @return
 297    */
 298   protected boolean searchNextVisibleRegion(SequenceI seq, Regex searchPattern)
 299   {
 300     Range visible = getNextVisibleSequenceRegion(seq, columnIndex);
 301     if (visible == null)
 302     {
 303       return false;
 304     }
 305     String seqString = seq.getSequenceAsString(visible.start, visible.end + 1);
 306     String noGaps = AlignSeq.extractGaps(Comparison.GapChars, seqString);
 307
 308     if (searchPattern.search(noGaps))
 309     {
 310       int sequenceStartPosition = seq.findPosition(visible.start);
 311       recordMatch(seq, searchPattern, sequenceStartPosition);
 312       return true;
 313     }
 314     else
 315     {
 316       /*
 317        * no match - advance columnIndex past this visible region
 318        * so the next visible region (if any) is searched next
 319        */
 320       columnIndex = visible.end + 1;
 321     }
 322
 323     return false;
 324   }
 325
 326   /**
 327    * Adds the match held in the <code>searchPattern</code> Regex to the
 328    * <code>searchResults</code>, unless it is a subregion of the last match
 329    * recorded. <code>columnIndex</code> is advanced to the position after the
 330    * start of the matched region, ready for the next search. Answers true if a
 331    * match was added, else false.
 332    *
 333    * @param seq
 334    * @param searchPattern
 335    * @param firstResiduePosition
 336    * @return
 337    */
 338   protected boolean recordMatch(SequenceI seq, Regex searchPattern,
 339           int firstResiduePosition)
 340   {
 341     /*
 342      * get start/end of the match in sequence coordinates
 343      */
 344     int offset = searchPattern.matchedFrom();
 345     int matchStartPosition = firstResiduePosition + offset;
 346     int matchEndPosition = matchStartPosition
 347             + searchPattern.charsMatched() - 1;
 348
 349     /*
 350      * update columnIndex to next column after the start of the match
 351      * (findIndex returns a value base 1, columnIndex is held base 0)
 352      */
 353     columnIndex = seq.findIndex(matchStartPosition);
 354
 355     /*
 356      * check that this match is not a subset of the previous one (JAL-2302)
 357      */
 358     List<SearchResultMatchI> matches = searchResults.getResults();
 359     SearchResultMatchI lastMatch = matches.isEmpty() ? null
 360             : matches.get(matches.size() - 1);
 361
 362     if (lastMatch == null || !lastMatch.contains(seq, matchStartPosition,
 363             matchEndPosition))
 364     {
 365       searchResults.addResult(seq, matchStartPosition, matchEndPosition);
 366       return true;
 367     }
 368
 369     return false;
 370   }
 371
 372   /**
 373    * Does searches other than for residue patterns. Currently this includes
 374    * <ul>
 375    * <li>find residue by position (if search string is a number)</li>
 376    * <li>match search string to sequence id</li>
 377    * <li>match search string to sequence description (optional)</li>
 378    * </ul>
 379    * Answers true if a match is found, else false.
 380    *
 381    * @param seq
 382    * @param searchString
 383    * @param searchPattern
 384    * @param includeDescription
 385    * @return
 386    */
 387   protected boolean doNonMotifSearches(SequenceI seq, String searchString,
 388           Regex searchPattern, boolean includeDescription)
 389   {
 390     /*
 391      * position sequence search to start of sequence
 392      */
 393     columnIndex = 0;
 394
 395     if (searchForResidueNumber(seq, searchString))
 396     {
 397       return true;
 398     }
 399     if (searchSequenceName(seq, searchPattern))
 400     {
 401       return true;
 402     }
 403     if (includeDescription && searchSequenceDescription(seq, searchPattern))
 404     {
 405       return true;
 406     }
 407     return false;
 408   }
 409
 410   /**
 411    * Searches for a match with the sequence description, and if found, adds the
 412    * sequence to the list of match ids (but not as a duplicate). Answers true if
 413    * a match was added, else false.
 414    *
 415    * @param seq
 416    * @param searchPattern
 417    * @return
 418    */
 419   protected boolean searchSequenceDescription(SequenceI seq, Regex searchPattern)
 420   {
 421     String desc = seq.getDescription();
 422     if (desc != null && searchPattern.search(desc) && !idMatches.contains(seq))
 423     {
 424       idMatches.addElement(seq);
 425       return true;
 426     }
 427     return false;
 428   }
 429
 430   /**
 431    * Searches for a match with the sequence name, and if found, adds the
 432    * sequence to the list of match ids (but not as a duplicate). Answers true if
 433    * a match was added, else false.
 434    *
 435    * @param seq
 436    * @param searchPattern
 437    * @return
 438    */
 439   protected boolean searchSequenceName(SequenceI seq, Regex searchPattern)
 440   {
 441     if (searchPattern.search(seq.getName()) && !idMatches.contains(seq))
 442     {
 443       idMatches.addElement(seq);
 444       return true;
 445     }
 446     return false;
 447   }
 448
 449   /**
 450    * Tries to interpret the search string as a residue position, and if valid,
 451    * adds the position to the search results and returns true, else answers
 452    * false
 453    */
 454   protected boolean searchForResidueNumber(SequenceI seq, String searchString)
 455   {
 456     try
 457     {
 458       int res = Integer.parseInt(searchString);
 459       if (seq.getStart() <= res && seq.getEnd() >= res)
 460       {
 461         searchResults.addResult(seq, res, res);
 462         return true;
 463       }
 464     } catch (NumberFormatException ex)
 465     {
 466     }
 467     return false;
 468   }
 469
 470   /* (non-Javadoc)
 471    * @see jalview.analysis.FinderI#getIdMatch()
 472    */
 473   @Override
 474   public Vector<SequenceI> getIdMatches()
 475   {
 476     return idMatches;
 477   }
 478
 479   /* (non-Javadoc)
 480    * @see jalview.analysis.FinderI#getSearchResults()
 481    */
 482   @Override
 483   public SearchResultsI getSearchResults()
 484   {
 485     return searchResults;
 486   }
 487 }