1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 package org.apache.commons.math4.legacy.stat.descriptive.rank; 18 19 import java.util.Arrays; 20 21 import org.apache.commons.math4.legacy.exception.NullArgumentException; 22 import org.apache.commons.math4.core.jdkmath.JdkMath; 23 24 /** 25 * A Simple K<sup>th</sup> selector implementation to pick up the 26 * K<sup>th</sup> ordered element from a work array containing the input 27 * numbers. 28 * @since 3.4 29 */ 30 public class KthSelector { 31 /** Minimum selection size for insertion sort rather than selection. */ 32 private static final int MIN_SELECT_SIZE = 15; 33 34 /** A {@link PivotingStrategy} used for pivoting. */ 35 private final PivotingStrategy pivotingStrategy; 36 37 /** 38 * Constructor with default {@link MedianOf3PivotingStrategy median of 3} pivoting strategy. 39 */ 40 public KthSelector() { 41 this.pivotingStrategy = new MedianOf3PivotingStrategy(); 42 } 43 44 /** 45 * Constructor with specified pivoting strategy. 46 * 47 * @param pivotingStrategy pivoting strategy to use 48 * @throws NullArgumentException when pivotingStrategy is null 49 * @see MedianOf3PivotingStrategy 50 * @see RandomPivotingStrategy 51 * @see CentralPivotingStrategy 52 */ 53 public KthSelector(final PivotingStrategy pivotingStrategy) { 54 NullArgumentException.check(pivotingStrategy); 55 this.pivotingStrategy = pivotingStrategy; 56 } 57 58 /** Get the pivoting strategy. 59 * @return pivoting strategy 60 */ 61 public PivotingStrategy getPivotingStrategy() { 62 return pivotingStrategy; 63 } 64 65 /** 66 * Select K<sup>th</sup> value in the array. 67 * 68 * @param work work array to use to find out the K<sup>th</sup> value 69 * @param pivotsHeap cached pivots heap that can be used for efficient estimation 70 * @param k the index whose value in the array is of interest 71 * @return K<sup>th</sup> value 72 */ 73 public double select(final double[] work, final int[] pivotsHeap, final int k) { 74 int begin = 0; 75 int end = work.length; 76 int node = 0; 77 final boolean usePivotsHeap = pivotsHeap != null; 78 while (end - begin > MIN_SELECT_SIZE) { 79 final int pivot; 80 81 if (usePivotsHeap && node < pivotsHeap.length && 82 pivotsHeap[node] >= 0) { 83 // the pivot has already been found in a previous call 84 // and the array has already been partitioned around it 85 pivot = pivotsHeap[node]; 86 } else { 87 // select a pivot and partition work array around it 88 pivot = partition(work, begin, end, pivotingStrategy.pivotIndex(work, begin, end)); 89 if (usePivotsHeap && node < pivotsHeap.length) { 90 pivotsHeap[node] = pivot; 91 } 92 } 93 94 if (k == pivot) { 95 // the pivot was exactly the element we wanted 96 return work[k]; 97 } else if (k < pivot) { 98 // the element is in the left partition 99 end = pivot; 100 node = JdkMath.min(2 * node + 1, usePivotsHeap ? pivotsHeap.length : end); 101 } else { 102 // the element is in the right partition 103 begin = pivot + 1; 104 node = JdkMath.min(2 * node + 2, usePivotsHeap ? pivotsHeap.length : end); 105 } 106 } 107 Arrays.sort(work, begin, end); 108 return work[k]; 109 } 110 111 /** 112 * Partition an array slice around a pivot.Partitioning exchanges array 113 * elements such that all elements smaller than pivot are before it and 114 * all elements larger than pivot are after it. 115 * 116 * @param work work array 117 * @param begin index of the first element of the slice of work array 118 * @param end index after the last element of the slice of work array 119 * @param pivot initial index of the pivot 120 * @return index of the pivot after partition 121 */ 122 private int partition(final double[] work, final int begin, final int end, final int pivot) { 123 124 final double value = work[pivot]; 125 work[pivot] = work[begin]; 126 127 int i = begin + 1; 128 int j = end - 1; 129 while (i < j) { 130 while (i < j && Double.compare(work[j], value) > 0) { 131 --j; 132 } 133 while (i < j && Double.compare(work[i], value) < 0) { 134 ++i; 135 } 136 137 if (i < j) { 138 final double tmp = work[i]; 139 work[i++] = work[j]; 140 work[j--] = tmp; 141 } 142 } 143 144 if (i >= end || Double.compare(work[i], value) > 0) { 145 --i; 146 } 147 work[begin] = work[i]; 148 work[i] = value; 149 return i; 150 } 151 }