+++ /dev/null
-/*
- * 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)
- {
- getContactPoints(contactFeatureStarts, start, result, true);
- getContactPoints(contactFeatureEnds, start, result, false);
- }
- 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 getContactPoints(List<SequenceFeature> l, long pos,
- List<SequenceFeature> result, boolean isStart)
- {
- int low = 0;
- int high = l.size() - 1;
- while (low <= high)
- {
- int mid = (low + high) >>> 1;
- SequenceFeature f = l.get(mid);
- switch (Long.signum((isStart ? f.begin : f.end) - 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
- && (isStart ? f.begin : f.end) == pos)
- {
- result.add(f);
- }
- while (--m >= low && (f = l.get(m)) != null
- && (isStart ? f.begin : f.end) == pos)
- {
- 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);
- }
- }
-}
git://source.jalview.org / jalview.git / blobdiff