4 Copyright (c) 2018, Mungo Carstairs
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions are met:
10 * Redistributions of source code must retain the above copyright notice, this
11 list of conditions and the following disclaimer.
13 * Redistributions in binary form must reproduce the above copyright notice,
14 this list of conditions and the following disclaimer in the documentation
15 and/or other materials provided with the distribution.
17 * Neither the name of the copyright holder nor the names of its
18 contributors may be used to endorse or promote products derived from
19 this software without specific prior written permission.
21 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
22 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
24 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
25 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
27 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
28 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
29 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 package intervalstore.nonc;
34 import jalview.datamodel.SequenceFeature;
36 import java.util.AbstractCollection;
37 import java.util.ArrayList;
38 import java.util.Arrays;
39 import java.util.BitSet;
40 import java.util.Collections;
41 import java.util.Comparator;
42 import java.util.Iterator;
43 import java.util.List;
44 import java.util.NoSuchElementException;
46 import intervalstore.api.IntervalI;
47 import intervalstore.api.IntervalStoreI;
51 * A fourth idea, implementing NCList as a pointer system identical in operation
52 * to IntervalStoreJ's implementation using ArrayLists but here using just two
53 * int[] arrays and a single IntervalI[] array that is in the proper order for
54 * holding all nested and unnested arrays.
56 * Use of unnesting is optional and can be experimented with by changing the
57 * createUnnested flag to false.
59 * Preliminary testing suggests that this implementation is about 10% faster for
60 * store interval size 50, store sequence factor 10, query width -1000 (fixed
61 * 1000-unit-wide window), and query count 100000.
63 * Origional note (Mungo Carstairs, IntervalStoreJ)
65 * A Collection class to store interval-associated data, with options for "lazy"
66 * sorting so as to speed incremental construction of the data prior to issuing
69 * Accepts duplicate entries but not null values.
73 * @author Bob Hanson 2019.09.01
76 * any type providing <code>getBegin()</code> and
77 * <code>getEnd()</code>, primarily
79 public class IntervalStore<T extends IntervalI>
80 extends AbstractCollection<T> implements IntervalStoreI<T>
84 * Search for the last interval that ends at or just after the specified
85 * position. In the situation that there are multiple intervals starting at
86 * pos, this method returns the first of those.
89 * the nest-ordered array from createArrays()
91 * the position at the start of the interval of interest
93 * the starting point for the subarray search
95 * the ending point for the subarray search
96 * @return index into the nests array or one greater than end if not found
98 public static int binarySearchFirstEndNotBefore(IntervalI[] nests, long from,
101 int matched = end + 1;
105 mid = (start + end) >>> 1;
106 if (nests[mid].getEnd() >= from)
120 * My preference is for a bigendian comparison, but you may differ.
122 private Comparator<? super IntervalI> icompare;
125 * bigendian is what NCList does; change icompare to switch to that
127 private boolean bigendian;
129 // private final boolean DO_PRESORT;
131 // private boolean isSorted;
133 private boolean createUnnested = true;
135 private int minStart = Integer.MAX_VALUE, maxStart = Integer.MIN_VALUE,
136 maxEnd = Integer.MAX_VALUE;
138 private boolean isTainted;
140 private int capacity = 8;
142 protected IntervalI[] intervals = new IntervalI[capacity];
144 private int[] offsets;
146 protected int intervalCount;
152 private BitSet bsDeleted;
155 * the key array that lists the intervals in sub-interval order so that the
156 * binary search can be isolated to a single subinterval just by indicating
157 * start and end within one array
159 private IntervalI[] nests;
162 * pointers to the starting positions in nests[] for a subinterval; the first
163 * element is the "unnested" pointer when unnesting (2) or the root level nest
164 * pointer when not unnesting (1); the second element is root level nest when
165 * unnesting or the start of nest data when not unnesting; after that, nests
166 * are in contiguous sets of binary-searchable blocks
169 private int[] nestOffsets;
172 * the count of intervals within a nest
175 private int[] nestLengths;
178 * pointer to the root nest (intervalCount)
183 * pointer to the unnested set (intervalCount + 1);
185 private int unnested;
187 public IntervalStore()
192 // public IntervalStore(boolean presort)
194 // this(null, presort);
198 * Constructor given a list of intervals. Note that the list may get sorted as
199 * a side-effect of calling this constructor.
201 public IntervalStore(List<T> intervals)
203 this(intervals, null, true);
209 * intervals to initialize with (others may still be added)
211 * IntervalI.COMPARATOR_BEGIN_ASC_END_ASC or
212 * IntervalI.COMPARE_BEGIN_ASC_END_DESC, but this could also be one
213 * that sorts by description as well, for example.
215 * true if the comparator sorts [10-100] before [10-80]; defaults to
218 public IntervalStore(List<T> intervals,
219 Comparator<? super IntervalI> comparator, boolean bigendian)
221 // COMPARE_BEGIN_ASC_END_DESC is standard, meaning
222 // the order will be [10,100] before [10,80]
223 // this order doesn't really matter much.
224 icompare = (comparator != null ? comparator
225 : bigendian ? IntervalI.COMPARE_BEGIN_ASC_END_DESC
226 : IntervalI.COMPARE_BEGIN_ASC_END_ASC);
227 this.bigendian = bigendian;
229 if (intervals != null)
231 // So, five hours later, we learn that all my timing has been thrown off
232 // because I used Array.sort, which if you look in the Java JDK is exactly
233 // what Collections.sort is, but for whatever reason, all my times were
234 // high by about 100-200 ms 100% reproducibly. Just one call to Array.sort
235 // prior to the nanotimer start messed it all up. Some sort of memory or
236 // garbage issue; I do not know. But using Collections.sort here fixes the
239 Collections.sort(intervals, icompare);
241 this.intervals = new IntervalI[capacity = intervalCount = intervals
245 // DO_PRESORT = presort;
255 // isSorted = DO_PRESORT;
261 * Adds one interval to the store, allowing duplicates.
266 public boolean add(T interval)
268 return add(interval, true);
272 * Adds one interval to the store, optionally checking for duplicates.
274 * This fast-adding algorithm uses a double-length int[] (offsets) to hold
275 * pointers into intervals[] that allows continual sorting of an expanding
276 * array buffer. When the time comes, this is cleaned up and packed back into
277 * a standard array, but in the mean time, it can be added to with no loss of
281 * @param allowDuplicates
284 public boolean add(T interval, boolean allowDuplicates)
286 if (interval == null)
301 synchronized (intervals)
303 int index = intervalCount;
304 int start = interval.getBegin();
306 if (intervalCount + added + 1 >= capacity)
308 intervals = finalizeAddition(
309 new IntervalI[capacity = capacity << 1]);
313 // if (DO_PRESORT && isSorted)
315 if (intervalCount == 0)
321 index = findInterval(interval, allowDuplicates);
322 if (!allowDuplicates && index >= 0)
339 // if (!allowDuplicates && findInterval(interval) >= 0)
346 if (index == intervalCount)
348 intervals[intervalCount++] = interval;
349 // System.out.println("added " + intervalCount + " " + interval);
353 int pt = capacity - ++added;
354 intervals[pt] = interval;
355 // System.out.println("stashed " + pt + " " + interval + " for "
356 // + index + " " + intervals[index]);
359 offsets = new int[capacity];
362 offsets[pt] = offsets[index];
367 minStart = Math.min(minStart, start);
368 maxStart = Math.max(maxStart, start);
374 * Clean up the intervals array into a simple ordered array.
379 private IntervalI[] finalizeAddition(IntervalI[] dest)
387 if (intervalCount > 0 && dest != intervals)
389 System.arraycopy(intervals, 0, dest, 0, intervalCount);
391 capacity = dest.length;
394 // System.out.println("finalizing " + intervalCount + " " + added);
396 // array is [(intervalCount)...null...(added)]
398 int ntotal = intervalCount + added;
399 for (int ptShift = ntotal, pt = intervalCount; pt >= 0;)
402 while (--pt >= 0 && offsets[pt] == 0)
411 // shift upper intervals right
415 System.arraycopy(intervals, pt, dest, ptShift, nOK);
421 for (int offset = offsets[pt]; offset > 0; offset = offsets[offset])
423 dest[--ptShift] = intervals[offset];
428 intervalCount = ntotal;
429 capacity = dest.length;
434 * A binary search for a duplicate.
439 public int binaryIdentitySearch(IntervalI interval)
441 return binaryIdentitySearch(interval, null, false);
445 * for remove() and contains()
452 * don't do a full identity check, just a range check
453 * @return index or, if not found, -1 - "would be here"
455 private int binaryIdentitySearch(IntervalI interval, BitSet bsIgnore,
459 int r0 = interval.getBegin();
460 int r1 = interval.getEnd();
461 int end = intervalCount - 1;
462 if (end < 0 || r0 < minStart)
468 return -1 - intervalCount;
472 int mid = (start + end) >>> 1;
473 IntervalI r = intervals[mid];
474 switch (compareRange(r, r0, r1))
483 IntervalI iv = intervals[mid];
484 if (!rangeOnly && (bsIgnore == null || !bsIgnore.get(mid))
485 && sameInterval(interval, iv))
488 // found one; just scan up and down now, first checking the range, but
489 // also checking other possible aspects of equivalence.
492 for (int i = mid; ++i <= end;)
494 if ((iv = intervals[i]).getBegin() != r0 || iv.getEnd() != r1)
498 if (!rangeOnly && (bsIgnore == null || !bsIgnore.get(i))
499 && sameInterval(interval, iv))
504 for (int i = mid; --i >= start;)
506 if ((iv = intervals[i]).getBegin() != r0
507 || (bigendian ? r1 < iv.getEnd() : iv.getEnd() < r1))
511 if ((bsIgnore == null || !bsIgnore.get(i))
512 && sameInterval(interval, iv))
523 public boolean canCheckForDuplicates()
535 intervalCount = added = 0;
539 intervals = new IntervalI[8];
540 nestOffsets = nestLengths = null;
542 minStart = maxEnd = Integer.MAX_VALUE;
543 maxStart = Integer.MIN_VALUE;
547 * Compare an interval t to a from/to range for insertion purposes
552 * @return 0 if same, 1 if start is after from, or start equals from and
553 * [bigendian: end is before to | littleendian: end is after to], else
556 private int compareRange(IntervalI t, long from, long to)
558 int order = Long.signum(t.getBegin() - from);
560 ? Long.signum(bigendian ? to - t.getEnd() : t.getEnd() - to)
565 public boolean contains(Object entry)
567 if (entry == null || intervalCount == 0 && added == 0 && deleted == 0)
576 return (findInterval((IntervalI) entry, false) >= 0);
580 * Check to see if a given interval is within another.
588 public boolean containsInterval(IntervalI outer, IntervalI inner)
590 return false; // not applicable
594 * Ensure that all addition, deletion, and sorting has been done, and that the
595 * nesting arrays have been created so that we are ready for findOverlaps().
599 private void ensureFinalized()
604 added > 0 || deleted > 0)
608 if (intervalCount > 0)
617 * Find all overlaps within the given range, inclusively.
619 * @return a list sorted in ascending order of start position
623 public List<T> findOverlaps(long from, long to)
625 return findOverlaps(from, to, null);
629 * Find all overlaps within the given range, inclusively.
631 * @return a list sorted in the order provided by the features list comparator
635 @SuppressWarnings("unchecked")
637 public List<T> findOverlaps(long from, long to, List<T> result)
641 result = new ArrayList<>();
643 switch (intervalCount + added)
648 IntervalI sf = intervals[0];
649 if (sf.getBegin() <= to && sf.getEnd() >= from)
658 if (from > maxEnd || to < minStart)
664 if (nestLengths[unnested] > 0)
666 searchUnnested(from, to, (List<IntervalI>) result);
669 if (nestLengths[root] > 0)
671 search(nests, from, to, root, result);
677 * A simpler search, since we know we don't have any subintervals. Not
678 * necessary, actually.
687 private void searchUnnested(long from, long to, List<IntervalI> result)
689 int start = nestOffsets[unnested];
690 int end = start + nestLengths[unnested] - 1;
691 for (int pt = binarySearchFirstEndNotBefore(nests, from, start,
692 end); pt <= end; pt++)
694 IntervalI ival = nests[pt];
695 if (ival.getBegin() > to)
704 * The main search of the nests[] array's subarrays
712 @SuppressWarnings("unchecked")
713 private void search(IntervalI[] nests, long from, long to, int nest,
716 int start = nestOffsets[nest];
717 int n = nestLengths[nest];
718 int end = start + n - 1;
719 IntervalI first = nests[start];
720 IntervalI last = nests[end];
722 // quick tests for common cases:
724 if (last.getEnd() < from || first.getBegin() > to)
732 // just one interval and hasn't failed begin/end test
736 // just two and didn't fail begin/end test
737 // so there is only one option: either the first or the second is our
739 pt = (first.getEnd() >= from ? start : end);
742 // do the binary search
743 pt = binarySearchFirstEndNotBefore(nests, from, start, end);
746 for (; pt <= end; pt++)
748 IntervalI ival = nests[pt];
749 // check for out of range
750 if (ival.getBegin() > to)
754 result.add((T) ival);
755 if (nestLengths[pt] > 0)
757 // check subintervals in this nest
758 search(nests, from, to, pt, result);
764 * return the i-th interval in the designated order (bigendian or
767 public IntervalI get(int i)
769 if (i < 0 || i >= intervalCount + added)
778 * Return the deepest level of nesting.
782 public int getDepth()
785 BitSet bsTested = new BitSet();
786 return Math.max((createUnnested ? getDepth(unnested, bsTested) : 0),
787 getDepth(root, bsTested));
791 * Iteratively dive deeply.
797 private int getDepth(int pt, BitSet bsTested)
801 int n = nestLengths[pt];
802 if (n == 0 || bsTested.get(pt))
807 for (int st = nestOffsets[pt], i = st + n; --i >= st;)
809 if ((depth = getDepth(i, bsTested)) > maxDepth)
818 * Get the number of root-level nests.
821 public int getWidth()
824 return nestLengths[root] + (createUnnested ? nestLengths[unnested] : 0);
827 public boolean isValid()
834 * Answers an iterator over the intervals in the store, with no particular
835 * ordering guaranteed. The iterator does not support the optional
836 * <code>remove</code> operation (throws
837 * <code>UnsupportedOperationException</code> if attempted).
840 public Iterator<T> iterator()
843 return new Iterator<T>()
849 public boolean hasNext()
851 return next < intervalCount;
854 @SuppressWarnings("unchecked")
858 if (next >= intervalCount)
860 throw new NoSuchElementException();
862 return (T) intervals[next++];
869 * Indented printing of the intervals.
873 public String prettyPrint()
876 StringBuffer sb = new StringBuffer();
879 sb.append("unnested:");
880 dump(intervalCount + 1, sb, "\n");
881 sb.append("\nnested:");
883 dump(intervalCount, sb, "\n");
884 return sb.toString();
888 * Iterative nest dump.
894 private void dump(int nest, StringBuffer sb, String sep)
896 int pt = nestOffsets[nest];
897 int n = nestLengths[nest];
900 for (int i = 0; i < n; i++)
902 sb.append(sep).append(nests[pt + i].toString());
903 if (nestLengths[pt + i] > 0)
905 dump(pt + i, sb, sep + " ");
911 public synchronized boolean remove(Object o)
915 // throw new NullPointerException();
917 return (o != null && intervalCount > 0
918 && removeInterval((IntervalI) o));
922 * Find the interval or return where it should go, possibly into the add
927 * don't do a full identity check, just a range check
929 * @return index (nonnegative) or index where it would go (negative)
932 private int findInterval(IntervalI interval, boolean rangeOnly)
937 int pt = binaryIdentitySearch(interval, null, rangeOnly);
938 // if (addPt == intervalCount || offsets[pt] == 0)
940 if (pt >= 0 || added == 0 || pt == -1 - intervalCount)
945 int start = interval.getBegin();
946 int end = interval.getEnd();
950 while ((pt = offsets[pt]) != 0)
952 IntervalI iv = intervals[pt];
953 switch (compareRange(iv, start, end))
958 if (!rangeOnly && sameInterval(iv, interval))
972 // int i = intervalCount;
973 // while (--i >= 0 && !sameInterval(intervals[i], interval))
982 * Uses a binary search to find the entry and removes it if found.
987 protected boolean removeInterval(IntervalI interval)
995 int i = binaryIdentitySearch(interval, bsDeleted, false);
1002 if (bsDeleted == null)
1004 bsDeleted = new BitSet(intervalCount);
1013 return (isTainted = true);
1017 * Fill in the gaps of the intervals array after one or more deletions.
1020 private void finalizeDeletion()
1027 // ......xxx.....xxxx.....xxxxx....
1031 for (int i = bsDeleted.nextSetBit(0), pt = i; i >= 0;)
1033 i = bsDeleted.nextClearBit(i + 1);
1034 int pt1 = bsDeleted.nextSetBit(i + 1);
1037 pt1 = intervalCount;
1040 System.arraycopy(intervals, i, intervals, pt, n);
1042 if (pt1 == intervalCount)
1044 for (i = pt1; --i >= pt;)
1046 intervals[i] = null;
1048 intervalCount -= deleted;
1059 * Recreate the key nest arrays.
1062 public boolean revalidate()
1065 // isSorted = false;
1071 * Return the total number of intervals in the store.
1077 return intervalCount + added - deleted;
1081 * AbstractCollection override to ensure that we have finalized the store.
1084 public Object[] toArray()
1087 return super.toArray();
1091 * Sort intervals by start.
1097 intervals = finalizeAddition(new IntervalI[intervalCount + added]);
1099 else if (deleted > 0)
1105 // SOMETHING HAPPENS WHEN Arrays.sort is run that
1106 // adds 100 ms to a 150 ms run time.
1107 // I don't know why.
1108 Arrays.sort(intervals, 0, intervalCount, icompare);
1110 updateMinMaxStart();
1115 * Create the key arrays: nests, nestOffsets, and nestLengths. The starting
1116 * point is getting the container array, which may point to then root nest or
1119 * This is a pretty complicated method; it was way simpler before I decided to
1120 * support unnesting as an option.
1123 private void createArrays()
1126 // goal here is to create an array, nests[], that is a block
1129 * When unnesting, we need a second top-level listing.
1132 int len = intervalCount + (createUnnested ? 2 : 1);
1133 root = intervalCount;
1134 unnested = intervalCount + 1;
1137 * The three key arrays produced by this method:
1139 nests = new IntervalI[intervalCount];
1140 nestOffsets = new int[len];
1141 nestLengths = new int[len];
1144 * the objectives of Phase One
1147 int[] myContainer = new int[intervalCount];
1148 int[] counts = new int[len];
1150 // Phase One: Get the temporary container array myContainer.
1152 myContainer[0] = (createUnnested ? unnested : root);
1153 counts[myContainer[0]] = 1;
1155 // memories for previous begin and end
1157 int beginLast = intervals[0].getBegin();
1158 int endLast = intervals[0].getEnd();
1160 // memories for previous unnested pt, begin, and end
1162 int ptLastNot2 = root;
1163 int beginLast2 = beginLast;
1164 int endLast2 = endLast;
1166 for (int i = 1; i < intervalCount; i++)
1169 int begin = intervals[i].getBegin();
1170 int end = intervals[i].getEnd();
1172 // initialize the container to either root or unnested
1174 myContainer[i] = myContainer[0];
1176 // OK, now figure it all out...
1181 // Using a method isNested(...) here, because there are different
1182 // ways of defining "nested" when start or end are the
1183 // same. The definition used here would not be my first choice,
1184 // but it matches results for IntervalStoreJ
1185 // perfectly, down to the exact number of times that the
1186 // binary search runs through its start/mid/end loops in findOverlap.
1188 // beginLast2 and endLast2 refer to the last unnested level
1190 isNested = isNested(begin, end, beginLast2, endLast2);
1193 // this is tricky; making sure we properly get the
1194 // nests that are to be removed from the top-level
1195 // unnested list assigned a container root, while all
1196 // top-level nests get the pointer to unnested.
1199 isNested = (pt == root || isNested(begin, end,
1200 intervals[pt].getBegin(), intervals[pt].getEnd()));
1203 myContainer[i] = root;
1209 isNested = isNested(begin, end, beginLast, endLast);
1212 // ...almost done...
1216 myContainer[i] = pt;
1221 // monotonic -- find the parent that is doing the nesting
1223 while ((pt = myContainer[pt]) < root)
1225 if (isNested(begin, end, intervals[pt].getBegin(),
1226 intervals[pt].getEnd()))
1228 myContainer[i] = pt;
1229 // fully contained by a previous interval
1230 // System.out.println("mycontainer " + i + " = " + pt);
1236 // update the counts and pointers
1238 counts[myContainer[i]]++;
1239 if (myContainer[i] == unnested)
1252 // System.out.println("intervals " + Arrays.toString(intervals));
1253 // System.out.println("conts " + Arrays.toString(myContainer));
1254 // System.out.println("counts " + Arrays.toString(counts));
1256 // Phase Two: Construct the nests[] array and its associated
1257 // starting pointer array and nest element counts. These counts
1258 // are actually produced above, but we reconstruct it as a set
1259 // of dynamic pointers during construction.
1261 // The reason this is two phases is that only now do we know where to start
1262 // the nested set. If we did not unnest, we could do this all in one pass
1263 // using a reverse sort for the root, and then just reverse that, but with
1264 // unnesting, we have two unknown starts, and that doesn't give us that
1268 * this temporary array tracks the pointer within nestOffsets to the nest
1269 * block offset for intervals[i]'s container.
1271 int[] startPt = new int[len];
1273 startPt[root] = root;
1275 int nextStart = counts[root];
1279 nestOffsets[root] = counts[unnested];
1280 nextStart += counts[unnested];
1281 startPt[unnested] = unnested;
1284 // Now get all the pointers right and set the nests[] pointer into intervals
1287 for (int i = 0; i < intervalCount; i++)
1289 int ptOffset = startPt[myContainer[i]];
1290 int p = nestOffsets[ptOffset] + nestLengths[ptOffset]++;
1291 nests[p] = intervals[i];
1294 // this is a container
1296 nestOffsets[p] = nextStart;
1297 nextStart += counts[i];
1301 // System.out.println("intervals " + Arrays.toString(intervals));
1302 // System.out.println("nests " + Arrays.toString(nests));
1303 // System.out.println("conts " + Arrays.toString(myContainer));
1304 // System.out.println("offsets " + Arrays.toString(nestOffsets));
1305 // System.out.println("lengths " + Arrays.toString(nestLengths));
1306 // System.out.println(
1307 // "done " + nestLengths[root]
1308 // + (unnested > 0 ? " " + nestLengths[unnested] : ""));
1312 * Child-Parent relationships to match IntervalStoreJ. Perhaps a bit arcane?
1313 * Objective is to minimize the depth when we can.
1317 * @param parentStart
1321 private static boolean isNested(int childStart, int childEnd,
1322 int parentStart, int parentEnd)
1324 return (parentStart <= childStart && parentEnd > childEnd
1325 || parentStart < childStart && parentEnd == childEnd);
1329 * Just a couple of pointers to help speed findOverlaps along a bit.
1332 private void updateMinMaxStart()
1334 if (intervalCount > 0)
1336 minStart = intervals[0].getBegin();
1337 maxStart = intervals[intervalCount - 1].getBegin();
1341 minStart = Integer.MAX_VALUE;
1342 maxStart = Integer.MIN_VALUE;
1347 public String toString()
1349 return prettyPrint();
1353 * Tests for instance equality without using {@code instanceof}
1358 * @throws ClassCastException
1360 protected boolean sameInterval(IntervalI i1, IntervalI i2)
1362 return ((SequenceFeature) i1).equals((SequenceFeature) i2, false);