/* sort/test_source.c

 * 

 * Copyright (C) 1996, 1997, 1998, 1999, 2000, 2007 Thomas Walter, Brian Gough

 * 

 * This program is free software; you can redistribute it and/or modify

 * it under the terms of the GNU General Public License as published by

 * the Free Software Foundation; either version 3 of the License, or (at

 * your option) any later version.

 * 

 * This program is distributed in the hope that it will be useful, but

 * WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

 * General Public License for more details.

 * 

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

 */

void TYPE (test_sort_vector) (size_t N, size_t stride);

void FUNCTION (my, initialize) (TYPE (gsl_vector) * v);

void FUNCTION (my, randomize) (TYPE (gsl_vector) * v);

int FUNCTION (my, check) (TYPE (gsl_vector) * data, TYPE (gsl_vector) * orig);

int FUNCTION (my, pcheck) (gsl_permutation * p, TYPE (gsl_vector) * data, TYPE (gsl_vector) * orig);

int FUNCTION (my, scheck) (BASE * x, size_t k, TYPE (gsl_vector) * data);

int FUNCTION (my, lcheck) (BASE * x, size_t k, TYPE (gsl_vector) * data);

int FUNCTION (my, sicheck) (size_t * p, size_t k, gsl_permutation * perm,

                            TYPE (gsl_vector) * data);

int FUNCTION (my, licheck) (size_t * p, size_t k, gsl_permutation * perm,

                            TYPE (gsl_vector) * data);

void

TYPE (test_sort_vector) (size_t N, size_t stride)

