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  
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 }