2 * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3 * Copyright (C) $$Year-Rel$$ The Jalview Authors
5 * This file is part of Jalview.
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.
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.
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.
21 package jalview.datamodel.features;
23 import jalview.datamodel.SequenceFeature;
25 import java.util.ArrayList;
26 import java.util.List;
28 import intervalstore.nonc.IntervalStore;
31 * An adaption of FeatureStore that is efficient and lightweight, accelerating
32 * processing speed in JavaScript.
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.
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.
43 * See the discussion folder at https://github.com/BobHanson/IntervalStoreJ for
47 * @author Bob Hanson 2019.08.03-2019.08.16
50 public class FeatureStoreJS extends FeatureStore
52 private IntervalStore<SequenceFeature> featureStore;
54 public FeatureStoreJS()
56 // the only reference to features field in this class -- for the superclass
58 // linked-list no-NCList IntervalStore with presort
60 features = featureStore = new IntervalStore<>(true);
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.
73 protected synchronized boolean addContactFeature(SequenceFeature feature)
75 if (contactFeatureStarts == null)
77 contactFeatureStarts = new ArrayList<>();
78 contactFeatureEnds = new ArrayList<>();
80 contactFeatureStarts.add(
81 findFirstBegin(contactFeatureStarts, feature.begin), feature);
82 contactFeatureEnds.add(findFirstEnd(contactFeatureEnds, feature.end),
89 * Add a feature to the IntervalStore, not allowing for duplicates.
92 * @return false if could not add it (late check for duplicate)
95 protected synchronized boolean addPositionalFeature(
96 SequenceFeature feature)
98 return featureStore.add(feature, false);
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
108 * @return false -- meaning "maybe not contained; continue adding"
111 protected boolean checkContainsPositionalFeatureForAdd(
112 SequenceFeature feature)
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
123 * @return true if this feature or its equivalent (based on equalsInterval) is
124 * present already in the collection.
127 protected boolean containsFeature(SequenceFeature feature)
129 return featureStore.contains(feature);
133 protected boolean findAndRemoveNonContactFeature(SequenceFeature sf)
135 return featureStore.remove(sf);
139 * Add contact features to the result list where either the second or the
140 * first contact position lies within the target range, inclusively.
147 protected void findContactFeatures(long from, long to,
148 List<SequenceFeature> result)
150 getContactStartOverlaps(from, to, result);
151 getContactEndOverlaps(from, to, result);
155 * Locate the first feature start in a standard ArrayList that is at or after
161 protected int findFirstBegin(List<SequenceFeature> list, long pos)
163 int matched = list.size();
164 int end = matched - 1;
165 int start = (end < 0 || list.get(end).begin < pos ? matched : 0);
168 int mid = (start + end) / 2;
169 if (list.get(mid).begin >= pos)
183 * Locate the feature end in a standard ArrayList that is after or at this
189 protected int findFirstEnd(List<SequenceFeature> list, long pos)
191 int matched = list.size();
192 int end = matched - 1;
196 int mid = (start + end) / 2;
197 if (list.get(mid).end >= pos)
211 * Returns a (possibly empty) list of features whose extent overlaps the given
212 * range. The returned list is ordered as follows:
214 * (1) ContactFeature starts
216 * (2) ContactFeature ends (that are not also starts)
218 * (3) noncontact SequenceFeatures, in reverse start order
220 * (This last reverse order is for efficiency in processing only.)
225 * start position of overlap range (inclusive)
227 * end position of overlap range (inclusive)
230 * optional result list; for highest efficiency, provide this
232 * @return result same as result parameter, or a new ArrayList if that is null
236 public List<SequenceFeature> findOverlappingFeatures(long start, long end,
237 List<SequenceFeature> result)
241 result = new ArrayList<>();
243 if (contactFeatureStarts != null)
247 getContactPointStarts(contactFeatureStarts, start, result);
248 getContactPointEnds(contactFeatureEnds, end, result);
252 findContactFeatures(start, end, result);
255 if (featureStore.size() > 0)
257 featureStore.findOverlaps(start, end, result);
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
271 private void getContactEndOverlaps(long from, long to,
272 List<SequenceFeature> result)
274 // find the first contact feature (if any)
275 // with end point not before the target range
277 for (int i = findFirstEnd(contactFeatureEnds,
278 from), n = contactFeatureEnds.size(); i < n; i++)
280 SequenceFeature sf = contactFeatureEnds.get(i);
281 if (sf.begin >= from && sf.begin <= to)
283 // this feature's first contact position lies in the search range
284 // so we don't include it in results a second time
290 // this feature (and all following) has end point after the target range
294 // feature has end >= from and end <= to
295 // i.e. contact end point lies within overlap search range
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%.
310 * @author Bob Hanson 2019.07.30
312 private void getContactPointStarts(List<SequenceFeature> l, long pos,
313 List<SequenceFeature> result)
316 int high = l.size() - 1;
319 int mid = (low + high) >>> 1;
320 SequenceFeature f = l.get(mid);
321 switch (Long.signum(f.begin - pos))
332 // could be "5" in 12345556788 ?
333 while (++mid <= high && (f = l.get(mid)) != null && f.begin == pos)
337 while (--m >= low && (f = l.get(m)) != null && f.begin == pos)
346 private void getContactPointEnds(List<SequenceFeature> l, long pos,
347 List<SequenceFeature> result)
350 int high = l.size() - 1;
353 int mid = (low + high) >>> 1;
354 SequenceFeature f = l.get(mid);
355 switch (Long.signum(f.end - pos))
365 if (f.begin != f.end)
369 // could be "5" in 12345556788 ?
370 while (++mid <= high && (f = l.get(mid)) != null
373 if (f.begin != f.end)
378 while (--m >= low && (f = l.get(m)) != null
381 if (f.begin != f.end)
392 * Adds contact features whose start position lies in the from-to range to the
400 private void getContactStartOverlaps(long from, long to,
401 List<SequenceFeature> result)
403 for (int i = findFirstBegin(contactFeatureStarts,
404 from), n = contactFeatureStarts.size(); i < n; i++)
406 SequenceFeature sf = contactFeatureStarts.get(i);