htswanalysis/MACS/lib/gsl/gsl-1.11/sort/test_heapsort.c

   1 /* sort/test_heapsort.c
   2  *
   3  * Copyright (C) 1996, 1997, 1998, 1999, 2000, 2007 Thomas Walter, Brian Gough
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 3 of the License, or (at
   8  * your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  18  */
  19
  20 int cmp_dbl (const void *a, const void *b);
  21 void test_heapsort (size_t N);
  22 void initialize (double *data, size_t N);
  23 void cpy (double *dest, double *src, size_t N);
  24 void randomize (double *data, size_t n);
  25 void reverse (double *data, size_t N);
  26 int check (double *data, double *orig, size_t N);
  27 int pcheck (size_t * p, double *data, double *orig, size_t N);
  28
  29 void
  30 test_heapsort (size_t N)
  31 {
  32   int status;
  33
  34   double *orig = (double *) malloc (N * sizeof (double));
  35   double *data = (double *) malloc (N * sizeof (double));
  36   size_t  *p = (size_t *) malloc (N * sizeof(size_t));
  37
  38   initialize (orig, N);
  39
  40   /* Already sorted */
  41   cpy (data, orig, N);
  42
  43   status = gsl_heapsort_index (p, data, N, sizeof (double), (gsl_comparison_fn_t) & cmp_dbl);
  44   status |= pcheck (p, data, orig, N);
  45   gsl_test (status, "indexing array, n = %u, ordered", N);
  46
  47   gsl_heapsort (data, N, sizeof (double), (gsl_comparison_fn_t) & cmp_dbl);
  48   status = check (data, orig, N);
  49
  50   gsl_test (status, "sorting, array, n = %u, ordered", N);
  51
  52   /* Reverse the data */
  53
  54   cpy (data, orig, N);
  55   reverse (data, N);
  56
  57   status = gsl_heapsort_index (p, data, N, sizeof (double), (gsl_comparison_fn_t) & cmp_dbl);
  58   status |= pcheck (p, data, orig, N);
  59   gsl_test (status, "indexing array, n = %u, reversed", N);
  60
  61   gsl_heapsort (data, N, sizeof (double), (gsl_comparison_fn_t) & cmp_dbl);
  62   status = check (data, orig, N);
  63
  64   gsl_test (status, "sorting, array, n = %u, reversed", N);
  65
  66   /* Perform some shuffling */
  67
  68   cpy (data, orig, N);
  69   randomize (data, N);
  70
  71   status = gsl_heapsort_index (p, data, N, sizeof (double), (gsl_comparison_fn_t) & cmp_dbl);
  72   status |= pcheck (p, data, orig, N);
  73   gsl_test (status, "indexing array, n = %u, randomized", N);
  74
  75   gsl_heapsort (data, N, sizeof (double), (gsl_comparison_fn_t) & cmp_dbl);
  76   status = check (data, orig, N);
  77
  78   gsl_test (status, "sorting, array, n = %u, randomized", N);
  79
  80   free (orig);
  81   free (data);
  82   free (p);
  83 }
  84
  85 void
  86 initialize (double *data, size_t N)
  87 {
  88   size_t i;
  89
  90   for (i = 0; i < N; i++)
  91     {
  92       data[i] = i;
  93     }
  94 }
  95
  96 void
  97 cpy (double *dest, double *src, size_t N)
  98 {
  99   size_t i;
 100
 101   for (i = 0; i < N; i++)
 102     {
 103       dest[i] = src[i];
 104     }
 105 }
 106
 107 void
 108 randomize (double *data, size_t N)
 109 {
 110   size_t i;
 111
 112   for (i = 0; i < N; i++)
 113     {
 114       size_t j = urand (N);
 115       double tmp = data[i];
 116       data[i] = data[j];
 117       data[j] = tmp;
 118     }
 119 }
 120
 121 void
 122 reverse (double *data, size_t N)
 123 {
 124   size_t i;
 125
 126   for (i = 0; i < N / 2; i++)
 127     {
 128       size_t j = N - i - 1;
 129
 130       {
 131         double tmp = data[i];
 132         data[i] = data[j];
 133         data[j] = tmp;
 134       }
 135     }
 136 }
 137
 138 int
 139 check (double *data, double *orig, size_t N)
 140 {
 141   size_t i;
 142
 143   for (i = 0; i < N; i++)
 144     {
 145       if (data[i] != orig[i])
 146         {
 147           return GSL_FAILURE;
 148         }
 149     }
 150
 151   return GSL_SUCCESS;
 152 }
 153
 154 int
 155 pcheck (size_t * p, double *data, double *orig, size_t N)
 156 {
 157   size_t i;
 158
 159   for (i = 0; i < N; i++)
 160     {
 161       if (data[p[i]] != orig[i])
 162         {
 163           return GSL_FAILURE;
 164         }
 165     }
 166
 167   return GSL_SUCCESS;
 168 }
 169
 170
 171
 172 int
 173 cmp_dbl (const void *a, const void *b)
 174 {
 175   const double x = *(const double *) a;
 176   const double y = *(const double *) b;
 177   if (x > y)
 178     return 1;
 179   if (x == y)
 180     return 0;
 181   else
 182     return -1;
 183 }