kfaraz commented on code in PR #13369:
URL: https://github.com/apache/druid/pull/13369#discussion_r1034817428
##########
core/src/main/java/org/apache/druid/java/util/common/Intervals.java:
##########
@@ -68,6 +72,50 @@ public static boolean isEternity(final Interval interval)
return ETERNITY.equals(interval);
}
+ /**
+ * Finds an interval from the given set of sortedIntervals which overlaps
with
+ * the searchInterval. If multiple candidate intervals overlap with the
+ * searchInterval, the "smallest" interval based on the
+ * {@link Comparators#intervalsByStartThenEnd()} is returned.
+ *
+ * @param searchInterval Interval which should overlap with the result
+ * @param sortedIntervals Candidate overlapping intervals, sorted in
ascending
+ * order, using {@link
Comparators#intervalsByStartThenEnd()}.
+ * @return The first overlapping interval, if one exists, otherwise null.
+ */
+ @Nullable
+ public static Interval findOverlappingInterval(Interval searchInterval,
Interval[] sortedIntervals)
+ {
+ Arrays.sort(sortedIntervals, Comparators.intervalsByStartThenEnd());
+ int index = Arrays.binarySearch(
+ sortedIntervals,
+ searchInterval,
+ Comparators.intervalsByStartThenEnd()
+ );
+ if (index >= 0) {
+ return sortedIntervals[index];
+ }
+
+ // Key was not found, index returned from binarySearch is
(-(insertionPoint) - 1)
+ index = -(index + 1);
+
+ // If the interval at (index - 1) doesn't overlap, (index - 2) wouldn't
overlap either
Review Comment:
Simplified interval search. The binary search doesn't seem to have a
significant benefit in the avg case even with 100k search intervals and 100k
invocations of `findOverlappingInterval`. The method can be optimized in the
future if needed, seems overkill for now.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
