+
+ /**
+ * Returns the maximal start-end positions in the given (ordered) list of
+ * ranges which is overlapped by the given begin-end range, or null if there
+ * is no overlap.
+ *
+ * <pre>
+ * Examples:
+ * if ranges is {[4, 8], [10, 12], [16, 19]}
+ * then
+ * findOverlap(ranges, 1, 20) == [4, 19]
+ * findOverlap(ranges, 6, 11) == [6, 11]
+ * findOverlap(ranges, 9, 15) == [10, 12]
+ * findOverlap(ranges, 13, 15) == null
+ * </pre>
+ *
+ * @param ranges
+ * @param begin
+ * @param end
+ * @return
+ */
+ protected static int[] findOverlap(List<int[]> ranges, final int begin,
+ final int end)
+ {
+ boolean foundStart = false;
+ int from = 0;
+ int to = 0;
+
+ /*
+ * traverse the ranges to find the first position (if any) >= begin,
+ * and the last position (if any) <= end
+ */
+ for (int[] range : ranges)
+ {
+ if (!foundStart)
+ {
+ if (range[0] >= begin)
+ {
+ /*
+ * first range that starts with, or follows, begin
+ */
+ foundStart = true;
+ from = Math.max(range[0], begin);
+ }
+ else if (range[1] >= begin)
+ {
+ /*
+ * first range that contains begin
+ */
+ foundStart = true;
+ from = begin;
+ }
+ }
+
+ if (range[0] <= end)
+ {
+ to = Math.min(end, range[1]);
+ }
+ }
+
+ return foundStart && to >= from ? new int[] { from, to } : null;
+ }