src/jalview/datamodel/features/FeatureStoreJS.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.features;
  22
  23 import jalview.datamodel.SequenceFeature;
  24
  25 import java.util.ArrayList;
  26 import java.util.List;
  27
  28 import intervalstore.nonc.IntervalStore;
  29
  30 /**
  31  * An adaption of FeatureStore that is efficient and lightweight, accelerating
  32  * processing speed in JavaScript.
  33  *
  34  * It could be used in Java as well, with significant acceleration, but all this
  35  * is so fast anyway that it probably will not be noticed in Java to speed it up
  36  * by a factor of two or three. So for now, at least, this implementation is
  37  * just in JavaScript. The flag for this is in SequenceFeatures.
  38  *
  39  * This implementation uses the IntervalStore developed by Bob Hanson, found at
  40  * https://github.com/BobHanson/IntervalStoreJ, forked from the one developed by
  41  * Mungo Carstairs at https://github.com/bartongroup/IntervalStoreJ.
  42  *
  43  * See the discussion folder at https://github.com/BobHanson/IntervalStoreJ for
  44  * details.
  45  *
  46  * @author gmcarstairs
  47  * @author Bob Hanson 2019.08.03-2019.08.16
  48  *
  49  */
  50 public class FeatureStoreJS extends FeatureStore
  51 {
  52   private IntervalStore<SequenceFeature> featureStore;
  53
  54   public FeatureStoreJS()
  55   {
  56     // the only reference to features field in this class -- for the superclass
  57
  58     // linked-list no-NCList IntervalStore with presort
  59
  60     features = featureStore = new IntervalStore<>(true);
  61   }
  62
  63   /**
  64    * Add a contact feature to the lists that hold them ordered by start (first
  65    * contact) and by end (second contact) position, ensuring the lists remain
  66    * ordered. This method allows duplicate features to be added, so test before
  67    * calling to avoid this.
  68    *
  69    * @param feature
  70    * @return true
  71    */
  72   @Override
  73   protected synchronized boolean addContactFeature(SequenceFeature feature)
  74   {
  75     if (contactFeatureStarts == null)
  76     {
  77       contactFeatureStarts = new ArrayList<>();
  78       contactFeatureEnds = new ArrayList<>();
  79     }
  80     contactFeatureStarts.add(
  81             findFirstBegin(contactFeatureStarts, feature.begin), feature);
  82     contactFeatureEnds.add(findFirstEnd(contactFeatureEnds, feature.end),
  83             feature);
  84     return true;
  85   }
  86
  87
  88   /**
  89    * Add a feature to the IntervalStore, not allowing for duplicates.
  90    *
  91    *
  92    * @return false if could not add it (late check for duplicate)
  93    */
  94   @Override
  95   protected synchronized boolean addPositionalFeature(
  96           SequenceFeature feature)
  97   {
  98     return featureStore.add(feature, false);
  99   }
 100
 101   /**
 102    * Initial check in FeatureStore.add(feature) that in other implementations
 103    * does a containment check, but in this implementation just returns false to
 104    * indicate that we should continue. This implementation will do this check as
 105    * part of the add() method for greater efficiency (one binary search instead
 106    * of two).
 107    *
 108    * @return false -- meaning "maybe not contained; continue adding"
 109    */
 110   @Override
 111   protected boolean checkContainsPositionalFeatureForAdd(
 112           SequenceFeature feature)
 113   {
 114     return false;
 115   }
 116
 117   /**
 118    * Check to see if a feature (or its equivalent based on
 119    * IntervalI.equalsInterval) is already in this store. This method should be
 120    * avoided except when necessary, as it involves a binary search with identity
 121    * check.
 122    *
 123    * @return true if this feature or its equivalent (based on equalsInterval) is
 124    *         present already in the collection.
 125    */
 126   @Override
 127   protected boolean containsFeature(SequenceFeature feature)
 128   {
 129     return featureStore.contains(feature);
 130   }
 131
 132   @Override
 133   protected boolean findAndRemoveNonContactFeature(SequenceFeature sf)
 134   {
 135     return featureStore.remove(sf);
 136   }
 137
 138   /**
 139    * Add contact features to the result list where either the second or the
 140    * first contact position lies within the target range, inclusively.
 141    *
 142    * @param from
 143    * @param to
 144    * @param result
 145    */
 146   @Override
 147   protected void findContactFeatures(long from, long to,
 148           List<SequenceFeature> result)
 149   {
 150     getContactStartOverlaps(from, to, result);
 151     getContactEndOverlaps(from, to, result);
 152   }
 153
 154   /**
 155    * Locate the first feature start in a standard ArrayList that is at or after
 156    * this position.
 157    *
 158    */
 159
 160   @Override
 161   protected int findFirstBegin(List<SequenceFeature> list, long pos)
 162   {
 163     int matched = list.size();
 164     int end = matched - 1;
 165     int start = (end < 0 || list.get(end).begin < pos ? matched : 0);
 166     while (start <= end)
 167     {
 168       int mid = (start + end) / 2;
 169       if (list.get(mid).begin >= pos)
 170       {
 171         matched = mid;
 172         end = mid - 1;
 173       }
 174       else
 175       {
 176         start = mid + 1;
 177       }
 178     }
 179     return matched;
 180   }
 181
 182   /**
 183    * Locate the feature end in a standard ArrayList that is after or at this
 184    * position.
 185    *
 186    */
 187
 188   @Override
 189   protected int findFirstEnd(List<SequenceFeature> list, long pos)
 190   {
 191     int matched = list.size();
 192     int end = matched - 1;
 193     int start = 0;
 194     while (start <= end)
 195     {
 196       int mid = (start + end) / 2;
 197       if (list.get(mid).end >= pos)
 198       {
 199         matched = mid;
 200         end = mid - 1;
 201       }
 202       else
 203       {
 204         start = mid + 1;
 205       }
 206     }
 207     return matched;
 208   }
 209
 210   /**
 211    * Returns a (possibly empty) list of features whose extent overlaps the given
 212    * range. The returned list is ordered as follows:
 213    *
 214    * (1) ContactFeature starts
 215    *
 216    * (2) ContactFeature ends (that are not also starts)
 217    *
 218    * (3) noncontact SequenceFeatures, in reverse start order
 219    *
 220    * (This last reverse order is for efficiency in processing only.)
 221    *
 222    *
 223    *
 224    * @param start
 225    *          start position of overlap range (inclusive)
 226    * @param end
 227    *          end position of overlap range (inclusive)
 228    *
 229    * @param result
 230    *          optional result list; for highest efficiency, provide this
 231    *          parameter
 232    * @return result same as result parameter, or a new ArrayList if that is null
 233    */
 234
 235   @Override
 236   public List<SequenceFeature> findOverlappingFeatures(long start, long end,
 237           List<SequenceFeature> result)
 238   {
 239     if (result == null)
 240     {
 241       result = new ArrayList<>();
 242     }
 243     if (contactFeatureStarts != null)
 244     {
 245       if (start == end)
 246       {
 247         getContactPoints(contactFeatureStarts, start, result, true);
 248         getContactPoints(contactFeatureEnds, start, result, false);
 249       }
 250       else
 251       {
 252         findContactFeatures(start, end, result);
 253       }
 254     }
 255     if (featureStore.size() > 0)
 256     {
 257       featureStore.findOverlaps(start, end, result);
 258     }
 259     return result;
 260   }
 261
 262   /**
 263    * Adds to the result list any contact features having end (second contact
 264    * point), but not start (first contact point), in the query from-to range
 265    *
 266    * @param from
 267    * @param to
 268    * @param result
 269    */
 270
 271   private void getContactEndOverlaps(long from, long to,
 272           List<SequenceFeature> result)
 273   {
 274     // find the first contact feature (if any)
 275     // with end point not before the target range
 276
 277     for (int i = findFirstEnd(contactFeatureEnds,
 278             from), n = contactFeatureEnds.size(); i < n; i++)
 279     {
 280       SequenceFeature sf = contactFeatureEnds.get(i);
 281       if (sf.begin >= from && sf.begin <= to)
 282       {
 283         // this feature's first contact position lies in the search range
 284         // so we don't include it in results a second time
 285         continue;
 286       }
 287
 288       if (sf.end > to)
 289       {
 290         // this feature (and all following) has end point after the target range
 291         break;
 292       }
 293
 294       // feature has end >= from and end <= to
 295       // i.e. contact end point lies within overlap search range
 296       result.add(sf);
 297     }
 298   }
 299
 300   /**
 301    * Binary search for contact start or end matching a specific position. This
 302    * efficient search was designed specifically for rapid return for the
 303    * OverviewPanel. It's implementation sped processing of that panel by 2300%.
 304    *
 305    * @param l
 306    * @param pos
 307    * @param result
 308    * @param isStart
 309    *
 310    * @author Bob Hanson 2019.07.30
 311    */
 312   private void getContactPoints(List<SequenceFeature> l, long pos,
 313           List<SequenceFeature> result, boolean isStart)
 314   {
 315     int low = 0;
 316     int high = l.size() - 1;
 317     while (low <= high)
 318     {
 319       int mid = (low + high) >>> 1;
 320       SequenceFeature f = l.get(mid);
 321       switch (Long.signum((isStart ? f.begin : f.end) - pos))
 322       {
 323       case -1:
 324         low = mid + 1;
 325         continue;
 326       case 1:
 327         high = mid - 1;
 328         continue;
 329       case 0:
 330         int m = mid;
 331         result.add(f);
 332         // could be "5" in 12345556788 ?
 333         while (++mid <= high && (f = l.get(mid)) != null
 334                 && (isStart ? f.begin : f.end) == pos)
 335         {
 336           result.add(f);
 337         }
 338         while (--m >= low && (f = l.get(m)) != null
 339                 && (isStart ? f.begin : f.end) == pos)
 340         {
 341           result.add(f);
 342         }
 343         return;
 344       }
 345     }
 346   }
 347
 348   /**
 349    * Adds contact features whose start position lies in the from-to range to the
 350    * result list
 351    *
 352    * @param from
 353    * @param to
 354    * @param result
 355    */
 356
 357   private void getContactStartOverlaps(long from, long to,
 358           List<SequenceFeature> result)
 359   {
 360     for (int i = findFirstBegin(contactFeatureStarts,
 361             from), n = contactFeatureStarts.size(); i < n; i++)
 362     {
 363       SequenceFeature sf = contactFeatureStarts.get(i);
 364       if (sf.begin > to)
 365       {
 366         break;
 367       }
 368       result.add(sf);
 369     }
 370   }
 371 }