/*
* 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 .
* 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 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 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 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 findOverlappingFeatures(long start, long end,
List result)
{
result = new ArrayList<>();
findContactFeatures(start, end, result);
findOverlaps(start, end, result);
return result;
}
private void findOverlaps(long start, long end,
List result)
{
result.addAll(((IntervalStoreI) features)
.findOverlaps(start, end));
}
@Override
protected int findFirstBegin(List 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 list,
long pos)
{
return BinarySearcher.findFirst(list, f -> f.getBegin() >= pos);
}
@Override
protected int findFirstEnd(List 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 list,
long pos)
{
return BinarySearcher.findFirst(list, f -> f.getEnd() >= pos);
}
@Override
protected boolean findAndRemoveNonContactFeature(SequenceFeature sf)
{
return features.remove(sf);
}
}