Fix KthSelector to consider natural order of doubles
Project: http://git-wip-us.apache.org/repos/asf/commons-math/repo Commit: http://git-wip-us.apache.org/repos/asf/commons-math/commit/81931848 Tree: http://git-wip-us.apache.org/repos/asf/commons-math/tree/81931848 Diff: http://git-wip-us.apache.org/repos/asf/commons-math/diff/81931848 Branch: refs/heads/develop Commit: 819318486d9cfb430749ee33d3c5c4ec4417babc Parents: 83b70a3 Author: Otmar Ertl <[email protected]> Authored: Fri Aug 5 17:03:09 2016 +0200 Committer: Emmanuel Bourg <[email protected]> Committed: Fri Aug 5 17:03:09 2016 +0200 ---------------------------------------------------------------------- .../apache/commons/math4/util/KthSelector.java | 6 +-- .../commons/math4/util/KthSelectorTest.java | 56 ++++++++++++++++++++ 2 files changed, 59 insertions(+), 3 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/commons-math/blob/81931848/src/main/java/org/apache/commons/math4/util/KthSelector.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math4/util/KthSelector.java b/src/main/java/org/apache/commons/math4/util/KthSelector.java index 9a71a2f..2820cbf 100644 --- a/src/main/java/org/apache/commons/math4/util/KthSelector.java +++ b/src/main/java/org/apache/commons/math4/util/KthSelector.java @@ -133,10 +133,10 @@ public class KthSelector implements Serializable { int i = begin + 1; int j = end - 1; while (i < j) { - while (i < j && work[j] > value) { + while (i < j && Double.compare(work[j], value) > 0) { --j; } - while (i < j && work[i] < value) { + while (i < j && Double.compare(work[i], value) < 0) { ++i; } @@ -147,7 +147,7 @@ public class KthSelector implements Serializable { } } - if (i >= end || work[i] > value) { + if (i >= end || Double.compare(work[i], value) > 0) { --i; } work[begin] = work[i]; http://git-wip-us.apache.org/repos/asf/commons-math/blob/81931848/src/test/java/org/apache/commons/math4/util/KthSelectorTest.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/commons/math4/util/KthSelectorTest.java b/src/test/java/org/apache/commons/math4/util/KthSelectorTest.java new file mode 100644 index 0000000..a366257 --- /dev/null +++ b/src/test/java/org/apache/commons/math4/util/KthSelectorTest.java @@ -0,0 +1,56 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math4.util; + +import static org.junit.Assert.assertEquals; + +import java.util.Arrays; +import java.util.Random; + +import org.junit.Test; + +public class KthSelectorTest { + + @Test + public void testRandom() { + + final int numIterations = 100000; + final double[] possibleValues = {Double.NaN, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, Double.MAX_VALUE, Double.MIN_VALUE, -10, -9, -8, -7, -6, -5, -4, -3, -2, -1, -0., 0., 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + final Random rnd = new Random(0); + for (int i = 0; i < numIterations; ++i) { + + final int dataSize = rnd.nextInt(30); + + final double[] data = new double[dataSize]; + + for (int j = 0; j < dataSize; ++j) { + data[j] = possibleValues[rnd.nextInt(possibleValues.length)]; + } + + final double[] dataSorted = Arrays.copyOf(data, data.length); + Arrays.sort(dataSorted); + + for (int j = 0; j < dataSize; ++j) { + + final double[] dataTmp = Arrays.copyOf(data, data.length); + final double resultKthSelector = new KthSelector().select(dataTmp, null, j); + final double resultSort = dataSorted[j]; + assertEquals(Double.doubleToLongBits(resultKthSelector), Double.doubleToLongBits(resultSort)); + } + } + } +}
