/* MAXIMUM FINDING
 *
 * This was written in pre-ANSI C since that was the only language
 * understood by the tcov profiler.
 *
 * Copyright: Jyrki Katajainen, 1998                                  
 *
 * Run at DIKU as follows:
 * gcc -O4 -o max maximum.c
 * max [n]
 */

#include <assert.h>             /* Declare assert */
#include <stddef.h>             /* Declare NULL */
#include <stdlib.h>             /* Declare malloc */
#include <stdio.h>              /* Declare printf */
#include <time.h>               /* Declare clock and clock_t */
#include "random_permutation.c" /* Declare permute */

/* Compute the maximum of the n numbers in array a */
unsigned int maximum(a, n)
  unsigned int * a;
  unsigned int n;
{
  unsigned int i;
  unsigned int j;
  unsigned int t;

  t = a[0];
  j = 0;
  for (i = 1; i < n; i++) {
    if (a[i] > t) {
      t = a[i];
      j = i;
    }
  }
  return j;
}

int main(argc, argv)
  unsigned int argc;
  char** argv;
{
  const double s = (double) CLOCKS_PER_SEC;
  clock_t cpu_time;
  unsigned int i;
  unsigned int n;
  unsigned int * x;

  if (argc == 1) n = 1000000;
  else if (argc == 2) n = atoi(argv[1]);
  else fprintf(stderr, "Usage: %s [<n>]\n", argv[0]);

  printf("Generating a random permutation of {0,1,2,...,%ld} ...\n", n - 1);
  x = (unsigned int *) malloc(n * sizeof(unsigned int));
  assert(x != NULL);
  for (i = 0; i < n; i++) x[i] = i;   
  permute(x, n);

  printf("Computing the maximum of these %ld numbers ...\n", n);
  cpu_time = clock();
  i = maximum(x, n);
  cpu_time = clock() - cpu_time;
  assert(x[i] == (n - 1));
  printf("Running time in seconds: ");
  printf("%.3f\n", ((double) cpu_time)/s);
  
  free(x);
  return 0;
}