{

  int status;

  size_t  k = N/2;

  TYPE (gsl_block) * b1 = FUNCTION (gsl_block, calloc) (N * stride);

  TYPE (gsl_block) * b2 = FUNCTION (gsl_block, calloc) (N * stride);

  TYPE (gsl_block) * b3 = FUNCTION (gsl_block, calloc) (N * stride);

  TYPE (gsl_vector) * orig = FUNCTION (gsl_vector, alloc_from_block) (b1, 0, N, stride);

  TYPE (gsl_vector) * data = FUNCTION (gsl_vector, alloc_from_block) (b2, 0, N, stride);

  TYPE (gsl_vector) * data2 = FUNCTION (gsl_vector, alloc_from_block) (b3, 0, N, stride);

  BASE * small = (BASE *)malloc(k * sizeof(BASE));

  BASE * large = (BASE *)malloc(k * sizeof(BASE));

  size_t * index = (size_t *)malloc(k * sizeof(size_t));

  gsl_permutation *p = gsl_permutation_alloc (N);

  FUNCTION (my, initialize) (orig);

  /* Already sorted */

  FUNCTION (gsl_vector, memcpy) (data, orig);

  status = FUNCTION (gsl_sort_vector, index) (p, data);

  status |= FUNCTION (my, pcheck) (p, data, orig);

  gsl_test (status, "indexing " NAME (gsl_vector) ", n = %u, stride = %u, ordered", N, stride);

  TYPE (gsl_sort_vector) (data);

  status = FUNCTION (my, check) (data, orig);

  gsl_test (status, "sorting, " NAME (gsl_vector) ", n = %u, stride = %u, ordered", N, stride);

  FUNCTION (gsl_sort_vector, smallest) (small, k, data);

  status = FUNCTION (my, scheck) (small, k, orig);

  gsl_test (status, "smallest, " NAME (gsl_vector) ", n = %u, stride = %u, ordered", N, stride);

  FUNCTION (gsl_sort_vector, largest) (large, k, data);

  status = FUNCTION (my, lcheck) (large, k, orig);

  gsl_test (status, "largest, " NAME (gsl_vector) ", n = %u, stride = %u, ordered", N, stride);

  FUNCTION (gsl_sort_vector, smallest_index) (index, k, data);

  status = FUNCTION (my, sicheck) (index, k, p, data);

  gsl_test (status, "smallest index, " NAME (gsl_vector) ", n = %u, stride = %u, ordered", N, stride);

  FUNCTION (gsl_sort_vector, largest_index) (index, k, data);

  status = FUNCTION (my, licheck) (index, k, p, data);

  gsl_test (status, "largest index, " NAME (gsl_vector) ", n = %u, stride = %u, ordered", N, stride);

  /* Reverse the data */

  FUNCTION (gsl_vector, memcpy) (data, orig);

  FUNCTION (gsl_vector, reverse) (data);

  status = FUNCTION (gsl_sort_vector, index) (p, data);

  status |= FUNCTION (my, pcheck) (p, data, orig);

  gsl_test (status, "indexing " NAME (gsl_vector) ", n = %u, stride = %u, reversed", N, stride);

  TYPE (gsl_sort_vector) (data);

  status = FUNCTION (my, check) (data, orig);

  gsl_test (status, "sorting, " NAME (gsl_vector) ", n = %u, stride = %u, reversed", N, stride);

  FUNCTION (gsl_vector, memcpy) (data, orig);

  FUNCTION (gsl_vector, reverse) (data);

  FUNCTION (gsl_vector, memcpy) (data2, data);

  TYPE (gsl_sort_vector2) (data, data2);

  status = FUNCTION (my, check) (data, orig);

  gsl_test (status, "sorting2, " NAME (gsl_vector) ", n = %u, stride = %u, reversed data", N, stride);

  status = FUNCTION (my, check) (data2, orig);

  gsl_test (status, "sorting2, " NAME (gsl_vector) ", n = %u, stride = %u, reversed data2", N, stride);

  FUNCTION (gsl_vector, memcpy) (data, orig);

  FUNCTION (gsl_vector, reverse) (data);

  FUNCTION (gsl_sort_vector, smallest) (small, k, data);

  status = FUNCTION (my, scheck) (small, k, orig);

  gsl_test (status, "smallest, " NAME (gsl_vector) ", n = %u, stride = %u, reversed", N, stride);

  FUNCTION (gsl_sort_vector, largest) (large, k, data);

  status = FUNCTION (my, lcheck) (large, k, orig);

  gsl_test (status, "largest, " NAME (gsl_vector) ", n = %u, stride = %u, reversed", N, stride);

  FUNCTION (gsl_sort_vector, smallest_index) (index, k, data);

  status = FUNCTION (my, sicheck) (index, k, p, data);

  gsl_test (status, "smallest index, " NAME (gsl_vector) ", n = %u, stride = %u, reversed", N, stride);

  FUNCTION (gsl_sort_vector, largest_index) (index, k, data);

  status = FUNCTION (my, licheck) (index, k, p, data);

  gsl_test (status, "largest index, " NAME (gsl_vector) ", n = %u, stride = %u, reversed", N, stride);

  /* Perform some shuffling */

  FUNCTION (gsl_vector, memcpy) (data, orig);

  FUNCTION (my, randomize) (data);

  FUNCTION (gsl_vector, memcpy) (data2, data);

  TYPE (gsl_sort_vector2) (data, data2);

  status = FUNCTION (my, check) (data, orig);

  gsl_test (status, "sorting2, " NAME (gsl_vector) ", n = %u, stride = %u, randomized data", N, stride);

  status = FUNCTION (my, check) (data2, orig);

  gsl_test (status, "sorting2, " NAME (gsl_vector) ", n = %u, stride = %u, randomized data2", N, stride);

  FUNCTION (gsl_vector, memcpy) (data, orig);

  FUNCTION (my, randomize) (data);

  FUNCTION (gsl_vector, memcpy) (data2, data);

  status = FUNCTION (gsl_sort_vector, index) (p, data);

  status |= FUNCTION (my, pcheck) (p, data, orig);

  gsl_test (status, "indexing " NAME (gsl_vector) ", n = %u, stride = %u, randomized", N, stride);

  TYPE (gsl_sort_vector) (data);

  status = FUNCTION (my, check) (data, orig);

  gsl_test (status, "sorting, " NAME (gsl_vector) ", n = %u, stride = %u, randomized", N, stride);

  FUNCTION (gsl_vector, memcpy) (data, data2);

  FUNCTION (gsl_sort_vector, smallest) (small, k, data);

  status = FUNCTION (my, scheck) (small, k, orig);

  gsl_test (status, "smallest, " NAME (gsl_vector) ", n = %u, stride = %u, randomized", N, stride);

  FUNCTION (gsl_sort_vector, largest) (large, k, data);

  status = FUNCTION (my, lcheck) (large, k, orig);

  gsl_test (status, "largest, " NAME (gsl_vector) ", n = %u, stride = %u, randomized", N, stride);

  FUNCTION (gsl_sort_vector, smallest_index) (index, k, data);

  status = FUNCTION (my, sicheck) (index, k, p, data);

  gsl_test (status, "smallest index, " NAME (gsl_vector) ", n = %u, stride = %u, randomized", N, stride);

  FUNCTION (gsl_sort_vector, largest_index) (index, k, data);

  status = FUNCTION (my, licheck) (index, k, p, data);

  gsl_test (status, "largest index, " NAME (gsl_vector) ", n = %u, stride = %u, randomized", N, stride);

  FUNCTION (gsl_vector, free) (orig);

  FUNCTION (gsl_vector, free) (data);

  FUNCTION (gsl_vector, free) (data2);

  FUNCTION (gsl_block, free) (b1);

  FUNCTION (gsl_block, free) (b2);

  FUNCTION (gsl_block, free) (b3);

  gsl_permutation_free (p);

  free (small);

  free (large);

  free (index);

}

