1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 package org.apache.commons.math.stat.ranking;
19
20 import java.util.ArrayList;
21 import java.util.Arrays;
22 import java.util.Iterator;
23 import java.util.List;
24
25 import org.apache.commons.math.random.RandomData;
26 import org.apache.commons.math.random.RandomDataImpl;
27 import org.apache.commons.math.random.RandomGenerator;
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69 public class NaturalRanking implements RankingAlgorithm {
70
71
72 private final NaNStrategy nanStrategy;
73
74
75 private final TiesStrategy tiesStrategy;
76
77
78 private final RandomData randomData;
79
80
81 public static final NaNStrategy DEFAULT_NAN_STRATEGY = NaNStrategy.MAXIMAL;
82
83
84 public static final TiesStrategy DEFAULT_TIES_STRATEGY = TiesStrategy.AVERAGE;
85
86
87
88
89 public NaturalRanking() {
90 super();
91 tiesStrategy = DEFAULT_TIES_STRATEGY;
92 nanStrategy = DEFAULT_NAN_STRATEGY;
93 randomData = null;
94 }
95
96
97
98
99
100
101 public NaturalRanking(TiesStrategy tiesStrategy) {
102 super();
103 this.tiesStrategy = tiesStrategy;
104 nanStrategy = DEFAULT_NAN_STRATEGY;
105 randomData = new RandomDataImpl();
106 }
107
108
109
110
111
112
113 public NaturalRanking(NaNStrategy nanStrategy) {
114 super();
115 this.nanStrategy = nanStrategy;
116 tiesStrategy = DEFAULT_TIES_STRATEGY;
117 randomData = null;
118 }
119
120
121
122
123
124
125
126 public NaturalRanking(NaNStrategy nanStrategy, TiesStrategy tiesStrategy) {
127 super();
128 this.nanStrategy = nanStrategy;
129 this.tiesStrategy = tiesStrategy;
130 randomData = new RandomDataImpl();
131 }
132
133
134
135
136
137
138
139 public NaturalRanking(RandomGenerator randomGenerator) {
140 super();
141 this.tiesStrategy = TiesStrategy.RANDOM;
142 nanStrategy = DEFAULT_NAN_STRATEGY;
143 randomData = new RandomDataImpl(randomGenerator);
144 }
145
146
147
148
149
150
151
152
153
154 public NaturalRanking(NaNStrategy nanStrategy,
155 RandomGenerator randomGenerator) {
156 super();
157 this.nanStrategy = nanStrategy;
158 this.tiesStrategy = TiesStrategy.RANDOM;
159 randomData = new RandomDataImpl(randomGenerator);
160 }
161
162
163
164
165
166
167 public NaNStrategy getNanStrategy() {
168 return nanStrategy;
169 }
170
171
172
173
174
175
176 public TiesStrategy getTiesStrategy() {
177 return tiesStrategy;
178 }
179
180
181
182
183
184
185
186
187
188 public double[] rank(double[] data) {
189
190
191 IntDoublePair[] ranks = new IntDoublePair[data.length];
192 for (int i = 0; i < data.length; i++) {
193 ranks[i] = new IntDoublePair(data[i], i);
194 }
195
196
197 List<Integer> nanPositions = null;
198 switch (nanStrategy) {
199 case MAXIMAL:
200 recodeNaNs(ranks, Double.POSITIVE_INFINITY);
201 break;
202 case MINIMAL:
203 recodeNaNs(ranks, Double.NEGATIVE_INFINITY);
204 break;
205 case REMOVED:
206 ranks = removeNaNs(ranks);
207 break;
208 case FIXED:
209 nanPositions = getNanPositions(ranks);
210 break;
211 }
212
213
214 Arrays.sort(ranks);
215
216
217
218 double[] out = new double[ranks.length];
219 int pos = 1;
220 out[ranks[0].getPosition()] = pos;
221 List<Integer> tiesTrace = new ArrayList<Integer>();
222 tiesTrace.add(ranks[0].getPosition());
223 for (int i = 1; i < ranks.length; i++) {
224 if (Double.compare(ranks[i].getValue(), ranks[i - 1].getValue()) > 0) {
225
226 pos = i + 1;
227 if (tiesTrace.size() > 1) {
228 resolveTie(out, tiesTrace);
229 }
230 tiesTrace = new ArrayList<Integer>();
231 tiesTrace.add(ranks[i].getPosition());
232 } else {
233
234 tiesTrace.add(ranks[i].getPosition());
235 }
236 out[ranks[i].getPosition()] = pos;
237 }
238 if (tiesTrace.size() > 1) {
239 resolveTie(out, tiesTrace);
240 }
241 if (nanStrategy == NaNStrategy.FIXED) {
242 restoreNaNs(out, nanPositions);
243 }
244 return out;
245 }
246
247
248
249
250
251
252
253
254 private IntDoublePair[] removeNaNs(IntDoublePair[] ranks) {
255 if (!containsNaNs(ranks)) {
256 return ranks;
257 }
258 IntDoublePair[] outRanks = new IntDoublePair[ranks.length];
259 int j = 0;
260 for (int i = 0; i < ranks.length; i++) {
261 if (Double.isNaN(ranks[i].getValue())) {
262
263 for (int k = i + 1; k < ranks.length; k++) {
264 ranks[k] = new IntDoublePair(
265 ranks[k].getValue(), ranks[k].getPosition() - 1);
266 }
267 } else {
268 outRanks[j] = new IntDoublePair(
269 ranks[i].getValue(), ranks[i].getPosition());
270 j++;
271 }
272 }
273 IntDoublePair[] returnRanks = new IntDoublePair[j];
274 System.arraycopy(outRanks, 0, returnRanks, 0, j);
275 return returnRanks;
276 }
277
278
279
280
281
282
283
284 private void recodeNaNs(IntDoublePair[] ranks, double value) {
285 for (int i = 0; i < ranks.length; i++) {
286 if (Double.isNaN(ranks[i].getValue())) {
287 ranks[i] = new IntDoublePair(
288 value, ranks[i].getPosition());
289 }
290 }
291 }
292
293
294
295
296
297
298
299 private boolean containsNaNs(IntDoublePair[] ranks) {
300 for (int i = 0; i < ranks.length; i++) {
301 if (Double.isNaN(ranks[i].getValue())) {
302 return true;
303 }
304 }
305 return false;
306 }
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322 private void resolveTie(double[] ranks, List<Integer> tiesTrace) {
323
324
325 final double c = ranks[tiesTrace.get(0)];
326
327
328 final int length = tiesTrace.size();
329
330 switch (tiesStrategy) {
331 case AVERAGE:
332 fill(ranks, tiesTrace, (2 * c + length - 1) / 2d);
333 break;
334 case MAXIMUM:
335 fill(ranks, tiesTrace, c + length - 1);
336 break;
337 case MINIMUM:
338 fill(ranks, tiesTrace, c);
339 break;
340 case RANDOM:
341 Iterator<Integer> iterator = tiesTrace.iterator();
342 long f = Math.round(c);
343 while (iterator.hasNext()) {
344 ranks[iterator.next()] =
345 randomData.nextLong(f, f + length - 1);
346 }
347 break;
348 case SEQUENTIAL:
349
350 iterator = tiesTrace.iterator();
351 f = Math.round(c);
352 int i = 0;
353 while (iterator.hasNext()) {
354 ranks[iterator.next()] = f + i++;
355 }
356 break;
357 }
358 }
359
360
361
362
363
364
365
366
367 private void fill(double[] data, List<Integer> tiesTrace, double value) {
368 Iterator<Integer> iterator = tiesTrace.iterator();
369 while (iterator.hasNext()) {
370 data[iterator.next()] = value;
371 }
372 }
373
374
375
376
377
378
379
380 private void restoreNaNs(double[] ranks, List<Integer> nanPositions) {
381 if (nanPositions.size() == 0) {
382 return;
383 }
384 Iterator<Integer> iterator = nanPositions.iterator();
385 while (iterator.hasNext()) {
386 ranks[iterator.next().intValue()] = Double.NaN;
387 }
388
389 }
390
391
392
393
394
395
396
397 private List<Integer> getNanPositions(IntDoublePair[] ranks) {
398 ArrayList<Integer> out = new ArrayList<Integer>();
399 for (int i = 0; i < ranks.length; i++) {
400 if (Double.isNaN(ranks[i].getValue())) {
401 out.add(Integer.valueOf(i));
402 }
403 }
404 return out;
405 }
406
407
408
409
410
411
412
413 private static class IntDoublePair implements Comparable<IntDoublePair> {
414
415
416 final private double value;
417
418
419 final private int position;
420
421
422
423
424
425
426 public IntDoublePair(double value, int position) {
427 this.value = value;
428 this.position = position;
429 }
430
431
432
433
434
435
436
437
438 public int compareTo(IntDoublePair other) {
439 return Double.compare(value, other.value);
440 }
441
442
443
444
445
446 public double getValue() {
447 return value;
448 }
449
450
451
452
453
454 public int getPosition() {
455 return position;
456 }
457 }
458 }