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 }