From c769685cc0a0eead20b9ce9b5a3d0d96f664b6cb Mon Sep 17 00:00:00 2001 From: hansonr Date: Sun, 22 Sep 2019 11:03:22 -0400 Subject: [PATCH] JAL-3253-applet JAL-3397 updates intervalstore.nonc to not use interval.equals() unnecessarily. --- src/intervalstore/nonc/IntervalStore.java | 462 +++++++++++--------- src/intervalstore/nonc/IntervalStore0.java | 250 +++++++---- src/jalview/datamodel/features/FeatureStore.java | 35 +- test/intervalstore/nonc/SimpleFeature.java | 13 +- .../datamodel/features/FeatureStoreLinkedTest.java | 2 +- .../features/FeatureStoreNCListBufferTest.java | 2 +- 6 files changed, 439 insertions(+), 325 deletions(-) diff --git a/src/intervalstore/nonc/IntervalStore.java b/src/intervalstore/nonc/IntervalStore.java index 5c013ad..405a471 100644 --- a/src/intervalstore/nonc/IntervalStore.java +++ b/src/intervalstore/nonc/IntervalStore.java @@ -31,6 +31,8 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ package intervalstore.nonc; +import jalview.datamodel.SequenceFeature; + import java.util.AbstractCollection; import java.util.ArrayList; import java.util.Arrays; @@ -124,10 +126,10 @@ public class IntervalStore */ 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, @@ -164,65 +166,61 @@ public class IntervalStore * 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 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 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 intervals, boolean presort, + public IntervalStore(List intervals, Comparator 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); @@ -243,23 +241,24 @@ public class IntervalStore 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 */ @@ -311,15 +310,15 @@ public class IntervalStore } - 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; @@ -334,15 +333,15 @@ public class IntervalStore } } - } - else - { - if (!allowDuplicates && findInterval(interval) >= 0) - { - return false; - } - isSorted = false; - } + // } + // else + // { + // if (!allowDuplicates && findInterval(interval) >= 0) + // { + // return false; + // } + // isSorted = false; + // } if (index == intervalCount) { @@ -402,7 +401,7 @@ public class IntervalStore int pt0 = pt; while (--pt >= 0 && offsets[pt] == 0) { - + ; } if (pt < 0) { @@ -428,7 +427,6 @@ public class IntervalStore offsets = null; intervalCount = ntotal; capacity = dest.length; - // System.out.println(Arrays.toString(dest)); return dest; } @@ -440,7 +438,7 @@ public class IntervalStore */ public int binaryIdentitySearch(IntervalI interval) { - return binaryIdentitySearch(interval, null); + return binaryIdentitySearch(interval, null, false); } /** @@ -450,9 +448,12 @@ public class IntervalStore * @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(); @@ -480,7 +481,7 @@ public class IntervalStore 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; @@ -494,7 +495,7 @@ public class IntervalStore { break; } - if ((bsIgnore == null || !bsIgnore.get(i)) + if (!rangeOnly && (bsIgnore == null || !bsIgnore.get(i)) && sameInterval(interval, iv)) { return i; @@ -519,21 +520,9 @@ public class IntervalStore 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; } /** @@ -544,11 +533,11 @@ public class IntervalStore 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; @@ -579,12 +568,12 @@ public class IntervalStore { 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); } /** @@ -611,7 +600,8 @@ public class IntervalStore { if (isTainted) { - if (!isSorted || added > 0 || deleted > 0) + if (// !isSorted || + added > 0 || deleted > 0) { sort(); } @@ -669,17 +659,14 @@ public class IntervalStore { return result; } - int root = 0; if (createUnnested) { - if (nestCounts[0] > 0) + if (nestLengths[unnested] > 0) { - searchNonnested(nestCounts[0], nests, from, to, - (List) result); + searchUnnested(from, to, (List) result); } - root = 1; } - if (nestCounts[root] > 0) + if (nestLengths[root] > 0) { search(nests, from, to, root, result); } @@ -690,18 +677,18 @@ public class IntervalStore * 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 result) + private void searchUnnested(long from, long to, List 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]; @@ -726,8 +713,8 @@ public class IntervalStore private void search(IntervalI[] nests, long from, long to, int nest, List 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]; @@ -765,7 +752,7 @@ public class IntervalStore break; } result.add((T) ival); - if (nestCounts[pt] > 0) + if (nestLengths[pt] > 0) { // check subintervals in this nest search(nests, from, to, pt, result); @@ -774,6 +761,20 @@ public class IntervalStore } /** + * 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. * */ @@ -782,8 +783,8 @@ public class IntervalStore { 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)); } /** @@ -797,13 +798,13 @@ public class IntervalStore { 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) { @@ -814,6 +815,22 @@ public class IntervalStore } /** + * 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 * remove operation (throws @@ -860,14 +877,10 @@ public class IntervalStore 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(); } @@ -880,14 +893,14 @@ public class IntervalStore */ 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 + " "); } @@ -897,6 +910,10 @@ public class IntervalStore @Override public synchronized boolean remove(Object o) { + // if (o == null) + // { + // throw new NullPointerException(); + // } return (o != null && intervalCount > 0 && removeInterval((IntervalI) o)); } @@ -906,15 +923,18 @@ public class IntervalStore * 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) @@ -935,7 +955,7 @@ public class IntervalStore case -1: break; case 0: - if (sameInterval(interval, iv)) + if (!rangeOnly && sameInterval(iv, interval)) { return pt; } @@ -946,16 +966,16 @@ public class IntervalStore } } 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; + // } } /** @@ -967,11 +987,12 @@ public class IntervalStore 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; @@ -1041,7 +1062,7 @@ public class IntervalStore public boolean revalidate() { isTainted = true; - isSorted = false; + // isSorted = false; ensureFinalized(); return true; } @@ -1087,85 +1108,70 @@ public class IntervalStore 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... @@ -1179,25 +1185,22 @@ public class IntervalStore // 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; } } } @@ -1217,7 +1220,7 @@ public class IntervalStore // 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())) @@ -1232,8 +1235,8 @@ public class IntervalStore // update the counts and pointers - counts[myContainer[i] + incr]++; - if (myContainer[i] == -2) + counts[myContainer[i]]++; + if (myContainer[i] == unnested) { endLast2 = end; beginLast2 = begin; @@ -1246,36 +1249,36 @@ public class IntervalStore } } - // 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 @@ -1283,24 +1286,26 @@ public class IntervalStore 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] : "")); } /** @@ -1344,5 +1349,28 @@ public class IntervalStore 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); + } } diff --git a/src/intervalstore/nonc/IntervalStore0.java b/src/intervalstore/nonc/IntervalStore0.java index 1050ee0..c998dc1 100644 --- a/src/intervalstore/nonc/IntervalStore0.java +++ b/src/intervalstore/nonc/IntervalStore0.java @@ -31,6 +31,8 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ package intervalstore.nonc; +import jalview.datamodel.SequenceFeature; + import java.util.AbstractCollection; import java.util.ArrayList; import java.util.Arrays; @@ -67,7 +69,10 @@ import intervalstore.api.IntervalStoreI; public class IntervalStore0 extends AbstractCollection implements IntervalStoreI { - 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 @@ -146,10 +151,6 @@ public class IntervalStore0 */ 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; @@ -178,12 +179,7 @@ public class IntervalStore0 */ public IntervalStore0() { - this(true); - } - - public IntervalStore0(boolean presort) - { - this(null, presort); + this(null); } /** @@ -192,35 +188,21 @@ public class IntervalStore0 */ public IntervalStore0(List 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 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 intervals, boolean presort, + public IntervalStore0(List intervals, Comparator comparator, boolean bigendian) { if (intervals != null) @@ -229,17 +211,19 @@ public class IntervalStore0 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; } @@ -251,7 +235,7 @@ public class IntervalStore0 @Override public boolean add(T interval) { - return add(interval, false); + return add(interval, true); } /** @@ -290,15 +274,15 @@ public class IntervalStore0 } - 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; @@ -313,15 +297,15 @@ public class IntervalStore0 } } - } - else - { - if (!allowDuplicates && findInterval(interval) >= 0) - { - return false; - } - isSorted = false; - } + // } + // else + // { + // if (!allowDuplicates && findInterval(interval) >= 0) + // { + // return false; + // } + // isSorted = false; + // } if (index == intervalCount) { @@ -369,12 +353,12 @@ public class IntervalStore0 // 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) { @@ -403,9 +387,15 @@ public class IntervalStore0 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); } /** @@ -415,9 +405,12 @@ public class IntervalStore0 * @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(); @@ -445,7 +438,7 @@ public class IntervalStore0 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; @@ -459,7 +452,7 @@ public class IntervalStore0 { break; } - if ((bsIgnore == null || !bsIgnore.get(i)) + if (!rangeOnly && (bsIgnore == null || !bsIgnore.get(i)) && sameInterval(interval, iv)) { return i; @@ -483,19 +476,39 @@ public class IntervalStore0 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; @@ -527,17 +540,18 @@ public class IntervalStore0 { 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) @@ -555,7 +569,8 @@ public class IntervalStore0 { if (isTainted) { - if (!isSorted || added > 0 || deleted > 0) + if (// !isSorted || + added > 0 || deleted > 0) { sort(); } @@ -649,6 +664,16 @@ public class IntervalStore0 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) @@ -698,6 +723,26 @@ public class IntervalStore0 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 @@ -807,15 +852,17 @@ public class IntervalStore0 * 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) @@ -836,7 +883,7 @@ public class IntervalStore0 case -1: break; case 0: - if (sameInterval(interval, iv)) + if (!rangeOnly && sameInterval(iv, interval)) { return pt; } @@ -847,16 +894,16 @@ public class IntervalStore0 } } 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; + // } } /** @@ -868,11 +915,12 @@ public class IntervalStore0 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; @@ -931,6 +979,14 @@ public class IntervalStore0 } + public boolean revalidate() + { + isTainted = true; + // isSorted = false; + ensureFinalized(); + return true; + } + @Override public int size() { @@ -962,7 +1018,7 @@ public class IntervalStore0 Arrays.sort(intervals, 0, intervalCount, icompare); } updateMinMaxStart(); - isSorted = true; + // isSorted = true; } private void updateMinMaxStart() @@ -984,4 +1040,34 @@ public class IntervalStore0 { 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); + } + } diff --git a/src/jalview/datamodel/features/FeatureStore.java b/src/jalview/datamodel/features/FeatureStore.java index 4073dd6..b7cd330 100644 --- a/src/jalview/datamodel/features/FeatureStore.java +++ b/src/jalview/datamodel/features/FeatureStore.java @@ -101,26 +101,23 @@ public class FeatureStore /** * linked-list IntervalStore */ - public final static int INTERVAL_STORE_LINKED_LIST_PRESORT = 1; - - /** - * linked-list IntervalStore - */ - public final static int INTERVAL_STORE_LINKED_LIST_NO_PRESORT = 2; - - /** - * NCList as array buffer IntervalStore - */ - public final static int INTERVAL_STORE_NCLIST_BUFFER_PRESORT = 3; + public final static int INTERVAL_STORE_LINKED_LIST = 1; /** * NCList as array buffer IntervalStore */ - public final static int INTERVAL_STORE_NCLIST_BUFFER_NO_PRESORT = 4; + public final static int INTERVAL_STORE_NCARRAY = 3; static final int intervalStoreJavaOption = INTERVAL_STORE_NCLIST_OBJECT; - static final int intervalStoreJSOption = INTERVAL_STORE_NCLIST_BUFFER_PRESORT; + private final static boolean isJSLinkedTest = false; + + static final int intervalStoreJSOption = (isJSLinkedTest + ? INTERVAL_STORE_LINKED_LIST + : INTERVAL_STORE_NCARRAY); + + // TODO: compare performance in real situations using + // INTERVAL_STORE_LINKED_LIST; /** * Answers the 'length' of the feature, counting 0 for non-positional features @@ -259,14 +256,10 @@ public class FeatureStore default: case INTERVAL_STORE_NCLIST_OBJECT: return new intervalstore.impl.IntervalStore<>(); - case INTERVAL_STORE_NCLIST_BUFFER_PRESORT: - return new intervalstore.nonc.IntervalStore<>(true); - case INTERVAL_STORE_NCLIST_BUFFER_NO_PRESORT: - return new intervalstore.nonc.IntervalStore<>(false); - case INTERVAL_STORE_LINKED_LIST_PRESORT: - return new intervalstore.nonc.IntervalStore0<>(true); - case INTERVAL_STORE_LINKED_LIST_NO_PRESORT: - return new intervalstore.nonc.IntervalStore0<>(false); + case INTERVAL_STORE_NCARRAY: + return new intervalstore.nonc.IntervalStore<>(); + case INTERVAL_STORE_LINKED_LIST: + return new intervalstore.nonc.IntervalStore0<>(); } } diff --git a/test/intervalstore/nonc/SimpleFeature.java b/test/intervalstore/nonc/SimpleFeature.java index d10d90a..e05d1e3 100644 --- a/test/intervalstore/nonc/SimpleFeature.java +++ b/test/intervalstore/nonc/SimpleFeature.java @@ -31,12 +31,17 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ package intervalstore.nonc; -import intervalstore.api.IntervalI; +import jalview.datamodel.SequenceFeature; /** - * A simplified feature instance sufficient for unit test purposes + * A simplified feature instance sufficient for unit test purposes. + * + * Subclasses SequenceFeature only because otherwise we have to use equals() in + * the Jalview version of nonc.IntervalStore, and that does a class check that + * we were trying to avoid. + * */ -public class SimpleFeature implements IntervalI +public class SimpleFeature extends SequenceFeature { final private int begin; @@ -53,6 +58,7 @@ public class SimpleFeature implements IntervalI */ public SimpleFeature(int from, int to, String desc) { + super("", desc, from, to, ""); begin = from; end = to; description = desc; @@ -80,6 +86,7 @@ public class SimpleFeature implements IntervalI return end; } + @Override public String getDescription() { return description; diff --git a/test/jalview/datamodel/features/FeatureStoreLinkedTest.java b/test/jalview/datamodel/features/FeatureStoreLinkedTest.java index c1cd6d7..74c413f 100644 --- a/test/jalview/datamodel/features/FeatureStoreLinkedTest.java +++ b/test/jalview/datamodel/features/FeatureStoreLinkedTest.java @@ -19,7 +19,7 @@ public class FeatureStoreLinkedTest private FeatureStore newFeatureStore() { return new FeatureStore( - FeatureStore.INTERVAL_STORE_LINKED_LIST_PRESORT); + FeatureStore.INTERVAL_STORE_LINKED_LIST); } @Test(groups = "Functional") diff --git a/test/jalview/datamodel/features/FeatureStoreNCListBufferTest.java b/test/jalview/datamodel/features/FeatureStoreNCListBufferTest.java index c7598d4..66cd892 100644 --- a/test/jalview/datamodel/features/FeatureStoreNCListBufferTest.java +++ b/test/jalview/datamodel/features/FeatureStoreNCListBufferTest.java @@ -19,7 +19,7 @@ public class FeatureStoreNCListBufferTest private FeatureStore newFeatureStore() { return new FeatureStore( - FeatureStore.INTERVAL_STORE_NCLIST_BUFFER_PRESORT); + FeatureStore.INTERVAL_STORE_NCARRAY); } @Test(groups = "Functional") -- 1.7.10.2