/*
* 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;
/**
* 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
{
public FeatureStoreJS()
{
super();
}
public FeatureStoreJS(int option)
{
super(option);
}
/**
* 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 features.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 features.contains(feature);
}
@Override
protected boolean findAndRemoveNonContactFeature(SequenceFeature sf)
{
return features.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 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 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 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 findOverlappingFeatures(long start, long end,
List result)
{
if (result == null)
{
result = new ArrayList<>();
}
if (contactFeatureStarts != null)
{
if (start == end)
{
getContactPointStarts(contactFeatureStarts, start, result);
getContactPointEnds(contactFeatureEnds, end, result);
}
else
{
findContactFeatures(start, end, result);
}
}
if (features.size() > 0)
{
features.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 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 getContactPointStarts(List l, long pos,
List result)
{
int low = 0;
int high = l.size() - 1;
while (low <= high)
{
int mid = (low + high) >>> 1;
SequenceFeature f = l.get(mid);
switch (Long.signum(f.begin - 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 && f.begin == pos)
{
result.add(f);
}
while (--m >= low && (f = l.get(m)) != null && f.begin == pos)
{
result.add(f);
}
return;
}
}
}
private void getContactPointEnds(List l, long pos,
List result)
{
int low = 0;
int high = l.size() - 1;
while (low <= high)
{
int mid = (low + high) >>> 1;
SequenceFeature f = l.get(mid);
switch (Long.signum(f.end - pos))
{
case -1:
low = mid + 1;
continue;
case 1:
high = mid - 1;
continue;
case 0:
int m = mid;
if (f.begin != f.end)
{
result.add(f);
}
// could be "5" in 12345556788 ?
while (++mid <= high && (f = l.get(mid)) != null
&& f.end == pos)
{
if (f.begin != f.end)
{
result.add(f);
}
}
while (--m >= low && (f = l.get(m)) != null
&& f.end == pos)
{
if (f.begin != f.end)
{
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 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);
}
}
}