/*JS*********************************************************************
*
*    Program : TESTSORT
*    Language: ANSI-C
*    Author  : Joerg Schoen
*    Purpose : Test program for "gensort.h" sorting routines.
*
*************************************************************************/

#ifndef lint
static const char rcsid[] = "$Id$";
#endif

/*********     INCLUDES                                         *********/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define Prototype
/*********     PROTOTYPES                                       *********/
Prototype int            checkSort(int *vector,int *array,long n,char *descript,
				   void (*routine)(int *array,long n));

Prototype void           quicksort(int *array,long n);
Prototype void           quicksortp(int *array,long n);
Prototype void           heapsort(int *array,long n);

Prototype void           wrapqsort(int *array,long n);
Prototype int            longcmp(const void *a,const void *b);

/*********     GLOBAL/ STATIC VARIABLES                         *********/
static int QuickLimit = 0;

/*JS*********************************************************************
*
*************************************************************************/

int main(int argc,char **argv)

/************************************************************************/
{
  int mode,*vector,*array;
  long i,k,n,n2;

  /*   Drop program name   */
  argv++; argc--;

  /*   Preset mode   */
  mode = 1;

  /*   Get arguments       */
  for(i = 0 ; argc-- > 0 ; argv++) {
    if(*argv) {
      switch(++i) {
      default:
	fprintf(stderr,"ERROR: To many arguments -- Break.\n");
	goto help;
      case 1: /*  "n"     */
	n = atoi(*argv);
	break;
      case 2: /*   "mode" */
	mode = atoi(*argv);
	break;
      case 3: /*   "seed" */
	srand( atoi(*argv) );
	break;
      case 4: /*   "limit" */
	QuickLimit = atoi(*argv);
	break;
      }
    }
  }

  /*   Less than one arguments?    */
  if(i < 1) goto help;

  /*   Get temporary memory for vector   */
  if( (vector = (int *)malloc(2 * n * sizeof(*vector))) == NULL ) {
    fprintf(stderr,"ERROR: Not enough memory (%ld Bytes needed) -- Break.\n",
	    2 * n * sizeof(*vector));
    exit(30);
  }
  array = vector + n;

  switch(mode) {
  default:
    printf("Unknown mode %d -- Break.\n",mode);
    goto help;
  case 2:  /*  random but many (10) values are equal   */
    printf("Building random vector with all values appearing 10 times...\n");
    n2 = n / 10;
    for(i = 0 ; i < n ; i++) {
      k = rand() % n2;
      k = abs(k);
      vector[i] = k;
    }
    break;
  case 1:  /*   random   */
    printf("Building up random vector....\n");
    n2 = n;
    for(i = 0 ; i < n ; i++) {
      k = rand() % n2;
      k = abs(k);
      vector[i] = k;
    }
    break;
  case 3:  /*  ordered   */
    /*   Fill vector with random values    */
    printf("Building up ordered vector.\n");
    for(i = 0 ; i < n ; i++) {
      vector[i] = i;
    }
    break;
  case 4: /*  invers   */
    /*   Fill vector with random values    */
    printf("Building up invers ordered vector....\n");
    for(i = 0 ; i < n ; i++) {
      vector[i] = n - i;
    }
    break;
  }

  printf("Testing sorting routines:\n");

  if(checkSort(vector,array,n,"generated quicksort",quicksort))
    goto ende;

  if(checkSort(vector,array,n,"generated quicksort with pointers",quicksortp))
    goto ende;

  if(checkSort(vector,array,n,"generated heapsort",heapsort))
    goto ende;

  if(checkSort(vector,array,n,"standard library quicksort",wrapqsort))
    goto ende;

/*
  printf("The sorted vector:\n");
  for(i = 0 ; i < n ; i++)
    printf("%d%c",array[i],(i % 20) == 19 ? '\n' : ' ');
  putchar('\n');
*/
ende:

  free(vector);

  return(0);
help:
  printf("Usage: testsort <n> [<mode> [<seed> [<limit>]]]\n\
 Tests out the quicksort and heapsort routines generated by \"gensort.h\".\n\
 Integer arrays of size <n> are sorted according to size. <limit> is the\n\
 treshhold for the array size below of which quicksort uses straight\n\
 insertion.\n\
 Mode: 1: random vector (Default).\n\
       2: random vector so that every value appears 10 times.\n\
       3: ordered vector.\n\
       4: invers ordered vector.\n");
  return(10);
}

/*JS*********************************************************************
*
*************************************************************************/

int checkSort(int *vector,int *array,long n,char *descript,
	       void (*routine)(int *array,long n))

/************************************************************************/
{
  time_t tim;
  int i;

  /*  Make temporary copy of vector   */
  memcpy(array,vector,n * sizeof(vector[0]));

  printf("  Using %-35s...",descript); fflush(stdout);

  tim = clock();
  (*routine)(array,n);
  printf("%g seconds needed.",(clock() - tim) / (double) CLOCKS_PER_SEC);

  /*   Check sorting  */
  for(i = 1 ; i < n ; i++)
    if(array[i - 1] > array[i]) {
      printf("*** Sorting invalid: a[%d] = %d > a[%d] = %d!\n",
	     i - 1,array[i - 1],i,array[i]);
      goto error;
    }

  printf(" Sorting ok.\n");

  return(0);
error:
  return(-1);
}

/* ***  Generate normal QUICKSORT  *** */
#define GENSORT_NAME                 quicksort
#define GENSORT_TYPE                 int
#define GENSORT_KEYTYPE              int
#define GENSORT_GETKEY(a)            a
#define GENSORT_COMPAREKEYS(k1,k2)   k1 < k2
#define GENSORT_LIMIT                QuickLimit
#include "gensort.h"

/* ***  Generate QUICKSORT with pointers  *** */
#define GENSORT_NAME                 quicksortp
#define GENSORT_TYPE                 int
#define GENSORT_KEYTYPE              int
#define GENSORT_GETKEY(a)            a
#define GENSORT_COMPAREKEYS(k1,k2)   k1 < k2
#define GENSORT_LIMIT                QuickLimit
#define GENSORT_USEPOINTERS
#include "gensort.h"
#undef GENSORT_USEPOINTERS

/* ***  Generate HEAPSORT  *** */
#define GENSORT_NAME                 heapsort
#define GENSORT_TYPE                 int
#define GENSORT_KEYTYPE              int
#define GENSORT_GETKEY(a)            a
#define GENSORT_COMPAREKEYS(k1,k2)   k1 < k2
#define GENSORT_HEAPSORT
#include "gensort.h"

/* ***  Wrapper for standard library qsort  *** */
void wrapqsort(int *array,long n)
{
  qsort(array,n,sizeof(int),longcmp);
}

int longcmp(const void *a,const void *b)
{
  return( (int) (*(int*)a - *(int*) b) );
}
