+++ /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.api.IntervalStoreI;
-import intervalstore.impl.BinarySearcher;
-
-/**
- * A data store for a set of sequence features that supports efficient lookup of
- * features overlapping a given range. Intended for (but not limited to) storage
- * of features for one sequence and feature type.
- *
- * @author gmcarstairs
- *
- */
-public class FeatureStoreImpl extends FeatureStore
-{
-
- /**
- * Default constructor uses NCList
- */
- public FeatureStoreImpl()
- {
- this(true);
- }
-
- public FeatureStoreImpl(boolean useNCList)
- {
- features = (useNCList ? new intervalstore.impl.IntervalStore<>()
- : new intervalstore.nonc.IntervalStore<>(false));
- }
-
- /**
- * 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, and returns true. This method allows duplicate features to be
- * added, so test before calling to avoid this.
- *
- * @param feature
- * @return
- */
- @Override
- protected synchronized boolean addContactFeature(SequenceFeature feature)
- {
- if (contactFeatureStarts == null)
- {
- contactFeatureStarts = new ArrayList<>();
- contactFeatureEnds = new ArrayList<>();
- }
-
- /*
- * insert into list sorted by start (first contact position):
- * binary search the sorted list to find the insertion point
- */
- int insertPosition = findFirstBeginStatic(contactFeatureStarts,
- feature.getBegin());
- contactFeatureStarts.add(insertPosition, feature);
-
- /*
- * insert into list sorted by end (second contact position):
- * binary search the sorted list to find the insertion point
- */
- insertPosition = findFirstEndStatic(contactFeatureEnds,
- feature.getEnd());
- contactFeatureEnds.add(insertPosition, feature);
-
- return true;
- }
-
- /**
- * Adds one feature to the IntervalStore that can manage nested features
- * (creating the IntervalStore if necessary)
- */
- @Override
- protected synchronized boolean addPositionalFeature(
- SequenceFeature feature)
- {
- return features.add(feature);
- }
-
- /**
- * Adds contact features to the result list where either the second or the
- * first contact position lies within the target range
- *
- * @param from
- * @param to
- * @param result
- */
- @Override
- protected void findContactFeatures(long from, long to,
- List<SequenceFeature> result)
- {
- if (contactFeatureStarts != null)
- {
- findContactStartOverlaps(from, to, result);
- findContactEndOverlaps(from, to, result);
- }
- }
-
- @Override
- protected boolean containsFeature(SequenceFeature feature)
- {
- return features.contains(feature);
- }
-
- /**
- * Adds to the result list any contact features whose end (second contact
- * point), but not start (first contact point), lies in the query from-to
- * range
- *
- * @param from
- * @param to
- * @param result
- */
-
- private void findContactEndOverlaps(long from, long to,
- List<SequenceFeature> result)
- {
- /*
- * find the first contact feature (if any)
- * whose end point is not before the target range
- */
- int index = findFirstEndStatic(contactFeatureEnds, from);
-
- int n = contactFeatureEnds.size();
- while (index < n)
- {
- SequenceFeature sf = contactFeatureEnds.get(index);
- if (!sf.isContactFeature())
- {
- System.err.println("Error! non-contact feature type " + sf.getType()
- + " in contact features list");
- index++;
- continue;
- }
-
- int begin = sf.getBegin();
- if (begin >= from && begin <= to)
- {
- /*
- * this feature's first contact position lies in the search range
- * so we don't include it in results a second time
- */
- index++;
- continue;
- }
-
- if (sf.getEnd() > 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);
- index++;
- }
- }
-
- /**
- * Adds contact features whose start position lies in the from-to range to the
- * result list
- *
- * @param from
- * @param to
- * @param result
- */
-
- private void findContactStartOverlaps(long from, long to,
- List<SequenceFeature> result)
- {
- int index = findFirstBegin(contactFeatureStarts, from);
-
- while (index < contactFeatureStarts.size())
- {
- SequenceFeature sf = contactFeatureStarts.get(index);
- if (!sf.isContactFeature())
- {
- System.err.println("Error! non-contact feature " + sf.toString()
- + " in contact features list");
- index++;
- continue;
- }
- if (sf.getBegin() > to)
- {
- /*
- * this feature's start (and all following) follows the target range
- */
- break;
- }
-
- /*
- * feature has begin >= from and begin <= to
- * i.e. contact start point lies within overlap search range
- */
- result.add(sf);
- index++;
- }
- }
-
- /**
- * Returns a (possibly empty) list of features whose extent overlaps the given
- * range. The returned list is not ordered. Contact features are included if
- * either of the contact points lies within the range.
- *
- * @param start
- * start position of overlap range (inclusive)
- * @param end
- * end position of overlap range (inclusive)
- * @param result
- * ignored
- * @return
- */
-
- @Override
- public List<SequenceFeature> findOverlappingFeatures(long start, long end,
- List<SequenceFeature> result)
- {
- result = new ArrayList<>();
- findContactFeatures(start, end, result);
- findOverlaps(start, end, result);
- return result;
- }
-
- private void findOverlaps(long start, long end,
- List<SequenceFeature> result)
- {
- result.addAll(((IntervalStoreI<SequenceFeature>) features)
- .findOverlaps(start, end));
- }
-
- @Override
- protected int findFirstBegin(List<SequenceFeature> list, long pos)
- {
- return findFirstBeginStatic(list, pos);
- }
-
- /**
- * Possibly a bit faster using a static method.
- *
- * @param list
- * @param pos
- * @return
- */
- private static int findFirstBeginStatic(List<SequenceFeature> list,
- long pos)
- {
- return BinarySearcher.findFirst(list, f -> f.getBegin() >= pos);
- }
-
- @Override
- protected int findFirstEnd(List<SequenceFeature> list, long pos)
- {
- return findFirstEndStatic(list, pos);
- }
-
- /**
- * Possibly a bit faster using a static method.
- *
- * @param list
- * @param pos
- * @return
- */
- private static int findFirstEndStatic(List<SequenceFeature> list,
- long pos)
- {
- return BinarySearcher.findFirst(list, f -> f.getEnd() >= pos);
- }
-
- @Override
- protected boolean findAndRemoveNonContactFeature(SequenceFeature sf)
- {
- return features.remove(sf);
- }
-
-}
git://source.jalview.org / jalview.git / blobdiff