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