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