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

#define EVEN 0
#define ODD 1
#define MINUSINFINITY -1000000000
#define PLUSINFINITY 1000000000

typedef struct _node {
   int key;
   struct _node *L, *R, *P;
} tnode;

typedef tnode *BST;

typedef struct {
   tnode *x, *y;
   int gap;
} neighbor;

BST insert ( BST T, int x )
{
   BST p, q;

   p = T; q = NULL;
   while (p) {
      if (p -> key == x) return T;
      q = p;
      p = (x < p -> key) ? p -> L : p -> R;
   }

   p = (tnode *)malloc(sizeof(tnode));
   p -> key = x; p -> L = p -> R = NULL; p -> P = q;

   if (q == NULL) return p;

   if (x < q -> key) q -> L = p; else q -> R = p;

   return T;
}

/* Assumes n >= 3 */
BST gentree ( int n )
{
   BST T;
   int i, j, t, *gaps, *keys;

   gaps = (int *)malloc(n * sizeof(int));
   gaps[0] = rand() % 100;
   for (i=1; i<n; ++i) gaps[i] = gaps[i-1] + 1 + rand() % 5;
   printf("Smallest gap = %d, largest gap = %d\n", gaps[1], gaps[n-1]);
   for (i=1; i<n; ++i) {
      do j = 1 + rand() % (n-1); while (j == i);
      t = gaps[i]; gaps[i] = gaps[j]; gaps[j] = t;
   }

   keys = (int *)malloc(n * sizeof(int));
   keys[0] = 100 + rand() % 100;
   for (i=1; i<n; ++i) keys[i] = keys[i-1] + gaps[i];
   for (i=0; i<n; ++i) {
      do j = rand() % n; while (j == i);
      t = keys[i]; keys[i] = keys[j]; keys[j] = t;
   }

   printf("Keys to insert:\n");
   T = NULL;
   for (i=0; i<n; ++i) {
      printf("%5d ", keys[i]);
      T = insert(T,keys[i]);
      if (i % 12 == 11) printf("\n");
   }
   if (i % 12) printf("\n");

   free(gaps); free(keys);

   return T;
}

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

/* T is the current node, and *P is the previous node in the inorder traversal */
void inorder ( BST T, BST *P, neighbor *N, int parity )
{
   int gap;

   if (T == NULL) return;

   inorder(T->L, P, N, parity);

   if (parity == EVEN) {
      if (*P != NULL) {
         gap = (T -> key) - ((*P) -> key);
         if (gap < N -> gap) {
            N -> x = *P; N -> y = T;
            N -> gap = gap;
         }
      }
   } else {
      if (*P != NULL) {
         gap = (T -> key) - ((*P) -> key);
         if (gap > N -> gap) {
            N -> x = *P; N -> y = T;
            N -> gap = gap;
         }
      }
   }
   *P = T;

   inorder(T->R, P, N, parity);
}

neighbor findnbr ( BST T, int parity )
{
   neighbor N;
   BST P;

   N.x = N.y = NULL;
   N.gap = (parity == EVEN) ? PLUSINFINITY : MINUSINFINITY;

   P = NULL;
   inorder(T,&P,&N,parity);

   return N;
}

BST lrotate ( BST u )
{
   BST v, w;

   v = u -> R;
   if (v == NULL) {
      fprintf(stderr, "*** Left rotate not allowed\n");
      return u;
   }

   w = v -> L;
   v -> L = u;
   u -> R = w;

   v -> P = u -> P;
   u -> P = v;
   if (w) w -> P = u;

   return v;
}

BST rrotate ( BST u )
{
   BST v, w;

   v = u -> L;
   if (v == NULL) {
      fprintf(stderr, "*** Right rotate not allowed\n");
      return u;
   }

   w = v -> R;
   v -> R = u;
   u -> L = w;

   v -> P = u -> P;
   u -> P = v;
   if (w) w -> P = u;

   return v;
}

BST makechild ( BST T, neighbor N, int parity )
{
   int nrots = 0;
   BST p, q;

   if (parity == EVEN) {
      if ((N.y) -> L) {
         printf("*** Case 1: x is a descendent of y\n");
         while ((N.y) -> L != N.x) {
            (N.y) -> L = lrotate((N.y) -> L);
            ++nrots;
         }
      } else {
         printf("*** Case 2: y is a descendent of x\n");
         while ((N.x) -> R != N.y) {
            (N.x) -> R = rrotate((N.x) -> R);
            ++nrots;
         }
         p = (N.x) -> P;
         q = lrotate(N.x);
         ++nrots;
         if (p == NULL) { printf("*** Rotation at root\n"); T = q; }
         else if (q -> key < p -> key) p -> L = q;
         else p -> R = q;
      }
      printf("    Number of rotations = %d\n", nrots);
      printf("    y = %d, y -> L = %d, y -> R = ", N.y -> key, N.y -> L -> key);
      if (N.y -> R) printf("%d\n", N.y -> R -> key); else printf("NULL\n");
   } else {
      if ((N.x) -> R) {
         printf("*** Case 1: y is a descendent of x\n");
         while((N.x) -> R != N.y) {
            (N.x) -> R = rrotate((N.x) -> R);
            ++nrots;
         }
      } else {
         printf("*** Case 2: x is a descendent of y\n");
         while ((N.y) -> L != N.x) {
            (N.y) -> L = lrotate((N.y) -> L);
            ++nrots;
         }
         p = (N.y) -> P;
         q = rrotate(N.y);
         ++nrots;
         if (p == NULL) { printf("*** Rotation at root\n"); T = q; }
         else if (q -> key < p -> key) p -> L = q;
         else p -> R = q;
      }
      printf("    Number of rotations = %d\n", nrots);
      printf("    x = %d, x -> L = ", N.x -> key);
      if (N.x -> L) printf("%d", N.x -> L -> key); else printf("NULL");
      printf(", x -> R = %d\n", N.x -> R -> key);
   }
   return T;
}

int main ( int argc, char *argv[] )
{
   int n, npr, parity;
   BST T;
   neighbor N;

   srand((unsigned int)time(NULL));

   if (argc > 1) n = atoi(argv[1]); else scanf("%d", &n);
   if (argc > 2) parity = atoi(argv[2]); else scanf("%d", &parity);
   parity %= 2; if (parity < 0) parity = -parity;
   printf("%s PC\nn = %d\n", (parity == 0) ? "EVEN" : "ODD", n);

   T = gentree(n);

   printf("\n+++ Preorder traversal of initial tree");
   npr = 0; preorder(T, &npr); printf("\n");

   printf("\n+++ Finding %s neighbor\n", (parity == 0) ? "closest" : "farthest");
   N = findnbr(T,parity);
   printf("    x = %d, y = %d, gap = %d\n", (N.x)->key, (N.y)->key, N.gap);

   printf("\n+++ Bringing neighboring key to child position\n");
   T = makechild(T,N,parity);

   printf("\n+++ Preorder traversal of final tree");
   npr = 0; preorder(T, &npr); printf("\n");

   exit(0);
}