*/
package intervalstore.nonc;
+import jalview.datamodel.SequenceFeature;
+
import java.util.AbstractCollection;
import java.util.ArrayList;
import java.util.Arrays;
*/
private boolean bigendian;
- private final boolean DO_PRESORT;
-
- private boolean isSorted;
-
+ // private final boolean DO_PRESORT;
+ //
+ // private boolean isSorted;
+ //
private boolean createUnnested = true;
private int minStart = Integer.MAX_VALUE, maxStart = Integer.MIN_VALUE,
* are in contiguous sets of binary-searchable blocks
*
*/
- private int[] nestStarts;
+ private int[] nestOffsets;
/**
* the count of intervals within a nest
*
*/
- private int[] nestCounts;
+ private int[] nestLengths;
- public IntervalStore()
- {
- this(true);
- }
+ /**
+ * pointer to the root nest (intervalCount)
+ */
+ private int root;
- public IntervalStore(boolean presort)
+ /**
+ * pointer to the unnested set (intervalCount + 1);
+ */
+ private int unnested;
+
+ public IntervalStore()
{
- this(null, presort);
+ this(null);
}
+ // public IntervalStore(boolean presort)
+ // {
+ // this(null, presort);
+ // }
+ //
/**
* Constructor given a list of intervals. Note that the list may get sorted as
* a side-effect of calling this constructor.
*/
public IntervalStore(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 IntervalStore(List<T> intervals, boolean presort)
- {
- // setting default to BIG_ENDIAN, meaning
- // the order will be [10,100] before [10,80]
- // this order doesn't really matter much.
- this(intervals, presort, null, true);
+ this(intervals, null, true);
}
/**
*
* @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 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-100] before [10-80]; defaults to
* true
*/
- public IntervalStore(List<T> intervals, boolean presort,
+ public IntervalStore(List<T> intervals,
Comparator<? super IntervalI> comparator, boolean bigendian)
{
+ // 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.intervals = new IntervalI[capacity = intervalCount = intervals
.size()]);
}
- DO_PRESORT = presort;
- if (DO_PRESORT && intervalCount > 1)
+ isTainted = true;
+ // DO_PRESORT = presort;
+ if (// DO_PRESORT &&
+ intervalCount > 1)
{
updateMinMaxStart();
- isSorted = true;
- isTainted = true;
+ // isSorted = true;
ensureFinalized();
}
- else
- {
- isSorted = DO_PRESORT;
- isTainted = true;
- }
+ // else
+ // {
+ // isSorted = DO_PRESORT;
+ // isTainted = true;
+ // }
}
/**
- * Adds one interval to the store, allowing duplicates
+ * Adds one interval to the store, allowing duplicates.
*
* @param interval
*/
}
- 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)
{
int pt0 = pt;
while (--pt >= 0 && offsets[pt] == 0)
{
-
+ ;
}
if (pt < 0)
{
offsets = null;
intervalCount = ntotal;
capacity = dest.length;
- // System.out.println(Arrays.toString(dest));
return dest;
}
*/
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;
}
- /**
- * Answers true if the two intervals are equal (as determined by
- * {@code i1.equals(i2)}, else false
- *
- * @param i1
- * @param i2
- * @return
- */
- static boolean sameInterval(IntervalI i1, IntervalI i2)
+ public boolean canCheckForDuplicates()
{
- /*
- * for speed, do the fast check for begin/end equality before
- * the equals check which includes type checking
- */
- return i1.equalsInterval(i2) && i1.equals(i2);
+ return true;
}
/**
public void clear()
{
intervalCount = added = 0;
- isSorted = true;
+ // isSorted = true;
isTainted = true;
offsets = null;
intervals = new IntervalI[8];
- nestStarts = nestCounts = null;
+ nestOffsets = nestLengths = null;
nests = null;
minStart = maxEnd = Integer.MAX_VALUE;
maxStart = Integer.MIN_VALUE;
{
return false;
}
- if (!isSorted || deleted > 0)
+ if (// !isSorted ||
+ deleted > 0)
{
sort();
}
- int n = findInterval((IntervalI) entry);
- return (n >= 0);
+ return (findInterval((IntervalI) entry, false) >= 0);
}
/**
{
if (isTainted)
{
- if (!isSorted || added > 0 || deleted > 0)
+ if (// !isSorted ||
+ added > 0 || deleted > 0)
{
sort();
}
{
return result;
}
- int root = 0;
if (createUnnested)
{
- if (nestCounts[0] > 0)
+ if (nestLengths[unnested] > 0)
{
- searchNonnested(nestCounts[0], nests, from, to,
- (List<IntervalI>) result);
+ searchUnnested(from, to, (List<IntervalI>) result);
}
- root = 1;
}
- if (nestCounts[root] > 0)
+ if (nestLengths[root] > 0)
{
search(nests, from, to, root, result);
}
* A simpler search, since we know we don't have any subintervals. Not
* necessary, actually.
*
- * @param nestStarts
- * @param nestCounts
+ * @param nestOffsets
+ * @param nestLengths
* @param nests
* @param from
* @param to
* @param result
*/
- private static void searchNonnested(int n,
- IntervalI[] nests, long from, long to, List<IntervalI> result)
+ private void searchUnnested(long from, long to, List<IntervalI> result)
{
- int end = 2 + n - 1;
- for (int pt = binarySearchFirstEndNotBefore(nests, from, 2,
+ int start = nestOffsets[unnested];
+ int end = start + nestLengths[unnested] - 1;
+ for (int pt = binarySearchFirstEndNotBefore(nests, from, start,
end); pt <= end; pt++)
{
IntervalI ival = nests[pt];
private void search(IntervalI[] nests, long from, long to, int nest,
List<T> result)
{
- int start = nestStarts[nest];
- int n = nestCounts[nest];
+ int start = nestOffsets[nest];
+ int n = nestLengths[nest];
int end = start + n - 1;
IntervalI first = nests[start];
IntervalI last = nests[end];
break;
}
result.add((T) ival);
- if (nestCounts[pt] > 0)
+ if (nestLengths[pt] > 0)
{
// check subintervals in this nest
search(nests, from, to, pt, result);
}
/**
+ * return the i-th interval in the designated order (bigendian or
+ * littleendian)
+ */
+ public IntervalI get(int i)
+ {
+ if (i < 0 || i >= intervalCount + added)
+ {
+ return null;
+ }
+ ensureFinalized();
+ return intervals[i];
+ }
+
+ /**
* Return the deepest level of nesting.
*
*/
{
ensureFinalized();
BitSet bsTested = new BitSet();
- return Math.max((createUnnested ? getDepth(1, bsTested) : 0),
- getDepth(0, bsTested));
+ return Math.max((createUnnested ? getDepth(unnested, bsTested) : 0),
+ getDepth(root, bsTested));
}
/**
{
int maxDepth = 0;
int depth;
- int n = nestCounts[pt];
+ int n = nestLengths[pt];
if (n == 0 || bsTested.get(pt))
{
return 1;
}
bsTested.set(pt);
- for (int st = nestStarts[pt], i = st + n; --i >= st;)
+ for (int st = nestOffsets[pt], i = st + n; --i >= st;)
{
if ((depth = getDepth(i, bsTested)) > maxDepth)
{
}
/**
+ * Get the number of root-level nests.
+ *
+ */
+ public int getWidth()
+ {
+ ensureFinalized();
+ return nestLengths[root] + (createUnnested ? nestLengths[unnested] : 0);
+ }
+
+ 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
* <code>remove</code> operation (throws
if (createUnnested)
{
sb.append("unnested:");
- dump(0, sb, "\n");
+ dump(intervalCount + 1, sb, "\n");
sb.append("\nnested:");
- dump(1, sb, "\n");
- }
- else
- {
- dump(0, sb, "\n");
}
+ dump(intervalCount, sb, "\n");
return sb.toString();
}
*/
private void dump(int nest, StringBuffer sb, String sep)
{
- int pt = nestStarts[nest];
- int n = nestCounts[nest];
+ int pt = nestOffsets[nest];
+ int n = nestLengths[nest];
sep += " ";
for (int i = 0; i < n; i++)
{
sb.append(sep).append(nests[pt + i].toString());
- if (nestCounts[pt + i] > 0)
+ if (nestLengths[pt + i] > 0)
{
dump(pt + i, sb, sep + " ");
}
@Override
public synchronized boolean remove(Object o)
{
+ // if (o == null)
+ // {
+ // throw new NullPointerException();
+ // }
return (o != null && intervalCount > 0
&& removeInterval((IntervalI) o));
}
* buffer
*
* @param interval
+ * @param rangeOnly
+ * don't do a full identity check, just a range check
+ *
* @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 && !sameInterval(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;
+ // isSorted = false;
ensureFinalized();
return true;
}
Arrays.sort(intervals, 0, intervalCount, icompare);
}
updateMinMaxStart();
- isSorted = true;
+ // isSorted = true;
}
- // 0 5-5
- // 1 6-8
- // 2 10-80
- // 3 10-100
- // 4 10-100
- // 5 20-30
- // 6 35-40
- // 7 50-80
- // 8 51-51
- // 9 52-52
- // 10 55-60
- // 11 56-56
- // 12 70-120
- // 13 78-78
- //
- // cont [-1, -1, -1, -1, 3, 4, 4, 4, 7, 7, 7, 10, -1, 12]
- // nests [0, 0, 1, 2, 3, 12, 4, 5, 6, 7, 8, 9, 10, 11, 13]
- // starts [1, 0, 0, 0, 6, 14, 7, 0, 0, 10, 0, 0, 13, 0, 0]
- // counts [5, 0, 0, 0, 1, 1, 3, 0, 0, 3, 0, 0, 1, 0, 0]
-
/**
- * Create the key arrays: nests, nestStarts, and nestCounts. The starting
- * point is getting the container array, which may hold -1 (top level nesting)
- * and -2 (unnested set, if doing that).
+ * Create the key arrays: nests, nestOffsets, and nestLengths. The starting
+ * point is getting the container array, which may point to then root nest or
+ * the unnested set.
*
* This is a pretty complicated method; it was way simpler before I decided to
- * support nesting as an option.
+ * support unnesting as an option.
*
*/
private void createArrays()
{
+ // goal here is to create an array, nests[], that is a block
+
/**
* When unnesting, we need a second top-level listing.
*
*/
- int incr = (createUnnested ? 2 : 1);
+ int len = intervalCount + (createUnnested ? 2 : 1);
+ root = intervalCount;
+ unnested = intervalCount + 1;
/**
* The three key arrays produced by this method:
*/
-
- nests = new IntervalI[intervalCount + incr];
- nestStarts = new int[intervalCount + incr];
- nestCounts = new int[intervalCount + incr];
+ nests = new IntervalI[intervalCount];
+ nestOffsets = new int[len];
+ nestLengths = new int[len];
/**
- * a temporary array used in Phase Two.
+ * the objectives of Phase One
*/
- int[] counts = new int[intervalCount + incr];
-
- /**
- * the objective of Phase One
- */
int[] myContainer = new int[intervalCount];
+ int[] counts = new int[len];
+
+ // Phase One: Get the temporary container array myContainer.
+
+ myContainer[0] = (createUnnested ? unnested : root);
+ counts[myContainer[0]] = 1;
+
+ // memories for previous begin and end
- myContainer[0] = -incr;
- counts[0] = 1;
int beginLast = intervals[0].getBegin();
int endLast = intervals[0].getEnd();
- int ptLastNot2 = -1;
- int endLast2 = endLast;
+
+ // memories for previous unnested pt, begin, and end
+
+ int ptLastNot2 = root;
int beginLast2 = beginLast;
+ int endLast2 = endLast;
- // Phase One: Get the temporary container array myContainer.
for (int i = 1; i < intervalCount; i++)
{
int pt = i - 1;
- int end = intervals[i].getEnd();
int begin = intervals[i].getBegin();
+ int end = intervals[i].getEnd();
- // set the pointer to the element that is containing
- // this interval, or -2 (unnested) or -1 (root-level nest)
+ // initialize the container to either root or unnested
- myContainer[i] = -incr;
+ myContainer[i] = myContainer[0];
// OK, now figure it all out...
// perfectly, down to the exact number of times that the
// binary search runs through its start/mid/end loops in findOverlap.
- // beginLast2 and endLast2 refer to the root-level or unnested level
+ // beginLast2 and endLast2 refer to the last unnested level
- if (!isNested(begin, end, beginLast2, endLast2))
- {
- isNested = false;
- }
- else
+ isNested = isNested(begin, end, beginLast2, endLast2);
+ if (isNested)
{
// this is tricky; making sure we properly get the
// nests that are to be removed from the top-level
- // unnested list assigned a container -1, while all
- // top-level nests get -2.
+ // unnested list assigned a container root, while all
+ // top-level nests get the pointer to unnested.
pt = ptLastNot2;
- isNested = (pt < 0 || isNested(begin, end,
+ isNested = (pt == root || isNested(begin, end,
intervals[pt].getBegin(), intervals[pt].getEnd()));
if (!isNested)
{
- myContainer[i] = -1;
+ myContainer[i] = root;
}
}
}
// monotonic -- find the parent that is doing the nesting
- while ((pt = myContainer[pt]) >= 0)
+ while ((pt = myContainer[pt]) < root)
{
if (isNested(begin, end, intervals[pt].getBegin(),
intervals[pt].getEnd()))
// update the counts and pointers
- counts[myContainer[i] + incr]++;
- if (myContainer[i] == -2)
+ counts[myContainer[i]]++;
+ if (myContainer[i] == unnested)
{
endLast2 = end;
beginLast2 = begin;
}
}
- // Phase Two: construct the nests[] array and its associated
+ // System.out.println("intervals " + Arrays.toString(intervals));
+ // System.out.println("conts " + Arrays.toString(myContainer));
+ // System.out.println("counts " + Arrays.toString(counts));
+
+ // Phase Two: Construct the nests[] array and its associated
// starting pointer array and nest element counts. These counts
// are actually produced above, but we reconstruct it as a set
// of dynamic pointers during construction.
- // incr is either 1 (no separate unnested set) or 2 (include unnested)
+ // The reason this is two phases is that only now do we know where to start
+ // the nested set. If we did not unnest, we could do this all in one pass
+ // using a reverse sort for the root, and then just reverse that, but with
+ // unnesting, we have two unknown starts, and that doesn't give us that
+ // opportunity.
- int nextStart = counts[0] + incr;
/**
- * this array tracks the pointer within nestStarts to the nest block start
- * in nests[].
+ * this temporary array tracks the pointer within nestOffsets to the nest
+ * block offset for intervals[i]'s container.
*/
- int[] startPt = new int[intervalCount + incr];
- nestStarts[0] = incr;
-
- // When not unnesting, nestStarts[0] = 1, and the length
- // will start out here as 0 but increment as we go.
- // We do this even though we know its size already, because that
- // value serves as a dynamic pointer as well.
+ int[] startPt = new int[len];
- if (createUnnested)
- {
-
- // Unnesting requires two separate lists with proper pointers and counts.
- // The first, nestStarts[0] = 0, is for the unnested set (container -2);
- // the second (container -1, nestStarts[1]) is for the nest root.
+ startPt[root] = root;
- startPt[1] = 1;
- nestStarts[1] = nextStart;
- nextStart += counts[1];
+ int nextStart = counts[root];
+
+ if (unnested > 0)
+ {
+ nestOffsets[root] = counts[unnested];
+ nextStart += counts[unnested];
+ startPt[unnested] = unnested;
}
// Now get all the pointers right and set the nests[] pointer into intervals
for (int i = 0; i < intervalCount; i++)
{
- int n = counts[i + incr];
- int ptNest = startPt[myContainer[i] + incr];
- int p = nestStarts[ptNest] + nestCounts[ptNest]++;
+ int ptOffset = startPt[myContainer[i]];
+ int p = nestOffsets[ptOffset] + nestLengths[ptOffset]++;
nests[p] = intervals[i];
- if (n > 0)
+ if (counts[i] > 0)
{
- startPt[i + incr] = p;
- nestStarts[p] = nextStart;
- nextStart += n;
+ // this is a container
+ startPt[i] = p;
+ nestOffsets[p] = nextStart;
+ nextStart += counts[i];
}
}
// System.out.println("intervals " + Arrays.toString(intervals));
// System.out.println("nests " + Arrays.toString(nests));
// System.out.println("conts " + Arrays.toString(myContainer));
- // System.out.println("starts " + Arrays.toString(nestStarts));
- // System.out.println("counts " + Arrays.toString(nestCounts));
- // System.out.println("done " + nestCounts[0]);
+ // System.out.println("offsets " + Arrays.toString(nestOffsets));
+ // System.out.println("lengths " + Arrays.toString(nestLengths));
+ // System.out.println(
+ // "done " + nestLengths[root]
+ // + (unnested > 0 ? " " + nestLengths[unnested] : ""));
}
/**
return prettyPrint();
}
+ /**
+ * 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);
+ }
}
*/
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 / commitdiff