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