This is an automated email from the ASF dual-hosted git repository.
asf-gitbox-commits pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-numbers.git
The following commit(s) were added to refs/heads/master by this push:
new f971927c Partition KBM to return the exact pivot range
f971927c is described below
commit f971927cf4cceee33991f90ab188aa2caf27da99
Author: Alex Herbert <[email protected]>
AuthorDate: Thu Aug 27 18:44:37 2026 +0100
Partition KBM to return the exact pivot range
Returning [l, r] instead of [l, rr] where rr = r-1 creates a bug in
linearPartition when a sub-range of the array is partitioned for the
FLAG_MOVE_SAMPLE option, and a[r] > a[rr]. The bound p1 == r is
incorrect and a[p0] != a[p1] for some data.
---
.../numbers/examples/jmh/arrays/Partition.java | 8 ++++--
.../numbers/examples/jmh/arrays/PartitionTest.java | 32 +++++++++++++++++++++-
2 files changed, 36 insertions(+), 4 deletions(-)
diff --git
a/commons-numbers-examples/examples-jmh/src/main/java/org/apache/commons/numbers/examples/jmh/arrays/Partition.java
b/commons-numbers-examples/examples-jmh/src/main/java/org/apache/commons/numbers/examples/jmh/arrays/Partition.java
index ce748984..a927cb5f 100644
---
a/commons-numbers-examples/examples-jmh/src/main/java/org/apache/commons/numbers/examples/jmh/arrays/Partition.java
+++
b/commons-numbers-examples/examples-jmh/src/main/java/org/apache/commons/numbers/examples/jmh/arrays/Partition.java
@@ -7835,9 +7835,11 @@ final class Partition {
while (x[p + 1] == v) {
if (++p == rr) {
// Edge-case: constant value in [ll, rr]
- // Return the full range [l, r] as a single edge element
- // will also be partitioned.
- upper[0] = r;
+ // Note the full range [l, r] will also be partitioned
+ // as a[r] >= a[rr].
+ // Callers that have used part of the remaining array
+ // to find a pivot require [l, rr] not [l, r].
+ upper[0] = rr;
return l;
}
}
diff --git
a/commons-numbers-examples/examples-jmh/src/test/java/org/apache/commons/numbers/examples/jmh/arrays/PartitionTest.java
b/commons-numbers-examples/examples-jmh/src/test/java/org/apache/commons/numbers/examples/jmh/arrays/PartitionTest.java
index 23d94ede..b4ec887f 100644
---
a/commons-numbers-examples/examples-jmh/src/test/java/org/apache/commons/numbers/examples/jmh/arrays/PartitionTest.java
+++
b/commons-numbers-examples/examples-jmh/src/test/java/org/apache/commons/numbers/examples/jmh/arrays/PartitionTest.java
@@ -968,7 +968,7 @@ class PartitionTest {
}
@ParameterizedTest
- @MethodSource(value = {"testPartition"})
+ @MethodSource(value = {"testPartition", "testPartitionLSPMoveSample"})
void testPartitionLSPMoveSample(double[] values, int[] indices) {
Assumptions.assumeTrue(indices.length == 1 ||
(indices.length == 2 && Math.abs(indices[1] - indices[0]) < 10));
@@ -979,6 +979,36 @@ class PartitionTest {
::partitionLSP);
}
+ static Stream<Arguments> testPartitionLSPMoveSample() {
+ return Stream.of(
+ // Edge case that uncovered a bug in partitionKBM when upgrading
+ // Commons RNG 1.6 to 1.7.
+ Arguments.of(
+ new double[] {0.0, -0.0, -14.0, 11.0, 20.0, 0.0, 21.0, -21.0,
0.0, 22.0, 0.0, -0.0, 15.0, -0.0, -19.0,
+ 0.0, -22.0, 0.0, -18.0, 13.0, -0.0, -0.0, 0.0, 12.0, 16.0,
17.0, 19.0, 23.0, 0.0, 14.0, 0.0, -0.0,
+ 0.0, -13.0, -15.0, -23.0, -0.0, -0.0, -17.0, -0.0, -16.0,
-0.0, -20.0, -0.0, 0.0, 18.0, -0.0},
+ new int[] {37}));
+ }
+
+ /**
+ * Test partition KBM honours the contract to return the correct bounds
+ * of the pivot region [p0, p1] when the input array is a constant
+ * value with a single higher value at the end of the array.
+ * Returning the full range [l, r] is an optimisation if the method is
allowed
+ * to indicate the full range of partitioned data. It will cause a bug if
+ * downstream code requires p1 to define the end the the pivot region.
+ * This occurs in linearSelect when the {@link Partition#FLAG_MOVE_SAMPLE}
+ * option is enabled and KBM is used for the sub-partition.
+ */
+ @Test
+ void testPartitionKBM() {
+ final double[] a = {0, 0, 0, 0, 1};
+ final int bound[] = {0};
+ final double p0 = Partition.partitionKBM(a, 0, a.length - 1, 2, bound);
+ Assertions.assertEquals(p0, 0);
+ Assertions.assertEquals(bound[0], 3);
+ }
+
@ParameterizedTest
@MethodSource(value = {"testPartition"})
void testPartitionLinearBFPRTPER(double[] values, int[] indices) {
