#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>
#include <fcntl.h>

#define UNDEFINED -1

void geninput ( int n )
{
   FILE *fp;
   int i;

   fp = (FILE *)fopen("C1input.txt", "w");
   for (i=0; i<n; ++i) {
      fprintf(fp, " %4d", 1 + rand() % 99);
      if (i % 16 == 15) fprintf(fp, "\n");
   }
   if (i % 16) fprintf(fp, "\n");
   fprintf(fp, "   -1\n");
   fclose(fp);
}

void initroot ( )
{
   FILE *fp;
   int fd;

   fp = (FILE *)fopen("C1input.txt", "r");
   fd = fileno(fp);
   close(0);
   dup(fd);
}

void buildproctree ( int *key, int *parent, int *lchild, int *rchild, int *n, int *ndisc, int pfd[], int lfd[], int rfd[] )
{
   int nextkey;
   char keybuff[16];

   if (*parent == UNDEFINED) {
      printf("\n+++ Building process tree\n");
      fflush(stdout);
   }

   while (1) {
      if (*parent == UNDEFINED) {
         scanf("%d", &nextkey);
         sprintf(keybuff, "%15d", nextkey);
      } else {
         read(pfd[0], keybuff, 16);
         sscanf(keybuff, "%d", &nextkey);
      }
      if (nextkey != UNDEFINED) ++(*n);
      if (nextkey == UNDEFINED) {
         if (*lchild != UNDEFINED) write(lfd[1], keybuff, 16);
         if (*rchild != UNDEFINED) write(rfd[1], keybuff, 16);
         return;
      } else if (*key == UNDEFINED) {
         *key = nextkey;
         printf("    Process %5d with parent %5d gets key = %4d  [ New,  assigned ]\n", getpid(), *parent, *key);
         fflush(stdout);
      } else if (nextkey < *key) {
         if (*lchild == UNDEFINED) {
            pipe(lfd);
            *lchild = fork();
            if (*lchild == 0) {
               *parent = getppid();
               *key = *lchild = *rchild = UNDEFINED;
               *ndisc = 0;
               pfd[0] = lfd[0]; pfd[1] = lfd[1];
               lfd[0] = lfd[1] = rfd[0] = rfd[1] = UNDEFINED;
            }
         }
         if (*lchild != UNDEFINED) write(lfd[1], keybuff, 16);
      } else if (nextkey > *key) {
         if (*rchild == UNDEFINED) {
            pipe(rfd);
            *rchild = fork();
            if (*rchild == 0) {
               *parent = getppid();
               *key = *lchild = *rchild = UNDEFINED;
               *ndisc = 0;
               pfd[0] = rfd[0]; pfd[1] = rfd[1];
               lfd[0] = lfd[1] = rfd[0] = rfd[1] = UNDEFINED;
            }
         }
         if (*rchild != UNDEFINED) write(rfd[1], keybuff, 16);
      } else {
         ++(*ndisc);
         printf("    Process %5d with parent %5d gets key = %4d  [ Old, discarded ]\n", getpid(), *parent, nextkey);
         fflush(stdout);
      }
   }
}

int calcheight ( int parent, int lchild, int rchild, int pfd[], int lfd[], int rfd[] )
{
   char htbuff[16] = "";
   int ht, lht, rht;

   lht = rht = -1;
   if (lchild != UNDEFINED) {
      read(lfd[0], htbuff, 16);
      sscanf(htbuff, "%d", &lht);
   }
   if (rchild != UNDEFINED) {
      read(rfd[0], htbuff, 16);
      sscanf(htbuff, "%d", &rht);
   }
   ht = 1 + ( (lht >= rht) ? lht : rht);
   sprintf(htbuff, "%15d", ht);
   if (parent != UNDEFINED) write(pfd[1], htbuff, 16);
   return ht;
}

void inorder ( int key, int parent, int lchild, int rchild, int pfd[], int lfd[], int rfd[] )
{
   char notbuff[1] = "";

   if (parent != UNDEFINED) read(pfd[0], notbuff, 1);
   if (lchild != UNDEFINED) {
      write(lfd[1], notbuff, 1);
      waitpid(lchild, NULL, 0);
   }
   printf(" %d", key);
   fflush(stdout);
   if (rchild != UNDEFINED) {
      write(rfd[1], notbuff, 1);
      waitpid(rchild, NULL, 0);
   }
}

void synchronize ( int n, int ndisc, int parent, int sfd[], int tfd[] )
{
   int i;
   char syncbuff[1024] = "";

   if (parent == UNDEFINED) {
      for (i=0; i<n-ndisc-1; ++i) read(sfd[0], syncbuff, 1);
      printf("\n");
      write(tfd[1], syncbuff, n-ndisc-1);
   } else {
      write(sfd[1], syncbuff, ndisc+1);
      read(tfd[0], syncbuff, ndisc+1);
   }
}

int main ( int argc, char *argv[] )
{
   int n, key, parent, lchild, rchild, h;
   int pfd[2], lfd[2], rfd[2];
   int ndisc, sfd[2], tfd[2], ufd[2], vfd[2];

   srand((unsigned int)time(NULL));
   if (argc > 1) n = atoi(argv[1]); else scanf("%d", &n);
   geninput(n);
   
   key = parent = lchild = rchild = UNDEFINED;
   pfd[0] = pfd[1] = lfd[0] = lfd[1] = rfd[0] = rfd[1] = UNDEFINED;
   n = ndisc = 0;
   initroot();
   pipe(sfd); pipe(tfd);
   pipe(ufd); pipe(vfd);

   buildproctree(&key, &parent, &lchild, &rchild, &n, &ndisc, pfd, lfd, rfd);

   synchronize(n, ndisc, parent, sfd, tfd);

   h = calcheight(parent, lchild, rchild, pfd, lfd, rfd);
   printf("    Height of the process %5d with key %4d is %d  %s\n",
          getpid(), key, h, (parent == UNDEFINED) ? "[Height of entire tree]" : "");
   fflush(stdout);

   synchronize(n, ndisc, parent, ufd, vfd);

   if (parent == UNDEFINED) {
      printf("+++ Inorder listing of the keys:");
      fflush(stdout);
   }
   inorder(key, parent, lchild, rchild, pfd, lfd, rfd);
   if (parent == UNDEFINED) printf("\n\n");

   exit(0);
}