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.api.IntervalStoreI;
29 import intervalstore.impl.BinarySearcher;
32 * A data store for a set of sequence features that supports efficient lookup of
33 * features overlapping a given range. Intended for (but not limited to) storage
34 * of features for one sequence and feature type.
39 public class FeatureStoreImpl extends FeatureStore
43 * Default constructor uses NCList
45 public FeatureStoreImpl()
50 public FeatureStoreImpl(boolean useNCList)
52 features = (useNCList ? new intervalstore.impl.IntervalStore<>()
53 : new intervalstore.nonc.IntervalStore<>(false));
57 * Add a contact feature to the lists that hold them ordered by start (first
58 * contact) and by end (second contact) position, ensuring the lists remain
59 * ordered, and returns true. This method allows duplicate features to be
60 * added, so test before calling to avoid this.
66 protected synchronized boolean addContactFeature(SequenceFeature feature)
68 if (contactFeatureStarts == null)
70 contactFeatureStarts = new ArrayList<>();
71 contactFeatureEnds = new ArrayList<>();
75 * insert into list sorted by start (first contact position):
76 * binary search the sorted list to find the insertion point
78 int insertPosition = findFirstBeginStatic(contactFeatureStarts,
80 contactFeatureStarts.add(insertPosition, feature);
83 * insert into list sorted by end (second contact position):
84 * binary search the sorted list to find the insertion point
86 insertPosition = findFirstEndStatic(contactFeatureEnds,
88 contactFeatureEnds.add(insertPosition, feature);
94 * Adds one feature to the IntervalStore that can manage nested features
95 * (creating the IntervalStore if necessary)
98 protected synchronized boolean addPositionalFeature(
99 SequenceFeature feature)
101 return features.add(feature);
105 * Adds contact features to the result list where either the second or the
106 * first contact position lies within the target range
113 protected void findContactFeatures(long from, long to,
114 List<SequenceFeature> result)
116 if (contactFeatureStarts != null)
118 findContactStartOverlaps(from, to, result);
119 findContactEndOverlaps(from, to, result);
124 protected boolean containsFeature(SequenceFeature feature)
126 return features.contains(feature);
130 * Adds to the result list any contact features whose end (second contact
131 * point), but not start (first contact point), lies in the query from-to
139 private void findContactEndOverlaps(long from, long to,
140 List<SequenceFeature> result)
143 * find the first contact feature (if any)
144 * whose end point is not before the target range
146 int index = findFirstEndStatic(contactFeatureEnds, from);
148 int n = contactFeatureEnds.size();
151 SequenceFeature sf = contactFeatureEnds.get(index);
152 if (!sf.isContactFeature())
154 System.err.println("Error! non-contact feature type " + sf.getType()
155 + " in contact features list");
160 int begin = sf.getBegin();
161 if (begin >= from && begin <= to)
164 * this feature's first contact position lies in the search range
165 * so we don't include it in results a second time
171 if (sf.getEnd() > to)
174 * this feature (and all following) has end point after the target range
180 * feature has end >= from and end <= to
181 * i.e. contact end point lies within overlap search range
189 * Adds contact features whose start position lies in the from-to range to the
197 private void findContactStartOverlaps(long from, long to,
198 List<SequenceFeature> result)
200 int index = findFirstBegin(contactFeatureStarts, from);
202 while (index < contactFeatureStarts.size())
204 SequenceFeature sf = contactFeatureStarts.get(index);
205 if (!sf.isContactFeature())
207 System.err.println("Error! non-contact feature " + sf.toString()
208 + " in contact features list");
212 if (sf.getBegin() > to)
215 * this feature's start (and all following) follows the target range
221 * feature has begin >= from and begin <= to
222 * i.e. contact start point lies within overlap search range
230 * Returns a (possibly empty) list of features whose extent overlaps the given
231 * range. The returned list is not ordered. Contact features are included if
232 * either of the contact points lies within the range.
235 * start position of overlap range (inclusive)
237 * end position of overlap range (inclusive)
244 public List<SequenceFeature> findOverlappingFeatures(long start, long end,
245 List<SequenceFeature> result)
247 result = new ArrayList<>();
248 findContactFeatures(start, end, result);
249 findOverlaps(start, end, result);
253 private void findOverlaps(long start, long end,
254 List<SequenceFeature> result)
256 result.addAll(((IntervalStoreI<SequenceFeature>) features)
257 .findOverlaps(start, end));
261 protected int findFirstBegin(List<SequenceFeature> list, long pos)
263 return findFirstBeginStatic(list, pos);
267 * Possibly a bit faster using a static method.
273 private static int findFirstBeginStatic(List<SequenceFeature> list,
276 return BinarySearcher.findFirst(list, f -> f.getBegin() >= pos);
280 protected int findFirstEnd(List<SequenceFeature> list, long pos)
282 return findFirstEndStatic(list, pos);
286 * Possibly a bit faster using a static method.
292 private static int findFirstEndStatic(List<SequenceFeature> list,
295 return BinarySearcher.findFirst(list, f -> f.getEnd() >= pos);
299 protected boolean findAndRemoveNonContactFeature(SequenceFeature sf)
301 return features.remove(sf);