#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define FILELIMIT 32
#define INFINITY 1000000000

typedef struct _node {
   int min, max;
   int fidx;
   struct _node *L, *R;
} node;

typedef node *BST;

typedef struct {
   int height;
   int size;
   int nleaves;
} treeinfo;

FILE *initfile ( char fname[] )
{
   FILE *fp;
   int i;

   fp = (FILE *)fopen(fname, "w+");
   fprintf(fp, "%7d\n", 0);
   for (i=1; i<=FILELIMIT; ++i)
      fprintf(fp, "%7s%c", "_", ((i % 10 == 0) || (i == FILELIMIT)) ? '\n' : ' ');
   return fp;
}

int readsize ( FILE *fp )
{
   int n;

   fseek(fp, 0, SEEK_SET);
   fscanf(fp, "%d", &n);
   return n;
}

void writesize ( FILE *fp, int n )
{
   fseek(fp, 0, SEEK_SET);
   fprintf(fp, "%7d\n", n);
}

int readkey ( FILE *fp, int i )
{
   int key;

   fseek(fp, 8*i, SEEK_SET);
   fscanf(fp, "%d", &key);
   return key;
}

void writekey ( FILE *fp, int i, int key )
{
   fseek(fp, 8*i, SEEK_SET);
   fprintf(fp, "%7d%c", key, ((i % 10 == 0) || (i == FILELIMIT)) ? '\n' : ' ');
}

void erasekey ( FILE *fp, int i )
{
   fseek(fp, 8*i, SEEK_SET);
   fprintf(fp, "%7s%c", "_", ((i % 10 == 0) || (i == FILELIMIT)) ? '\n' : ' ');
}

int hsearch ( FILE *fp, int x )
{
   int n, i, key;

   fseek(fp, 0, SEEK_SET);
   fscanf(fp, "%d", &n);
   for (i=0; i<n; ++i) {
      fscanf(fp, "%d", &key);
      if (key == x) return 1;
   }
   return 0;
}

void happend ( FILE *fp, int x )
{
   int n;

   n = readsize(fp);
   if (n == FILELIMIT) {
      fprintf(stderr, "*** File limit reached. Split the heap.\n");
      return;
   }
   ++n;
   writesize(fp,n);
   writekey(fp,n,x);
}

void hinsert ( FILE *fp, int x )
{
   int i, p, n, t;

   n = readsize(fp);
   ++n;
   writesize(fp,n);
   writekey(fp,n,x);
   i = n;
   while (i > 1) {
      p = i / 2;
      t = readkey(fp,p);
      if (t < x) break;
      writekey(fp,p,x);
      writekey(fp,i,t);
      i = p;
   }
}

int hfindmin ( FILE *fp )
{
   if (readsize(fp) == 0) return INFINITY;
   return readkey(fp,1);
}

int hfindmax ( FILE *fp )
{
   int maxkey = -INFINITY, n, i, x;

   n = readsize(fp);
   for (i=0; i<n; ++i) {
      fscanf(fp, "%d", &x);
      if (x > maxkey) maxkey = x;
   }
   return maxkey;
}

void hdelmin ( FILE *fp )
{
   int n, i, l, r, x, lkey, rkey;

   n = readsize(fp);
   if (n == 0) {
      fprintf(stderr, "*** Cannot delete from empty heap\n");
      return;
   }
   x = readkey(fp,n);
   writekey(fp,1,x);
   erasekey(fp,n);
   --n;
   writesize(fp,n);
   i = 1;
   while (1) {
      x = readkey(fp,i);

      l = 2*i;
      if (l > n) break;

      r = 2*i+1;
      if (r > n) {
         lkey = readkey(fp,l);
         if (lkey < x) {
            writekey(fp,l,x);
            writekey(fp,i,lkey);
         }
         break;
      }

      lkey = readkey(fp,l);
      rkey = readkey(fp,r);
      if ((x < lkey) && (x < rkey)) break;
      if (lkey < rkey) {
         writekey(fp,i,lkey);
         writekey(fp,l,x);
         i = l;
      } else {
         writekey(fp,i,rkey);
         writekey(fp,r,x);
         i = r;
      }
   }
}

