*/
package intervalstore.nonc;
+import jalview.datamodel.SequenceFeature;
+
import java.util.AbstractCollection;
import java.util.ArrayList;
import java.util.Arrays;
public class IntervalStore0<T extends IntervalI>
extends AbstractCollection<T> implements IntervalStoreI<T>
{
- private static int NOT_CONTAINED = Integer.MIN_VALUE;
+
+ static int NOT_CONTAINED = Integer.MIN_VALUE;
+
+ static int CONTAINMENT_UNKNOWN = 0;
/**
* Search for the last interval that starts before or at the specified from/to
*/
private boolean bigendian;
- private final boolean DO_PRESORT;
-
- private boolean isSorted;
-
private int minStart = Integer.MAX_VALUE, maxStart = Integer.MIN_VALUE,
maxEnd = Integer.MAX_VALUE;
*/
public IntervalStore0()
{
- this(true);
- }
-
- public IntervalStore0(boolean presort)
- {
- this(null, presort);
+ this(null);
}
/**
*/
public IntervalStore0(List<T> intervals)
{
- this(intervals, true);
- }
-
- /**
- * Allows a presort option, which can speed up initial loading of individual
- * features but will delay the first findOverlap if set to true.
- *
- * @param intervals
- * @param presort
- */
- public IntervalStore0(List<T> intervals, boolean presort)
- {
- this(intervals, presort, null, false);
+ this(intervals, null, false);
}
/**
*
* @param intervals
* intervals to initialize with (others may still be added)
- * @param presort
- * whether or not to presort the list as additions are made
* @param comparator
- * IntervalI.COMPARATOR_LITTLEENDIAN or
- * IntervalI.COMPARATOR_BIGENDIAN, but this could also be one that
- * sorts by description as well, for example.
+ * IntervalI.COMPARATOR_BEGIN_ASC_END_ASC (default) or
+ * IntervalI.COMPARE_BEGIN_ASC_END_DESC, but this could also be one
+ * that sorts by description as well, for example.
* @param bigendian
* true if the comparator sorts [10-30] before [10-20]
*/
- public IntervalStore0(List<T> intervals, boolean presort,
+ public IntervalStore0(List<T> intervals,
Comparator<? super IntervalI> comparator, boolean bigendian)
{
if (intervals != null)
this.intervals = new IntervalI[capacity = intervalCount = intervals
.size()]);
}
- DO_PRESORT = presort;
+ // COMPARE_BEGIN_ASC_END_DESC is standard, meaning
+ // the order will be [10,100] before [10,80]
+ // this order doesn't really matter much.
icompare = (comparator != null ? comparator
: bigendian ? IntervalI.COMPARE_BEGIN_ASC_END_DESC
: IntervalI.COMPARE_BEGIN_ASC_END_ASC);
this.bigendian = bigendian;
- if (DO_PRESORT && intervalCount > 1)
+ if (// DO_PRESORT &&
+ intervalCount > 1)
{
sort();
}
- isSorted = DO_PRESORT;
isTainted = true;
}
@Override
public boolean add(T interval)
{
- return add(interval, false);
+ return add(interval, true);
}
/**
}
- if (DO_PRESORT && isSorted)
- {
+ // if (DO_PRESORT && isSorted)
+ // {
if (intervalCount == 0)
{
// ignore
}
else
{
- index = findInterval(interval);
+ index = findInterval(interval, allowDuplicates);
if (!allowDuplicates && index >= 0)
{
return false;
}
}
- }
- else
- {
- if (!allowDuplicates && findInterval(interval) >= 0)
- {
- return false;
- }
- isSorted = false;
- }
+ // }
+ // else
+ // {
+ // if (!allowDuplicates && findInterval(interval) >= 0)
+ // {
+ // return false;
+ // }
+ // isSorted = false;
+ // }
if (index == intervalCount)
{
// array is [(intervalCount)...null...(added)]
int ntotal = intervalCount + added;
- for (int ptShift = intervalCount + added, pt = intervalCount; pt >= 0;)
+ for (int ptShift = ntotal, pt = intervalCount; pt >= 0;)
{
int pt0 = pt;
while (--pt >= 0 && offsets[pt] == 0)
{
-
+ ;
}
if (pt < 0)
{
return dest;
}
+ /**
+ * A binary search for a duplicate.
+ *
+ * @param interval
+ * @return
+ */
public int binaryIdentitySearch(IntervalI interval)
{
- return binaryIdentitySearch(interval, null);
+ return binaryIdentitySearch(interval, null, false);
}
/**
* @param interval
* @param bsIgnore
* for deleted
+ * @param rangeOnly
+ * don't do a full identity check, just a range check
* @return index or, if not found, -1 - "would be here"
*/
- public int binaryIdentitySearch(IntervalI interval, BitSet bsIgnore)
+ private int binaryIdentitySearch(IntervalI interval, BitSet bsIgnore,
+ boolean rangeOnly)
{
int start = 0;
int r0 = interval.getBegin();
continue;
case 0:
IntervalI iv = intervals[mid];
- if ((bsIgnore == null || !bsIgnore.get(mid))
+ if (!rangeOnly && (bsIgnore == null || !bsIgnore.get(mid))
&& sameInterval(interval, iv))
{
return mid;
{
break;
}
- if ((bsIgnore == null || !bsIgnore.get(i))
+ if (!rangeOnly && (bsIgnore == null || !bsIgnore.get(i))
&& sameInterval(interval, iv))
{
return i;
return -1 - start;
}
- boolean sameInterval(IntervalI i1, IntervalI i2)
- {
- /*
- * do the quick test of begin/end first for speed
- */
- return i1.equalsInterval(i2) && i1.equals(i2);
- }
+ // private int binaryInsertionSearch(long from, long to)
+ // {
+ // int matched = intervalCount;
+ // int end = matched - 1;
+ // int start = matched;
+ // if (end < 0 || from > intervals[end].getEnd()
+ // || from < intervals[start = 0].getBegin())
+ // return start;
+ // while (start <= end)
+ // {
+ // int mid = (start + end) >>> 1;
+ // switch (compareRange(intervals[mid], from, to))
+ // {
+ // case 0:
+ // return mid;
+ // case 1:
+ // matched = mid;
+ // end = mid - 1;
+ // continue;
+ // case -1:
+ // start = mid + 1;
+ // continue;
+ // }
+ //
+ // }
+ // return matched;
+ // }
@Override
public void clear()
{
intervalCount = added = 0;
- isSorted = true;
+ // isSorted = true;
isTainted = true;
offsets = null;
minStart = maxEnd = Integer.MAX_VALUE;
{
return false;
}
- if (!isSorted || deleted > 0)
+ if (// !isSorted ||
+ deleted > 0)
{
sort();
}
- return (findInterval((IntervalI) entry) >= 0);
+ return (findInterval((IntervalI) entry, false) >= 0);
}
public boolean containsInterval(IntervalI outer, IntervalI inner)
{
ensureFinalized();
- int index = binaryIdentitySearch(inner, null);
+ int index = binaryIdentitySearch(inner);
if (index >= 0)
{
while ((index = index - Math.abs(offsets[index])) >= 0)
{
if (isTainted)
{
- if (!isSorted || added > 0 || deleted > 0)
+ if (// !isSorted ||
+ added > 0 || deleted > 0)
{
sort();
}
return result;
}
+ public IntervalI get(int i)
+ {
+ if (i < 0 || i >= intervalCount + added)
+ {
+ return null;
+ }
+ ensureFinalized();
+ return intervals[i];
+ }
+
private int getContainedBy(int index, int begin)
{
while (index >= 0)
return maxDepth;
}
+ public int getWidth()
+ {
+ ensureFinalized();
+ int w = 0;
+ for (int i = offsets.length; --i >= 0;)
+ {
+ if (offsets[i] > 0)
+ {
+ w++;
+ }
+ }
+ return w;
+ }
+
+ public boolean isValid()
+ {
+ ensureFinalized();
+ return true;
+ }
+
/**
* Answers an iterator over the intervals in the store, with no particular
* ordering guaranteed. The iterator does not support the optional
* buffer
*
* @param interval
+ * @param rangeOnly
+ * don't do a full check for identity, just check for range
* @return index (nonnegative) or index where it would go (negative)
*/
- private int findInterval(IntervalI interval)
+ private int findInterval(IntervalI interval, boolean rangeOnly)
{
- if (isSorted)
- {
- int pt = binaryIdentitySearch(interval, null);
+ // if (isSorted)
+ // {
+ int pt = binaryIdentitySearch(interval, null, rangeOnly);
// if (addPt == intervalCount || offsets[pt] == 0)
// return pt;
if (pt >= 0 || added == 0 || pt == -1 - intervalCount)
case -1:
break;
case 0:
- if (sameInterval(interval, iv))
+ if (!rangeOnly && sameInterval(iv, interval))
{
return pt;
}
}
}
return -1 - match;
- }
- else
- {
- int i = intervalCount;
- while (--i >= 0 && !sameInterval(intervals[i], interval))
- {
-
- }
- return i;
- }
+ // }
+ // else
+ // {
+ // int i = intervalCount;
+ // while (--i >= 0 && !sameRange(intervals[i], interval))
+ // {
+ // ;
+ // }
+ // return i;
+ // }
}
/**
protected boolean removeInterval(IntervalI interval)
{
- if (!isSorted || added > 0)
+ if (// !isSorted ||
+ added > 0)
{
sort();
}
- int i = binaryIdentitySearch(interval, bsDeleted);
+ int i = binaryIdentitySearch(interval, bsDeleted, false);
if (i < 0)
{
return false;
}
+ public boolean revalidate()
+ {
+ isTainted = true;
+ // isSorted = false;
+ ensureFinalized();
+ return true;
+ }
+
@Override
public int size()
{
Arrays.sort(intervals, 0, intervalCount, icompare);
}
updateMinMaxStart();
- isSorted = true;
+ // isSorted = true;
}
private void updateMinMaxStart()
{
return prettyPrint();
}
+
+ public boolean canCheckForDuplicates()
+ {
+ return true;
+ }
+
+ /**
+ * CAUTION! This presumes that equalsInterval does check descriptions. Note
+ * that bartongroup.IntervalStoreJ does NOT do this and
+ * jalview.datamodel.features.SequenceFeature does not, either. But
+ * nonc.SimpleFeature in test DOES, because it overrides equalsInterval.
+ *
+ * The reason we do it this way is to avoid an unnecessary and costly test for
+ * obj instanceof IntervalI.
+ *
+ * Added by Mungo to use equals, but that requires use of instance checking,
+ * which is not significant in Java (apparently), but is a bigger deal in
+ * JavaScript. So here we have to hack
+ * bobhanson.IntervalStoreJ.nonc.InervalStore to bypass equals.
+ *
+ * @param i1
+ * @param i2
+ * @return
+ */
+ boolean sameInterval(IntervalI i1, IntervalI i2)
+ {
+ // avoiding equals() for JavaScript performance
+ return ((SequenceFeature) i1).equals((SequenceFeature) i2, false);
+ }
+
}
git://source.jalview.org / jalview.git / blobdiff