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.util;
018
019import java.io.Serializable;
020import java.util.Arrays;
021
022import org.apache.commons.math4.exception.NullArgumentException;
023
024
025/**
026 * A Simple K<sup>th</sup> selector implementation to pick up the
027 * K<sup>th</sup> ordered element from a work array containing the input
028 * numbers.
029 * @since 3.4
030 */
031public class KthSelector implements Serializable {
032
033    /** Serializable UID. */
034    private static final long serialVersionUID = 20140713L;
035
036    /** Minimum selection size for insertion sort rather than selection. */
037    private static final int MIN_SELECT_SIZE = 15;
038
039    /** A {@link PivotingStrategyInterface} used for pivoting  */
040    private final PivotingStrategyInterface pivotingStrategy;
041
042    /**
043     * Constructor with default {@link MedianOf3PivotingStrategy median of 3} pivoting strategy
044     */
045    public KthSelector() {
046        this.pivotingStrategy = new MedianOf3PivotingStrategy();
047    }
048
049    /**
050     * Constructor with specified pivoting strategy
051     *
052     * @param pivotingStrategy pivoting strategy to use
053     * @throws NullArgumentException when pivotingStrategy is null
054     * @see MedianOf3PivotingStrategy
055     * @see RandomPivotingStrategy
056     * @see CentralPivotingStrategy
057     */
058    public KthSelector(final PivotingStrategyInterface pivotingStrategy)
059        throws NullArgumentException {
060        MathUtils.checkNotNull(pivotingStrategy);
061        this.pivotingStrategy = pivotingStrategy;
062    }
063
064    /** Get the pivoting strategy.
065     * @return pivoting strategy
066     */
067    public PivotingStrategyInterface getPivotingStrategy() {
068        return pivotingStrategy;
069    }
070
071    /**
072     * Select K<sup>th</sup> value in the array.
073     *
074     * @param work work array to use to find out the K<sup>th</sup> value
075     * @param pivotsHeap cached pivots heap that can be used for efficient estimation
076     * @param k the index whose value in the array is of interest
077     * @return K<sup>th</sup> value
078     */
079    public double select(final double[] work, final int[] pivotsHeap, final int k) {
080        int begin = 0;
081        int end = work.length;
082        int node = 0;
083        final boolean usePivotsHeap = pivotsHeap != null;
084        while (end - begin > MIN_SELECT_SIZE) {
085            final int pivot;
086
087            if (usePivotsHeap && node < pivotsHeap.length &&
088                    pivotsHeap[node] >= 0) {
089                // the pivot has already been found in a previous call
090                // and the array has already been partitioned around it
091                pivot = pivotsHeap[node];
092            } else {
093                // select a pivot and partition work array around it
094                pivot = partition(work, begin, end, pivotingStrategy.pivotIndex(work, begin, end));
095                if (usePivotsHeap && node < pivotsHeap.length) {
096                    pivotsHeap[node] = pivot;
097                }
098            }
099
100            if (k == pivot) {
101                // the pivot was exactly the element we wanted
102                return work[k];
103            } else if (k < pivot) {
104                // the element is in the left partition
105                end  = pivot;
106                node = FastMath.min(2 * node + 1, usePivotsHeap ? pivotsHeap.length : end);
107            } else {
108                // the element is in the right partition
109                begin = pivot + 1;
110                node  = FastMath.min(2 * node + 2, usePivotsHeap ? pivotsHeap.length : end);
111            }
112        }
113        Arrays.sort(work, begin, end);
114        return work[k];
115    }
116
117    /**
118     * Partition an array slice around a pivot.Partitioning exchanges array
119     * elements such that all elements smaller than pivot are before it and
120     * all elements larger than pivot are after it.
121     *
122     * @param work work array
123     * @param begin index of the first element of the slice of work array
124     * @param end index after the last element of the slice of work array
125     * @param pivot initial index of the pivot
126     * @return index of the pivot after partition
127     */
128    private int partition(final double[] work, final int begin, final int end, final int pivot) {
129
130        final double value = work[pivot];
131        work[pivot] = work[begin];
132
133        int i = begin + 1;
134        int j = end - 1;
135        while (i < j) {
136            while (i < j && Double.compare(work[j], value) > 0) {
137                --j;
138            }
139            while (i < j && Double.compare(work[i], value) < 0) {
140                ++i;
141            }
142
143            if (i < j) {
144                final double tmp = work[i];
145                work[i++] = work[j];
146                work[j--] = tmp;
147            }
148        }
149
150        if (i >= end || Double.compare(work[i], value) > 0) {
151            --i;
152        }
153        work[begin] = work[i];
154        work[i] = value;
155        return i;
156    }
157}