X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fintervalstore%2Fnonc%2FIntervalStore0.java;fp=src%2Fintervalstore%2Fnonc%2FIntervalStore0.java;h=c998dc1de6757dc14c21f84c54302bc4b86d56a1;hb=c769685cc0a0eead20b9ce9b5a3d0d96f664b6cb;hp=1050ee09171ee27a66d2af010a5087ef1f6ec067;hpb=6e22e196339bb4bd20c7556f66c062021977ca13;p=jalview.git 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); + } + }