import java.util.ArrayList;
import java.util.List;
+import intervalstore.nonc.IntervalStore;
+
/**
* An adaption of FeatureStore that is efficient and lightweight, accelerating
* processing speed in JavaScript.
{
boolean contactsTainted = true;
+ private IntervalStore<SequenceFeature> featureStore;
- /**
- * internal reference to features as an ArrayList
- */
- private ArrayList<SequenceFeature> featureList;
+ //
+ // /**
+ // * internal reference to features as an ArrayList
+ // */
+ // private ArrayList<SequenceFeature> featureList;
+ //
+ // /**
+ // * contact features ordered by first contact position
+ // */
+ // private SequenceFeature[] orderedFeatureStarts;
- /**
- * contact features ordered by first contact position
- */
- private SequenceFeature[] orderedFeatureStarts;
-
- /**
- * indicates that we need to rebuild orderedFeatureStarts and reset index
- * fields
- */
- private boolean isTainted = true;
+ // /**
+ // * indicates that we need to rebuild orderedFeatureStarts and reset index
+ // * fields
+ // */
+ // private boolean isTainted = true;
/**
* Constructor
*/
public FeatureStoreJS()
{
- features = featureList = new ArrayList<>();
+ // the only reference to features field in this class -- for the superclass
+
+ features = featureStore = new IntervalStore<>(); // featureList = new
+ // ArrayList<>();
}
/**
/**
* Adds one feature to the IntervalStore that can manage nested features
* (creating the IntervalStore if necessary)
+ *
+ * @return false if could not add it (late check for contained
*/
@Override
- protected synchronized void addPositionalFeature(SequenceFeature feature)
+ protected synchronized boolean addPositionalFeature(
+ SequenceFeature feature)
{
- featureList.add(findFirstBegin(featureList, feature.begin), feature);
- isTainted = true;
+
+ return featureStore.add(feature, false);
+ // features.add(feature);
+ // featureList.add(findFirstBegin(featureList, feature.begin), feature);
+ // isTainted = true;
}
@Override
- protected boolean containsFeature(SequenceFeature feature)
+ protected boolean checkContainsPositionalFeatureForAdd(
+ SequenceFeature feature)
{
+ // the non-NCList IntervalStore does this as part of the add for greater
+ // efficiency (one binary search)
+ return false;
+ }
- return getEquivalentFeatureIndex(featureList, feature) >= 0;
+ @Override
+ protected boolean containsFeature(SequenceFeature feature)
+ {
+ return featureStore.contains(feature);
+ // return getEquivalentFeatureIndex(featureList, feature) >= 0;
}
@Override
protected boolean findAndRemoveNonContactFeature(SequenceFeature sf)
{
- int pos = getEquivalentFeatureIndex(featureList, sf);
- if (pos < 0)
- {
- return false;
- }
- featureList.remove(pos);
- return (isTainted = true);
+ return featureStore.remove(sf);
+ // int pos = getEquivalentFeatureIndex(featureList, sf);
+ // if (pos < 0)
+ // {
+ // return false;
+ // }
+ // featureList.remove(pos);
+ // return (isTainted = true);
}
/**
findContactFeatures(start, end, result);
}
}
- if (featureList.size() > 0)
+ if (featureStore.size() > 0)
{
- getOverlaps(start, end, result);
+ featureStore.findOverlaps(start, end, result);
+ // getOverlaps(start, end, result);
}
return result;
}
- /**
- * A binary search identical to the one used for contact start/end, but here
- * we return the feature itself. Unlike Collection.BinarySearch, all we have
- * to be is close, not exact, and we make sure if there is a string of
- * identical starts, then we slide to the end so that we can check all of
- * them.
- *
- * @param l
- * @param pos
- * @return
- */
- private int getClosestFeature(SequenceFeature[] l, long pos)
- {
- int low = 0;
- int high = l.length - 1;
- while (low <= high)
- {
- int mid = (low + high) >>> 1;
- SequenceFeature f = l[mid];
- switch (Long.signum(f.begin - pos))
- {
- case -1:
- low = mid + 1;
- continue;
- case 1:
- high = mid - 1;
- continue;
- case 0:
-
- while (++mid <= high && l[mid].begin == pos)
- {
- ;
- }
- return --mid;
- }
- }
- return (high < 0 ? -1 : high);
- }
+ // /**
+ // * A binary search identical to the one used for contact start/end, but here
+ // * we return the feature itself. Unlike Collection.BinarySearch, all we have
+ // * to be is close, not exact, and we make sure if there is a string of
+ // * identical starts, then we slide to the end so that we can check all of
+ // * them.
+ // *
+ // * @param l
+ // * @param pos
+ // * @return
+ // */
+ // private int getClosestFeature(SequenceFeature[] l, long pos)
+ // {
+ // int low = 0;
+ // int high = l.length - 1;
+ // while (low <= high)
+ // {
+ // int mid = (low + high) >>> 1;
+ // SequenceFeature f = l[mid];
+ // switch (Long.signum(f.begin - pos))
+ // {
+ // case -1:
+ // low = mid + 1;
+ // continue;
+ // case 1:
+ // high = mid - 1;
+ // continue;
+ // case 0:
+ //
+ // while (++mid <= high && l[mid].begin == pos)
+ // {
+ // ;
+ // }
+ // return --mid;
+ // }
+ // }
+ // return (high < 0 ? -1 : high);
+ // }
/**
* Adds to the result list any contact features whose end (second contact
}
}
- /**
- * Since we are traversing the sorted feature array in a forward direction,
- * all elements prior to the one we are working on have been fully linked. All
- * we are doing is following those links until we find the first array feature
- * with a containedBy element that has an end >= our begin point. It is
- * generally a very short list -- maybe one or two depths. But it might be
- * more than that.
- *
- * @param sf
- * @param sf0
- * @return
- */
- private SequenceFeature getContainedBy(SequenceFeature sf,
- SequenceFeature sf0)
- {
- int begin = sf0.begin;
- while (sf != null)
- {
- if (begin <= sf.end)
- {
- // System.out.println("\nFSJS found " + sf0 + "\nFS in " + sf);
- return sf;
- }
- sf = sf.containedBy;
- }
- return null;
- }
-
- /**
- * Fast find of known features already on the list; slower removal of
- * equivalent feature, not necessarily identical.
- *
- * @param feature
- * @return 0-based index for this feature in featureList
- */
- @Override
- protected int getEquivalentFeatureIndex(List<SequenceFeature> list,
- SequenceFeature feature)
- {
- int pos = feature.index1 - 1;
- if (!isTainted && pos >= 0)
- {
- return pos;
- }
- return super.getEquivalentFeatureIndex(list, feature);
- }
-
- /**
- * Find all overlaps; special case when there is only one feature. The
- * required array of start-sorted SequenceFeature is created lazily.
- *
- * @param start
- * @param end
- * @param result
- */
- private void getOverlaps(long start, long end,
- List<SequenceFeature> result)
- {
- int n = featureList.size();
- switch (n)
- {
- case 0:
- return;
- case 1:
- justCheckOne(featureList.get(0), start, end, result);
- return;
- default:
- if (isTainted)
- {
- orderedFeatureStarts = featureList
- .toArray(new SequenceFeature[featureList.size()]);
- linkFeatures(orderedFeatureStarts);
- isTainted = false;
- }
- break;
- }
-
- // (1) Find the closest feature to this position.
-
- int index = getClosestFeature(orderedFeatureStarts, start);
- SequenceFeature sf = (index < 0 ? null : orderedFeatureStarts[index]);
-
- // (2) Traverse the containedBy field, checking for overlap.
-
- while (sf != null)
- {
- if (sf.end >= start)
- {
- result.add(sf);
- }
- sf = sf.containedBy;
- }
-
- // (3) For an interval, find the last feature that starts in this interval,
- // and add all features up through that feature.
-
- if (end > start)
- {
- // fill in with all features that start within this interval, fully
- // inclusive
- int index2 = getClosestFeature(orderedFeatureStarts, end);
- while (++index <= index2)
- {
- result.add(orderedFeatureStarts[index]);
- }
-
- }
- }
-
- /**
- * Quick check when we only have one feature.
- *
- * @param sf
- * @param start
- * @param end
- * @param result
- */
- private void justCheckOne(SequenceFeature sf, long start, long end,
- List<SequenceFeature> result)
- {
- if (sf.begin <= end && sf.end >= start)
- {
- result.add(sf);
- }
- return;
- }
-
- /**
- * Run through the sorted sequence array once, building the containedBy linked
- * list references. Does a check first to make sure there is actually
- * something out there that is overlapping. A null for sf.containedBy means
- * there are no overlaps for this feature.
- *
- * @param features
- */
- private void linkFeatures(SequenceFeature[] features)
- {
- int n = features.length;
- switch (n)
- {
- case 0:
- return;
- case 1:
- features[0].index1 = 1;
- return;
- }
- int maxEnd = features[0].end;
- for (int i = 1; i < n;)
- {
- SequenceFeature sf = features[i];
- if (sf.begin <= maxEnd)
- {
- sf.containedBy = getContainedBy(features[i - 1], sf);
- }
- if (sf.end > maxEnd)
- {
- maxEnd = sf.end;
- }
- sf.index1 = ++i;
- }
- }
+ // /**
+ // * Since we are traversing the sorted feature array in a forward direction,
+ // * all elements prior to the one we are working on have been fully linked.
+ // All
+ // * we are doing is following those links until we find the first array
+ // feature
+ // * with a containedBy element that has an end >= our begin point. It is
+ // * generally a very short list -- maybe one or two depths. But it might be
+ // * more than that.
+ // *
+ // * @param sf
+ // * @param sf0
+ // * @return
+ // */
+ // private SequenceFeature getContainedBy(SequenceFeature sf,
+ // SequenceFeature sf0)
+ // {
+ // int begin = sf0.begin;
+ // while (sf != null)
+ // {
+ // if (begin <= sf.end)
+ // {
+ // // System.out.println("\nFSJS found " + sf0 + "\nFS in " + sf);
+ // return sf;
+ // }
+ // sf = sf.containedBy;
+ // }
+ // return null;
+ // }
+
+ // /**
+ // * Fast find of known features already on the list; slower removal of
+ // * equivalent feature, not necessarily identical.
+ // *
+ // * @param feature
+ // * @return 0-based index for this feature in featureList
+ // */
+ // @Override
+ // protected int getEquivalentFeatureIndex(List<SequenceFeature> list,
+ // SequenceFeature feature)
+ // {
+ // int pos = feature.index - 1;
+ // if (!isTainted && pos >= 0)
+ // {
+ // return pos;
+ // }
+ // return super.getEquivalentFeatureIndex(list, feature);
+ // }
+ //
+ // /**
+ // * Find all overlaps; special case when there is only one feature. The
+ // * required array of start-sorted SequenceFeature is created lazily.
+ // *
+ // * @param start
+ // * @param end
+ // * @param result
+ // */
+ // private void getOverlaps(long start, long end,
+ // List<SequenceFeature> result)
+ // {
+ // int n = featureList.size();
+ // switch (n)
+ // {
+ // case 0:
+ // return;
+ // case 1:
+ // justCheckOne(featureList.get(0), start, end, result);
+ // return;
+ // default:
+ // if (isTainted)
+ // {
+ // orderedFeatureStarts = featureList
+ // .toArray(new SequenceFeature[featureList.size()]);
+ // linkFeatures(orderedFeatureStarts);
+ // isTainted = false;
+ // }
+ // break;
+ // }
+ //
+ // // (1) Find the closest feature to this position.
+ //
+ // int index = getClosestFeature(orderedFeatureStarts, start);
+ // SequenceFeature sf = (index < 0 ? null : orderedFeatureStarts[index]);
+ //
+ // // (2) Traverse the containedBy field, checking for overlap.
+ //
+ // while (sf != null)
+ // {
+ // if (sf.end >= start)
+ // {
+ // result.add(sf);
+ // }
+ // sf = sf.containedBy;
+ // }
+ //
+ // // (3) For an interval, find the last feature that starts in this interval,
+ // // and add all features up through that feature.
+ //
+ // if (end > start)
+ // {
+ // // fill in with all features that start within this interval, fully
+ // // inclusive
+ // int index2 = getClosestFeature(orderedFeatureStarts, end);
+ // while (++index <= index2)
+ // {
+ // result.add(orderedFeatureStarts[index]);
+ // }
+ //
+ // }
+ // }
+ //
+ // /**
+ // * Quick check when we only have one feature.
+ // *
+ // * @param sf
+ // * @param start
+ // * @param end
+ // * @param result
+ // */
+ // private void justCheckOne(SequenceFeature sf, long start, long end,
+ // List<SequenceFeature> result)
+ // {
+ // if (sf.begin <= end && sf.end >= start)
+ // {
+ // result.add(sf);
+ // }
+ // return;
+ // }
+ //
+ // /**
+ // * Run through the sorted sequence array once, building the containedBy
+ // linked
+ // * list references. Does a check first to make sure there is actually
+ // * something out there that is overlapping. A null for sf.containedBy means
+ // * there are no overlaps for this feature.
+ // *
+ // * @param features
+ // */
+ // private void linkFeatures(SequenceFeature[] features)
+ // {
+ // int n = features.length;
+ // switch (n)
+ // {
+ // case 0:
+ // return;
+ // case 1:
+ // features[0].index = 1;
+ // return;
+ // }
+ // int maxEnd = features[0].end;
+ // for (int i = 1; i < n;)
+ // {
+ // SequenceFeature sf = features[i];
+ // if (sf.begin <= maxEnd)
+ // {
+ // sf.containedBy = getContainedBy(features[i - 1], sf);
+ // }
+ // if (sf.end > maxEnd)
+ // {
+ // maxEnd = sf.end;
+ // }
+ // sf.index = ++i;
+ // }
+ // }
}
git://source.jalview.org / jalview.git / blobdiff