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

#define INFINITY 1000000000

typedef struct _tnode {
   int a, b;
   struct _tnode *L, *R;
} tnode;

typedef struct _lnode {
   int a, b;
   struct _lnode *next;
} lnode;

typedef struct _plnode {
   tnode *t;
   struct _plnode *next;
} plnode;

int gcd ( int a, int b )
{
   int r;

   if ((a <= 0) || (b <= 0)) return 0;

   while (b) {
      r = a % b;
      a = b;
      b = r;
   }

   return a;
}

tnode *tinit ( )
{
   tnode *T;

   T = (tnode *)malloc(sizeof(tnode));
   T -> a = T -> b = 1;
   T -> L = T -> R = NULL;
   return T;
}

tnode *tsearch ( tnode *T, int a, int b )
{
   lnode *L, *p;

   if (gcd(a,b) != 1) return NULL;

   L = (lnode *)malloc(sizeof(lnode));
   L -> a = a; L -> b = b; L -> next = NULL;
   while (a != b) {
      if (a > b) a -= b; else b -= a;
      p = (lnode *)malloc(sizeof(lnode));
      p -> a = a; p -> b = b; p -> next = L; L = p;
   }

   p = L -> next;
   while ((p) && (T)) {
      a = p -> a; b = p -> b;
      T = (a > b) ? T -> L : T -> R; 
      p = p -> next;
   }

   p = L;
   while (p) {
      L = p;
      p = p -> next;
      free(L);
   }

   return T;
}

int tinsert ( tnode *T, int a, int b )
{
   lnode *L, *p;
   int nnew = 0;

   if (gcd(a,b) != 1) {
      fprintf(stderr, "*** Invalid pair (%d,%d)\n", a, b);
      return 0;
   }

   L = (lnode *)malloc(sizeof(lnode));
   L -> a = a; L -> b = b; L -> next = NULL;
   while (a != b) {
      if (a > b) a -= b; else b -= a;
      p = (lnode *)malloc(sizeof(lnode));
      p -> a = a; p -> b = b; p -> next = L; L = p;
   }

   nnew = 0;
   p = L -> next;
   while (p) {
      a = p -> a; b = p -> b;
      if (a > b) {
         if (T -> L == NULL) {
            T -> L = (tnode *)malloc(sizeof(tnode));
            T -> L -> a = a; T -> L -> b = b;
            T -> L -> L = T -> L -> R = NULL;
            ++nnew;
         }
         T = T -> L;
      } else {
         if (T -> R == NULL) {
            T -> R = (tnode *)malloc(sizeof(tnode));
            T -> R -> a = a; T -> R -> b = b;
            T -> R -> L = T -> R -> R = NULL;
            ++nnew;
         }
         T = T -> R;
      }
      p = p -> next;
   }

   p = L;
   while (p) {
      L = p;
      p = p -> next;
      free(L);
   }

   return nnew;
}

void recdel ( tnode *T, int *ndel )
{
   if (T == NULL) return;
   recdel(T -> L, ndel); recdel(T -> R, ndel);
   ++(*ndel);
   free(T);
}

int tdelete ( tnode *T, int a, int b )
{
   int ndel = 0;

   if ((a == 1) && (b == 1)) {
      fprintf(stderr, "*** Deletion of root not permitted\n");
      return 0;
   }

   if (a > b) {
      T = tsearch(T,a-b,b);
      if (T == NULL) return 0;
      recdel(T -> L, &ndel);
      T -> L = NULL;
   } else {
      T = tsearch(T,a,b-a);
      if (T == NULL) return 0;
      recdel(T -> R, &ndel);
      T -> R = NULL;
   }
   return ndel;
}

int amax ( tnode *T )
{
   int ac, a;

   if (T == NULL) return -INFINITY;
   a = T -> a;
   ac = amax(T -> L); if (ac > a) a = ac;
   ac = amax(T -> R); if (ac > a) a = ac;
   return a;
}

void preorder ( tnode *T, int *npr )
{
   if (T == NULL) return;
   if (*npr % 12 == 0) printf("\n   ");
   printf(" (%2d,%2d)", T->a, T->b);
   ++(*npr);
   preorder(T->L,npr);
   preorder(T->R,npr);
}

