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
23 package org.hipparchus.stat.ranking;
24
25 import java.util.ArrayList;
26 import java.util.Arrays;
27 import java.util.Iterator;
28 import java.util.List;
29
30 import org.hipparchus.exception.LocalizedCoreFormats;
31 import org.hipparchus.exception.MathIllegalArgumentException;
32 import org.hipparchus.exception.MathRuntimeException;
33 import org.hipparchus.random.RandomDataGenerator;
34 import org.hipparchus.random.RandomGenerator;
35 import org.hipparchus.util.FastMath;
36
37
38 /**
39 * <p> Ranking based on the natural ordering on doubles.</p>
40 * <p>NaNs are treated according to the configured {@link NaNStrategy} and ties
41 * are handled using the selected {@link TiesStrategy}.
42 * Configuration settings are supplied in optional constructor arguments.
43 * Defaults are {@link NaNStrategy#FAILED} and {@link TiesStrategy#AVERAGE},
44 * respectively. When using {@link TiesStrategy#RANDOM}, a
45 * {@link RandomGenerator} may be supplied as a constructor argument.</p>
46 * <table border="1">
47 * <caption>Examples</caption>
48 * <tr><th colspan="3">
49 * Input data: (20, 17, 30, 42.3, 17, 50, Double.NaN, Double.NEGATIVE_INFINITY, 17)
50 * </th></tr>
51 * <tr><th>NaNStrategy</th><th>TiesStrategy</th>
52 * <th><code>rank(data)</code></th>
53 * <tr>
54 * <td>default (NaNs maximal)</td>
55 * <td>default (ties averaged)</td>
56 * <td>(5, 3, 6, 7, 3, 8, 9, 1, 3)</td></tr>
57 * <tr>
58 * <td>default (NaNs maximal)</td>
59 * <td>MINIMUM</td>
60 * <td>(5, 2, 6, 7, 2, 8, 9, 1, 2)</td></tr>
61 * <tr>
62 * <td>MINIMAL</td>
63 * <td>default (ties averaged)</td>
64 * <td>(6, 4, 7, 8, 4, 9, 1.5, 1.5, 4)</td></tr>
65 * <tr>
66 * <td>REMOVED</td>
67 * <td>SEQUENTIAL</td>
68 * <td>(5, 2, 6, 7, 3, 8, 1, 4)</td></tr>
69 * <tr>
70 * <td>MINIMAL</td>
71 * <td>MAXIMUM</td>
72 * <td>(6, 5, 7, 8, 5, 9, 2, 2, 5)</td></tr></table>
73 *
74 */
75 public class NaturalRanking implements RankingAlgorithm {
76
77 /** default NaN strategy */
78 public static final NaNStrategy DEFAULT_NAN_STRATEGY = NaNStrategy.FAILED;
79
80 /** default ties strategy */
81 public static final TiesStrategy DEFAULT_TIES_STRATEGY = TiesStrategy.AVERAGE;
82
83 /** NaN strategy - defaults to NaNs maximal */
84 private final NaNStrategy nanStrategy;
85
86 /** Ties strategy - defaults to ties averaged */
87 private final TiesStrategy tiesStrategy;
88
89 /** Source of random data - used only when ties strategy is RANDOM */
90 private final RandomDataGenerator randomData;
91
92 /**
93 * Create a NaturalRanking with default strategies for handling ties and NaNs.
94 */
95 public NaturalRanking() {
96 tiesStrategy = DEFAULT_TIES_STRATEGY;
97 nanStrategy = DEFAULT_NAN_STRATEGY;
98 randomData = null;
99 }
100
101 /**
102 * Create a NaturalRanking with the given TiesStrategy.
103 *
104 * @param tiesStrategy the TiesStrategy to use
105 */
106 public NaturalRanking(TiesStrategy tiesStrategy) {
107 this.tiesStrategy = tiesStrategy;
108 nanStrategy = DEFAULT_NAN_STRATEGY;
109 randomData = new RandomDataGenerator();
110 }
111
112 /**
113 * Create a NaturalRanking with the given NaNStrategy.
114 *
115 * @param nanStrategy the NaNStrategy to use
116 */
117 public NaturalRanking(NaNStrategy nanStrategy) {
118 this.nanStrategy = nanStrategy;
119 tiesStrategy = DEFAULT_TIES_STRATEGY;
120 randomData = null;
121 }
122
123 /**
124 * Create a NaturalRanking with the given NaNStrategy and TiesStrategy.
125 *
126 * @param nanStrategy NaNStrategy to use
127 * @param tiesStrategy TiesStrategy to use
128 */
129 public NaturalRanking(NaNStrategy nanStrategy, TiesStrategy tiesStrategy) {
130 this.nanStrategy = nanStrategy;
131 this.tiesStrategy = tiesStrategy;
132 randomData = new RandomDataGenerator();
133 }
134
135 /**
136 * Create a NaturalRanking with TiesStrategy.RANDOM and the given
137 * RandomGenerator as the source of random data.
138 *
139 * @param randomGenerator source of random data
140 */
141 public NaturalRanking(RandomGenerator randomGenerator) {
142 this.tiesStrategy = TiesStrategy.RANDOM;
143 nanStrategy = DEFAULT_NAN_STRATEGY;
144 randomData = RandomDataGenerator.of(randomGenerator);
145 }
146
147
148 /**
149 * Create a NaturalRanking with the given NaNStrategy, TiesStrategy.RANDOM
150 * and the given source of random data.
151 *
152 * @param nanStrategy NaNStrategy to use
153 * @param randomGenerator source of random data
154 */
155 public NaturalRanking(NaNStrategy nanStrategy,
156 RandomGenerator randomGenerator) {
157 this.nanStrategy = nanStrategy;
158 this.tiesStrategy = TiesStrategy.RANDOM;
159 randomData = RandomDataGenerator.of(randomGenerator);
160 }
161
162 /**
163 * Return the NaNStrategy
164 *
165 * @return returns the NaNStrategy
166 */
167 public NaNStrategy getNanStrategy() {
168 return nanStrategy;
169 }
170
171 /**
172 * Return the TiesStrategy
173 *
174 * @return the TiesStrategy
175 */
176 public TiesStrategy getTiesStrategy() {
177 return tiesStrategy;
178 }
179
180 /**
181 * Rank <code>data</code> using the natural ordering on Doubles, with
182 * NaN values handled according to <code>nanStrategy</code> and ties
183 * resolved using <code>tiesStrategy.</code>
184 *
185 * @param data array to be ranked
186 * @return array of ranks
187 * @throws MathIllegalArgumentException if the selected {@link NaNStrategy} is {@code FAILED}
188 * and a {@link Double#NaN} is encountered in the input data
189 */
190 @Override
191 public double[] rank(double[] data) {
192
193 // Array recording initial positions of data to be ranked
194 IntDoublePair[] ranks = new IntDoublePair[data.length];
195 for (int i = 0; i < data.length; i++) {
196 ranks[i] = new IntDoublePair(data[i], i);
197 }
198
199 // Recode, remove or record positions of NaNs
200 List<Integer> nanPositions = null;
201 switch (nanStrategy) {
202 case MAXIMAL: // Replace NaNs with +INFs
203 recodeNaNs(ranks, Double.POSITIVE_INFINITY);
204 break;
205 case MINIMAL: // Replace NaNs with -INFs
206 recodeNaNs(ranks, Double.NEGATIVE_INFINITY);
207 break;
208 case REMOVED: // Drop NaNs from data
209 ranks = removeNaNs(ranks);
210 break;
211 case FIXED: // Record positions of NaNs
212 nanPositions = getNanPositions(ranks);
213 break;
214 case FAILED:
215 nanPositions = getNanPositions(ranks);
216 if (!nanPositions.isEmpty()) {
217 throw new MathIllegalArgumentException(LocalizedCoreFormats.NAN_NOT_ALLOWED);
218 }
219 break;
220 default: // this should not happen unless NaNStrategy enum is changed
221 throw MathRuntimeException.createInternalError();
222 }
223
224 // Sort the IntDoublePairs
225 Arrays.sort(ranks, (p1, p2) -> Double.compare(p1.value, p2.value));
226
227 // Walk the sorted array, filling output array using sorted positions,
228 // resolving ties as we go
229 double[] out = new double[ranks.length];
230 int pos = 1; // position in sorted array
231 out[ranks[0].getPosition()] = pos;
232 List<Integer> tiesTrace = new ArrayList<>();
233 tiesTrace.add(ranks[0].getPosition());
234 for (int i = 1; i < ranks.length; i++) {
235 if (Double.compare(ranks[i].getValue(), ranks[i - 1].getValue()) > 0) {
236 // tie sequence has ended (or had length 1)
237 pos = i + 1;
238 if (tiesTrace.size() > 1) { // if seq is nontrivial, resolve
239 resolveTie(out, tiesTrace);
240 }
241 tiesTrace = new ArrayList<>();
242 tiesTrace.add(ranks[i].getPosition());
243 } else {
244 // tie sequence continues
245 tiesTrace.add(ranks[i].getPosition());
246 }
247 out[ranks[i].getPosition()] = pos;
248 }
249 if (tiesTrace.size() > 1) { // handle tie sequence at end
250 resolveTie(out, tiesTrace);
251 }
252 if (nanStrategy == NaNStrategy.FIXED) {
253 restoreNaNs(out, nanPositions);
254 }
255 return out;
256 }
257
258 /**
259 * Returns an array that is a copy of the input array with IntDoublePairs
260 * having NaN values removed.
261 *
262 * @param ranks input array
263 * @return array with NaN-valued entries removed
264 */
265 private IntDoublePair[] removeNaNs(IntDoublePair[] ranks) {
266 if (!containsNaNs(ranks)) {
267 return ranks;
268 }
269 IntDoublePair[] outRanks = new IntDoublePair[ranks.length];
270 int j = 0;
271 for (int i = 0; i < ranks.length; i++) {
272 if (Double.isNaN(ranks[i].getValue())) {
273 // drop, but adjust original ranks of later elements
274 for (int k = i + 1; k < ranks.length; k++) {
275 ranks[k] = new IntDoublePair(
276 ranks[k].getValue(), ranks[k].getPosition() - 1);
277 }
278 } else {
279 outRanks[j] = new IntDoublePair(
280 ranks[i].getValue(), ranks[i].getPosition());
281 j++;
282 }
283 }
284 IntDoublePair[] returnRanks = new IntDoublePair[j];
285 System.arraycopy(outRanks, 0, returnRanks, 0, j);
286 return returnRanks;
287 }
288
289 /**
290 * Recodes NaN values to the given value.
291 *
292 * @param ranks array to recode
293 * @param value the value to replace NaNs with
294 */
295 private void recodeNaNs(IntDoublePair[] ranks, double value) {
296 for (int i = 0; i < ranks.length; i++) {
297 if (Double.isNaN(ranks[i].getValue())) {
298 ranks[i] = new IntDoublePair(
299 value, ranks[i].getPosition());
300 }
301 }
302 }
303
304 /**
305 * Checks for presence of NaNs in <code>ranks.</code>
306 *
307 * @param ranks array to be searched for NaNs
308 * @return true iff ranks contains one or more NaNs
309 */
310 private boolean containsNaNs(IntDoublePair[] ranks) {
311 for (IntDoublePair rank : ranks) {
312 if (Double.isNaN(rank.getValue())) {
313 return true;
314 }
315 }
316 return false;
317 }
318
319 /**
320 * Resolve a sequence of ties, using the configured {@link TiesStrategy}.
321 * The input <code>ranks</code> array is expected to take the same value
322 * for all indices in <code>tiesTrace</code>. The common value is recoded
323 * according to the tiesStrategy. For example, if ranks = <5,8,2,6,2,7,1,2>,
324 * tiesTrace = <2,4,7> and tiesStrategy is MINIMUM, ranks will be unchanged.
325 * The same array and trace with tiesStrategy AVERAGE will come out
326 * <5,8,3,6,3,7,1,3>.
327 *
328 * @param ranks array of ranks
329 * @param tiesTrace list of indices where <code>ranks</code> is constant
330 * -- that is, for any i and j in TiesTrace, <code> ranks[i] == ranks[j]
331 * </code>
332 */
333 private void resolveTie(double[] ranks, List<Integer> tiesTrace) {
334
335 // constant value of ranks over tiesTrace
336 final double c = ranks[tiesTrace.get(0)];
337
338 // length of sequence of tied ranks
339 final int length = tiesTrace.size();
340
341 switch (tiesStrategy) {
342 case AVERAGE: // Replace ranks with average
343 fill(ranks, tiesTrace, (2 * c + length - 1) / 2d);
344 break;
345 case MAXIMUM: // Replace ranks with maximum values
346 fill(ranks, tiesTrace, c + length - 1);
347 break;
348 case MINIMUM: // Replace ties with minimum
349 fill(ranks, tiesTrace, c);
350 break;
351 case RANDOM: // Fill with random integral values in [c, c + length - 1]
352 Iterator<Integer> iterator = tiesTrace.iterator();
353 long f = FastMath.round(c);
354 while (iterator.hasNext()) {
355 // No advertised exception because args are guaranteed valid
356 ranks[iterator.next()] =
357 randomData.nextLong(f, f + length - 1);
358 }
359 break;
360 case SEQUENTIAL: // Fill sequentially from c to c + length - 1
361 // walk and fill
362 iterator = tiesTrace.iterator();
363 f = FastMath.round(c);
364 int i = 0;
365 while (iterator.hasNext()) {
366 ranks[iterator.next()] = f + i++;
367 }
368 break;
369 default: // this should not happen unless TiesStrategy enum is changed
370 throw MathRuntimeException.createInternalError();
371 }
372 }
373
374 /**
375 * Sets<code>data[i] = value</code> for each i in <code>tiesTrace.</code>
376 *
377 * @param data array to modify
378 * @param tiesTrace list of index values to set
379 * @param value value to set
380 */
381 private void fill(double[] data, List<Integer> tiesTrace, double value) {
382 for (Integer integer : tiesTrace) {
383 data[integer] = value;
384 }
385 }
386
387 /**
388 * Set <code>ranks[i] = Double.NaN</code> for each i in <code>nanPositions.</code>
389 *
390 * @param ranks array to modify
391 * @param nanPositions list of index values to set to <code>Double.NaN</code>
392 */
393 private void restoreNaNs(double[] ranks, List<Integer> nanPositions) {
394 if (nanPositions.isEmpty()) {
395 return;
396 }
397 for (Integer nanPosition : nanPositions) {
398 ranks[nanPosition] = Double.NaN;
399 }
400
401 }
402
403 /**
404 * Returns a list of indexes where <code>ranks</code> is <code>NaN.</code>
405 *
406 * @param ranks array to search for <code>NaNs</code>
407 * @return list of indexes i such that <code>ranks[i] = NaN</code>
408 */
409 private List<Integer> getNanPositions(IntDoublePair[] ranks) {
410 ArrayList<Integer> out = new ArrayList<>();
411 for (int i = 0; i < ranks.length; i++) {
412 if (Double.isNaN(ranks[i].getValue())) {
413 out.add(i);
414 }
415 }
416 return out;
417 }
418
419 /**
420 * Represents the position of a double value in an ordering.
421 */
422 private static class IntDoublePair {
423
424 /** Value of the pair */
425 private final double value;
426
427 /** Original position of the pair */
428 private final int position;
429
430 /**
431 * Construct an IntDoublePair with the given value and position.
432 * @param value the value of the pair
433 * @param position the original position
434 */
435 IntDoublePair(double value, int position) {
436 this.value = value;
437 this.position = position;
438 }
439
440 /**
441 * Returns the value of the pair.
442 * @return value
443 */
444 public double getValue() {
445 return value;
446 }
447
448 /**
449 * Returns the original position of the pair.
450 * @return position
451 */
452 public int getPosition() {
453 return position;
454 }
455 }
456 }