00001 /*****************************************************************************
00002    Major portions of this software are copyrighted by the Medical College
00003    of Wisconsin, 1994-2000, and are released under the Gnu General Public
00004    License, Version 2.  See the file README.Copyright for details.
00005 ******************************************************************************/
00006 
00007 /*
00008   This file contains routines for sorting numbers and determining ranks.
00009 
00010   File:    ranks.c
00011   Author:  B. Douglas Ward
00012   Date:    31 March 2000
00013 
00014 */
00015 
00016 /*---------------------------------------------------------------------------*/
00017 /*
00018   Structure to store list of values, sorted in increasing order.
00019 */
00020   
00021 typedef struct node
00022 {
00023   float fval;             /* floating point value */
00024   int d;                  /* count of number of occurances of this value */
00025   struct node * next;     /* link to next node */
00026 } node;
00027 
00028 
00029 /*---------------------------------------------------------------------------*/
00030 /*
00031   Print contents of list, starting at smallest value. 
00032 */
00033 
00034 void list_print (node * n, int * count)
00035 {
00036   int i;
00037 
00038   for (i = 0;  i < n->d;  i++)
00039     {
00040       printf (" %6.1f", n->fval);
00041       *count += 1;
00042       if (*count % 10 == 0)
00043         printf ("\n");
00044     }
00045 
00046   if (n->next != NULL)
00047     list_print (n->next, count);
00048 }
00049 
00050 
00051 /*---------------------------------------------------------------------------*/
00052 /*
00053   Delete the entire list.
00054 */
00055 
00056 void list_delete (node ** n)
00057 {
00058   if ((*n)->next != NULL)
00059     list_delete (&((*n)->next));
00060   free (*n);
00061   *n = NULL;
00062 }
00063 
00064 
00065 /*---------------------------------------------------------------------------*/
00066 /*
00067   Insert one node with value r; reset pointers.
00068 */
00069 
00070 void node_insert (node ** n, float r)
00071 {
00072   node * ptr;
00073 
00074   ptr = *n;
00075   *n = (node *) malloc (sizeof(node));
00076   (*n)->fval = r;
00077   (*n)->d = 1;
00078   (*n)->next = ptr;
00079 }
00080 
00081 
00082 /*---------------------------------------------------------------------------*/
00083 /*
00084   Add number r to list; if number is already in the list, just increment the
00085   counter.  Otherwise, insert new node.
00086 */
00087 
00088 void node_addvalue (node ** head, float r)
00089 {
00090   node ** lastptr;
00091   node * ptr;
00092 
00093 
00094   if (*head == NULL)  node_insert (head, r);
00095   else
00096     {
00097       lastptr = head;
00098       ptr = *head;
00099 
00100       while ( (ptr->fval < r) && (ptr->next != NULL) )
00101         {
00102           lastptr = &(ptr->next);
00103           ptr = ptr->next;
00104         }
00105       
00106       if (ptr->fval > r)
00107         node_insert (lastptr, r);
00108       else
00109         if (ptr->fval == r)
00110           ptr->d += 1;
00111         else
00112           node_insert (&(ptr->next), r);
00113     }
00114 }
00115 
00116 
00117 /*---------------------------------------------------------------------------*/
00118 /*
00119   Get rank corresponding to number r.  If ties exist, return average rank.
00120 */
00121 
00122 float node_get_rank (node * head, float r)
00123 {
00124   node * ptr;
00125   float rank;
00126 
00127   ptr = head;
00128   rank = 0.0;
00129 
00130   while (ptr->fval != r)
00131     {
00132       rank += ptr->d;
00133       ptr = ptr->next;
00134     }
00135 
00136   rank += (ptr->d + 1) / 2.0;
00137   return (rank);
00138 }
00139 
00140 
00141 /*---------------------------------------------------------------------------*/
00142 /*
00143   Return value corresponding to the specified rank.
00144 */
00145 
00146 float node_get_value (node * head, int rank)
00147 {
00148   node * ptr;
00149   int k;
00150 
00151   ptr = head;
00152   k = 0;
00153 
00154   while (k + ptr->d < rank)
00155     {
00156       k += ptr->d;
00157       ptr = ptr->next;
00158     }
00159 
00160   return (ptr->fval);
00161 }
00162 
00163 
00164 /*---------------------------------------------------------------------------*/
00165 /*
00166   Return value corresponding to the median value.
00167 */
00168 
00169 float node_get_median (node * head, int n)
00170 {
00171   float median;
00172 
00173 
00174   if (n % 2)
00175     median = node_get_value(head, n/2 + 1);
00176   else
00177     median = 0.5 * (node_get_value(head, n/2) + 
00178                     node_get_value(head, n/2 + 1));
00179 
00180   return (median);
00181 }
00182 
00183 
00184 /*---------------------------------------------------------------------------*/
00185 /*
00186   Sort the input data array of floats, and return a new array containing 
00187   the ranks of the input data. 
00188 */
00189 
00190 float * rank_array
00191 (
00192   int n,                             /* number of data points */
00193   float * xarray                     /* array of data to be ranked */
00194 )
00195 
00196 {
00197   int i;                             /* array index */
00198   node * xhead = NULL;               /* pointer to list of sorted values */
00199   float * rarray = NULL;             /* array of ranks */
00200 
00201 
00202   /*----- Allocate memory for array of ranks -----*/
00203   rarray = (float *) malloc (sizeof(float) * n);    MTEST (rarray); 
00204 
00205 
00206   /*----- Enter and sort original data  -----*/
00207   for (i = 0;  i < n;  i++)
00208     node_addvalue (&xhead, xarray[i]); 
00209 
00210 
00211   /*----- Get ranks of data -----*/
00212   for (i = 0;  i < n;  i++)
00213     rarray[i] = node_get_rank (xhead, xarray[i]);
00214 
00215 
00216   /*----- Deallocate memory -----*/
00217   list_delete (&xhead);
00218 
00219 
00220   /*----- Return array of ranks -----*/
00221   return (rarray);
00222 }
00223 
00224 
00225 /*---------------------------------------------------------------------------*/
00226 /*
00227   Sort the input data array of doubles, and return a new array containing 
00228   the ranks of the input data. 
00229 */
00230 
00231 float * rank_darray
00232 (
00233   int n,                             /* number of data points */
00234   double * darray                    /* array of data to be ranked */
00235 )
00236 
00237 {
00238   int i;                             /* array index */
00239   node * xhead = NULL;               /* pointer to list of sorted values */
00240   float * rarray = NULL;             /* array of ranks */
00241 
00242 
00243   /*----- Allocate memory for array of ranks -----*/
00244   rarray = (float *) malloc (sizeof(float) * n);    MTEST (rarray); 
00245 
00246 
00247   /*----- Enter and sort original data  -----*/
00248   for (i = 0;  i < n;  i++)
00249     node_addvalue (&xhead, (float) darray[i]); 
00250 
00251 
00252   /*----- Get ranks of data -----*/
00253   for (i = 0;  i < n;  i++)
00254     rarray[i] = node_get_rank (xhead, (float) darray[i]);
00255 
00256 
00257   /*----- Deallocate memory -----*/
00258   list_delete (&xhead);
00259 
00260 
00261   /*----- Return array of ranks -----*/
00262   return (rarray);
00263 }
00264 
00265 
00266 /*---------------------------------------------------------------------------*/
00267