    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     */
    017
    018    package org.apache.commons.math.stat.ranking;
    019
    020    import java.util.ArrayList;
    021    import java.util.Arrays;
    022    import java.util.Iterator;
    023    import java.util.List;
    024
    025    import org.apache.commons.math.exception.MathInternalError;
    026    import org.apache.commons.math.random.RandomData;
    027    import org.apache.commons.math.random.RandomDataImpl;
    028    import org.apache.commons.math.random.RandomGenerator;
    029    import org.apache.commons.math.util.FastMath;
    030
    031
    032    /**
    033     * <p> Ranking based on the natural ordering on doubles.</p>
    034     * <p>NaNs are treated according to the configured {@link NaNStrategy} and ties
    035     * are handled using the selected {@link TiesStrategy}.
    036     * Configuration settings are supplied in optional constructor arguments.
    037     * Defaults are {@link NaNStrategy#MAXIMAL} and {@link TiesStrategy#AVERAGE},
    038     * respectively. When using {@link TiesStrategy#RANDOM}, a
    039     * {@link RandomGenerator} may be supplied as a constructor argument.</p>
    040     * <p>Examples:
    041     * <table border="1" cellpadding="3">
    042     * <tr><th colspan="3">
    043     * Input data: (20, 17, 30, 42.3, 17, 50, Double.NaN, Double.NEGATIVE_INFINITY, 17)
    044     * </th></tr>
    045     * <tr><th>NaNStrategy</th><th>TiesStrategy</th>
    046     * <th><code>rank(data)</code></th>
    047     * <tr>
    048     * <td>default (NaNs maximal)</td>
    049     * <td>default (ties averaged)</td>
    050     * <td>(5, 3, 6, 7, 3, 8, 9, 1, 3)</td></tr>
    051     * <tr>
    052     * <td>default (NaNs maximal)</td>
    053     * <td>MINIMUM</td>
    054     * <td>(5, 2, 6, 7, 2, 8, 9, 1, 2)</td></tr>
    055     * <tr>
    056     * <td>MINIMAL</td>
    057     * <td>default (ties averaged)</td>
    058     * <td>(6, 4, 7, 8, 4, 9, 1.5, 1.5, 4)</td></tr>
    059     * <tr>
    060     * <td>REMOVED</td>
    061     * <td>SEQUENTIAL</td>
    062     * <td>(5, 2, 6, 7, 3, 8, 1, 4)</td></tr>
    063     * <tr>
    064     * <td>MINIMAL</td>
    065     * <td>MAXIMUM</td>
    066     * <td>(6, 5, 7, 8, 5, 9, 2, 2, 5)</td></tr></table></p>
    067     *
    068     * @since 2.0
    069     * @version $Revision: 1061496 $ $Date: 2011-01-20 21:32:16 +0100 (jeu. 20 janv. 2011) $
    070     */
    071    public class NaturalRanking implements RankingAlgorithm {
    072
    073        /** default NaN strategy */
    074        public static final NaNStrategy DEFAULT_NAN_STRATEGY = NaNStrategy.MAXIMAL;
    075
    076        /** default ties strategy */
    077        public static final TiesStrategy DEFAULT_TIES_STRATEGY = TiesStrategy.AVERAGE;
    078
    079        /** NaN strategy - defaults to NaNs maximal */
    080        private final NaNStrategy nanStrategy;
    081
    082        /** Ties strategy - defaults to ties averaged */
    083        private final TiesStrategy tiesStrategy;
    084
    085        /** Source of random data - used only when ties strategy is RANDOM */
    086        private final RandomData randomData;
    087
    088        /**
    089         * Create a NaturalRanking with default strategies for handling ties and NaNs.
    090         */
    091        public NaturalRanking() {
    092            super();
    093            tiesStrategy = DEFAULT_TIES_STRATEGY;
    094            nanStrategy = DEFAULT_NAN_STRATEGY;
    095            randomData = null;
    096        }
    097
    098        /**
    099         * Create a NaturalRanking with the given TiesStrategy.
    100         *
    101         * @param tiesStrategy the TiesStrategy to use
    102         */
    103        public NaturalRanking(TiesStrategy tiesStrategy) {
    104            super();
    105            this.tiesStrategy = tiesStrategy;
    106            nanStrategy = DEFAULT_NAN_STRATEGY;
    107            randomData = new RandomDataImpl();
    108        }
    109
    110        /**
    111         * Create a NaturalRanking with the given NaNStrategy.
    112         *
    113         * @param nanStrategy the NaNStrategy to use
    114         */
    115        public NaturalRanking(NaNStrategy nanStrategy) {
    116            super();
    117            this.nanStrategy = nanStrategy;
    118            tiesStrategy = DEFAULT_TIES_STRATEGY;
    119            randomData = null;
    120        }
    121
    122        /**
    123         * Create a NaturalRanking with the given NaNStrategy and TiesStrategy.
    124         *
    125         * @param nanStrategy NaNStrategy to use
    126         * @param tiesStrategy TiesStrategy to use
    127         */
    128        public NaturalRanking(NaNStrategy nanStrategy, TiesStrategy tiesStrategy) {
    129            super();
    130            this.nanStrategy = nanStrategy;
    131            this.tiesStrategy = tiesStrategy;
    132            randomData = new RandomDataImpl();
    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            super();
    143            this.tiesStrategy = TiesStrategy.RANDOM;
    144            nanStrategy = DEFAULT_NAN_STRATEGY;
    145            randomData = new RandomDataImpl(randomGenerator);
    146        }
    147
    148
    149        /**
    150         * Create a NaturalRanking with the given NaNStrategy, TiesStrategy.RANDOM
    151         * and the given source of random data.
    152         *
    153         * @param nanStrategy NaNStrategy to use
    154         * @param randomGenerator source of random data
    155         */
    156        public NaturalRanking(NaNStrategy nanStrategy,
    157                RandomGenerator randomGenerator) {
    158            super();
    159            this.nanStrategy = nanStrategy;
    160            this.tiesStrategy = TiesStrategy.RANDOM;
    161            randomData = new RandomDataImpl(randomGenerator);
    162        }
    163
    164        /**
    165         * Return the NaNStrategy
    166         *
    167         * @return returns the NaNStrategy
    168         */
    169        public NaNStrategy getNanStrategy() {
    170            return nanStrategy;
    171        }
    172
    173        /**
    174         * Return the TiesStrategy
    175         *
    176         * @return the TiesStrategy
    177         */
    178        public TiesStrategy getTiesStrategy() {
    179            return tiesStrategy;
    180        }
    181
    182        /**
    183         * Rank <code>data</code> using the natural ordering on Doubles, with
    184         * NaN values handled according to <code>nanStrategy</code> and ties
    185         * resolved using <code>tiesStrategy.</code>
    186         *
    187         * @param data array to be ranked
    188         * @return array of ranks
    189         */
    190        public double[] rank(double[] data) {
    191
    192            // Array recording initial positions of data to be ranked
    193            IntDoublePair[] ranks = new IntDoublePair[data.length];
    194            for (int i = 0; i < data.length; i++) {
    195                ranks[i] = new IntDoublePair(data[i], i);
    196            }
    197
    198            // Recode, remove or record positions of NaNs
    199            List<Integer> nanPositions = null;
    200            switch (nanStrategy) {
    201                case MAXIMAL: // Replace NaNs with +INFs
    202                    recodeNaNs(ranks, Double.POSITIVE_INFINITY);
    203                    break;
    204                case MINIMAL: // Replace NaNs with -INFs
    205                    recodeNaNs(ranks, Double.NEGATIVE_INFINITY);
    206                    break;
    207                case REMOVED: // Drop NaNs from data
    208                    ranks = removeNaNs(ranks);
    209                    break;
    210                case FIXED:   // Record positions of NaNs
    211                    nanPositions = getNanPositions(ranks);
    212                    break;
    213                default: // this should not happen unless NaNStrategy enum is changed
    214                    throw new MathInternalError();
    215            }
    216
    217            // Sort the IntDoublePairs
    218            Arrays.sort(ranks);
    219
    220            // Walk the sorted array, filling output array using sorted positions,
    221            // resolving ties as we go
    222            double[] out = new double[ranks.length];
    223            int pos = 1;  // position in sorted array
    224            out[ranks[0].getPosition()] = pos;
    225            List<Integer> tiesTrace = new ArrayList<Integer>();
    226            tiesTrace.add(ranks[0].getPosition());
    227            for (int i = 1; i < ranks.length; i++) {
    228                if (Double.compare(ranks[i].getValue(), ranks[i - 1].getValue()) > 0) {
    229                    // tie sequence has ended (or had length 1)
    230                    pos = i + 1;
    231                    if (tiesTrace.size() > 1) {  // if seq is nontrivial, resolve
    232                        resolveTie(out, tiesTrace);
    233                    }
    234                    tiesTrace = new ArrayList<Integer>();
    235                    tiesTrace.add(ranks[i].getPosition());
    236                } else {
    237                    // tie sequence continues
    238                    tiesTrace.add(ranks[i].getPosition());
    239                }
    240                out[ranks[i].getPosition()] = pos;
    241            }
    242            if (tiesTrace.size() > 1) {  // handle tie sequence at end
    243                resolveTie(out, tiesTrace);
    244            }
    245            if (nanStrategy == NaNStrategy.FIXED) {
    246                restoreNaNs(out, nanPositions);
    247            }
    248            return out;
    249        }
    250
    251        /**
    252         * Returns an array that is a copy of the input array with IntDoublePairs
    253         * having NaN values removed.
    254         *
    255         * @param ranks input array
    256         * @return array with NaN-valued entries removed
    257         */
    258        private IntDoublePair[] removeNaNs(IntDoublePair[] ranks) {
    259            if (!containsNaNs(ranks)) {
    260                return ranks;
    261            }
    262            IntDoublePair[] outRanks = new IntDoublePair[ranks.length];
    263            int j = 0;
    264            for (int i = 0; i < ranks.length; i++) {
    265                if (Double.isNaN(ranks[i].getValue())) {
    266                    // drop, but adjust original ranks of later elements
    267                    for (int k = i + 1; k < ranks.length; k++) {
    268                        ranks[k] = new IntDoublePair(
    269                                ranks[k].getValue(), ranks[k].getPosition() - 1);
    270                    }
    271                } else {
    272                    outRanks[j] = new IntDoublePair(
    273                            ranks[i].getValue(), ranks[i].getPosition());
    274                    j++;
    275                }
    276            }
    277            IntDoublePair[] returnRanks = new IntDoublePair[j];
    278            System.arraycopy(outRanks, 0, returnRanks, 0, j);
    279            return returnRanks;
    280        }
    281
    282        /**
    283         * Recodes NaN values to the given value.
    284         *
    285         * @param ranks array to recode
    286         * @param value the value to replace NaNs with
    287         */
    288        private void recodeNaNs(IntDoublePair[] ranks, double value) {
    289            for (int i = 0; i < ranks.length; i++) {
    290                if (Double.isNaN(ranks[i].getValue())) {
    291                    ranks[i] = new IntDoublePair(
    292                            value, ranks[i].getPosition());
    293                }
    294            }
    295        }
    296
    297        /**
    298         * Checks for presence of NaNs in <code>ranks.</code>
    299         *
    300         * @param ranks array to be searched for NaNs
    301         * @return true iff ranks contains one or more NaNs
    302         */
    303        private boolean containsNaNs(IntDoublePair[] ranks) {
    304            for (int i = 0; i < ranks.length; i++) {
    305                if (Double.isNaN(ranks[i].getValue())) {
    306                    return true;
    307                }
    308            }
    309            return false;
    310        }
    311
    312        /**
    313         * Resolve a sequence of ties, using the configured {@link TiesStrategy}.
    314         * The input <code>ranks</code> array is expected to take the same value
    315         * for all indices in <code>tiesTrace</code>.  The common value is recoded
    316         * according to the tiesStrategy. For example, if ranks = <5,8,2,6,2,7,1,2>,
    317         * tiesTrace = <2,4,7> and tiesStrategy is MINIMUM, ranks will be unchanged.
    318         * The same array and trace with tiesStrategy AVERAGE will come out
    319         * <5,8,3,6,3,7,1,3>.
    320         *
    321         * @param ranks array of ranks
    322         * @param tiesTrace list of indices where <code>ranks</code> is constant
    323         * -- that is, for any i and j in TiesTrace, <code> ranks[i] == ranks[j]
    324         * </code>
    325         */
    326        private void resolveTie(double[] ranks, List<Integer> tiesTrace) {
    327
    328            // constant value of ranks over tiesTrace
    329            final double c = ranks[tiesTrace.get(0)];
    330
    331            // length of sequence of tied ranks
    332            final int length = tiesTrace.size();
    333
    334            switch (tiesStrategy) {
    335                case  AVERAGE:  // Replace ranks with average
    336                    fill(ranks, tiesTrace, (2 * c + length - 1) / 2d);
    337                    break;
    338                case MAXIMUM:   // Replace ranks with maximum values
    339                    fill(ranks, tiesTrace, c + length - 1);
    340                    break;
    341                case MINIMUM:   // Replace ties with minimum
    342                    fill(ranks, tiesTrace, c);
    343                    break;
    344                case RANDOM:    // Fill with random integral values in [c, c + length - 1]
    345                    Iterator<Integer> iterator = tiesTrace.iterator();
    346                    long f = FastMath.round(c);
    347                    while (iterator.hasNext()) {
    348                        ranks[iterator.next()] =
    349                            randomData.nextLong(f, f + length - 1);
    350                    }
    351                    break;
    352                case SEQUENTIAL:  // Fill sequentially from c to c + length - 1
    353                    // walk and fill
    354                    iterator = tiesTrace.iterator();
    355                    f = FastMath.round(c);
    356                    int i = 0;
    357                    while (iterator.hasNext()) {
    358                        ranks[iterator.next()] = f + i++;
    359                    }
    360                    break;
    361                default: // this should not happen unless TiesStrategy enum is changed
    362                    throw new MathInternalError();
    363            }
    364        }
    365
    366        /**
    367         * Sets<code>data[i] = value</code> for each i in <code>tiesTrace.</code>
    368         *
    369         * @param data array to modify
    370         * @param tiesTrace list of index values to set
    371         * @param value value to set
    372         */
    373        private void fill(double[] data, List<Integer> tiesTrace, double value) {
    374            Iterator<Integer> iterator = tiesTrace.iterator();
    375            while (iterator.hasNext()) {
    376                data[iterator.next()] = value;
    377            }
    378        }
    379
    380        /**
    381         * Set <code>ranks[i] = Double.NaN</code> for each i in <code>nanPositions.</code>
    382         *
    383         * @param ranks array to modify
    384         * @param nanPositions list of index values to set to <code>Double.NaN</code>
    385         */
    386        private void restoreNaNs(double[] ranks, List<Integer> nanPositions) {
    387            if (nanPositions.size() == 0) {
    388                return;
    389            }
    390            Iterator<Integer> iterator = nanPositions.iterator();
    391            while (iterator.hasNext()) {
    392                ranks[iterator.next().intValue()] = Double.NaN;
    393            }
    394
    395        }
    396
    397        /**
    398         * Returns a list of indexes where <code>ranks</code> is <code>NaN.</code>
    399         *
    400         * @param ranks array to search for <code>NaNs</code>
    401         * @return list of indexes i such that <code>ranks[i] = NaN</code>
    402         */
    403        private List<Integer> getNanPositions(IntDoublePair[] ranks) {
    404            ArrayList<Integer> out = new ArrayList<Integer>();
    405            for (int i = 0; i < ranks.length; i++) {
    406                if (Double.isNaN(ranks[i].getValue())) {
    407                    out.add(Integer.valueOf(i));
    408                }
    409            }
    410            return out;
    411        }
    412
    413        /**
    414         * Represents the position of a double value in an ordering.
    415         * Comparable interface is implemented so Arrays.sort can be used
    416         * to sort an array of IntDoublePairs by value.  Note that the
    417         * implicitly defined natural ordering is NOT consistent with equals.
    418         */
    419        private static class IntDoublePair implements Comparable<IntDoublePair>  {
    420
    421            /** Value of the pair */
    422            private final double value;
    423
    424            /** Original position of the pair */
    425            private final int position;
    426
    427            /**
    428             * Construct an IntDoublePair with the given value and position.
    429             * @param value the value of the pair
    430             * @param position the original position
    431             */
    432            public IntDoublePair(double value, int position) {
    433                this.value = value;
    434                this.position = position;
    435            }
    436
    437            /**
    438             * Compare this IntDoublePair to another pair.
    439             * Only the <strong>values</strong> are compared.
    440             *
    441             * @param other the other pair to compare this to
    442             * @return result of <code>Double.compare(value, other.value)</code>
    443             */
    444            public int compareTo(IntDoublePair other) {
    445                return Double.compare(value, other.value);
    446            }
    447
    448            /**
    449             * Returns the value of the pair.
    450             * @return value
    451             */
    452            public double getValue() {
    453                return value;
    454            }
    455
    456            /**
    457             * Returns the original position of the pair.
    458             * @return position
    459             */
    460            public int getPosition() {
    461                return position;
    462            }
    463        }
    464    }