void

FUNCTION (my, initialize) (TYPE (gsl_vector) * v)

{

  size_t i;

  ATOMIC k = 0;

  volatile ATOMIC kk;

  /* Must be sorted initially */

  for (i = 0; i < v->size; i++)

    {

      kk = k;

      k++;

      /* Prevent overflow */

      if (k < kk) k = kk;

      FUNCTION (gsl_vector, set) (v, i, k);

    }

}

void

FUNCTION (my, randomize) (TYPE (gsl_vector) * v)

{

  size_t i;

  for (i = 0; i < v->size; i++)

    {

      size_t j = urand (v->size);

      FUNCTION (gsl_vector, swap_elements) (v, i, j);

    }

}

int

FUNCTION (my, check) (TYPE (gsl_vector) * data, TYPE (gsl_vector) * orig)

{

  size_t i;

  for (i = 0; i < data->size; i++)

    {

      if (FUNCTION (gsl_vector, get) (data, i) != FUNCTION (gsl_vector, get) (orig, i))

        {

#if DUMP_ERROR

          size_t j;

          for (j = 0 ; j < data->size; j++) {

            printf("%u: " OUT_FORMAT " " OUT_FORMAT " %c\n", j,

                   FUNCTION (gsl_vector, get) (data, j),

                   FUNCTION (gsl_vector, get) (orig, j),

                   (i == j) ? '*' : ' ');

          }

#endif

          return GSL_FAILURE;

        }

    }

  return GSL_SUCCESS;

}

int

FUNCTION (my, pcheck) (gsl_permutation * p, TYPE (gsl_vector) * data, TYPE (gsl_vector) * orig)

{

  size_t i;

  for (i = 0; i < p->size; i++)

    {

      if (FUNCTION (gsl_vector, get) (data, p->data[i]) != FUNCTION (gsl_vector, get) (orig, i))

        {

          return GSL_FAILURE;

        }

    }

  return GSL_SUCCESS;

}

int

FUNCTION (my, scheck) (BASE * x, size_t k, TYPE (gsl_vector) * data)

{

  size_t i;

  for (i = 0; i < k; i++)

    {

      if (x[i] != FUNCTION (gsl_vector, get) (data, i))

        {

          return GSL_FAILURE;

        }

    }

  return GSL_SUCCESS;

}

int

FUNCTION (my, lcheck) (BASE * x, size_t k, TYPE (gsl_vector) * data)

{

  size_t i;

  for (i = 0; i < k; i++)

    {

      if (x[i] != FUNCTION (gsl_vector, get) (data, data->size - i - 1))

        {

          return GSL_FAILURE;

        }

    }

  return GSL_SUCCESS;

}

int

FUNCTION (my, sicheck) (size_t * p1, size_t k, gsl_permutation * p,

                        TYPE (gsl_vector) * data)

{

  size_t i;

  for (i = 0; i < k; i++)

    {

      if (FUNCTION(gsl_vector,get)(data,p1[i]) 

          != FUNCTION(gsl_vector,get)(data, p->data[i]))

        {

          return GSL_FAILURE;

        }

    }

  return GSL_SUCCESS;

}

int

FUNCTION (my, licheck) (size_t * p1, size_t k, gsl_permutation * p,

                        TYPE (gsl_vector) * data)

{

  size_t i;

  for (i = 0; i < k; i++)

    {

      if (FUNCTION(gsl_vector,get)(data,p1[i]) 

          != FUNCTION(gsl_vector,get)(data, p->data[p->size - i - 1]))

        {

          return GSL_FAILURE;

        }

    }

  return GSL_SUCCESS;

}