View Javadoc

    1   package baseCode.math;
    2
    3   import java.util.Arrays;
    4   import java.util.Iterator;
    5   import java.util.LinkedHashMap;
    6   import java.util.Map;
    7
    8   import cern.colt.list.DoubleArrayList;
    9   import cern.colt.list.IntArrayList;
    10  import cern.colt.list.ObjectArrayList;
    11
    12  /***
    13   * Calculate rank statistics for arrays.
    14   * <p>
    15   * Copyright (c) 2004
    16   * </p>
    17   * <p>
    18   * Institution: Columbia University
    19   * </p>
    20   *
    21   * @author Paul Pavlidis
    22   * @version $Id: Rank.java,v 1.12 2004/12/24 23:16:10 pavlidis Exp $
    23   */
    24  public class Rank {
    25
    26     /***
    27      * Return a permutation which puts the array in sorted order. In other words, the values returned indicate the
    28      * positions of the sorted values in the current array (the lowest value has the lowest rank, but it could be located
    29      * anywhere in the array).
    30      *
    31      * @param array
    32      * @return
    33      */
    34     public static IntArrayList order( DoubleArrayList array ) {
    35
    36        // FIXME this is easily done, albeit very inefficiently, if we 1) get the ranks and then 2) find the indexes of the
    37        // ranks.
    38        IntArrayList ranks = rankTransform( array );
    39
    40        IntArrayList order = new IntArrayList( ranks.size() );
    41
    42        for ( int i = 0; i < ranks.size(); i++ ) {
    43
    44           // find the ith item.
    45           for ( int j = 0; j < ranks.size(); j++ ) {
    46              if ( i == ranks.getQuick( j ) ) {
    47                 order.add(  j );
    48                 break;
    49              }
    50           }
    51
    52        }
    53        return order;
    54     }
    55
    56     /***
    57      * Rank transform an array. Ties are not handled specially. The ranks are constructed based on the sort order of the
    58      * elements. That is, low values get low numbered ranks.
    59      *
    60      * @param array DoubleArrayList
    61      * @return cern.colt.list.DoubleArrayList
    62      */
    63     public static IntArrayList rankTransform( DoubleArrayList array ) {
    64        if ( array == null ) {
    65           throw new IllegalArgumentException( "Null array" );
    66        }
    67
    68        int size = array.size();
    69        if ( size == 0 ) {
    70           return null;
    71        }
    72
    73        ObjectArrayList ranks = new ObjectArrayList( size );
    74        IntArrayList result = new IntArrayList( new int[size] );
    75
    76        // store the ranks in the array.
    77        for ( int i = 0; i < size; i++ ) {
    78           rankData rd = new rankData( i, array.get( i ) );
    79           ranks.add( rd );
    80        }
    81
    82        ranks.sort();
    83
    84        // fill in the results.
    85        for ( int i = 0; i < size; i++ ) {
    86           result.set( ( ( rankData ) ranks.get( i ) ).getIndex(), i );
    87        }
    88
    89        return result;
    90     }
    91
    92     /***
    93      * Rank transform a map, where the values are numerical (java.lang.Double) values we wish to rank. Ties are not
    94      * handled specially.
    95      *
    96      * @param m java.util.Map with keys Objects, values Doubles.
    97      * @return A java.util.Map keys=old keys, values=java.lang.Integer rank of the key.
    98      * @throws IllegalArgumentException if the input Map does not have Double values.
    99      */
    100    public static Map rankTransform( Map m ) throws IllegalArgumentException {
    101       int counter = 0;
    102
    103       keyAndValueData[] values = new keyAndValueData[m.size()];
    104
    105       /*
    106        * put the pvalues into an array of objects which contain the pvalue and the gene id
    107        */
    108       for ( Iterator itr = m.keySet().iterator(); itr.hasNext(); ) {
    109
    110          Object key = itr.next();
    111
    112          if ( !( m.get( key ) instanceof Double ) ) {
    113             throw new IllegalArgumentException(
    114                   "Attempt to rank a map with non-Double values" );
    115          }
    116
    117          double val = ( ( Double ) m.get( key ) ).doubleValue();
    118          values[counter] = new keyAndValueData( key, val );
    119          counter++;
    120       }
    121
    122       /* sort it */
    123       Arrays.sort( values );
    124       Map result = new LinkedHashMap();
    125       /* put the sorted items back into a hashmap with the rank */
    126       for ( int i = 0; i < m.size(); i++ ) {
    127          result.put( values[i].getKey(), new Integer( i ) );
    128       }
    129       return result;
    130    }
    131 }
    132
    133 /*
    134  * Helper class for rankTransform.
    135  */
    136
    137 class rankData implements Comparable {
    138
    139    private int index;
    140    private double value;
    141
    142    public rankData( int tindex, double tvalue ) {
    143       index = tindex;
    144       value = tvalue;
    145    }
    146
    147    public int compareTo( Object a ) {
    148       rankData other = ( rankData ) ( a );
    149       if ( this.value < other.getValue() ) {
    150          return -1;
    151       } else if ( this.value > other.getValue() ) {
    152          return 1;
    153       } else {
    154          return 0;
    155       }
    156    }
    157
    158    public int getIndex() {
    159       return index;
    160    }
    161
    162    public double getValue() {
    163       return value;
    164    }
    165 }
    166
    167 /*
    168  * Helper class for rankTransform map.
    169  */
    170
    171 class keyAndValueData implements Comparable {
    172    private Object key;
    173
    174    private double value;
    175
    176    public keyAndValueData( Object id, double v ) {
    177       this.key = id;
    178       this.value = v;
    179    }
    180
    181    public int compareTo( Object ob ) {
    182       keyAndValueData other = ( keyAndValueData ) ob;
    183
    184       if ( this.value < other.value ) {
    185          return -1;
    186       } else if ( this.value > other.value ) {
    187          return 1;
    188       } else {
    189          return 0;
    190       }
    191    }
    192
    193    public Object getKey() {
    194       return key;
    195    }
    196
    197    public double getValue() {
    198       return value;
    199    }
    200 }