#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "median.h"

#define N 1001 /*must be odd*/

int subtree_size(n)
node *n;
  {
  return(n==NULLTREE? 0: n->subtree_ref_count);
  }

void do_btck(n)
node *n;
  {
  while(n != NULLTREE)
    {
    if((n->parent != NULLTREE) && (n != n->parent->left_child) && (n != n->parent->right_child))
      printf("ERR 0\n");
    if((n->left_child != NULLTREE) && (n->left_child->parent != n))
      printf("ERR 1\n");
    if((n->right_child != NULLTREE) && (n->right_child->parent != n))
      printf("ERR 2\n"); /*possibly an ancestor of queue[863]*/
    if(n->subtree_ref_count != n->ref_count + subtree_size(n->left_child) + subtree_size(n->right_child))
      printf("ERR 3\n");
    do_btck(n->left_child);
    n = n->right_child;
    }
  }

void btck(t)
btree *t;
  {
  do_btck(t->tree);
  }

void do_print_btree(n, indent)
node *n;
int indent;
  {
  register int i;
  while(n != NULLTREE)
    {
    for(i = 0; i != indent; i++)
      putchar(' ');
    printf("%f %d\n", n->value, n->ref_count);
    do_print_btree(n->left_child, ++indent);
    n = n->right_child;
    }
  for(i = 0; i != indent; i++)
    putchar(' ');
  printf("<null>\n");
  }

void print_btree(t)
btree *t;
  {
  printf("head=%d tail=%d\n", t->head, t->tail);
  do_print_btree(t->tree, 0);
  }

static int comp(a, b)
int *a, *b;
  {
  return(*a<*b?-1:*a==*b?0:1);
  }

void main()
  {
  btree *t;
  int i, j;
  QVAL median, data[N], temp[N];
  t = create_btree(N);
  printf("PHASE 0:\n"); fflush(stdout);
  for(i = 0; i != N; i++)
    {
    printf("? "); scanf("%f", data+i);
    if(data[i]==0.0) print_btree(t);
    insert_newest(data[i], t);
    btck(t);
    for(j = 0; j <= i; j++)
      temp[j] = data[j];
    qsort(temp, 1+i, sizeof(*temp), comp);
    median = extract_median(t);
printf("%f %f\n", data[i], median);
    if((median != temp[i/2]) && ((~i&1) || (median != temp[i/2+1])))
      {printf("ACK!\n"); fflush(stdout);}
    }
  printf("PHASE 1:\n"); fflush(stdout);
  for(i = 0; i != N; i++)
    {
    delete_oldest(t);
    btck(t);
    data[i] = (QVAL)(random()&31);
    insert_newest(data[i], t);
    btck(t);
    for(j = 0; j != N; j++)
      temp[j] = data[j];
    qsort(temp, N, sizeof(*temp), comp);
    median = extract_median(t);
    if(median != temp[N/2])
      {printf("ACK!\n"); fflush(stdout);}
    }
  printf("PHASE 2:\n"); fflush(stdout);
  for(i = 1; i != N; i++)
    {
    for(j = i; j != N; j++)
      temp[j] = data[j];
    qsort(temp+i, N-i, sizeof(*temp), comp);
    delete_oldest(t);
    btck(t);
    median = extract_median(t);
    if((median != temp[i+(N-i)/2]) && (((N-i)&1) || (median != temp[i+(N-i)/2-1])))
      {printf("%f != %f", median, temp[i+(N-i)/2]);
       if(~(N-i)&1) printf(" or %f", temp[i+(N-i)/2-1]);
       putchar('\n');
       fflush(stdout);}
    }
  destroy_btree(t);
  }
