Perform positional bisect in findEndPosition instead of linear scan
@@ -484,12 +484,47 @@ public class WindowOperator
checkArgument(endPosition > 0, "endPosition must be greater than zero: %s", endPosition);
checkArgument(startPosition < endPosition, "startPosition must be less than endPosition: %s < %s", startPosition, endPosition);
- // TODO: do position binary search
- for (int first = startPosition, second = startPosition + 1; second < endPosition; first++, second++) {
+ int left = startPosition;
+ int right = endPosition - 1;
+ for (int i = 0; i < endPosition - startPosition; i++) {
+ int distance = right - left;
+
+ if (distance == 0) {
+ return right + 1;
+ }
+
+ if (distance == 1) {
+ if (comparator.test(left, right)) {
+ return right + 1;
+ }
+ return right;
+ }
+
+ int mid = left + distance / 2;
+ if (comparator.test(left, mid)) {
+ // explore to the right
+ left = mid;
+ }
+ else {
+ // explore to the left
+ right = mid;
+ }
+ }
+
+ // hasn't managed to find a solution after N iteration. Probably the input is not sorted. Lets verify it.
+ for (int first = startPosition; first < endPosition; first++) {
+ boolean previousPairsWereEqual = true;
+ for (int second = first + 1; second < endPosition; second++) {
if (!comparator.test(first, second)) {
- return second;
+ previousPairsWereEqual = false;
}
+ else if (!previousPairsWereEqual) {
+ throw new IllegalArgumentException("The input is not sorted");
}
- return endPosition;
+ }
+ }
+
+ // the input is sorted, but the algorithm has still failed
+ throw new IllegalArgumentException("failed to find a group ending");
}
}
