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