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

#define MINUS_INFTY -1000000000

typedef struct _tnode {
   int key;
   struct _tnode *L;
   struct _tnode *R;
} tnode;

tnode *addnoderec ( int n, int K[], int *i )
{
   int nl, nr;
   tnode *p;

   if (n == 0) return NULL;
   p = (tnode *)malloc(sizeof(tnode));
   p -> key = K[(*i)++];
   nl = rand() % n;
   nr = n - 1 - nl;
   printf("%-5d %3d %3d\n", p -> key, nl, nr);
   p -> L = addnoderec(nl,K,i);
   p -> R = addnoderec(nr,K,i);
   return p;
}

tnode *gentree ( int n )
{
   tnode *T;
   int *K, i, u, v, t;

   K = (int *)malloc(n * sizeof(int));
   K[0] = 100 + rand() % 100;
   for (i=1; i<n; ++i) K[i] = K[i-1] + 1 + rand() % 10;
   for (i=0; i<n; ++i) {
      u = rand() % n; v = rand() % n;
      t = K[u]; K[u] = K[v]; K[v] = t;
   }

   T = (tnode *)malloc(sizeof(tnode));
   T -> key = MINUS_INFTY;
   T -> L = NULL;
   i = 0; T -> R = addnoderec(n,K,&i);
   free(K);
   return T;
}

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

void inorder ( tnode *T, int *np )
{
   if (T == NULL) return;
   inorder(T->L,np);
   printf("%-5d ", T -> key);
   ++(*np);
   if (*np % 16 == 0) printf("\n    ");
   inorder(T->R,np);
}

void prntree ( tnode *T, int n )
{
   int np;

   printf("--- Preorder listing\n    ");
   np = 0; preorder(T->R,&np);
   if (n % 16) printf("\n");
   printf("--- Inorder listing\n    ");
   np = 0; inorder(T->R,&np);
   if (n % 16) printf("\n");
}

void childswap ( tnode *T )
{
   tnode *p;

   if (T == NULL) {
      fprintf(stderr, "*** Error in childswap(): empty tree\n");
      return;
   }
   p = T -> L;
   T -> L = T -> R;
   T -> R = p;
}

tnode *lrotate ( tnode *p )
{
   tnode *q, *RL;

   if (p == NULL) {
      fprintf(stderr, "*** Error in lrotate(): empty tree\n");
      return NULL;
   }
   q = p -> R;
   if (q == NULL) {
      fprintf(stderr, "*** Error in lrotate(): empty right subtree\n");
      exit(1);
      return p;
   }
   RL = q -> L;
   q -> L = p;
   p -> R = RL;
   return q;
}

tnode *rrotate ( tnode *p )
{
   tnode *q, *LR;

   if (p == NULL) {
      fprintf(stderr, "*** Error in rrotate(): empty tree\n");
      return NULL;
   }
   q = p -> L;
   if (q == NULL) {
      fprintf(stderr, "*** Error in rrotate(): empty left subtree\n");
      exit(1);
      return p;
   }
   LR = q -> R;
   q -> R = p;
   p -> L = LR;
   return q;
}

void makeskew ( tnode *T )
{
   tnode *p, *q;

   if (T == NULL) {
      fprintf(stderr, "*** Error in makeskew(): uninitialized tree\n");
      return;
   }
   p = T; q = T -> R;
   while (q) {
      while (q -> L) q = p -> R = rrotate(q);
      p = q;
      q = q -> R;
   }
}

void bsort ( tnode *T )
{
   int swapped;
   tnode *p, *q, *r;

   if (T == NULL) {
      fprintf(stderr, "*** Error in bsort(): uninitialized tree\n");
      return;
   }
   swapped = 1;
   while (swapped) {
      swapped = 0;
      p = T;
      q = p -> R;
      if (q == NULL) break;
      r = q -> R;
      while (r) {
         if (q -> key > q -> R -> key) {
            childswap(q);
            p -> R = rrotate(q);
            childswap(q);
            p = r;
            swapped = 1;
         } else {
            p = q;
            q = r;
         }
         r = q -> R;
      }
   }
}

void lunskew ( tnode *, int );
void runskew ( tnode *, int );

void lunskew ( tnode *p, int n )
{
   int i, nl, nr;
   tnode *q;

   if (n <= 2) return;
   nl = n / 2; nr = n - 1 - nl;
   q = p -> L;
   for (i=0; i<nr; ++i) q = q -> L;
   while (p -> L != q) p -> L = rrotate(p -> L);
   lunskew(q, nl);
   runskew(q, nr);
}

void runskew ( tnode *p, int n )
{
   int i, nl, nr;
   tnode *q;

   if (n <= 1) return;
   nl = n / 2; nr = n - 1 - nl;
   q = p -> R;
   for (i=0; i<nl; ++i) q = q -> R;
   while (p -> R != q) p -> R = lrotate(p -> R);
   lunskew(q, nl);
   runskew(q, nr);
}

int main ( int argc, char *argv[] )
{
   int n;
   tnode *T;

   srand((unsigned int)time(NULL));
   n = (argc > 1) ? atoi(argv[1]) : 100;
   printf("n = %3d\n\n", n);

   T = gentree(n);
   printf("\n+++ Initial tree\n"); prntree(T,n);

   makeskew(T);
   printf("\n+++ Tree made skew\n"); prntree(T,n);

   bsort(T);
   printf("\n+++ Tree after sorting\n"); prntree(T,n);

   runskew(T,n);
   printf("\n+++ Tree after rebalancing\n"); prntree(T,n);

   printf("\n");
   exit(0);
}