BST dbinit ( int *fidx )
{
   BST T;
   char fname[32];
   FILE *fp;

   T = (BST)malloc(sizeof(node));
   T -> min = INFINITY; T -> max = -INFINITY;
   T -> fidx = *fidx;
   T -> L = T -> R = NULL;
   sprintf(fname, "B1/%06d.dat", *fidx);
   fp = initfile(fname);
   fclose(fp);
   ++(*fidx);
   return T;
}

int dbsearch ( BST T, int x )
{
   FILE *fp;
   int res;
   char fname[32];

   while ((T -> L != NULL) && (T -> R != NULL)) {
      if ( (x < T -> min) || (x > T -> max) ) return 0;
      T = (x <= T -> L -> max) ? T -> L : T -> R;
   }
   sprintf(fname, "B1/%06d.dat", T -> fidx);
   fp = fopen(fname,"r");
   res = hsearch(fp,x);
   fclose(fp);
   return res;
}

void dbinsert ( BST T, int x, int *fidx )
{
   int n, i, key;
   char fname[32];
   FILE *fp, *nfp;

   while ((T -> L != NULL) && (T -> R != NULL)) {
      if (x < T -> min) { T -> min = x; T = T -> L; }
      else if (x > T -> max) { T -> max = x; T = T -> R; }
      else if (x <= T -> L -> max) T = T -> L;
      else T = T -> R;
   }
   if (x < T -> min) T -> min = x;
   if (x > T -> max) T -> max = x;
   sprintf(fname, "B1/%06d.dat", T -> fidx);
   fp = fopen(fname,"r+");
   if (hsearch(fp,x)) {
      fclose(fp);
      return;
   }
   n = readsize(fp);
   if (n < FILELIMIT) {
      hinsert(fp,x);
      fclose(fp);
   } else {
      T -> L = (BST)malloc(sizeof(node));
      T -> L -> L = T -> L -> R = NULL;
      T -> L -> fidx = *fidx;
      T -> R = (BST)malloc(sizeof(node));
      T -> R -> L = T -> R -> R = NULL;
      T -> R -> fidx = T -> fidx;
      T -> fidx = -1;
      sprintf(fname, "B1/%06d.dat", *fidx);
      nfp = initfile(fname);
      ++(*fidx);
      for (i=1; i<=FILELIMIT/2; ++i) {
         key = hfindmin(fp);
         hdelmin(fp);
         hinsert(nfp,key);
      }
      T -> L -> min = T -> min;
      T -> L -> max = readkey(nfp,FILELIMIT/2);
      if (x < T -> L -> max) hinsert(nfp,x); else hinsert(fp,x);
      T -> R -> min = readkey(fp,1);
      T -> R -> max = T -> max;
      fclose(fp); fclose(nfp);
   }
}

void inorder ( BST T, int *npr )
{
   if (T -> L) inorder(T -> L, npr);
   if ((T -> L == NULL) && (T -> R == NULL)) {
      printf("%7d %7d", T -> min, T -> max);
      *npr += 2;
      if (*npr == 10) { printf("\n"); *npr = 0; } else printf(" ");
   }
   if (T -> R) inorder(T -> R, npr);
}

void inorderfile ( BST T, int *npr )
{
   if (T -> L) inorderfile(T -> L, npr);
   if ((T -> L == NULL) && (T -> R == NULL)) {
      FILE *fp;
      char fname[32];

      sprintf(fname, "B1/%06d.dat", T -> fidx);
      fp = (FILE *)fopen(fname, "r");
      printf("%7d %7d", hfindmin(fp), hfindmax(fp));
      *npr += 2;
      if (*npr == 10) { printf("\n"); *npr = 0; } else printf(" ");
      fclose(fp);
   }
   if (T -> R) inorderfile(T -> R, npr);
}