void inorder ( tnode *T, int *npr )
{
   if (T == NULL) return;
   inorder(T->L,npr);
   if (*npr % 12 == 0) printf("\n   ");
   printf(" (%2d,%2d)", T->a, T->b);
   ++(*npr);
   inorder(T->R,npr);
}

plnode *pladd ( plnode *H, tnode *t )
{
   plnode *p;

   if (t == NULL) return H;
   p = (plnode *)malloc(sizeof(plnode));
   p -> t = t;
   p -> next = H;
   return p;
}

void lexorder ( tnode *T )
{
   int A, a, npr = 0;
   plnode **H, *p, *q;

   A = amax(T);
   H = (plnode **)malloc((A + 1) * sizeof(plnode *));
   for (a=0; a<=A; ++a) H[a] = NULL;
   H[1] = pladd(H[1],T);
   for (a=1; a<=A; ++a) {
      q = (plnode *)malloc(sizeof(plnode));
      q -> t = NULL;
      q -> next = H[a];
      H[a] = q;
      while (H[a] -> next) {
         q = H[a]; p = q -> next;
         while (p) {
            if (npr % 12 == 0) printf("\n   ");
            printf(" (%2d,%2d)", p -> t -> a, p -> t -> b);
            ++npr;
            if (p->t->L) H[a + p->t->b] = pladd(H[a + p->t->b], p->t->L);
            if (p->t->R) {
               p -> t = p -> t -> R;
               q = p;
            } else {
               q -> next = p -> next;
               free(p);
            }
            p = q -> next;
         }
      }
      free(H[a]);
      H[a] = NULL;
   }
   printf("\n");
   free(H);
}

int main ( int argc, char *argv[] )
{
   int nins, ndel, npr, i, a, b, n, m;
   tnode *T;

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

   T = tinit(); n = 1;

   printf("\n++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
   printf("+++ INSERTION PHASE");
   printf("\n++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n\n");

   for (i=0; i<nins; ++i) {
      do {
         a = 1 + rand() % 99;
         b = 1 + rand() % 99;
      } while (gcd(a,b) != 1);
      printf("    (%2d,%2d): ", a, b);
      m = tinsert(T,a,b);
      printf("%2d nodes added\n", m);
      n += m;
   }

   printf("\n+++ Number of nodes = %d\n", n);
   npr = 0; printf("\n+++ Preorder"); preorder(T,&npr); printf("\n");
   npr = 0; printf("\n+++ Inorder"); inorder(T,&npr); printf("\n");
   printf("\n+++ Lexical order"); lexorder(T);

   printf("\n++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
   printf("+++ SEARCH PHASE");
   printf("\n++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n\n");

   while (1) {
      a = 1 + rand() % 99;
      b = 1 + rand() % 99;
      if (gcd(a,b) != 1) continue;
      if (tsearch(T,a,b) == NULL) continue;
      break;
   }
   printf("    (%2d,%2d): Search successful\n", a, b);
   while (1) {
      a = 1 + rand() % 99;
      b = 1 + rand() % 99;
      if (gcd(a,b) != 1) continue;
      if (tsearch(T,a,b) != NULL) continue;
      break;
   }
   printf("    (%2d,%2d): Search failed\n", a, b);

   printf("\n++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
   printf("+++ DELETION PHASE");
   printf("\n++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n\n");

   for (i=0; i<ndel; ++i) {
      do {
         a = 1 + rand() % 99;
         b = 1 + rand() % 99;
      } while (tsearch(T,a,b) == NULL);
      printf("    (%2d,%2d): ", a, b);
      m = tdelete(T,a,b);
      printf("%2d nodes deleted\n", m);
      n -= m;
   }

   printf("\n+++ Number of nodes = %d\n", n);
   npr = 0; printf("\n+++ Preorder"); preorder(T,&npr); printf("\n");
   npr = 0; printf("\n+++ Inorder"); inorder(T,&npr); printf("\n");
   printf("\n+++ Lexical order"); lexorder(T);

   exit(0);
}