#include <stdio.h>
#include <stdlib.h>
#include "BB7.h"

#define MINUSINFTY -1000000000

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

void prntree ( char *prompt, BST T )
{
   int npr;

   printf("    %s : ", prompt);
   npr = 0; preorder(T,&npr); if (npr % 16) printf("\n");
}

BST lrot ( 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;
   return v;
}

BST rrot ( 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;
   return v;
}

int rskew ( BST T, BST *H )
{
   int nrots = 0;

   while (T -> R) {
      while (T -> R -> L) {
         T -> R = rrot(T -> R);
         if (H) H[nrots] = T;
         ++nrots;
      }
      T = T -> R;
   }

   return nrots;
}

void findcorr ( BST S, BST T, BST *HS, BST *HT, int nrots )
{
   int i;

   i = 0;
   while (i < nrots) {
      while (HT[i] != T) { S = S -> R; T = T -> R; }
      HS[i] = S; ++i;
   }
}

void unskew ( BST *H, int nrots )
{
   BST p;

   while (--nrots >= 0) {
      p = H[nrots];
      p -> R = lrot(p -> R);
   }
}

int main ( int argc, char *argv[] )
{
   int n, nrots;
   BST S, T, *HS, *HT;

   if (argc > 1) n = atoi(argv[1]); else scanf("%d", &n);
   printf("n = %d\n", n);

   registerme(n);

   /* Prepare the input trees with the dummy roots */
   printf("\n+++ Initial trees\n");
   S = (BST)malloc(sizeof(BSTnode));
   S -> key = MINUSINFTY; S -> L = NULL;
   S -> R = getsourcetree(); prntree("Source", S -> R);
   T = (BST)malloc(sizeof(BSTnode));
   T -> key = MINUSINFTY; T -> L = NULL;
   T -> R = gettargettree(); prntree("Target", T -> R);

   printf("\n+++ Right-skewing the trees\n");
   nrots = rskew(S,NULL); prntree("Source", S -> R);
   printf("             Number of rotations = %d\n", nrots);
   HT = (BST *)malloc(n * sizeof(BST));
   nrots = rskew(T,HT); prntree("Target", T -> R);
   printf("             Number of rotations = %d\n", nrots);

   HS = (BST *)malloc(n * sizeof(BST));
   printf("\n+++ Finding node correspondence\n"); findcorr(S,T,HS,HT,nrots);

   printf("\n+++ Reversing the skewing process\n");
   unskew(HS,nrots); prntree("Source", S -> R);
   unskew(HT,nrots); prntree("Target", T -> R);

   exit(0);
}