View Javadoc
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    *      https://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  
18  /*
19   * This is not the original file distributed by the Apache Software Foundation
20   * It has been modified by the Hipparchus project
21   */
22  package org.hipparchus.util;
23  
24  import java.io.Serializable;
25  import java.util.Arrays;
26  
27  import org.hipparchus.exception.NullArgumentException;
28  
29  
30  /**
31   * A Simple K<sup>th</sup> selector implementation to pick up the
32   * K<sup>th</sup> ordered element from a work array containing the
33   * input numbers.
34   */
35  public class KthSelector implements Serializable {
36  
37      /** Serializable UID. */
38      private static final long serialVersionUID = 20140713L;
39  
40      /** Minimum selection size for insertion sort rather than selection. */
41      private static final int MIN_SELECT_SIZE = 15;
42  
43      /** A {@link PivotingStrategy} used for pivoting.  */
44      private final PivotingStrategy pivotingStrategy;
45  
46      /**
47       * Constructor with default {@link PivotingStrategy#MEDIAN_OF_3 median of 3}
48       * pivoting strategy.
49       */
50      public KthSelector() {
51          this.pivotingStrategy = PivotingStrategy.MEDIAN_OF_3;
52      }
53  
54      /**
55       * Constructor with specified pivoting strategy
56       *
57       * @param pivotingStrategy pivoting strategy to use
58       * @throws NullArgumentException when pivotingStrategy is null
59       */
60      public KthSelector(final PivotingStrategy pivotingStrategy)
61          throws NullArgumentException {
62          MathUtils.checkNotNull(pivotingStrategy);
63          this.pivotingStrategy = pivotingStrategy;
64      }
65  
66      /** Get the pivoting strategy.
67       * @return pivoting strategy
68       */
69      public PivotingStrategy getPivotingStrategy() {
70          return pivotingStrategy;
71      }
72  
73      /**
74       * Select K<sup>th</sup> value in the array.
75       *
76       * @param work work array to use to find out the K<sup>th</sup> value
77       * @param pivotsHeap cached pivots heap that can be used for efficient estimation
78       * @param k the index whose value in the array is of interest
79       * @return K<sup>th</sup> value
80       */
81      public double select(final double[] work, final int[] pivotsHeap, final int k) {
82          int begin = 0;
83          int end = work.length;
84          int node = 0;
85          final boolean usePivotsHeap = pivotsHeap != null;
86          while (end - begin > MIN_SELECT_SIZE) {
87              final int pivot;
88  
89              if (usePivotsHeap && node < pivotsHeap.length &&
90                      pivotsHeap[node] >= 0) {
91                  // the pivot has already been found in a previous call
92                  // and the array has already been partitioned around it
93                  pivot = pivotsHeap[node];
94              } else {
95                  // select a pivot and partition work array around it
96                  pivot = partition(work, begin, end, pivotingStrategy.pivotIndex(work, begin, end));
97                  if (usePivotsHeap && node < pivotsHeap.length) {
98                      pivotsHeap[node] = pivot;
99                  }
100             }
101 
102             if (k == pivot) {
103                 // the pivot was exactly the element we wanted
104                 return work[k];
105             } else if (k < pivot) {
106                 // the element is in the left partition
107                 end  = pivot;
108                 node = FastMath.min(2 * node + 1, usePivotsHeap ? pivotsHeap.length : end);
109             } else {
110                 // the element is in the right partition
111                 begin = pivot + 1;
112                 node  = FastMath.min(2 * node + 2, usePivotsHeap ? pivotsHeap.length : end);
113             }
114         }
115         Arrays.sort(work, begin, end);
116         return work[k];
117     }
118 
119     /**
120      * Partition an array slice around a pivot.Partitioning exchanges array
121      * elements such that all elements smaller than pivot are before it and
122      * all elements larger than pivot are after it.
123      *
124      * @param work work array
125      * @param begin index of the first element of the slice of work array
126      * @param end index after the last element of the slice of work array
127      * @param pivot initial index of the pivot
128      * @return index of the pivot after partition
129      */
130     private int partition(final double[] work, final int begin, final int end, final int pivot) {
131 
132         final double value = work[pivot];
133         work[pivot] = work[begin];
134 
135         int i = begin + 1;
136         int j = end - 1;
137         while (i < j) {
138             while (i < j && Double.compare(work[j], value) > 0) {
139                 --j;
140             }
141             while (i < j && Double.compare(work[i], value) < 0) {
142                 ++i;
143             }
144 
145             if (i < j) {
146                 final double tmp = work[i];
147                 work[i++] = work[j];
148                 work[j--] = tmp;
149             }
150         }
151 
152         if (i >= end || Double.compare(work[i], value) > 0) {
153             --i;
154         }
155         work[begin] = work[i];
156         work[i] = value;
157         return i;
158     }
159 }