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