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

typedef struct {
   STACK F;
   STACK B;
} QUEUE;

QUEUE QINIT ()
{
   QUEUE Q;

   Q.F = SINIT();
   Q.B = SINIT();
   return Q;
}

QUEUE ENQUEUE ( QUEUE Q, int x )
{
   Q.B = PUSH(Q.B, x);
   return Q;
}

QUEUE DEQUEUE ( QUEUE Q )
{
   int x;

   if ((ISEMPTY(Q.F)) && (ISEMPTY(Q.B))) {
      fprintf(stderr, "*** Error in dequeue: Empty queue\n");
   } else {
      if (ISEMPTY(Q.F)) {
         while (!ISEMPTY(Q.B)) {
            x = TOP(Q.B);
            Q.B = POP(Q.B);
            Q.F = PUSH(Q.F, x);
         }
      }
      Q.F = POP(Q.F);
   }
   return Q;
}

void QPRN ( QUEUE Q )
{
   SPRNT2B(Q.F);
   SPRNB2T(Q.B);
}

int height ( TREE T )
{
   int lht, rht;

   if (T == NULL) return -1;
   lht = height(T -> L);
   rht = height(T -> R);
   return (lht >= rht) ? lht + 1 : rht + 1;
}

void traverse ( TREE T, int l, TREE *lvlhead, TREE *lvltail )
{
   if (T == NULL) return;

   /* Append node to the level-l list */
   if (lvlhead[l] == NULL) lvlhead[l] = lvltail[l] = T;
   else lvltail[l] = lvltail[l] -> N = T;

   /* Recurse on two subtrees */
   traverse(T->L, l+1, lvlhead, lvltail);
   traverse(T->R, l+1, lvlhead, lvltail);
}

/* Let h be the hright of T. The space usage of this function is θ(h). */
TREE SETN ( TREE T )
{
   TREE *lvlhead, *lvltail;
   int h, i;

   h = height(T);

   /* Initialize h+2 level-wise linked lists to empty */
   lvlhead = (TREE *)malloc((h+2)*sizeof(TREE));
   lvltail = (TREE *)malloc((h+2)*sizeof(TREE));
   for (i=0; i<=h+1; ++i) { lvlhead[i] = lvltail[i] = NULL; }

   /* Make traversal */
   traverse(T,0,lvlhead,lvltail);

   /* Join the lists */
   for (i=0; i<=h; ++i) lvltail[i] -> N = lvlhead[i+1];

   return lvlhead[0];
}

/* This is a constant-space implementation of SETN */
void SETNCS ( TREE T )
{
   TREE p, q;  /* Only two extra pointers are used */

   if (T == NULL) return;  /* Empty tree */

   /* First set the N link of the root */
   if (T -> L) T -> N = T -> L;
   else if (T -> R) T -> N = T -> R;
   else { T -> N = NULL; return; }

   /* Next keep on setting the N links of the two children of each node
      down the list. p is the pointer pointing to the node, the N pointers
      of whose children are to be set. The assumption is that the N
      pointer of p itself is already set. Now, comsider the three cases.

      Case 1:
      p has both children. Then, p -> L -> N should be p -> R. For setting
      p -> R -> N, use Case 2.

      Case 2:
      p has only one child or we are setting the N link of its right child.
      Then, the N link of that child should point to the first child of a
      node q such that:

      (i)   q follows p in the N-based linked list (q != p)
      (ii)  q is the first node after p in the N-based linked list to
            have a child
      (iii) If no such q exists, the N pointer of the concerned child of p
            will terminate the N list.

      Case 3:
      p has no children: Simply skip it

      This algorithm runs in O(n) time, because the pointers p and q never
      move backward in the N list.
   */

   p = q = T;        /* Start from the beginning */

   while (p) {       /* Iterate down the N list being built */
      if (p -> L) {  /* If p has a left child */
         if (p -> R) p -> L -> N = p -> R;  /* Case 1: p also has a right child */
         else {      /* Case 2: Find the suitable q */
            q = q -> N;
            while (q) {
               if (q -> L) { p -> L -> N = q -> L; break; }
               else if (q -> R) { p -> L -> N = q -> R; break; }
               else q = q -> N;
            }
            if (q == NULL) {
               p -> L -> N = NULL;
               break;
            }
         }
      }
      if (p == q) q = q -> N;
      if (p -> R) {  /* If p has a right child */
         while (q) { /* This is Case 2 again */
            if (q -> L) { p -> R -> N = q -> L; break; }
            else if (q -> R) { p -> R -> N = q -> R; break; }
            else q = q -> N;
         }
         if (q == NULL) {
            p -> R -> N = NULL;
            break;
         }
      }
      p = p -> N;  /* Done with p, go to the next node */
   }
}

void TPRNL ( TREE T )
{
   int i;

   i = 0;
   while (T) {
      if (i == 0) printf("    ");
      printf("%3d ", T -> key);
      T = T -> N;
      if (++i == 16) { printf("\n"); i = 0; }
   }
   if (i % 16) printf("\n");
}

int main ( int argc, char *argv[] )
{
   int n, nenq, ndeq, i, op, x;
   QUEUE Q;
   TREE T;

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

   registerme();

   printf("\n+++ Part 1\n");
   Q = QINIT();
   printf("\n    QINIT()      : Q = ["); QPRN(Q); printf(" ]\n");
   nenq = ndeq = 0;
   for (i=0; i<2*n; ++i) {
      if (nenq == n) op = 1;
      else {
         op = rand() % 2;
         if ((op == 1) && (nenq == ndeq)) op = 0;
      }
      if (op == 0) {
         x = 100 + rand() % 900;
         Q = ENQUEUE(Q,x);
         ++nenq;
      } else {
         Q = DEQUEUE(Q);
         ++ndeq;
      }
      if (op == 0) printf("    ENQUEUE(%3d) : Q = [", x);
      else printf("    DEQUEUE()    : Q = [");
      QPRN(Q);
      printf(" ]\n");
   }

   printf("\n+++ Part 2\n");
   T = TGEN(n);
   printf("\n--- Generated tree\n\n"); TPRN(T);
   SETN(T);
   printf("\n--- Level-by-level printing\n\n"); TPRNL(T);

   printf("\n+++ Part 2 (Constant Space)\n");
   T = TGEN(n);
   printf("\n--- Generated tree\n\n"); TPRN(T);
   SETNCS(T);
   printf("\n--- Level-by-level printing\n\n"); TPRNL(T);

   exit(0);
}