You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@groovy.apache.org by pa...@apache.org on 2025/05/06 01:28:24 UTC
(groovy) 03/04: add partitionPoint to Groovy Array and List - refactor after 1st review, method name to binaryPartitionPoint
This is an automated email from the ASF dual-hosted git repository.
paulk pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/groovy.git
commit 3029622fd42d3dfaa5a5a8c1851e6ee9454f090c
Author: John Dong <do...@gmail.com>
AuthorDate: Sun May 4 15:40:03 2025 +0800
add partitionPoint to Groovy Array and List - refactor after 1st review, method name to binaryPartitionPoint
---
.../groovy/runtime/ArrayGroovyMethods.java | 311 +++++++++++----------
.../groovy/runtime/DefaultGroovyMethods.java | 49 ++--
2 files changed, 197 insertions(+), 163 deletions(-)
diff --git a/src/main/java/org/codehaus/groovy/runtime/ArrayGroovyMethods.java b/src/main/java/org/codehaus/groovy/runtime/ArrayGroovyMethods.java
index bba5dcd8c4..9a3bc29b1c 100644
--- a/src/main/java/org/codehaus/groovy/runtime/ArrayGroovyMethods.java
+++ b/src/main/java/org/codehaus/groovy/runtime/ArrayGroovyMethods.java
@@ -6580,41 +6580,44 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
}
//--------------------------------------------------------------------------
- // partition_point
+ // binaryPartitionPoint
/**
* Returns the index of the partition point according to the given predicate
* (the index of the first element of the second partition).
* The arr is assumed to be partitioned according to the given predicate.
* <pre class="groovyTestCase">
- * def arr = [7, 15, 3, 5, 4, 12, 6] as Integer[];
- * assert arr.partitionPoint(0..arr.size()) { it%2 != 0 } == 4
+ * def arr = [7, 15, 3, 5, 4, 12, 6] as Integer[]
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it%2 != 0 } == 4
* </pre>
*
* <pre class="groovyTestCase">
- * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as Integer[];
+ * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as Integer[]
* //usage case as lowerBound(cpp), bisect_left(python)
- * assert arr.partitionPoint(0..arr.size()) { it < 4 } == 4
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it < 4 } == 4
* //usage case as upperBound(cpp), bisect_right(python)
- * assert arr.partitionPoint(0..arr.size()) { it <= 4 } == 6
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 4 } == 6
* //for all match condition
- * assert arr.partitionPoint(0..arr.size()) { it <= 100 } == arr.size()
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 100 } == arr.size()
* //for none match condition
- * assert arr.partitionPoint(0..arr.size()) { it <= 0 } == 0
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 0 } == 0
* //for none match condition with range
- * assert arr.partitionPoint(2..arr.size()) { it <= 0 } == 2
+ * assert arr.binaryPartitionPoint(2..<arr.size()) { it <= 0 } == 2
* </pre>
*
* @param self a groovy arr
- * @param intRange the range [l,r) to find data match the condition
+ * @param intRange the range [l,r] to find data match the condition
* @param condition the matching condition
* @return an integer that is the index of the first element of the second partition
* @since 5.0
*/
- public static <T> int partitionPoint(T[] self, IntRange intRange, @ClosureParams(FirstParam.FirstGenericType.class) Closure<?> condition) {
+ public static <T> int binaryPartitionPoint(T[] self, IntRange intRange, @ClosureParams(FirstParam.FirstGenericType.class) Closure<?> condition) {
+ Objects.requireNonNull(self);
+ assert !intRange.isReverse();
+ Objects.checkFromToIndex(intRange.getFromInt(),intRange.getToInt(), self.length);
int result = intRange.getFromInt();
BooleanClosureWrapper bcw = new BooleanClosureWrapper(condition);
- int left = intRange.getFromInt(), right = intRange.getToInt() - 1;
+ int left = intRange.getFromInt(), right = intRange.getToInt();
while (left <= right) {
int mid = left + (right - left) / 2;
if (bcw.call(self[mid])) {
@@ -6632,20 +6635,20 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
* (the index of the first element of the second partition).
* The arr is assumed to be partitioned according to the given predicate.
* <pre class="groovyTestCase">
- * def arr = [7, 15, 3, 5, 4, 12, 6] as Integer[];
- * assert arr.partitionPoint{ it%2 != 0 } == 4
+ * def arr = [7, 15, 3, 5, 4, 12, 6] as Integer[]
+ * assert arr.binaryPartitionPoint{ it%2 != 0 } == 4
* </pre>
*
* <pre class="groovyTestCase">
- * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as Integer[];
+ * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as Integer[]
* //usage case as lowerBound(cpp), bisect_left(python)
- * assert arr.partitionPoint{ it < 4 } == 4
+ * assert arr.binaryPartitionPoint{ it < 4 } == 4
* //usage case as upperBound(cpp), bisect_right(python)
- * assert arr.partitionPoint{ it <= 4 } == 6
+ * assert arr.binaryPartitionPoint{ it <= 4 } == 6
* //for all match condition
- * assert arr.partitionPoint(0..arr.size()) { it <= 100 } == arr.size()
+ * assert arr.binaryPartitionPoint{ it <= 100 } == arr.size()
* //for none match condition
- * assert arr.partitionPoint(0..arr.size()) { it <= 0 } == 0
+ * assert arr.binaryPartitionPoint{ it <= 0 } == 0
* </pre>
*
* @param self a groovy arr
@@ -6653,8 +6656,8 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
* @return an integer that is the index of the first element of the second partition
* @since 5.0
*/
- public static <T> int partitionPoint(T[] self, @ClosureParams(FirstParam.FirstGenericType.class) Closure<?> condition) {
- return partitionPoint(self, new IntRange(0, self.length), condition);
+ public static <T> int binaryPartitionPoint(T[] self, @ClosureParams(FirstParam.FirstGenericType.class) Closure<?> condition) {
+ return binaryPartitionPoint(self, new IntRange(0, self.length - 1), condition);
}
/**
@@ -6662,33 +6665,37 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
* (the index of the first element of the second partition).
* The arr is assumed to be partitioned according to the given predicate.
* <pre class="groovyTestCase">
- * def arr = [7, 15, 3, 5, 4, 12, 6] as char[];
- * assert arr.partitionPoint(0..arr.size()) { it%2 != 0 } == 4
+ * def arr = [7, 15, 3, 5, 4, 12, 6] as char[]
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it%2 != 0 } == 4
* </pre>
*
* <pre class="groovyTestCase">
- * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as char[];
+ * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as char[]
* //usage case as lowerBound(cpp), bisect_left(python)
- * assert arr.partitionPoint(0..arr.size()) { it < 4 } == 4
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it < 4 } == 4
* //usage case as upperBound(cpp), bisect_right(python)
- * assert arr.partitionPoint(0..arr.size()) { it <= 4 } == 6
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 4 } == 6
* //for all match condition
- * assert arr.partitionPoint(0..arr.size()) { it <= 100 } == arr.size()
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 100 } == arr.size()
* //for none match condition
- * assert arr.partitionPoint(0..arr.size()) { it <= 0 } == 0
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 0 } == 0
* //for none match condition with range
- * assert arr.partitionPoint(2..arr.size()) { it <= 0 } == 2
+ * assert arr.binaryPartitionPoint(2..<arr.size()) { it <= 0 } == 2
* </pre>
*
* @param self a groovy arr
- * @param intRange the range [l,r) to find data match the condition
+ * @param intRange the range [l,r] to find data match the condition
* @param condition the matching condition
* @return an integer that is the index of the first element of the second partition
* @since 5.0
*/
- public static int partitionPoint(char[] self, IntRange intRange, IntPredicate condition) {
+ public static int binaryPartitionPoint(char[] self, IntRange intRange, IntPredicate condition) {
+ Objects.requireNonNull(self);
+ assert !intRange.isReverse();
+ Objects.checkFromToIndex(intRange.getFromInt(),intRange.getToInt(), self.length);
+
int result = intRange.getFromInt();
- int left = intRange.getFromInt(), right = intRange.getToInt() - 1;
+ int left = intRange.getFromInt(), right = intRange.getToInt();
while (left <= right) {
int mid = left + (right - left) / 2;
if (condition.test(self[mid])) {
@@ -6706,20 +6713,20 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
* (the index of the first element of the second partition).
* The arr is assumed to be partitioned according to the given predicate.
* <pre class="groovyTestCase">
- * def arr = [7, 15, 3, 5, 4, 12, 6] as char[];
- * assert arr.partitionPoint{ it%2 != 0 } == 4
+ * def arr = [7, 15, 3, 5, 4, 12, 6] as char[]
+ * assert arr.binaryPartitionPoint{ it%2 != 0 } == 4
* </pre>
*
* <pre class="groovyTestCase">
- * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as char[];
+ * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as char[]
* //usage case as lowerBound(cpp), bisect_left(python)
- * assert arr.partitionPoint{ it < 4 } == 4
+ * assert arr.binaryPartitionPoint{ it < 4 } == 4
* //usage case as upperBound(cpp), bisect_right(python)
- * assert arr.partitionPoint{ it <= 4 } == 6
+ * assert arr.binaryPartitionPoint{ it <= 4 } == 6
* //for all match condition
- * assert arr.partitionPoint{ it <= 100 } == arr.size()
+ * assert arr.binaryPartitionPoint{ it <= 100 } == arr.size()
* //for none match condition
- * assert arr.partitionPoint{ it <= 0 } == 0
+ * assert arr.binaryPartitionPoint{ it <= 0 } == 0
* </pre>
*
* @param self a groovy arr
@@ -6727,8 +6734,8 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
* @return an integer that is the index of the first element of the second partition
* @since 5.0
*/
- public static int partitionPoint(char[] self, IntPredicate condition) {
- return partitionPoint(self, new IntRange(0, self.length), condition);
+ public static int binaryPartitionPoint(char[] self, IntPredicate condition) {
+ return binaryPartitionPoint(self, new IntRange(0, self.length - 1), condition);
}
/**
@@ -6736,33 +6743,37 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
* (the index of the first element of the second partition).
* The arr is assumed to be partitioned according to the given predicate.
* <pre class="groovyTestCase">
- * def arr = [7, 15, 3, 5, 4, 12, 6] as short[];
- * assert arr.partitionPoint(0..arr.size()) { it%2 != 0 } == 4
+ * def arr = [7, 15, 3, 5, 4, 12, 6] as short[]
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it%2 != 0 } == 4
* </pre>
*
* <pre class="groovyTestCase">
- * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as short[];
+ * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as short[]
* //usage case as lowerBound(cpp), bisect_left(python)
- * assert arr.partitionPoint(0..arr.size()) { it < 4 } == 4
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it < 4 } == 4
* //usage case as upperBound(cpp), bisect_right(python)
- * assert arr.partitionPoint(0..arr.size()) { it <= 4 } == 6
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 4 } == 6
* //for all match condition
- * assert arr.partitionPoint(0..arr.size()) { it <= 100 } == arr.size()
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 100 } == arr.size()
* //for none match condition
- * assert arr.partitionPoint(0..arr.size()) { it <= 0 } == 0
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 0 } == 0
* //for none match condition with range
- * assert arr.partitionPoint(2..arr.size()) { it <= 0 } == 2
+ * assert arr.binaryPartitionPoint(2..<arr.size()) { it <= 0 } == 2
* </pre>
*
* @param self a groovy arr
- * @param intRange the range [l,r) to find data match the condition
+ * @param intRange the range [l,r] to find data match the condition
* @param condition the matching condition
* @return an integer that is the index of the first element of the second partition
* @since 5.0
*/
- public static int partitionPoint(short[] self, IntRange intRange, IntPredicate condition) {
+ public static int binaryPartitionPoint(short[] self, IntRange intRange, IntPredicate condition) {
+ Objects.requireNonNull(self);
+ assert !intRange.isReverse();
+ Objects.checkFromToIndex(intRange.getFromInt(),intRange.getToInt(), self.length);
+
int result = intRange.getFromInt();
- int left = intRange.getFromInt(), right = intRange.getToInt() - 1;
+ int left = intRange.getFromInt(), right = intRange.getToInt();
while (left <= right) {
int mid = left + (right - left) / 2;
if (condition.test(self[mid])) {
@@ -6780,20 +6791,20 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
* (the index of the first element of the second partition).
* The arr is assumed to be partitioned according to the given predicate.
* <pre class="groovyTestCase">
- * def arr = [7, 15, 3, 5, 4, 12, 6] as short[];
- * assert arr.partitionPoint{ it%2 != 0 } == 4
+ * def arr = [7, 15, 3, 5, 4, 12, 6] as short[]
+ * assert arr.binaryPartitionPoint{ it%2 != 0 } == 4
* </pre>
*
* <pre class="groovyTestCase">
- * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as short[];
+ * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as short[]
* //usage case as lowerBound(cpp), bisect_left(python)
- * assert arr.partitionPoint{ it < 4 } == 4
+ * assert arr.binaryPartitionPoint{ it < 4 } == 4
* //usage case as upperBound(cpp), bisect_right(python)
- * assert arr.partitionPoint{ it <= 4 } == 6
+ * assert arr.binaryPartitionPoint{ it <= 4 } == 6
* //for all match condition
- * assert arr.partitionPoint{ it <= 100 } == arr.size()
+ * assert arr.binaryPartitionPoint{ it <= 100 } == arr.size()
* //for none match condition
- * assert arr.partitionPoint{ it <= 0 } == 0
+ * assert arr.binaryPartitionPoint{ it <= 0 } == 0
* </pre>
*
* @param self a groovy arr
@@ -6801,8 +6812,8 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
* @return an integer that is the index of the first element of the second partition
* @since 5.0
*/
- public static int partitionPoint(short[] self, IntPredicate condition) {
- return partitionPoint(self, new IntRange(0, self.length), condition);
+ public static int binaryPartitionPoint(short[] self, IntPredicate condition) {
+ return binaryPartitionPoint(self, new IntRange(0, self.length - 1), condition);
}
/**
@@ -6810,33 +6821,37 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
* (the index of the first element of the second partition).
* The arr is assumed to be partitioned according to the given predicate.
* <pre class="groovyTestCase">
- * def arr = [7, 15, 3, 5, 4, 12, 6] as int[];
- * assert arr.partitionPoint(0..arr.size()) { it%2 != 0 } == 4
+ * def arr = [7, 15, 3, 5, 4, 12, 6] as int[]
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it%2 != 0 } == 4
* </pre>
*
* <pre class="groovyTestCase">
- * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as int[];
+ * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as int[]
* //usage case as lowerBound(cpp), bisect_left(python)
- * assert arr.partitionPoint(0..arr.size()) { it < 4 } == 4
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it < 4 } == 4
* //usage case as upperBound(cpp), bisect_right(python)
- * assert arr.partitionPoint(0..arr.size()) { it <= 4 } == 6
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 4 } == 6
* //for all match condition
- * assert arr.partitionPoint(0..arr.size()) { it <= 100 } == arr.size()
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 100 } == arr.size()
* //for all match condition
- * assert arr.partitionPoint(0..arr.size()) { it <= 0 } == 0
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 0 } == 0
* //for none match condition with range
- * assert arr.partitionPoint(2..arr.size()) { it <= 0 } == 2
+ * assert arr.binaryPartitionPoint(2..<arr.size()) { it <= 0 } == 2
* </pre>
*
* @param self a groovy arr
- * @param intRange the range [l,r) to find data match the condition
+ * @param intRange the range [l,r] to find data match the condition
* @param condition the matching condition
* @return an integer that is the index of the first element of the second partition
* @since 5.0
*/
- public static int partitionPoint(int[] self, IntRange intRange, IntPredicate condition) {
+ public static int binaryPartitionPoint(int[] self, IntRange intRange, IntPredicate condition) {
+ Objects.requireNonNull(self);
+ assert !intRange.isReverse();
+ Objects.checkFromToIndex(intRange.getFromInt(),intRange.getToInt(), self.length);
+
int result = intRange.getFromInt();
- int left = intRange.getFromInt(), right = intRange.getToInt() - 1;
+ int left = intRange.getFromInt(), right = intRange.getToInt();
while (left <= right) {
int mid = left + (right - left) / 2;
if (condition.test(self[mid])) {
@@ -6854,20 +6869,20 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
* (the index of the first element of the second partition).
* The arr is assumed to be partitioned according to the given predicate.
* <pre class="groovyTestCase">
- * def arr = [7, 15, 3, 5, 4, 12, 6] as int[];
- * assert arr.partitionPoint{ it%2 != 0 } == 4
+ * def arr = [7, 15, 3, 5, 4, 12, 6] as int[]
+ * assert arr.binaryPartitionPoint{ it%2 != 0 } == 4
* </pre>
*
* <pre class="groovyTestCase">
- * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as int[];
+ * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as int[]
* //usage case as lowerBound(cpp), bisect_left(python)
- * assert arr.partitionPoint{ it < 4 } == 4
+ * assert arr.binaryPartitionPoint{ it < 4 } == 4
* //usage case as upperBound(cpp), bisect_right(python)
- * assert arr.partitionPoint{ it <= 4 } == 6
+ * assert arr.binaryPartitionPoint{ it <= 4 } == 6
* //for all match condition
- * assert arr.partitionPoint{ it <= 100 } == arr.size()
+ * assert arr.binaryPartitionPoint{ it <= 100 } == arr.size()
* //for none match condition
- * assert arr.partitionPoint{ it <= 0 } == 0
+ * assert arr.binaryPartitionPoint{ it <= 0 } == 0
* </pre>
*
* @param self a groovy arr
@@ -6875,8 +6890,8 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
* @return an integer that is the index of the first element of the second partition
* @since 5.0
*/
- public static int partitionPoint(int[] self, IntPredicate condition) {
- return partitionPoint(self, new IntRange(0, self.length), condition);
+ public static int binaryPartitionPoint(int[] self, IntPredicate condition) {
+ return binaryPartitionPoint(self, new IntRange(0, self.length - 1), condition);
}
/**
@@ -6884,33 +6899,37 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
* (the index of the first element of the second partition).
* The arr is assumed to be partitioned according to the given predicate.
* <pre class="groovyTestCase">
- * def arr = [7, 15, 3, 5, 4, 12, 6] as long[];
- * assert arr.partitionPoint(0..arr.size()) { it%2 != 0 } == 4
+ * def arr = [7, 15, 3, 5, 4, 12, 6] as long[]
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it%2 != 0 } == 4
* </pre>
*
* <pre class="groovyTestCase">
- * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as long[];
+ * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as long[]
* //usage case as lowerBound(cpp), bisect_left(python)
- * assert arr.partitionPoint(0..arr.size()) { it < 4 } == 4
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it < 4 } == 4
* //usage case as upperBound(cpp), bisect_right(python)
- * assert arr.partitionPoint(0..arr.size()) { it <= 4 } == 6
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 4 } == 6
* //for all match condition
- * assert arr.partitionPoint(0..arr.size()) { it <= 100 } == arr.size()
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 100 } == arr.size()
* //for none match condition
- * assert arr.partitionPoint(0..arr.size()) { it <= 0 } == 0
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 0 } == 0
* //for none match condition with range
- * assert arr.partitionPoint(2..arr.size()) { it <= 0 } == 2
+ * assert arr.binaryPartitionPoint(2..<arr.size()) { it <= 0 } == 2
* </pre>
*
* @param self a groovy arr
- * @param intRange the range [l,r) to find data match the condition
+ * @param intRange the range [l,r] to find data match the condition
* @param condition the matching condition
* @return an integer that is the index of the first element of the second partition
* @since 5.0
*/
- public static int partitionPoint(long[] self, IntRange intRange, LongPredicate condition) {
+ public static int binaryPartitionPoint(long[] self, IntRange intRange, LongPredicate condition) {
+ Objects.requireNonNull(self);
+ assert !intRange.isReverse();
+ Objects.checkFromToIndex(intRange.getFromInt(),intRange.getToInt(), self.length);
+
int result = intRange.getFromInt();
- int left = intRange.getFromInt(), right = intRange.getToInt() - 1;
+ int left = intRange.getFromInt(), right = intRange.getToInt();
while (left <= right) {
int mid = left + (right - left) / 2;
if (condition.test(self[mid])) {
@@ -6928,20 +6947,20 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
* (the index of the first element of the second partition).
* The arr is assumed to be partitioned according to the given predicate.
* <pre class="groovyTestCase">
- * def arr = [7, 15, 3, 5, 4, 12, 6] as long[];
- * assert arr.partitionPoint{ it%2 != 0 } == 4
+ * def arr = [7, 15, 3, 5, 4, 12, 6] as long[]
+ * assert arr.binaryPartitionPoint{ it%2 != 0 } == 4
* </pre>
*
* <pre class="groovyTestCase">
- * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as long[];
+ * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as long[]
* //usage case as lowerBound(cpp), bisect_left(python)
- * assert arr.partitionPoint{ it < 4 } == 4
+ * assert arr.binaryPartitionPoint{ it < 4 } == 4
* //usage case as upperBound(cpp), bisect_right(python)
- * assert arr.partitionPoint{ it <= 4 } == 6
+ * assert arr.binaryPartitionPoint{ it <= 4 } == 6
* //for all match condition
- * assert arr.partitionPoint{ it <= 100 } == arr.size()
+ * assert arr.binaryPartitionPoint{ it <= 100 } == arr.size()
* //for none match condition
- * assert arr.partitionPoint{ it <= 0 } == 0
+ * assert arr.binaryPartitionPoint{ it <= 0 } == 0
* </pre>
*
* @param self a groovy arr
@@ -6949,8 +6968,8 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
* @return an integer that is the index of the first element of the second partition
* @since 5.0
*/
- public static int partitionPoint(long[] self, LongPredicate condition) {
- return partitionPoint(self, new IntRange(0, self.length), condition);
+ public static int binaryPartitionPoint(long[] self, LongPredicate condition) {
+ return binaryPartitionPoint(self, new IntRange(0, self.length - 1), condition);
}
/**
@@ -6958,33 +6977,37 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
* (the index of the first element of the second partition).
* The arr is assumed to be partitioned according to the given predicate.
* <pre class="groovyTestCase">
- * def arr = [7, 15, 3, 5, 4, 12, 6] as float[];
- * assert arr.partitionPoint(0..arr.size()) { it%2 != 0 } == 4
+ * def arr = [7, 15, 3, 5, 4, 12, 6] as float[]
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it%2 != 0 } == 4
* </pre>
*
* <pre class="groovyTestCase">
- * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as float[];
+ * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as float[]
* //usage case as lowerBound(cpp), bisect_left(python)
- * assert arr.partitionPoint(0..arr.size()) { it < 4 } == 4
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it < 4 } == 4
* //usage case as upperBound(cpp), bisect_right(python)
- * assert arr.partitionPoint(0..arr.size()) { it <= 4 } == 6
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 4 } == 6
* //for all match condition
- * assert arr.partitionPoint(0..arr.size()) { it <= 100 } == arr.size()
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 100 } == arr.size()
* //for none match condition
- * assert arr.partitionPoint(0..arr.size()) { it <= 0 } == 0
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 0 } == 0
* //for none match condition with range
- * assert arr.partitionPoint(2..arr.size()) { it <= 0 } == 2
+ * assert arr.binaryPartitionPoint(2..<arr.size()) { it <= 0 } == 2
* </pre>
*
* @param self a groovy arr
- * @param intRange the range [l,r) to find data match the condition
+ * @param intRange the range [l,r] to find data match the condition
* @param condition the matching condition
* @return an integer that is the index of the first element of the second partition
* @since 5.0
*/
- public static int partitionPoint(float[] self, IntRange intRange, DoublePredicate condition) {
+ public static int binaryPartitionPoint(float[] self, IntRange intRange, DoublePredicate condition) {
+ Objects.requireNonNull(self);
+ assert !intRange.isReverse();
+ Objects.checkFromToIndex(intRange.getFromInt(),intRange.getToInt(), self.length);
+
int result = intRange.getFromInt();
- int left = intRange.getFromInt(), right = intRange.getToInt() - 1;
+ int left = intRange.getFromInt(), right = intRange.getToInt();
while (left <= right) {
int mid = left + (right - left) / 2;
if (condition.test(self[mid])) {
@@ -7002,20 +7025,20 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
* (the index of the first element of the second partition).
* The arr is assumed to be partitioned according to the given predicate.
* <pre class="groovyTestCase">
- * def arr = [7, 15, 3, 5, 4, 12, 6] as float[];
- * assert arr.partitionPoint{ it%2 != 0 } == 4
+ * def arr = [7, 15, 3, 5, 4, 12, 6] as float[]
+ * assert arr.binaryPartitionPoint{ it%2 != 0 } == 4
* </pre>
*
* <pre class="groovyTestCase">
- * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as float[];
+ * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as float[]
* //usage case as lowerBound(cpp), bisect_left(python)
- * assert arr.partitionPoint{ it < 4 } == 4
+ * assert arr.binaryPartitionPoint{ it < 4 } == 4
* //usage case as upperBound(cpp), bisect_right(python)
- * assert arr.partitionPoint{ it <= 4 } == 6
+ * assert arr.binaryPartitionPoint{ it <= 4 } == 6
* //for all match condition
- * assert arr.partitionPoint{ it <= 100 } == arr.size()
+ * assert arr.binaryPartitionPoint{ it <= 100 } == arr.size()
* //for none match condition
- * assert arr.partitionPoint{ it <= 0 } == 0
+ * assert arr.binaryPartitionPoint{ it <= 0 } == 0
* </pre>
*
* @param self a groovy arr
@@ -7023,8 +7046,8 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
* @return an integer that is the index of the first element of the second partition
* @since 5.0
*/
- public static int partitionPoint(float[] self, DoublePredicate condition) {
- return partitionPoint(self, new IntRange(0, self.length), condition);
+ public static int binaryPartitionPoint(float[] self, DoublePredicate condition) {
+ return binaryPartitionPoint(self, new IntRange(0, self.length - 1), condition);
}
/**
@@ -7032,33 +7055,37 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
* (the index of the first element of the second partition).
* The arr is assumed to be partitioned according to the given predicate.
* <pre class="groovyTestCase">
- * def arr = [7, 15, 3, 5, 4, 12, 6] as double[];
- * assert arr.partitionPoint(0..arr.size()) { it%2 != 0 } == 4
+ * def arr = [7, 15, 3, 5, 4, 12, 6] as double[]
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it%2 != 0 } == 4
* </pre>
*
* <pre class="groovyTestCase">
- * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as double[];
+ * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as double[]
* //usage case as lowerBound(cpp), bisect_left(python)
- * assert arr.partitionPoint(0..arr.size()) { it < 4 } == 4
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it < 4 } == 4
* //usage case as upperBound(cpp), bisect_right(python)
- * assert arr.partitionPoint(0..arr.size()) { it <= 4 } == 6
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 4 } == 6
* //for all match condition
- * assert arr.partitionPoint(0..arr.size()) { it <= 100 } == arr.size()
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 100 } == arr.size()
* //for all match condition
- * assert arr.partitionPoint(0..arr.size()) { it <= 0 } == 0
+ * assert arr.binaryPartitionPoint(0..<arr.size()) { it <= 0 } == 0
* //for none match condition with range
- * assert arr.partitionPoint(2..arr.size()) { it <= 0 } == 2
+ * assert arr.binaryPartitionPoint(2..<arr.size()) { it <= 0 } == 2
* </pre>
*
- * @param self a groovy arr
- * @param intRange the range [l,r) to find data match the condition
+ * @param self a groovy array
+ * @param intRange the range [l,r] to find data match the condition
* @param condition the matching condition
* @return an integer that is the index of the first element of the second partition
* @since 5.0
*/
- public static int partitionPoint(double[] self, IntRange intRange, DoublePredicate condition) {
+ public static int binaryPartitionPoint(double[] self, IntRange intRange, DoublePredicate condition) {
+ Objects.requireNonNull(self);
+ assert !intRange.isReverse();
+ Objects.checkFromToIndex(intRange.getFromInt(),intRange.getToInt(), self.length);
+
int result = intRange.getFromInt();
- int left = intRange.getFromInt(), right = intRange.getToInt() - 1;
+ int left = intRange.getFromInt(), right = intRange.getToInt() ;
while (left <= right) {
int mid = left + (right - left) / 2;
if (condition.test(self[mid])) {
@@ -7076,20 +7103,20 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
* (the index of the first element of the second partition).
* The arr is assumed to be partitioned according to the given predicate.
* <pre class="groovyTestCase">
- * def arr = [7, 15, 3, 5, 4, 12, 6] as long[];
- * assert arr.partitionPoint{ it%2 != 0 } == 4
+ * def arr = [7, 15, 3, 5, 4, 12, 6] as double[]
+ * assert arr.binaryPartitionPoint{ it%2 != 0 } == 4
* </pre>
*
* <pre class="groovyTestCase">
- * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as long[];
+ * def arr = [1, 2, 3, 3, 4, 4, 5, 6, 7] as double[]
* //usage case as lowerBound(cpp), bisect_left(python)
- * assert arr.partitionPoint{ it < 4 } == 4
+ * assert arr.binaryPartitionPoint{ it < 4 } == 4
* //usage case as upperBound(cpp), bisect_right(python)
- * assert arr.partitionPoint{ it <= 4 } == 6
+ * assert arr.binaryPartitionPoint{ it <= 4 } == 6
* //for all match condition
- * assert arr.partitionPoint{ it <= 100 } == arr.size()
+ * assert arr.binaryPartitionPoint{ it <= 100 } == arr.size()
* //for none match condition
- * assert arr.partitionPoint{ it <= 0 } == 0
+ * assert arr.binaryPartitionPoint{ it <= 0 } == 0
* </pre>
*
* @param self a groovy arr
@@ -7097,8 +7124,8 @@ public class ArrayGroovyMethods extends DefaultGroovyMethodsSupport {
* @return an integer that is the index of the first element of the second partition
* @since 5.0
*/
- public static int partitionPoint(double[] self, DoublePredicate condition) {
- return partitionPoint(self, new IntRange(0, self.length), condition);
+ public static int binaryPartitionPoint(double[] self, DoublePredicate condition) {
+ return binaryPartitionPoint(self, new IntRange(0, self.length - 1), condition);
}
//--------------------------------------------------------------------------
diff --git a/src/main/java/org/codehaus/groovy/runtime/DefaultGroovyMethods.java b/src/main/java/org/codehaus/groovy/runtime/DefaultGroovyMethods.java
index 56dc038547..d5a988346b 100644
--- a/src/main/java/org/codehaus/groovy/runtime/DefaultGroovyMethods.java
+++ b/src/main/java/org/codehaus/groovy/runtime/DefaultGroovyMethods.java
@@ -132,6 +132,7 @@ import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
+import java.util.AbstractList;
import java.util.ListIterator;
import java.util.Map;
import java.util.NavigableMap;
@@ -11049,40 +11050,43 @@ public class DefaultGroovyMethods extends DefaultGroovyMethodsSupport {
}
//--------------------------------------------------------------------------
- // partition_point
+ // binaryPartitionPoint
/**
* Returns the index of the partition point according to the given predicate
* (the index of the first element of the second partition).
* The list is assumed to be partitioned according to the given predicate.
* <pre class="groovyTestCase">
- * def list = [7, 15, 3, 5, 4, 12, 6];
- * assert list.partitionPoint(0..list.size()) { it%2 != 0 } == 4
+ * def list = [7, 15, 3, 5, 4, 12, 6]
+ * assert list.binaryPartitionPoint(0..<list.size()) { it%2 != 0 } == 4
* </pre>
*
* <pre class="groovyTestCase">
- * def list = [1, 2, 3, 3, 4, 4, 5, 6, 7] as Integer[];
+ * def list = [1, 2, 3, 3, 4, 4, 5, 6, 7]
* //usage case as lowerBound(cpp), bisect_left(python)
- * assert list.partitionPoint(0..list.size()) { it < 4 } == 4
+ * assert list.binaryPartitionPoint(0..<list.size()) { it < 4 } == 4
* //usage case as upperBound(cpp), bisect_right(python)
- * assert list.partitionPoint(0..list.size()) { it <= 4 } == 6
+ * assert list.binaryPartitionPoint(0..<list.size()) { it <= 4 } == 6
* //for all match condition
- * assert list.partitionPoint(0..list.size()) { it <= 100 } == list.size()
+ * assert list.binaryPartitionPoint(0..<list.size()) { it <= 100 } == list.size()
* //for none match condition
- * assert list.partitionPoint(0..list.size()) { it <= 0 } == 0
+ * assert list.binaryPartitionPoint(0..<list.size()) { it <= 0 } == 0
* //for none match condition with range
- * assert list.partitionPoint(2..list.size()) { it <= 0 } == 2
+ * assert list.binaryPartitionPoint(2..<list.size()) { it <= 0 } == 2
* </pre>
*
* @param self a groovy list
- * @param intRange the range [l,r) to find data match the condition
+ * @param intRange the range [l,r] to find data match the condition
* @param condition the matching condition
* @return an integer that is the index of the first element of the second partition
* @since 5.0
*/
- public static <T> int partitionPoint(List<T> self, IntRange intRange, Predicate<T> condition) {
+ public static <T> int binaryPartitionPoint(AbstractList<T> self, IntRange intRange, Predicate<T> condition) {
+ Objects.requireNonNull(self);
+ assert !intRange.isReverse();
+ Objects.checkFromToIndex(intRange.getFromInt(),intRange.getToInt(), self.size());
int result = intRange.getFromInt();
- int left = intRange.getFromInt(), right = intRange.getToInt() - 1;
+ int left = intRange.getFromInt(), right = intRange.getToInt();
while (left <= right) {
int mid = left + (right - left) / 2;
if (condition.test(self.get(mid))) {
@@ -11100,20 +11104,23 @@ public class DefaultGroovyMethods extends DefaultGroovyMethodsSupport {
* (the index of the first element of the second partition).
* The list is assumed to be partitioned according to the given predicate.
* <pre class="groovyTestCase">
- * def list = [7, 15, 3, 5, 4, 12, 6];
- * assert list.partitionPoint{ it%2 != 0 } == 4
+ * def list = [7, 15, 3, 5, 4, 12, 6]
+ * assert list.binaryPartitionPoint{ it%2 != 0 } == 4
* </pre>
*
* <pre class="groovyTestCase">
- * def list = [1, 2, 3, 3, 4, 4, 5, 6, 7];
+ * def list = [1, 2, 3, 3, 4, 4, 5, 6, 7]
* //usage case as lowerBound(cpp), bisect_left(python)
- * assert list.partitionPoint{ it < 4 } == 4
+ * assert list.binaryPartitionPoint{ it < 4 } == 4
* //usage case as upperBound(cpp), bisect_right(python)
- * assert list.partitionPoint{ it <= 4 } == 6
+ * assert list.binaryPartitionPoint{ it <= 4 } == 6
* //for all match condition
- * assert list.partitionPoint{ it <= 100 } == list.size()
+ * assert list.binaryPartitionPoint{ it <= 100 } == list.size()
* //for none match condition
- * assert list.partitionPoint{ it <= 0 } == 0
+ * assert list.binaryPartitionPoint{ it <= 0 } == 0
+ * //reverse logic test:
+ * assert [7, 6, 5, 4, 4, 3, 3, 2, 1].binaryPartitionPoint{ it > 4 } == 3
+ * assert [7, 6, 5, 4, 4, 3, 3, 2, 1].binaryPartitionPoint{ it >= 4 } == 5
* </pre>
*
* @param self a groovy list
@@ -11121,8 +11128,8 @@ public class DefaultGroovyMethods extends DefaultGroovyMethodsSupport {
* @return an integer that is the index of the first element of the second partition
* @since 5.0
*/
- public static <T> int partitionPoint(List<T> self, Predicate<T> condition) {
- return partitionPoint(self, new IntRange(0, self.size()), condition);
+ public static <T> int binaryPartitionPoint(AbstractList<T> self, Predicate<T> condition) {
+ return binaryPartitionPoint(self, new IntRange(0, self.size() - 1), condition);
}
//--------------------------------------------------------------------------