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 java.util.AbstractCollection;
35 import java.util.ArrayList;
36 import java.util.Arrays;
37 import java.util.BitSet;
38 import java.util.Collections;
39 import java.util.Comparator;
40 import java.util.Iterator;
41 import java.util.List;
42 import java.util.NoSuchElementException;
44 import intervalstore.api.IntervalI;
45 import intervalstore.api.IntervalStoreI;
49 * A fourth idea, implementing NCList as a pointer system identical in operation
50 * to IntervalStoreJ's implementation using ArrayLists but here using just two
51 * int[] arrays and a single IntervalI[] array that is in the proper order for
52 * holding all nested and unnested arrays.
54 * Use of unnesting is optional and can be experimented with by changing the
55 * createUnnested flag to false.
57 * Preliminary testing suggests that this implementation is about 10% faster for
58 * store interval size 50, store sequence factor 10, query width -1000 (fixed
59 * 1000-unit-wide window), and query count 100000.
61 * Origional note (Mungo Carstairs, IntervalStoreJ)
63 * A Collection class to store interval-associated data, with options for "lazy"
64 * sorting so as to speed incremental construction of the data prior to issuing
67 * Accepts duplicate entries but not null values.
71 * @author Bob Hanson 2019.09.01
74 * any type providing <code>getBegin()</code> and
75 * <code>getEnd()</code>, primarily
77 public class IntervalStore<T extends IntervalI>
78 extends AbstractCollection<T> implements IntervalStoreI<T>
82 * Search for the last interval that ends at or just after the specified
83 * position. In the situation that there are multiple intervals starting at
84 * pos, this method returns the first of those.
87 * the nest-ordered array from createArrays()
89 * the position at the start of the interval of interest
91 * the starting point for the subarray search
93 * the ending point for the subarray search
94 * @return index into the nests array or one greater than end if not found
96 public static int binarySearchFirstEndNotBefore(IntervalI[] nests, long from,
99 int matched = end + 1;
103 mid = (start + end) >>> 1;
104 if (nests[mid].getEnd() >= from)
118 * My preference is for a bigendian comparison, but you may differ.
120 private Comparator<? super IntervalI> icompare;
123 * bigendian is what NCList does; change icompare to switch to that
125 private boolean bigendian;
127 private final boolean DO_PRESORT;
129 private boolean isSorted;
131 private boolean createUnnested = true;
133 private int minStart = Integer.MAX_VALUE, maxStart = Integer.MIN_VALUE,
134 maxEnd = Integer.MAX_VALUE;
136 private boolean isTainted;
138 private int capacity = 8;
140 protected IntervalI[] intervals = new IntervalI[capacity];
142 private int[] offsets;
144 protected int intervalCount;
150 private BitSet bsDeleted;
153 * the key array that lists the intervals in sub-interval order so that the
154 * binary search can be isolated to a single subinterval just by indicating
155 * start and end within one array
157 private IntervalI[] nests;
160 * pointers to the starting positions in nests[] for a subinterval; the first
161 * element is the "unnested" pointer when unnesting (2) or the root level nest
162 * pointer when not unnesting (1); the second element is root level nest when
163 * unnesting or the start of nest data when not unnesting; after that, nests
164 * are in contiguous sets of binary-searchable blocks
167 private int[] nestStarts;
170 * the count of intervals within a nest
173 private int[] nestCounts;
175 public IntervalStore()
180 public IntervalStore(boolean presort)
186 * Constructor given a list of intervals. Note that the list may get sorted as
187 * a side-effect of calling this constructor.
189 public IntervalStore(List<T> intervals)
191 this(intervals, true);
195 * Allows a presort option, which can speed up initial loading of individual
196 * features but will delay the first findOverlap if set to true.
201 public IntervalStore(List<T> intervals, boolean presort)
203 // setting default to BIG_ENDIAN, meaning
204 // the order will be [10,100] before [10,80]
205 // this order doesn't really matter much.
206 this(intervals, presort, null, true);
212 * intervals to initialize with (others may still be added)
214 * whether or not to presort the list as additions are made
216 * IntervalI.COMPARATOR_LITTLEENDIAN or
217 * IntervalI.COMPARATOR_BIGENDIAN, but this could also be one that
218 * sorts by description as well, for example.
220 * true if the comparator sorts [10-100] before [10-80]; defaults to
223 public IntervalStore(List<T> intervals, boolean presort,
224 Comparator<? super IntervalI> comparator, boolean bigendian)
226 icompare = (comparator != null ? comparator
227 : bigendian ? IntervalI.COMPARATOR_BIGENDIAN
228 : IntervalI.COMPARATOR_LITTLEENDIAN);
229 this.bigendian = bigendian;
231 if (intervals != null)
233 // So, five hours later, we learn that all my timing has been thrown off
234 // because I used Array.sort, which if you look in the Java JDK is exactly
235 // what Collections.sort is, but for whatever reason, all my times were
236 // high by about 100-200 ms 100% reproducibly. Just one call to Array.sort
237 // prior to the nanotimer start messed it all up. Some sort of memory or
238 // garbage issue; I do not know. But using Collections.sort here fixes the
241 Collections.sort(intervals, icompare);
243 this.intervals = new IntervalI[capacity = intervalCount = intervals
246 DO_PRESORT = presort;
247 if (DO_PRESORT && intervalCount > 1)
256 isSorted = DO_PRESORT;
262 * Adds one interval to the store, allowing duplicates.
267 public boolean add(T interval)
269 return add(interval, true);
273 * Adds one interval to the store, optionally checking for duplicates.
275 * This fast-adding algorithm uses a double-length int[] (offsets) to hold
276 * pointers into intervals[] that allows continual sorting of an expanding
277 * array buffer. When the time comes, this is cleaned up and packed back into
278 * a standard array, but in the mean time, it can be added to with no loss of
282 * @param allowDuplicates
285 public boolean add(T interval, boolean allowDuplicates)
287 if (interval == null)
302 synchronized (intervals)
304 int index = intervalCount;
305 int start = interval.getBegin();
307 if (intervalCount + added + 1 >= capacity)
309 intervals = finalizeAddition(
310 new IntervalI[capacity = capacity << 1]);
314 if (DO_PRESORT && isSorted)
316 if (intervalCount == 0)
322 index = findInterval(interval);
323 // System.out.println("index = " + index + " for " + interval + "\n"
324 // + Arrays.toString(intervals) + "\n"
325 // + Arrays.toString(offsets));
326 if (!allowDuplicates && index >= 0)
343 if (!allowDuplicates && findInterval(interval) >= 0)
350 if (index == intervalCount)
352 intervals[intervalCount++] = interval;
353 // System.out.println("added " + intervalCount + " " + interval);
357 int pt = capacity - ++added;
358 intervals[pt] = interval;
359 // System.out.println("stashed " + pt + " " + interval + " for "
360 // + index + " " + intervals[index]);
363 offsets = new int[capacity];
366 offsets[pt] = offsets[index];
371 minStart = Math.min(minStart, start);
372 maxStart = Math.max(maxStart, start);
378 * Clean up the intervals array into a simple ordered array.
383 private IntervalI[] finalizeAddition(IntervalI[] dest)
391 if (intervalCount > 0 && dest != intervals)
393 System.arraycopy(intervals, 0, dest, 0, intervalCount);
395 capacity = dest.length;
398 // System.out.println("finalizing " + intervalCount + " " + added);
400 // array is [(intervalCount)...null...(added)]
402 int ntotal = intervalCount + added;
403 for (int ptShift = ntotal, pt = intervalCount; pt >= 0;)
406 while (--pt >= 0 && offsets[pt] == 0)
415 // shift upper intervals right
419 System.arraycopy(intervals, pt, dest, ptShift, nOK);
425 for (int offset = offsets[pt]; offset > 0; offset = offsets[offset])
427 dest[--ptShift] = intervals[offset];
432 intervalCount = ntotal;
433 capacity = dest.length;
434 // System.out.println(Arrays.toString(dest));
439 * A binary search for a duplicate.
444 public int binaryIdentitySearch(IntervalI interval)
446 return binaryIdentitySearch(interval, null);
450 * for remove() and contains()
456 * @return index or, if not found, -1 - "would be here"
458 public int binaryIdentitySearch(IntervalI interval, BitSet bsIgnore)
461 int r0 = interval.getBegin();
462 int r1 = interval.getEnd();
463 int end = intervalCount - 1;
464 if (end < 0 || r0 < minStart)
470 return -1 - intervalCount;
474 int mid = (start + end) >>> 1;
475 IntervalI r = intervals[mid];
476 switch (compareRange(r, r0, r1))
485 IntervalI iv = intervals[mid];
486 if ((bsIgnore == null || !bsIgnore.get(mid))
487 && iv.equalsInterval(interval))
490 // found one; just scan up and down now, first checking the range, but
491 // also checking other possible aspects of equivalence.
494 for (int i = mid; ++i <= end;)
496 if ((iv = intervals[i]).getBegin() != r0 || iv.getEnd() != r1)
500 if ((bsIgnore == null || !bsIgnore.get(i))
501 && iv.equalsInterval(interval))
506 for (int i = mid; --i >= start;)
508 if ((iv = intervals[i]).getBegin() != r0
509 || (bigendian ? r1 < iv.getEnd() : iv.getEnd() < r1))
513 if ((bsIgnore == null || !bsIgnore.get(i))
514 && iv.equalsInterval(interval))
526 public boolean canCheckForDuplicates()
538 intervalCount = added = 0;
542 intervals = new IntervalI[8];
543 nestStarts = nestCounts = null;
545 minStart = maxEnd = Integer.MAX_VALUE;
546 maxStart = Integer.MIN_VALUE;
550 * Compare an interval t to a from/to range for insertion purposes
555 * @return 0 if same, 1 if start is after from, or start equals from and
556 * [bigendian: end is before to | littleendian: end is after to], else
559 private int compareRange(IntervalI t, long from, long to)
561 int order = Long.signum(t.getBegin() - from);
563 ? Long.signum(bigendian ? to - t.getEnd() : t.getEnd() - to)
568 public boolean contains(Object entry)
570 if (entry == null || intervalCount == 0 && added == 0 && deleted == 0)
574 if (!isSorted || deleted > 0)
578 int n = findInterval((IntervalI) entry);
583 * Check to see if a given interval is within another.
591 public boolean containsInterval(IntervalI outer, IntervalI inner)
593 return false; // not applicable
597 * Ensure that all addition, deletion, and sorting has been done, and that the
598 * nesting arrays have been created so that we are ready for findOverlaps().
602 private void ensureFinalized()
606 if (!isSorted || added > 0 || deleted > 0)
610 if (intervalCount > 0)
619 * Find all overlaps within the given range, inclusively.
621 * @return a list sorted in ascending order of start position
625 public List<T> findOverlaps(long from, long to)
627 return findOverlaps(from, to, null);
631 * Find all overlaps within the given range, inclusively.
633 * @return a list sorted in the order provided by the features list comparator
637 @SuppressWarnings("unchecked")
639 public List<T> findOverlaps(long from, long to, List<T> result)
643 result = new ArrayList<>();
645 switch (intervalCount + added)
650 IntervalI sf = intervals[0];
651 if (sf.getBegin() <= to && sf.getEnd() >= from)
660 if (from > maxEnd || to < minStart)
667 if (nestCounts[0] > 0)
669 searchNonnested(nestCounts[0], nests, from, to,
670 (List<IntervalI>) result);
674 if (nestCounts[root] > 0)
676 search(nests, from, to, root, result);
682 * A simpler search, since we know we don't have any subintervals. Not
683 * necessary, actually.
692 private static void searchNonnested(int n,
693 IntervalI[] nests, long from, long to, List<IntervalI> result)
696 for (int pt = binarySearchFirstEndNotBefore(nests, from, 2,
697 end); pt <= end; pt++)
699 IntervalI ival = nests[pt];
700 if (ival.getBegin() > to)
709 * The main search of the nests[] array's subarrays
717 @SuppressWarnings("unchecked")
718 private void search(IntervalI[] nests, long from, long to, int nest,
721 int start = nestStarts[nest];
722 int n = nestCounts[nest];
723 int end = start + n - 1;
724 IntervalI first = nests[start];
725 IntervalI last = nests[end];
727 // quick tests for common cases:
729 if (last.getEnd() < from || first.getBegin() > to)
737 // just one interval and hasn't failed begin/end test
741 // just two and didn't fail begin/end test
742 // so there is only one option: either the first or the second is our
744 pt = (first.getEnd() >= from ? start : end);
747 // do the binary search
748 pt = binarySearchFirstEndNotBefore(nests, from, start, end);
751 for (; pt <= end; pt++)
753 IntervalI ival = nests[pt];
754 // check for out of range
755 if (ival.getBegin() > to)
759 result.add((T) ival);
760 if (nestCounts[pt] > 0)
762 // check subintervals in this nest
763 search(nests, from, to, pt, result);
769 * return the i-th interval in the designated order (bigendian or
773 public IntervalI get(int i)
775 if (i < 0 || i >= intervalCount + added)
784 * Return the deepest level of nesting.
788 public int getDepth()
791 BitSet bsTested = new BitSet();
792 return Math.max((createUnnested ? getDepth(1, bsTested) : 0),
793 getDepth(0, bsTested));
797 * Iteratively dive deeply.
803 private int getDepth(int pt, BitSet bsTested)
807 int n = nestCounts[pt];
808 if (n == 0 || bsTested.get(pt))
813 for (int st = nestStarts[pt], i = st + n; --i >= st;)
815 if ((depth = getDepth(i, bsTested)) > maxDepth)
824 * Get the number of root-level nests.
828 public int getWidth()
831 // System.out.println(
832 // "ISList w[0]=" + nestCounts[0] + " w[1]=" + nestCounts[1]);
833 return nestCounts[0] + (createUnnested ? nestCounts[1] : 0);
837 public boolean isValid()
844 * Answers an iterator over the intervals in the store, with no particular
845 * ordering guaranteed. The iterator does not support the optional
846 * <code>remove</code> operation (throws
847 * <code>UnsupportedOperationException</code> if attempted).
850 public Iterator<T> iterator()
853 return new Iterator<T>()
859 public boolean hasNext()
861 return next < intervalCount;
864 @SuppressWarnings("unchecked")
868 if (next >= intervalCount)
870 throw new NoSuchElementException();
872 return (T) intervals[next++];
879 * Indented printing of the intervals.
883 public String prettyPrint()
886 StringBuffer sb = new StringBuffer();
889 sb.append("unnested:");
891 sb.append("\nnested:");
898 return sb.toString();
902 * Iterative nest dump.
908 private void dump(int nest, StringBuffer sb, String sep)
910 int pt = nestStarts[nest];
911 int n = nestCounts[nest];
914 for (int i = 0; i < n; i++)
916 sb.append(sep).append(nests[pt + i].toString());
917 if (nestCounts[pt + i] > 0)
918 dump(pt + i, sb, sep + " ");
923 public synchronized boolean remove(Object o)
927 // throw new NullPointerException();
929 return (o != null && intervalCount > 0
930 && removeInterval((IntervalI) o));
934 * Find the interval or return where it should go, possibly into the add
938 * @return index (nonnegative) or index where it would go (negative)
941 private int findInterval(IntervalI interval)
946 int pt = binaryIdentitySearch(interval, null);
947 // if (addPt == intervalCount || offsets[pt] == 0)
949 if (pt >= 0 || added == 0 || pt == -1 - intervalCount)
954 int start = interval.getBegin();
955 int end = interval.getEnd();
959 while ((pt = offsets[pt]) != 0)
961 IntervalI iv = intervals[pt];
962 switch (compareRange(iv, start, end))
967 if (iv.equalsInterval(interval))
981 int i = intervalCount;
982 while (--i >= 0 && !intervals[i].equalsInterval(interval))
991 * Uses a binary search to find the entry and removes it if found.
996 protected boolean removeInterval(IntervalI interval)
999 if (!isSorted || added > 0)
1003 int i = binaryIdentitySearch(interval, bsDeleted);
1010 if (bsDeleted == null)
1012 bsDeleted = new BitSet(intervalCount);
1021 return (isTainted = true);
1025 * Fill in the gaps of the intervals array after one or more deletions.
1028 private void finalizeDeletion()
1035 // ......xxx.....xxxx.....xxxxx....
1039 for (int i = bsDeleted.nextSetBit(0), pt = i; i >= 0;)
1041 i = bsDeleted.nextClearBit(i + 1);
1042 int pt1 = bsDeleted.nextSetBit(i + 1);
1045 pt1 = intervalCount;
1048 System.arraycopy(intervals, i, intervals, pt, n);
1050 if (pt1 == intervalCount)
1052 for (i = pt1; --i >= pt;)
1054 intervals[i] = null;
1056 intervalCount -= deleted;
1067 * Recreate the key nest arrays.
1071 public boolean revalidate()
1080 * Return the total number of intervals in the store.
1086 return intervalCount + added - deleted;
1090 * AbstractCollection override to ensure that we have finalized the store.
1093 public Object[] toArray()
1096 return super.toArray();
1100 * Sort intervals by start.
1106 intervals = finalizeAddition(new IntervalI[intervalCount + added]);
1108 else if (deleted > 0)
1114 // SOMETHING HAPPENS WHEN Arrays.sort is run that
1115 // adds 100 ms to a 150 ms run time.
1116 // I don't know why.
1117 Arrays.sort(intervals, 0, intervalCount, icompare);
1119 updateMinMaxStart();
1138 // cont [-1, -1, -1, -1, 3, 4, 4, 4, 7, 7, 7, 10, -1, 12]
1139 // nests [0, 0, 1, 2, 3, 12, 4, 5, 6, 7, 8, 9, 10, 11, 13]
1140 // starts [1, 0, 0, 0, 6, 14, 7, 0, 0, 10, 0, 0, 13, 0, 0]
1141 // counts [5, 0, 0, 0, 1, 1, 3, 0, 0, 3, 0, 0, 1, 0, 0]
1144 * Create the key arrays: nests, nestStarts, and nestCounts. The starting
1145 * point is getting the container array, which may hold -1 (top level nesting)
1146 * and -2 (unnested set, if doing that).
1148 * This is a pretty complicated method; it was way simpler before I decided to
1149 * support nesting as an option.
1152 private void createArrays()
1156 * When unnesting, we need a second top-level listing.
1159 int incr = (createUnnested ? 2 : 1);
1162 * The three key arrays produced by this method:
1165 nests = new IntervalI[intervalCount + incr];
1166 nestStarts = new int[intervalCount + incr];
1167 nestCounts = new int[intervalCount + incr];
1170 * a temporary array used in Phase Two.
1173 int[] counts = new int[intervalCount + incr];
1176 * the objective of Phase One
1178 int[] myContainer = new int[intervalCount];
1180 myContainer[0] = -incr;
1182 int beginLast = intervals[0].getBegin();
1183 int endLast = intervals[0].getEnd();
1184 int ptLastNot2 = -1;
1185 int endLast2 = endLast;
1186 int beginLast2 = beginLast;
1188 // Phase One: Get the temporary container array myContainer.
1190 for (int i = 1; i < intervalCount; i++)
1193 int end = intervals[i].getEnd();
1194 int begin = intervals[i].getBegin();
1196 // set the pointer to the element that is containing
1197 // this interval, or -2 (unnested) or -1 (root-level nest)
1199 myContainer[i] = -incr;
1201 // OK, now figure it all out...
1206 // Using a method isNested(...) here, because there are different
1207 // ways of defining "nested" when start or end are the
1208 // same. The definition used here would not be my first choice,
1209 // but it matches results for IntervalStoreJ
1210 // perfectly, down to the exact number of times that the
1211 // binary search runs through its start/mid/end loops in findOverlap.
1213 // beginLast2 and endLast2 refer to the root-level or unnested level
1215 if (!isNested(begin, end, beginLast2, endLast2))
1221 // this is tricky; making sure we properly get the
1222 // nests that are to be removed from the top-level
1223 // unnested list assigned a container -1, while all
1224 // top-level nests get -2.
1227 isNested = (pt < 0 || isNested(begin, end,
1228 intervals[pt].getBegin(), intervals[pt].getEnd()));
1231 myContainer[i] = -1;
1237 isNested = isNested(begin, end, beginLast, endLast);
1240 // ...almost done...
1244 myContainer[i] = pt;
1249 // monotonic -- find the parent that is doing the nesting
1251 while ((pt = myContainer[pt]) >= 0)
1253 if (isNested(begin, end, intervals[pt].getBegin(),
1254 intervals[pt].getEnd()))
1256 myContainer[i] = pt;
1257 // fully contained by a previous interval
1258 // System.out.println("mycontainer " + i + " = " + pt);
1264 // update the counts and pointers
1266 counts[myContainer[i] + incr]++;
1267 if (myContainer[i] == -2)
1280 // Phase Two: construct the nests[] array and its associated
1281 // starting pointer array and nest element counts. These counts
1282 // are actually produced above, but we reconstruct it as a set
1283 // of dynamic pointers during construction.
1285 // incr is either 1 (no separate unnested set) or 2 (include unnested)
1287 int nextStart = counts[0] + incr;
1289 * this array tracks the pointer within nestStarts to the nest block start
1292 int[] startPt = new int[intervalCount + incr];
1293 nestStarts[0] = incr;
1295 // When not unnesting, nestStarts[0] = 1, and the length
1296 // will start out here as 0 but increment as we go.
1297 // We do this even though we know its size already, because that
1298 // value serves as a dynamic pointer as well.
1303 // Unnesting requires two separate lists with proper pointers and counts.
1304 // The first, nestStarts[0] = 0, is for the unnested set (container -2);
1305 // the second (container -1, nestStarts[1]) is for the nest root.
1308 nestStarts[1] = nextStart;
1309 nextStart += counts[1];
1312 // Now get all the pointers right and set the nests[] pointer into intervals
1315 for (int i = 0; i < intervalCount; i++)
1317 int n = counts[i + incr];
1318 int ptNest = startPt[myContainer[i] + incr];
1319 int p = nestStarts[ptNest] + nestCounts[ptNest]++;
1320 nests[p] = intervals[i];
1323 startPt[i + incr] = p;
1324 nestStarts[p] = nextStart;
1329 // System.out.println("intervals " + Arrays.toString(intervals));
1330 // System.out.println("nests " + Arrays.toString(nests));
1331 // System.out.println("conts " + Arrays.toString(myContainer));
1332 // System.out.println("starts " + Arrays.toString(nestStarts));
1333 // System.out.println("counts " + Arrays.toString(nestCounts));
1334 // System.out.println("done " + nestCounts[0]);
1338 * Child-Parent relationships to match IntervalStoreJ. Perhaps a bit arcane?
1339 * Objective is to minimize the depth when we can.
1343 * @param parentStart
1347 private static boolean isNested(int childStart, int childEnd,
1348 int parentStart, int parentEnd)
1350 return (parentStart <= childStart && parentEnd > childEnd
1351 || parentStart < childStart && parentEnd == childEnd);
1355 * Just a couple of pointers to help speed findOverlaps along a bit.
1358 private void updateMinMaxStart()
1360 if (intervalCount > 0)
1362 minStart = intervals[0].getBegin();
1363 maxStart = intervals[intervalCount - 1].getBegin();
1367 minStart = Integer.MAX_VALUE;
1368 maxStart = Integer.MIN_VALUE;
1373 public String toString()
1375 return prettyPrint();