src/jalview/datamodel/SearchResults.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.datamodel;
  22
  23 import java.util.ArrayList;
  24 import java.util.BitSet;
  25 import java.util.List;
  26 import java.util.SortedSet;
  27 import java.util.TreeSet;
  28
  29 /**
  30  * Holds a list of search result matches, where each match is a contiguous
  31  * stretch of a single sequence.
  32  *
  33  * @author gmcarstairs amwaterhouse
  34  *
  35  */
  36 public class SearchResults implements SearchResultsI
  37 {
  38   private int count;
  39
  40   private SortedSet<SearchResultMatchI> matches = new TreeSet<>();
  41
  42   /**
  43    * One match consists of a sequence reference, start and end positions.
  44    * Discontiguous ranges in a sequence require two or more Match objects.
  45    */
  46   public class Match implements SearchResultMatchI, Comparable<SearchResultMatchI>
  47   {
  48     final SequenceI sequence;
  49
  50     /**
  51      * Start position of match in sequence (base 1)
  52      */
  53     final int start;
  54
  55     /**
  56      * End position (inclusive) (base 1)
  57      */
  58     final int end;
  59
  60     /**
  61      * create a Match on a range of sequence. Match always holds region in
  62      * forwards order, even if given in reverse order (such as from a mapping to
  63      * a reverse strand); this avoids trouble for routines that highlight search
  64      * results etc
  65      *
  66      * @param seq
  67      *          a sequence
  68      * @param start
  69      *          start position of matched range (base 1)
  70      * @param end
  71      *          end of matched range (inclusive, base 1)
  72      */
  73     public Match(SequenceI seq, int start, int end)
  74     {
  75       sequence = seq;
  76
  77       /*
  78        * always hold in forwards order, even if given in reverse order
  79        * (such as from a mapping to a reverse strand); this avoids
  80        * trouble for routines that highlight search results etc
  81        */
  82       if (start <= end)
  83       {
  84         this.start = start;
  85         this.end = end;
  86       }
  87       else
  88       {
  89         // TODO: JBP could mark match as being specified in reverse direction
  90         // for use
  91         // by caller ? e.g. visualizing reverse strand highlight
  92         this.start = end;
  93         this.end = start;
  94       }
  95     }
  96
  97     @Override
  98     public SequenceI getSequence()
  99     {
 100       return sequence;
 101     }
 102
 103     @Override
 104     public int getStart()
 105     {
 106       return start;
 107     }
 108
 109     @Override
 110     public int getEnd()
 111     {
 112       return end;
 113     }
 114
 115     /**
 116      * Returns a representation as "seqid/start-end"
 117      */
 118     @Override
 119     public String toString()
 120     {
 121       StringBuilder sb = new StringBuilder();
 122       if (sequence != null)
 123       {
 124         sb.append(sequence.getName()).append("/");
 125       }
 126       sb.append(start).append("-").append(end);
 127       return sb.toString();
 128     }
 129
 130     /**
 131      * Hashcode is the hashcode of the matched sequence plus a hash of start and
 132      * end positions. Match objects that pass the test for equals are guaranteed
 133      * to have the same hashcode.
 134      */
 135     @Override
 136     public int hashCode()
 137     {
 138       int hash = sequence == null ? 0 : sequence.hashCode();
 139       hash += 31 * start;
 140       hash += 67 * end;
 141       return hash;
 142     }
 143
 144     /**
 145      * Two Match objects are equal if they are for the same sequence, start and
 146      * end positions
 147      */
 148     @Override
 149     public boolean equals(Object obj)
 150     {
 151       if (obj == null || !(obj instanceof SearchResultMatchI))
 152       {
 153         return false;
 154       }
 155       SearchResultMatchI m = (SearchResultMatchI) obj;
 156       return (sequence == m.getSequence() && start == m.getStart()
 157               && end == m.getEnd());
 158     }
 159
 160     @Override
 161     public boolean contains(SequenceI seq, int from, int to)
 162     {
 163       return (sequence == seq && start <= from && end >= to);
 164     }
 165     @Override
 166     public boolean adjacent(SequenceI seq, int from, int to)
 167     {
 168       return (sequence == seq && ((start <= from && end >= to) || (from<=(end+1) && to >=(end+1)) || (from<=(start-1) && to>=(start-1))));
 169     }
 170
 171     @Override
 172     public int compareTo(SearchResultMatchI o)
 173     {
 174       if (start<o.getStart())
 175       {
 176         return -1;
 177       }
 178       if (start > o.getStart())
 179       {
 180         return +1;
 181       }
 182       if (end < o.getEnd())
 183       {
 184         return -1;
 185       }
 186       if (end > o.getEnd())
 187       {
 188         return +1;
 189       }
 190       if (sequence!=o.getSequence())
 191       {
 192         int hashc =sequence.hashCode(),oseq=o.getSequence().hashCode();
 193         return (hashc < oseq) ? -1 : 1;
 194       }
 195       return 0;
 196     }
 197
 198   }
 199
 200   @Override
 201   public SearchResultMatchI addResult(SequenceI seq, int start, int end)
 202   {
 203     Match m = new Match(seq, start, end);
 204     if (!matches.contains(m))
 205     {
 206       matches.add(m);
 207       count++;
 208     }
 209     return m;
 210   }
 211
 212   @Override
 213   public void addResult(SequenceI seq, int[] positions)
 214   {
 215     /*
 216      * we only increment the match count by 1 - or not at all,
 217      * if the matches are all duplicates of existing
 218      */
 219     int beforeCount = count;
 220     for (int i = 0; i < positions.length - 1; i += 2)
 221     {
 222       addResult(seq, positions[i], positions[i + 1]);
 223     }
 224     if (count > beforeCount)
 225     {
 226       count = beforeCount + 1;
 227     }
 228   }
 229
 230
 231   @Override
 232   public boolean appendResult(SequenceI sequence, int start, int end)
 233   {
 234
 235     Match m = new Match(sequence, start, end);
 236     Match toAdd=null;
 237
 238     if (matches.contains(m))
 239     {
 240       return false;
 241     }
 242     boolean appending=false;
 243
 244     // we dynamically maintain an interval to add as we test each range in the list
 245
 246     int cstart=start,cend=end;
 247     List<SearchResultMatchI> toRemove=new ArrayList<>();
 248     for (SearchResultMatchI thatm:matches)
 249     {
 250       if (thatm.getSequence()==sequence)
 251       {
 252         if (thatm.adjacent(sequence, cstart, cend))
 253         {
 254           // update the match to add with the adjacent start/end
 255           start = Math.min(m.start, thatm.getStart());
 256           end = Math.max(m.end, thatm.getEnd());
 257           // and check if we keep or remove the old one
 258           if (thatm.getStart()!=start || thatm.getEnd()!=end)
 259           {
 260             toRemove.add(thatm);
 261             count--;
 262             cstart = start;
 263             cend = end;
 264             appending=true;
 265           } else {
 266             return false;
 267           }
 268         }
 269       }
 270     }
 271     matches.removeAll(toRemove);
 272     {
 273       matches.add(new Match(sequence,cstart,cend));
 274       count++;
 275     }
 276     return appending;
 277   }
 278   @Override
 279   public boolean involvesSequence(SequenceI sequence)
 280   {
 281     final int start = sequence.getStart();
 282     final int end = sequence.getEnd();
 283
 284     SequenceI ds = sequence.getDatasetSequence();
 285     for (SearchResultMatchI m : matches)
 286     {
 287       SequenceI matched = m.getSequence();
 288       if (matched != null && (matched == sequence || matched == ds)
 289               && (m.getEnd() >= start) && (m.getStart() <= end))
 290       {
 291         return true;
 292       }
 293     }
 294     return false;
 295   }
 296
 297   @Override
 298   public int[] getResults(SequenceI sequence, int start, int end)
 299   {
 300     if (matches.isEmpty())
 301     {
 302       return null;
 303     }
 304
 305     int[] result = null;
 306     int[] tmp = null;
 307     int resultLength, matchStart = 0, matchEnd = 0;
 308     boolean mfound;
 309     Match m;
 310     for (SearchResultMatchI _m : matches)
 311     {
 312       m = (Match) _m;
 313
 314       mfound = false;
 315       if (m.sequence == sequence
 316               || m.sequence == sequence.getDatasetSequence())
 317       {
 318         mfound = true;
 319         matchStart = sequence.findIndex(m.start) - 1;
 320         matchEnd = m.start == m.end ? matchStart
 321                 : sequence.findIndex(m.end) - 1;
 322       }
 323
 324       if (mfound)
 325       {
 326         if (matchStart <= end && matchEnd >= start)
 327         {
 328           if (matchStart < start)
 329           {
 330             matchStart = start;
 331           }
 332
 333           if (matchEnd > end)
 334           {
 335             matchEnd = end;
 336           }
 337
 338           if (result == null)
 339           {
 340             result = new int[] { matchStart, matchEnd };
 341           }
 342           else
 343           {
 344             resultLength = result.length;
 345             tmp = new int[resultLength + 2];
 346             System.arraycopy(result, 0, tmp, 0, resultLength);
 347             result = tmp;
 348             result[resultLength] = matchStart;
 349             result[resultLength + 1] = matchEnd;
 350           }
 351         }
 352         else
 353         {
 354           // debug
 355           // System.err.println("Outwith bounds!" + matchStart+">"+end +" or "
 356           // + matchEnd+"<"+start);
 357         }
 358       }
 359     }
 360     return result;
 361   }
 362
 363   @Override
 364   public int markColumns(SequenceCollectionI sqcol, BitSet bs)
 365   {
 366     int count = 0;
 367     BitSet mask = new BitSet();
 368     int startRes = sqcol.getStartRes();
 369     int endRes = sqcol.getEndRes();
 370
 371     for (SequenceI s : sqcol.getSequences())
 372     {
 373       int[] cols = getResults(s, startRes, endRes);
 374       if (cols != null)
 375       {
 376         for (int pair = 0; pair < cols.length; pair += 2)
 377         {
 378           mask.set(cols[pair], cols[pair + 1] + 1);
 379         }
 380       }
 381     }
 382     // compute columns that were newly selected
 383     BitSet original = (BitSet) bs.clone();
 384     original.and(mask);
 385     count = mask.cardinality() - original.cardinality();
 386     // and mark ranges not already marked
 387     bs.or(mask);
 388     return count;
 389   }
 390
 391   @Override
 392   public int getCount()
 393   {
 394     return count;
 395   }
 396
 397   @Override
 398   public boolean isEmpty()
 399   {
 400     return matches.isEmpty();
 401   }
 402
 403   @Override
 404   public List<SearchResultMatchI> getResults()
 405   {
 406     return List.copyOf(matches);
 407   }
 408
 409   /**
 410    * Return the results as a list of matches [seq1/from-to, seq2/from-to, ...]
 411    *
 412    * @return
 413    */
 414   @Override
 415   public String toString()
 416   {
 417     return matches == null ? "" : matches.toString();
 418   }
 419
 420   /**
 421    * Hashcode is derived from the list of matches. This ensures that when two
 422    * SearchResults objects satisfy the test for equals(), then they have the
 423    * same hashcode.
 424    *
 425    * @see Match#hashCode()
 426    * @see java.util.AbstractList#hashCode()
 427    */
 428   @Override
 429   public int hashCode()
 430   {
 431     return matches.hashCode();
 432   }
 433
 434   /**
 435    * Two SearchResults are considered equal if they contain the same matches
 436    * (Sequence, start position, end position) in the same order
 437    *
 438    * @see Match#equals(Object)
 439    */
 440   @Override
 441   public boolean equals(Object obj)
 442   {
 443     if (obj == null || !(obj instanceof SearchResultsI))
 444     {
 445       return false;
 446     }
 447     SearchResultsI sr = (SearchResultsI) obj;
 448     return matches.equals(sr.getResults());
 449   }
 450
 451   @Override
 452   public void addSearchResults(SearchResultsI toAdd)
 453   {
 454     matches.addAll(toAdd.getResults());
 455   }
 456
 457   @Override
 458   public List<SequenceI> getMatchingSubSequences()
 459   {
 460     List<SequenceI> seqs = new ArrayList<>();
 461
 462     /*
 463      * assemble dataset sequences, and template new sequence features,
 464      * for the amend features dialog
 465      */
 466     for (SearchResultMatchI match : matches)
 467     {
 468       SequenceI seq = match.getSequence();
 469       while (seq.getDatasetSequence() != null)
 470       {
 471         seq = seq.getDatasetSequence();
 472       }
 473       // getSubSequence is index-base0, findIndex returns index-base1
 474       seqs.add(seq.getSubSequence(seq.findIndex(match.getStart()) - 1,
 475               seq.findIndex(match.getEnd())));
 476     }
 477     return seqs;
 478   }
 479
 480 }