/*A testing laboratory made seven measurements each of the concentration of lead
  in the water supplies of five different municipalities.  Because the testing
  equipment occasionally generated large outliers, the experimenters decided to
  compute the median of each separate series of measurements, and then to take
  the median of those medians as a final result.  We'll write a generalised
  function that takes the median of any array of objects.*/

static void scalar_swap(b, i, j)
void *b;
int i, j;
  {
  int *bb = (int *)b;
  register int temp;
  temp = bb[i];
  bb[i] = bb[j];
  bb[j] = temp;
  }

static void vector_swap(b, i, j)
void *b;
int i, j;
  {
  int **bb = (int **)b;
  register int *temp;
  temp = bb[i];
  bb[i] = bb[j];
  bb[j] = temp;
  }

static int scalar_LessThan(b, i, j)
void *b;
int i, j;
  {
  int *bb = (int *)b;
  return(bb[i] < bb[j]);
  }

static int vector_LessThan(b, i, j)
void *b;
int i, j;
  {
  int **bb = (int **)b;
  return(bb[i][0] < bb[j][0]); /*median is in the 0th elt.*/
  }

/*Find the median of an array b.  This is accomplished using a partial
  quicksort; thus the contents of b end up as a permutation of the original
  sequence.  The median is placed in b[0].*/
void median(b, len, less_than, swap)
void *b;
int len;
int (*less_than)(void*, int, int);
void (*swap)(void*, int, int);
  {
  register int h, k, m, n;
  m = 0;
  n = len-1;
  /*inv: m <= len/2 < n and b[m..n] is a permutation of the subsequence
    b[m..n] of sorted sequence b[0..len-1]*/
  do
    {
    h = m+1;
    k = n;
    /*inv: b[m+1..h-1] <= b[m] and b[k+1..n] > b[m]*/
    while(h <= k)
      {
      while((h <= k) && (*less_than)(b, h, m))
	h++;
      while((h <= k) && !(*less_than)(b, k, m))
	k--;
      if(h < k)
	(*swap)(b, h++, k--);
      } /*elihw*/
    /*k=h-1*/
    if(k==m)
      m++;
    else if(h==n+1)
      (*swap)(b, m, n--);
    else
      {
      (*swap)(b, m, k);
      if(k <= len/2)
	m=k;
      else
	n=k;
      } /*fi*/
    /*b[k] is now in sorted position*/
    } while(k != len/2);
  (*swap)(b, k, 0); /*move the median element to the beginning of the array*/
  }

int main()
  {
  static int data0[] = {  48,   32,   27,    0, 1000,  101,   54};
  static int data1[] = {  96,  112,  132,  116,    0,  966,   98};
  static int data2[] = {  57,   63,   55,   59,   60, 1166,   54};
  static int data3[] = {2004,  512,  449,  613,  558,  485,  498};
  static int data4[] = { 208,  222,  199, 1170,  207,  238,  212};
  static int *(data[]) = {data0, data1, data2, data3, data4};
  register int sample;
  for(sample = 0; sample != 5; sample++)
    {
    median(data[sample], 7, scalar_LessThan, scalar_swap);
    printf("median of sample %d is %d\n", sample, data[sample][0]);
    }
  median(data, 5, vector_LessThan, vector_swap);
  printf("grand median is %d\n", data[0][0]);
  return 0;
  }

/*SUPPOSE WE DECLARED A TWO-DIMENSIONAL ARRAY data[][7] = {{...},{...},....}.
  WOULD THIS SIMPLIFY THINGS?  COULD WE USE THE SAME CODE FOR IT AS WE DID FOR
  THE ARRAY OF POINTERS ABOVE?  WHY, OR WHY NOT?  THINK ABOUT HOW THE TWO
  VERSIONS OF THE ARRAY ARE REPRESENTED IN MEMORY, AND HOW MANY LEVELS OF
  POINTERS THE PROGRAM IS DEREFERENCING.*/