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}