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 java.util.Locale;
  24
  25 import jalview.api.AlignViewportI;
  26 import jalview.api.FinderI;
  27 import jalview.datamodel.AlignmentI;
  28 import jalview.datamodel.SearchResultMatchI;
  29 import jalview.datamodel.SearchResults;
  30 import jalview.datamodel.SearchResultsI;
  31 import jalview.datamodel.SequenceGroup;
  32 import jalview.datamodel.SequenceI;
  33 import jalview.util.Comparison;
  34 import jalview.util.Platform;
  35 import jalview.util.MapList;
  36
  37 import java.util.ArrayList;
  38 import java.util.Arrays;
  39 import java.util.Iterator;
  40 import java.util.List;
  41
  42 import com.stevesoft.pat.Regex;
  43
  44 /**
  45  * Implements the search algorithm for the Find dialog
  46  */
  47 public class Finder implements FinderI
  48 {
  49   /*
  50    * matched residue locations
  51    */
  52   private SearchResultsI searchResults;
  53
  54   /*
  55    * sequences matched by id or description
  56    */
  57   private List<SequenceI> idMatches;
  58
  59   /*
  60    * the viewport to search over
  61    */
  62   private AlignViewportI viewport;
  63
  64   /*
  65    * sequence index in alignment to search from
  66    */
  67   private int sequenceIndex;
  68
  69   /*
  70    * position offset in sequence to search from, base 0
  71    * (position after start of last match for a 'find next')
  72    */
  73   private int residueIndex;
  74
  75   /*
  76    * the true sequence position of the start of the
  77    * last sequence searched (when 'ignore hidden regions' does not apply)
  78    */
  79   private int searchedSequenceStartPosition;
  80
  81   /*
  82    * when 'ignore hidden regions' applies, this holds the mapping from
  83    * the visible sequence positions (1, 2, ...) to true sequence positions
  84    */
  85   private MapList searchedSequenceMap;
  86
  87   private String seqToSearch;
  88
  89   /**
  90    * Constructor for searching a viewport
  91    *
  92    * @param av
  93    */
  94   public Finder(AlignViewportI av)
  95   {
  96     this.viewport = av;
  97     this.sequenceIndex = 0;
  98     this.residueIndex = -1;
  99   }
 100
 101   @Override
 102   public void findAll(String theSearchString, boolean matchCase,
 103           boolean searchDescription, boolean ignoreHidden)
 104   {
 105     /*
 106      * search from the start
 107      */
 108     sequenceIndex = 0;
 109     residueIndex = -1;
 110
 111     doFind(theSearchString, matchCase, searchDescription, true,
 112             ignoreHidden);
 113
 114     /*
 115      * reset to start for next search
 116      */
 117     sequenceIndex = 0;
 118     residueIndex = -1;
 119   }
 120
 121   @Override
 122   public void findNext(String theSearchString, boolean matchCase,
 123           boolean searchDescription, boolean ignoreHidden)
 124   {
 125     doFind(theSearchString, matchCase, searchDescription, false,
 126             ignoreHidden);
 127
 128     if (searchResults.isEmpty() && idMatches.isEmpty())
 129     {
 130       /*
 131        * search failed - reset to start for next search
 132        */
 133       sequenceIndex = 0;
 134       residueIndex = -1;
 135     }
 136   }
 137
 138   /**
 139    * Performs a 'find next' or 'find all'
 140    *
 141    * @param theSearchString
 142    * @param matchCase
 143    * @param searchDescription
 144    * @param findAll
 145    * @param ignoreHidden
 146    */
 147   protected void doFind(String theSearchString, boolean matchCase,
 148           boolean searchDescription, boolean findAll, boolean ignoreHidden)
 149   {
 150     searchResults = new SearchResults();
 151     idMatches = new ArrayList<>();
 152
 153     String searchString = matchCase ? theSearchString
 154             : theSearchString.toUpperCase(Locale.ROOT);
 155   Regex searchPattern = Platform.newRegex(searchString);
 156     searchPattern.setIgnoreCase(!matchCase);
 157
 158     SequenceGroup selection = viewport.getSelectionGroup();
 159     if (selection != null && selection.getSize() < 1)
 160     {
 161       selection = null; // ? ignore column-only selection
 162     }
 163
 164     AlignmentI alignment = viewport.getAlignment();
 165     int end = alignment.getHeight();
 166
 167     getSequence(ignoreHidden);
 168
 169     boolean found = false;
 170     while ((!found || findAll) && sequenceIndex < end)
 171     {
 172       found = findNextMatch(searchString, searchPattern, searchDescription,
 173               ignoreHidden);
 174     }
 175   }
 176
 177   /**
 178    * Calculates and saves the sequence string to search. The string is
 179    * restricted to the current selection region if there is one, and is saved
 180    * with all gaps removed.
 181    * <p>
 182    * If there are hidden columns, and option {@ignoreHidden} is selected, then
 183    * only visible positions of the sequence are included, and a mapping is also
 184    * constructed from the returned string positions to the true sequence
 185    * positions.
 186    * <p>
 187    * Note we have to do this each time {@code findNext} or {@code findAll} is
 188    * called, in case the alignment, selection group or hidden columns have
 189    * changed. In particular, if the sequence at offset {@code sequenceIndex} in
 190    * the alignment is (no longer) in the selection group, search is advanced to
 191    * the next sequence that is.
 192    * <p>
 193    * Sets sequence string to the empty string if there are no more sequences (in
 194    * selection group if any) at or after {@code sequenceIndex}.
 195    * <p>
 196    * Returns true if a sequence could be found, false if end of alignment was
 197    * reached
 198    *
 199    * @param ignoreHidden
 200    * @return
 201    */
 202   private boolean getSequence(boolean ignoreHidden)
 203   {
 204     AlignmentI alignment = viewport.getAlignment();
 205     if (sequenceIndex >= alignment.getHeight())
 206     {
 207       seqToSearch = "";
 208       return false;
 209     }
 210     SequenceI seq = alignment.getSequenceAt(sequenceIndex);
 211     SequenceGroup selection = viewport.getSelectionGroup();
 212     if (selection != null && !selection.contains(seq))
 213     {
 214       if (!nextSequence(ignoreHidden))
 215       {
 216         return false;
 217       }
 218       seq = alignment.getSequenceAt(sequenceIndex);
 219     }
 220
 221     String seqString = null;
 222     if (ignoreHidden)
 223     {
 224       seqString = getVisibleSequence(seq);
 225       this.searchedSequenceStartPosition = 1;
 226     }
 227     else
 228     {
 229       int startCol = 0;
 230       int endCol = seq.getLength() - 1;
 231       this.searchedSequenceStartPosition = seq.getStart();
 232       if (selection != null)
 233       {
 234         startCol = selection.getStartRes();
 235         endCol = Math.min(endCol, selection.getEndRes());
 236         this.searchedSequenceStartPosition = seq.findPosition(startCol);
 237       }
 238       seqString = seq.getSequenceAsString(startCol, endCol + 1);
 239     }
 240
 241     /*
 242      * remove gaps; note that even if this leaves an empty string, we 'search'
 243      * the sequence anyway (for possible match on name or description)
 244      */
 245     String ungapped = AlignSeq.extractGaps(Comparison.GapChars, seqString);
 246     this.seqToSearch = ungapped;
 247
 248     return true;
 249   }
 250
 251   /**
 252    * Returns a string consisting of only the visible residues of {@code seq}
 253    * from alignment column {@ fromColumn}, restricted to the current selection
 254    * region if there is one.
 255    * <p>
 256    * As a side-effect, also computes the mapping from the true sequence
 257    * positions to the positions (1, 2, ...) of the returned sequence. This is to
 258    * allow search matches in the visible sequence to be converted to sequence
 259    * positions.
 260    *
 261    * @param seq
 262    * @return
 263    */
 264   private String getVisibleSequence(SequenceI seq)
 265   {
 266     /*
 267      * get start / end columns of sequence and convert to base 0
 268      * (so as to match the visible column ranges)
 269      */
 270     int seqStartCol = seq.findIndex(seq.getStart()) - 1;
 271     int seqEndCol = seq.findIndex(seq.getStart() + seq.getLength() - 1) - 1;
 272     Iterator<int[]> visibleColumns = viewport.getViewAsVisibleContigs(true);
 273     StringBuilder visibleSeq = new StringBuilder(seqEndCol - seqStartCol);
 274     List<int[]> fromRanges = new ArrayList<>();
 275
 276     while (visibleColumns.hasNext())
 277     {
 278       int[] range = visibleColumns.next();
 279       if (range[0] > seqEndCol)
 280       {
 281         // beyond the end of the sequence
 282         break;
 283       }
 284       if (range[1] < seqStartCol)
 285       {
 286         // before the start of the sequence
 287         continue;
 288       }
 289       String subseq = seq.getSequenceAsString(range[0], range[1] + 1);
 290       String ungapped = AlignSeq.extractGaps(Comparison.GapChars, subseq);
 291       visibleSeq.append(ungapped);
 292       if (!ungapped.isEmpty())
 293       {
 294         /*
 295          * visible region includes at least one non-gap character,
 296          * so add the range to the mapping being constructed
 297          */
 298         int seqResFrom = seq.findPosition(range[0]);
 299         int seqResTo = seqResFrom + ungapped.length() - 1;
 300         fromRanges.add(new int[] { seqResFrom, seqResTo });
 301       }
 302     }
 303
 304     /*
 305      * construct the mapping
 306      * from: visible sequence positions 1..length
 307      * to:   true residue positions of the alignment sequence
 308      */
 309     List<int[]> toRange = Arrays
 310             .asList(new int[]
 311             { 1, visibleSeq.length() });
 312     searchedSequenceMap = new MapList(fromRanges, toRange, 1, 1);
 313
 314     return visibleSeq.toString();
 315   }
 316
 317   /**
 318    * Advances the search to the next sequence in the alignment. Sequences not in
 319    * the current selection group (if there is one) are skipped. The
 320    * (sub-)sequence to be searched is extracted, gaps removed, and saved, or set
 321    * to null if there are no more sequences to search.
 322    * <p>
 323    * Returns true if a sequence could be found, false if end of alignment was
 324    * reached
 325    *
 326    * @param ignoreHidden
 327    */
 328   private boolean nextSequence(boolean ignoreHidden)
 329   {
 330     sequenceIndex++;
 331     residueIndex = -1;
 332
 333     return getSequence(ignoreHidden);
 334   }
 335
 336   /**
 337    * Finds the next match in the given sequence, starting at offset
 338    * {@code residueIndex}. Answers true if a match is found, else false.
 339    * <p>
 340    * If a match is found, {@code residueIndex} is advanced to the position after
 341    * the start of the matched region, ready for the next search.
 342    * <p>
 343    * If no match is found, {@code sequenceIndex} is advanced ready to search the
 344    * next sequence.
 345    *
 346    * @param seqToSearch
 347    * @param searchString
 348    * @param searchPattern
 349    * @param matchDescription
 350    * @param ignoreHidden
 351    * @return
 352    */
 353   protected boolean findNextMatch(String searchString, Regex searchPattern,
 354           boolean matchDescription, boolean ignoreHidden)
 355   {
 356     if (residueIndex < 0)
 357     {
 358       /*
 359        * at start of sequence; try find by residue number, in sequence id,
 360        * or (optionally) in sequence description
 361        */
 362       if (doNonMotifSearches(searchString, searchPattern, matchDescription))
 363       {
 364         return true;
 365       }
 366     }
 367
 368     /*
 369      * search for next match in sequence string
 370      */
 371     int end = seqToSearch.length();
 372     while (residueIndex < end)
 373     {
 374       boolean matched = searchPattern.searchFrom(seqToSearch, residueIndex);
 375       if (matched)
 376       {
 377         if (recordMatch(searchPattern, ignoreHidden))
 378         {
 379           return true;
 380         }
 381       }
 382       else
 383       {
 384         residueIndex = Integer.MAX_VALUE;
 385       }
 386     }
 387
 388     nextSequence(ignoreHidden);
 389     return false;
 390   }
 391
 392   /**
 393    * Adds the match held in the <code>searchPattern</code> Regex to the
 394    * <code>searchResults</code>, unless it is a subregion of the last match
 395    * recorded. <code>residueIndex</code> is advanced to the position after the
 396    * start of the matched region, ready for the next search. Answers true if a
 397    * match was added, else false.
 398    * <p>
 399    * Matches that lie entirely within hidden regions of the alignment are not
 400    * added.
 401    *
 402    * @param searchPattern
 403    * @param ignoreHidden
 404    * @return
 405    */
 406   protected boolean recordMatch(Regex searchPattern, boolean ignoreHidden)
 407   {
 408     SequenceI seq = viewport.getAlignment().getSequenceAt(sequenceIndex);
 409
 410     /*
 411      * convert start/end of the match to sequence coordinates
 412      */
 413     int offset = searchPattern.matchedFrom();
 414     int matchStartPosition = this.searchedSequenceStartPosition + offset;
 415     int matchEndPosition = matchStartPosition + searchPattern.charsMatched()
 416             - 1;
 417
 418     /*
 419      * update residueIndex to next position after the start of the match
 420      * (findIndex returns a value base 1, columnIndex is held base 0)
 421      */
 422     residueIndex = searchPattern.matchedFrom() + 1;
 423
 424     /*
 425      * return false if the match is entirely in a hidden region
 426      */
 427     if (allHidden(seq, matchStartPosition, matchEndPosition))
 428     {
 429       return false;
 430     }
 431
 432     /*
 433      * check that this match is not a subset of the previous one (JAL-2302)
 434      */
 435     List<SearchResultMatchI> matches = searchResults.getResults();
 436     SearchResultMatchI lastMatch = matches.isEmpty() ? null
 437             : matches.get(matches.size() - 1);
 438
 439     if (lastMatch == null || !lastMatch.contains(seq, matchStartPosition,
 440             matchEndPosition))
 441     {
 442       addMatch(seq, matchStartPosition, matchEndPosition, ignoreHidden);
 443       return true;
 444     }
 445
 446     return false;
 447   }
 448
 449   /**
 450    * Adds one match to the stored list. If hidden residues are being skipped,
 451    * then the match may need to be split into contiguous positions of the
 452    * sequence (so it does not include skipped residues).
 453    *
 454    * @param seq
 455    * @param matchStartPosition
 456    * @param matchEndPosition
 457    * @param ignoreHidden
 458    */
 459   private void addMatch(SequenceI seq, int matchStartPosition,
 460           int matchEndPosition, boolean ignoreHidden)
 461   {
 462     if (!ignoreHidden)
 463     {
 464       /*
 465        * simple case
 466        */
 467       searchResults.addResult(seq, matchStartPosition, matchEndPosition);
 468       return;
 469     }
 470
 471     /*
 472      *  get start-end contiguous ranges in underlying sequence
 473      */
 474     int[] truePositions = searchedSequenceMap
 475             .locateInFrom(matchStartPosition, matchEndPosition);
 476     searchResults.addResult(seq, truePositions);
 477   }
 478
 479   /**
 480    * Returns true if all residues are hidden, else false
 481    *
 482    * @param seq
 483    * @param fromPos
 484    * @param toPos
 485    * @return
 486    */
 487   private boolean allHidden(SequenceI seq, int fromPos, int toPos)
 488   {
 489     if (!viewport.hasHiddenColumns())
 490     {
 491       return false;
 492     }
 493     for (int res = fromPos; res <= toPos; res++)
 494     {
 495       if (isVisible(seq, res))
 496       {
 497         return false;
 498       }
 499     }
 500     return true;
 501   }
 502
 503   /**
 504    * Does searches other than for residue patterns. Currently this includes
 505    * <ul>
 506    * <li>find residue by position (if search string is a number)</li>
 507    * <li>match search string to sequence id</li>
 508    * <li>match search string to sequence description (optional)</li>
 509    * </ul>
 510    * Answers true if a match is found, else false.
 511    *
 512    * @param searchString
 513    * @param searchPattern
 514    * @param includeDescription
 515    * @return
 516    */
 517   protected boolean doNonMotifSearches(String searchString,
 518           Regex searchPattern, boolean includeDescription)
 519   {
 520     SequenceI seq = viewport.getAlignment().getSequenceAt(sequenceIndex);
 521
 522     /*
 523      * position sequence search to start of sequence
 524      */
 525     residueIndex = 0;
 526     try
 527     {
 528       int res = Integer.parseInt(searchString);
 529       return searchForResidueNumber(seq, res);
 530     } catch (NumberFormatException ex)
 531     {
 532       // search pattern is not a number
 533     }
 534
 535     if (searchSequenceName(seq, searchPattern))
 536     {
 537       return true;
 538     }
 539     if (includeDescription && searchSequenceDescription(seq, searchPattern))
 540     {
 541       return true;
 542     }
 543     return false;
 544   }
 545
 546   /**
 547    * Searches for a match with the sequence description, and if found, adds the
 548    * sequence to the list of match ids (but not as a duplicate). Answers true if
 549    * a match was added, else false.
 550    *
 551    * @param seq
 552    * @param searchPattern
 553    * @return
 554    */
 555   protected boolean searchSequenceDescription(SequenceI seq,
 556           Regex searchPattern)
 557   {
 558     String desc = seq.getDescription();
 559     if (desc != null && searchPattern.search(desc)
 560             && !idMatches.contains(seq))
 561     {
 562       idMatches.add(seq);
 563       return true;
 564     }
 565     return false;
 566   }
 567
 568   /**
 569    * Searches for a match with the sequence name, and if found, adds the
 570    * sequence to the list of match ids (but not as a duplicate). Answers true if
 571    * a match was added, else false.
 572    *
 573    * @param seq
 574    * @param searchPattern
 575    * @return
 576    */
 577   protected boolean searchSequenceName(SequenceI seq, Regex searchPattern)
 578   {
 579     if (searchPattern.search(seq.getName()) && !idMatches.contains(seq))
 580     {
 581       idMatches.add(seq);
 582       return true;
 583     }
 584     return false;
 585   }
 586
 587   /**
 588    * If the residue position is valid for the sequence, and in a visible column,
 589    * adds the position to the search results and returns true, else answers
 590    * false.
 591    *
 592    * @param seq
 593    * @param resNo
 594    * @return
 595    */
 596   protected boolean searchForResidueNumber(SequenceI seq, int resNo)
 597   {
 598     if (seq.getStart() <= resNo && seq.getEnd() >= resNo)
 599     {
 600       if (isVisible(seq, resNo))
 601       {
 602         searchResults.addResult(seq, resNo, resNo);
 603         return true;
 604       }
 605     }
 606     return false;
 607   }
 608
 609   /**
 610    * Returns true if the residue is in a visible column, else false
 611    *
 612    * @param seq
 613    * @param res
 614    * @return
 615    */
 616   private boolean isVisible(SequenceI seq, int res)
 617   {
 618     if (!viewport.hasHiddenColumns())
 619     {
 620       return true;
 621     }
 622     int col = seq.findIndex(res); // base 1
 623     return viewport.getAlignment().getHiddenColumns().isVisible(col - 1); // base
 624                                                                           // 0
 625   }
 626
 627   @Override
 628   public List<SequenceI> getIdMatches()
 629   {
 630     return idMatches;
 631   }
 632
 633   @Override
 634   public SearchResultsI getSearchResults()
 635   {
 636     return searchResults;
 637   }
 638 }