Simplify WindowOperator.findEndPosition
@@ -474,51 +474,23 @@ public class WindowOperator
static int findEndPosition(int startPosition, int endPosition, BiPredicate<Integer, Integer> comparator)
{
checkArgument(startPosition >= 0, "startPosition must be greater or equal than zero: %s", startPosition);
- checkArgument(endPosition > 0, "endPosition must be greater than zero: %s", endPosition);
- checkArgument(startPosition < endPosition, "startPosition must be less than endPosition: %s < %s", startPosition, endPosition);
+ checkArgument(startPosition < endPosition, "startPosition (%s) must be less than endPosition (%s)", startPosition, endPosition);
int left = startPosition;
- int right = endPosition - 1;
- for (int i = 0; i < endPosition - startPosition; i++) {
- int distance = right - left;
+ int right = endPosition;
- if (distance == 0) {
- return right + 1;
- }
-
- if (distance == 1) {
- if (comparator.test(left, right)) {
- return right + 1;
- }
- return right;
- }
+ while (left + 1 < right) {
+ int middle = (left + right) >>> 1;
- int mid = left + distance / 2;
- if (comparator.test(left, mid)) {
- // explore to the right
- left = mid;
+ if (comparator.test(startPosition, middle)) {
+ left = middle;
}
else {
- // explore to the left
- right = mid;
+ right = middle;
}
}
- // 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)) {
- previousPairsWereEqual = false;
- }
- else if (!previousPairsWereEqual) {
- throw new IllegalArgumentException("The input is not sorted");
- }
- }
- }
-
- // the input is sorted, but the algorithm has still failed
- throw new IllegalArgumentException("failed to find a group ending");
+ return right;
}
@Override
