X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Fdatamodel%2Ffeatures%2FFeatureStoreJS.java;fp=src%2Fjalview%2Fdatamodel%2Ffeatures%2FFeatureStoreJS.java;h=4f4936072946d157a4ff2390631e0da607548b92;hb=a83adb45bdf9554e270921b4baad94defd314b36;hp=0000000000000000000000000000000000000000;hpb=d4ec118f86b5c9dee801e743c46aaacc7bb521d1;p=jalview.git

diff --git a/src/jalview/datamodel/features/FeatureStoreJS.java b/src/jalview/datamodel/features/FeatureStoreJS.java
new file mode 100644
index 0000000..4f49360
--- /dev/null
+++ b/src/jalview/datamodel/features/FeatureStoreJS.java
@@ -0,0 +1,414 @@
+/*
+ * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
+ * Copyright (C) $$Year-Rel$$ The Jalview Authors
+ * 
+ * This file is part of Jalview.
+ * 
+ * Jalview is free software: you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License 
+ * as published by the Free Software Foundation, either version 3
+ * of the License, or (at your option) any later version.
+ *  
+ * Jalview is distributed in the hope that it will be useful, but 
+ * WITHOUT ANY WARRANTY; without even the implied warranty 
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
+ * PURPOSE.  See the GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
+ * The Jalview Authors are detailed in the 'AUTHORS' file.
+ */
+package jalview.datamodel.features;
+
+import jalview.datamodel.SequenceFeature;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import intervalstore.nonc.IntervalStore;
+
+/**
+ * An adaption of FeatureStore that is efficient and lightweight, accelerating
+ * processing speed in JavaScript.
+ * 
+ * It could be used in Java as well, with significant acceleration, but all this
+ * is so fast anyway that it probably will not be noticed in Java to speed it up
+ * by a factor of two or three. So for now, at least, this implementation is
+ * just in JavaScript. The flag for this is in SequenceFeatures.
+ * 
+ * This implementation uses the IntervalStore developed by Bob Hanson, found at
+ * https://github.com/BobHanson/IntervalStoreJ, forked from the one developed by
+ * Mungo Carstairs at https://github.com/bartongroup/IntervalStoreJ.
+ * 
+ * See the discussion folder at https://github.com/BobHanson/IntervalStoreJ for
+ * details.
+ * 
+ * @author gmcarstairs
+ * @author Bob Hanson 2019.08.03-2019.08.16
+ *
+ */
+public class FeatureStoreJS extends FeatureStore
+{
+  private IntervalStore<SequenceFeature> featureStore;
+
+  public FeatureStoreJS()
+  {
+    // the only reference to features field in this class -- for the superclass
+
+    // linked-list no-NCList IntervalStore with presort
+
+    features = featureStore = new IntervalStore<>(true);
+  }
+
+  /**
+   * Add a contact feature to the lists that hold them ordered by start (first
+   * contact) and by end (second contact) position, ensuring the lists remain
+   * ordered. This method allows duplicate features to be added, so test before
+   * calling to avoid this.
+   * 
+   * @param feature
+   * @return true
+   */
+  @Override
+  protected synchronized boolean addContactFeature(SequenceFeature feature)
+  {
+    if (contactFeatureStarts == null)
+    {
+      contactFeatureStarts = new ArrayList<>();
+      contactFeatureEnds = new ArrayList<>();
+    }
+    contactFeatureStarts.add(
+            findFirstBegin(contactFeatureStarts, feature.begin), feature);
+    contactFeatureEnds.add(findFirstEnd(contactFeatureEnds, feature.end),
+            feature);
+    return true;
+  }
+
+
+  /**
+   * Add a feature to the IntervalStore, not allowing for duplicates.
+   *
+   *
+   * @return false if could not add it (late check for duplicate)
+   */
+  @Override
+  protected synchronized boolean addPositionalFeature(
+          SequenceFeature feature)
+  {
+    return featureStore.add(feature, false);
+  }
+
+  /**
+   * Initial check in FeatureStore.add(feature) that in other implementations
+   * does a containment check, but in this implementation just returns false to
+   * indicate that we should continue. This implementation will do this check as
+   * part of the add() method for greater efficiency (one binary search instead
+   * of two).
+   * 
+   * @return false -- meaning "maybe not contained; continue adding"
+   */
+  @Override
+  protected boolean checkContainsPositionalFeatureForAdd(
+          SequenceFeature feature)
+  {
+    return false;
+  }
+
+  /**
+   * Check to see if a feature (or its equivalent based on
+   * IntervalI.equalsInterval) is already in this store. This method should be
+   * avoided except when necessary, as it involves a binary search with identity
+   * check.
+   * 
+   * @return true if this feature or its equivalent (based on equalsInterval) is
+   *         present already in the collection.
+   */
+  @Override
+  protected boolean containsFeature(SequenceFeature feature)
+  {
+    return featureStore.contains(feature);
+  }
+
+  @Override
+  protected boolean findAndRemoveNonContactFeature(SequenceFeature sf)
+  {
+    return featureStore.remove(sf);
+  }
+
+  /**
+   * Add contact features to the result list where either the second or the
+   * first contact position lies within the target range, inclusively.
+   * 
+   * @param from
+   * @param to
+   * @param result
+   */
+  @Override
+  protected void findContactFeatures(long from, long to,
+          List<SequenceFeature> result)
+  {
+    getContactStartOverlaps(from, to, result);
+    getContactEndOverlaps(from, to, result);
+  }
+
+  /**
+   * Locate the first feature start in a standard ArrayList that is at or after
+   * this position.
+   * 
+   */
+
+  @Override
+  protected int findFirstBegin(List<SequenceFeature> list, long pos)
+  {
+    int matched = list.size();
+    int end = matched - 1;
+    int start = (end < 0 || list.get(end).begin < pos ? matched : 0);
+    while (start <= end)
+    {
+      int mid = (start + end) / 2;
+      if (list.get(mid).begin >= pos)
+      {
+        matched = mid;
+        end = mid - 1;
+      }
+      else
+      {
+        start = mid + 1;
+      }
+    }
+    return matched;
+  }
+
+  /**
+   * Locate the feature end in a standard ArrayList that is after or at this
+   * position.
+   * 
+   */
+
+  @Override
+  protected int findFirstEnd(List<SequenceFeature> list, long pos)
+  {
+    int matched = list.size();
+    int end = matched - 1;
+    int start = 0;
+    while (start <= end)
+    {
+      int mid = (start + end) / 2;
+      if (list.get(mid).end >= pos)
+      {
+        matched = mid;
+        end = mid - 1;
+      }
+      else
+      {
+        start = mid + 1;
+      }
+    }
+    return matched;
+  }
+
+  /**
+   * Returns a (possibly empty) list of features whose extent overlaps the given
+   * range. The returned list is ordered as follows:
+   * 
+   * (1) ContactFeature starts
+   * 
+   * (2) ContactFeature ends (that are not also starts)
+   * 
+   * (3) noncontact SequenceFeatures, in reverse start order
+   * 
+   * (This last reverse order is for efficiency in processing only.)
+   * 
+   * 
+   * 
+   * @param start
+   *          start position of overlap range (inclusive)
+   * @param end
+   *          end position of overlap range (inclusive)
+   * 
+   * @param result
+   *          optional result list; for highest efficiency, provide this
+   *          parameter
+   * @return result same as result parameter, or a new ArrayList if that is null
+   */
+
+  @Override
+  public List<SequenceFeature> findOverlappingFeatures(long start, long end,
+          List<SequenceFeature> result)
+  {
+    if (result == null)
+    {
+      result = new ArrayList<>();
+    }
+    if (contactFeatureStarts != null)
+    {
+      if (start == end)
+      {
+        getContactPointStarts(contactFeatureStarts, start, result);
+        getContactPointEnds(contactFeatureEnds, end, result);
+      }
+      else
+      {
+        findContactFeatures(start, end, result);
+      }
+    }
+    if (featureStore.size() > 0)
+    {
+      featureStore.findOverlaps(start, end, result);
+    }
+    return result;
+  }
+
+  /**
+   * Adds to the result list any contact features having end (second contact
+   * point), but not start (first contact point), in the query from-to range
+   * 
+   * @param from
+   * @param to
+   * @param result
+   */
+
+  private void getContactEndOverlaps(long from, long to,
+          List<SequenceFeature> result)
+  {
+    // find the first contact feature (if any)
+    // with end point not before the target range
+
+    for (int i = findFirstEnd(contactFeatureEnds,
+            from), n = contactFeatureEnds.size(); i < n; i++)
+    {
+      SequenceFeature sf = contactFeatureEnds.get(i);
+      if (sf.begin >= from && sf.begin <= to)
+      {
+        // this feature's first contact position lies in the search range
+        // so we don't include it in results a second time
+        continue;
+      }
+
+      if (sf.end > to)
+      {
+        // this feature (and all following) has end point after the target range
+        break;
+      }
+
+      // feature has end >= from and end <= to
+      // i.e. contact end point lies within overlap search range
+      result.add(sf);
+    }
+  }
+
+  /**
+   * Binary search for contact start or end matching a specific position. This
+   * efficient search was designed specifically for rapid return for the
+   * OverviewPanel. It's implementation sped processing of that panel by 2300%.
+   * 
+   * @param l
+   * @param pos
+   * @param result
+   * @param isStart
+   * 
+   * @author Bob Hanson 2019.07.30
+   */
+  private void getContactPointStarts(List<SequenceFeature> l, long pos,
+          List<SequenceFeature> result)
+  {
+    int low = 0;
+    int high = l.size() - 1;
+    while (low <= high)
+    {
+      int mid = (low + high) >>> 1;
+      SequenceFeature f = l.get(mid);
+      switch (Long.signum(f.begin - pos))
+      {
+      case -1:
+        low = mid + 1;
+        continue;
+      case 1:
+        high = mid - 1;
+        continue;
+      case 0:
+        int m = mid;
+        result.add(f);
+        // could be "5" in 12345556788 ?
+        while (++mid <= high && (f = l.get(mid)) != null && f.begin == pos)
+        {
+          result.add(f);
+        }
+        while (--m >= low && (f = l.get(m)) != null && f.begin == pos)
+        {
+          result.add(f);
+        }
+        return;
+      }
+    }
+  }
+
+  private void getContactPointEnds(List<SequenceFeature> l, long pos,
+          List<SequenceFeature> result)
+  {
+    int low = 0;
+    int high = l.size() - 1;
+    while (low <= high)
+    {
+      int mid = (low + high) >>> 1;
+      SequenceFeature f = l.get(mid);
+      switch (Long.signum(f.end - pos))
+      {
+      case -1:
+        low = mid + 1;
+        continue;
+      case 1:
+        high = mid - 1;
+        continue;
+      case 0:
+        int m = mid;
+        if (f.begin != f.end)
+        {
+          result.add(f);
+        }
+        // could be "5" in 12345556788 ?
+        while (++mid <= high && (f = l.get(mid)) != null
+                && f.end == pos)
+        {
+          if (f.begin != f.end)
+          {
+            result.add(f);
+          }
+        }
+        while (--m >= low && (f = l.get(m)) != null
+                && f.end == pos)
+        {
+          if (f.begin != f.end)
+          {
+            result.add(f);
+          }
+        }
+        return;
+      }
+    }
+  }
+
+  /**
+   * Adds contact features whose start position lies in the from-to range to the
+   * result list
+   * 
+   * @param from
+   * @param to
+   * @param result
+   */
+
+  private void getContactStartOverlaps(long from, long to,
+          List<SequenceFeature> result)
+  {
+    for (int i = findFirstBegin(contactFeatureStarts,
+            from), n = contactFeatureStarts.size(); i < n; i++)
+    {
+      SequenceFeature sf = contactFeatureStarts.get(i);
+      if (sf.begin > to)
+      {
+        break;
+      }
+      result.add(sf);
+    }
+  }
+}