void preorder ( BST T, int *npr )
{
   printf("%7d", T -> min);
   ++(*npr); if (*npr == 10) { printf("\n"); *npr = 0; } else printf(" ");
   if (T -> L) preorder(T -> L, npr);
   if (T -> R) preorder(T -> R, npr);
}

void postorder ( BST T, int *npr )
{
   if (T -> L) postorder(T -> L, npr);
   if (T -> R) postorder(T -> R, npr);
   printf("%7d", T -> max);
   ++(*npr); if (*npr == 10) { printf("\n"); *npr = 0; } else printf(" ");
}

treeinfo treestat ( BST T )
{
   treeinfo linfo, rinfo, myinfo;

   if (T == NULL) return (treeinfo){-1,0,0};
   linfo = treestat(T -> L);
   rinfo = treestat(T -> R);
   myinfo.height = 1 + ((linfo.height >= rinfo.height) ? linfo.height : rinfo.height);
   myinfo.size = 1 + linfo.size + rinfo.size;
   if (myinfo.size == 1) myinfo.nleaves = 1;
   else myinfo.nleaves = linfo.nleaves + rinfo.nleaves;
   return myinfo;
}

void printtree ( BST T, int level )
{
   int i;

   if (T == NULL) { printf("    NULL\n"); return; }

   if (level == 0) {
      printf("    Range = [%d,%d], File: ", T -> min, T -> max);
      if (T -> fidx >= 0) printf("B1/%06d.dat\n", T -> fidx);
      else printf("None\n");
   }

   if (T -> L) {
      for (i=0; i<=level; ++i) printf("    ");
      printf("+---");
      printf("Range = [%d,%d], File: ", T -> L -> min, T -> L -> max);
      if (T -> L -> fidx >= 0) printf("B1/%06d.dat\n", T -> L -> fidx);
      else printf("None\n");
      printtree(T->L,level+1);
   }

   if (T -> R) {
      for (i=0; i<=level; ++i) printf("    ");
      printf("+---");
      printf("Range = [%d,%d], File: ", T -> R -> min, T -> R -> max);
      if (T -> R -> fidx >= 0) printf("B1/%06d.dat\n", T -> R -> fidx);
      else printf("None\n");
      printtree(T->R,level+1);
   }
}

int main ( int argc, char *argv[] )
{
   int nins, npr, findex, i, j, x;
   BST T;
   treeinfo info;
   int pkey, akey;

   if (argc > 1) nins = atoi(argv[1]); else scanf("%d", &nins);
   printf("nins = %d\n", nins);
   srand((unsigned int)time(NULL));

   findex = 0;
   T = dbinit(&findex);

   akey = rand() % 10000000; j = rand() % nins;
   printf("Insert keys:");
   for (i=0; i<nins; ++i) {
      if (i % 10 == 0) printf("\n");
      do x = rand() % 10000000; while (x == akey);
      printf(" %7d", x);
      dbinsert(T,x,&findex);
      if (i == j) pkey = x;
   }

   printf("\n\n+++ Inorder listing of min and max values of leaves\n");
   npr = 0; inorder(T,&npr);

   printf("\n\n+++ Inorder listing of min and max values read from files\n");
   npr = 0; inorderfile(T,&npr);

   printf("\n\n+++ Sorted listing of min values at all nodes\n");
   npr = 0; preorder(T,&npr);

   printf("\n\n+++ Sorted listing of max values at all nodes\n");
   npr = 0; postorder(T,&npr);

   info = treestat(T);
   printf("\n\n+++ Statistics of the BST\n");
   printf("    Number of nodes  = %d\n", info.size);
   printf("    Number of leaves = %d\n", info.nleaves);
   printf("    Height           = %d\n", info.height);

   printf("\n+++ The BST\n");
   printtree(T,0);

   printf("\n+++ Search results\n");
   printf("    search(%7d): %7s\n", pkey, dbsearch(T,pkey) ? "PRESENT" : "ABSENT");
   printf("    search(%7d): %7s\n", akey, dbsearch(T,akey) ? "PRESENT" : "ABSENT");

   exit(0);
}