001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.commons.math4.legacy.stat.descriptive.rank; 018 019import java.util.Arrays; 020 021import org.apache.commons.math4.legacy.exception.NullArgumentException; 022import org.apache.commons.math4.core.jdkmath.JdkMath; 023 024/** 025 * A Simple K<sup>th</sup> selector implementation to pick up the 026 * K<sup>th</sup> ordered element from a work array containing the input 027 * numbers. 028 * @since 3.4 029 */ 030public class KthSelector { 031 /** Minimum selection size for insertion sort rather than selection. */ 032 private static final int MIN_SELECT_SIZE = 15; 033 034 /** A {@link PivotingStrategy} used for pivoting. */ 035 private final PivotingStrategy pivotingStrategy; 036 037 /** 038 * Constructor with default {@link MedianOf3PivotingStrategy median of 3} pivoting strategy. 039 */ 040 public KthSelector() { 041 this.pivotingStrategy = new MedianOf3PivotingStrategy(); 042 } 043 044 /** 045 * Constructor with specified pivoting strategy. 046 * 047 * @param pivotingStrategy pivoting strategy to use 048 * @throws NullArgumentException when pivotingStrategy is null 049 * @see MedianOf3PivotingStrategy 050 * @see RandomPivotingStrategy 051 * @see CentralPivotingStrategy 052 */ 053 public KthSelector(final PivotingStrategy pivotingStrategy) { 054 NullArgumentException.check(pivotingStrategy); 055 this.pivotingStrategy = pivotingStrategy; 056 } 057 058 /** Get the pivoting strategy. 059 * @return pivoting strategy 060 */ 061 public PivotingStrategy getPivotingStrategy() { 062 return pivotingStrategy; 063 } 064 065 /** 066 * Select K<sup>th</sup> value in the array. 067 * 068 * @param work work array to use to find out the K<sup>th</sup> value 069 * @param pivotsHeap cached pivots heap that can be used for efficient estimation 070 * @param k the index whose value in the array is of interest 071 * @return K<sup>th</sup> value 072 */ 073 public double select(final double[] work, final int[] pivotsHeap, final int k) { 074 int begin = 0; 075 int end = work.length; 076 int node = 0; 077 final boolean usePivotsHeap = pivotsHeap != null; 078 while (end - begin > MIN_SELECT_SIZE) { 079 final int pivot; 080 081 if (usePivotsHeap && node < pivotsHeap.length && 082 pivotsHeap[node] >= 0) { 083 // the pivot has already been found in a previous call 084 // and the array has already been partitioned around it 085 pivot = pivotsHeap[node]; 086 } else { 087 // select a pivot and partition work array around it 088 pivot = partition(work, begin, end, pivotingStrategy.pivotIndex(work, begin, end)); 089 if (usePivotsHeap && node < pivotsHeap.length) { 090 pivotsHeap[node] = pivot; 091 } 092 } 093 094 if (k == pivot) { 095 // the pivot was exactly the element we wanted 096 return work[k]; 097 } else if (k < pivot) { 098 // the element is in the left partition 099 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}