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 <[email protected]> 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); } //--------------------------------------------------------------------------
