/*
* this program is to demonstrate tree serializations by serial representation or stream representations. 
* why? serialization is used to save a tree to a file 
* or to transfer it to another machine through network
* serialize in post-order for bottom up rebuilding 
* serialize in pre-order for top down rebuilding  
* HBF
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct tree_node
{
  int data;   // data can be redefined to any data type
  int count;  // this variable is hold the number of nodes in the tree for time efficiency
  struct tree_node *left;
  struct tree_node *right;
} tnode;
tnode *new_tnode(int data);
void print_tree(tnode *root, int space, int child);
void print_postfix(tnode *root);
void clean_tree(tnode **rootp);
int node_count(tnode *root);
void set_count(tnode *root);


typedef struct preserialtype {  // data structure for pre-order streaming
  int lc; // left subtree node count
  int rc; // right subtree node count
  int data;
} PRESERIAL;

typedef struct serialtype { // data structure for post-order streaming
  char deg;  //0: no child; 1:only left child; 2: only right child; 3: two child 
  int data;  
} SERIAL;

typedef struct node { // data structure for post-order queue representation
  char deg;  //0: no child; 1:only left child; 2: only right child; 3: two child 
  int data;  
  struct node *next;
} sqnode;

sqnode *new_sqnode(int deg, int data);
void display_forward(sqnode *start);
void clean(sqnode **startp);
sqnode *dequeue(sqnode **frontp, sqnode **rearp);
void enqueue(sqnode **frontp, sqnode **rearp, sqnode *np);
void push(sqnode **topp, sqnode *np);
sqnode *pop(sqnode **topp);

// auxiliary data structure for tree stack node, used in re-building tree from serial representation
typedef struct stnode {
  tnode *tnp; 
  int deg;  
  struct stnode *next;
} stnode;
void tpush(stnode **topp, tnode *tnp);
tnode *tpop(stnode **topp);

void serialize(tnode *root, sqnode **frontp, sqnode **rearp);
tnode *deserialize(sqnode *front);
void preserialize(tnode *root, PRESERIAL ps[], int *i);
tnode *depreserialize(PRESERIAL ps[], int nc);

int main() {
  tnode *np, *root = NULL;
  tnode *n1 = new_tnode(1);
  tnode *n2 = new_tnode(2);
  tnode *n3 = new_tnode(3);
  tnode *n4 = new_tnode(4);
  tnode *n5 = new_tnode(5);
  tnode *n6 = new_tnode(6);
  tnode *n7 = new_tnode(7);  
  n1->left = n2;
  n1->right = n3;
  n2->left = n4;
  n2->right = n5;
  n3->left = n6;
  n3->right = n7;
  
  root = n1;
  printf("tree style\n");
  set_count(root); // set the node count for each node in the tree, only used in pre-order serialization
  print_tree(root, 0, 3);
  
  printf("\npost-order serialization in queue representation\n");
  sqnode *front = NULL, *rear = NULL;
  serialize(root, &front, &rear);
  display_forward(front);
  
  int nc = node_count(root);
  printf("\nnode count: %d\n", nc); 
  
  printf("\nqueue to array/stream\n");
  SERIAL ts[nc], *p = &ts[0];
  sqnode *sqp = front;
  while (sqp) {
  p->deg = sqp->deg;  
  p->data = sqp->data; 
    p++;
    sqp = sqp->next;  
  }
  int i;
  for (i=0; i<nc; i++)
    printf("[%d,%d]", ts[i].deg, ts[i].data);  
  
  tnode *root1 = deserialize(front);
  set_count(root1);
  printf("\ndeserialize from queue representation\n");
  print_tree(root1, 0, 3);
  
  
  printf("\npre-order serialization in array/stream representation\n");
  PRESERIAL ps[nc];
  int j=0, k;
  preserialize(root, ps, &j);
  for (k=0; k<nc; k++)
  printf("[%d,%d,%d]", ps[k].lc, ps[k].rc, ps[k].data);
  
  printf("\ndeserialize from array representation\n");
  tnode *root2 = depreserialize(ps, nc);
  print_tree(root2, 0, 3);
  
  printf("\nclean up\n");
  clean(&front);
  clean_tree(&root);
  clean_tree(&root1);
  clean_tree(&root2);
  
  printf("\ndone\n");  
  
  return 0;
}

tnode *new_tnode(int data)
{
  tnode *np = (tnode *) malloc(sizeof(tnode));
  if (np == NULL) return NULL;
  np->data = data;  
  np->left = NULL;
  np->right = NULL;
  return np;
}

void print_tree(tnode *root, int prelen, int child) {
  int i;
  if (root != NULL) {
    for (i=0; i < prelen; i++) 
       printf("%c", ' ');
    if (child == 0)
    printf("%s", "l___");
    else if (child == 1)
     printf("%s", "r___");
    else
     printf("%s", "|___");
    printf("%d,%d\n", root->data, root->count);
    print_tree(root->right, prelen+4, 1);
    print_tree(root->left, prelen+4, 0);  
  }
}

int node_count(tnode *root) {
   if (root == NULL) return 0;
   else if (root->left == NULL && root->right == NULL) return 1;
   else return 1+node_count(root->left) + node_count(root->right);   
}

void set_count(tnode *root) {
   if (root != NULL) {
     root->count = 1;
     if (root->left)  { set_count(root->left); root->count += root->left->count;}
     if (root->right) { set_count(root->right);root->count += root->right->count;}
   }   
}

void clean_tree(tnode **rootp) {
  tnode *root = *rootp;
  if (root) {
    if (root->left)
      clean_tree(&root->left);
    if (root->right)
      clean_tree(&root->right);
    free(root);
  }
  *rootp = NULL;
}


void print_postfix(tnode  *root) {
  if (root) {
      print_postfix(root->left);
      print_postfix(root->right);

      printf("%d ", root->data);
  }
}

// convert post-order serial queue representation to tree representation
// return the root of the tree
tnode *deserialize(sqnode *p) { 
  stnode *top = NULL;
  tnode *t, *t1, *t2; 
  while (p) {
    if ( p->deg == 0)  
    { 
      t = new_tnode(p->data); 
      tpush(&top, t); 
    } 
    else if ( p->deg == 1)  
    { 
      t = new_tnode(p->data); 
      t1 = tpop(&top); 
      t->left = t1; 
      tpush(&top, t); 
    }
    else if ( p->deg == 2)  
    { 
      t = new_tnode(p->data); 
      t1 = tpop(&top); 
      t->right = t1; 
      tpush(&top, t);  
    }
    else if ( p->deg == 3)  
    { 
      t = new_tnode(p->data); 
      t1 = tpop(&top); 
      t2 = tpop(&top); 
      t->right = t1; 
      t->left = t2; 
      tpush(&top, t); 
    }
    p = p->next;    
  } 
  t = tpop(&top); 
  return t; 
} 

// convert pre-order serial array representation to tree representation
// return the root of the tree
tnode *depreserialize(PRESERIAL ps[], int nc) {
  stnode *top = NULL; // stack to remember the path from root to working node
  tnode *t = NULL;    // pointer to newly created tnode 
  
  int i = 0, deg;
  for (i = 0; i< nc; i++) 
  {
    //create a new tnode
	t = new_tnode(ps[i].data); 
    t->count = 1 + ps[i].lc + ps[i].rc;
    t->left = NULL;
    t->right = NULL;
    
	// set the initial deg value for stack node 
	// the deg variable holds the tnode linking status
    deg = 0;
    if (ps[i].lc >0 && ps[i].rc == 0)
      deg = 1;
    else if (ps[i].lc == 0 && ps[i].rc > 0)
      deg = 2;
    else if (ps[i].lc > 0 && ps[i].rc > 0)
      deg = 3;  
 
	if (top) {
	  // pop till a node which needs to link to the new tnode 	
      while (top->deg == 0 || top->deg == 4 || top->deg == 5 || top->deg == 7)
        tpop(&top);
    
      if (top == NULL) ;  // do nothing if empty stack
      else if (top->deg == 1) { // only need to link the left child
        top->deg = 4;           // reset linking status to 4
        top->tnp->left = t;     // link to the left child
      }
      else if (top->deg == 2) { // only need to link the right child
        top->deg = 5;          
        top->tnp->right = t;    
      }
      else if (top->deg == 3) { // need to link the left child
        top->deg = 6;          
        top->tnp->left = t;
      }
      else if (top->deg == 6) { // need to link the right child 
        top->deg = 7;          
        top->tnp->right = t;
      }
	}
    tpush(&top, t);   // push the tnode pointer to stack
    top->deg = deg;   // set the linking status of the new tnode
  } 

  //pop stack to the last element to get the root of the tree
  while (top && top->next != NULL)   
    tpop(&top);

  return tpop(&top);   
}
  

sqnode *new_sqnode(int deg, int data) {
  sqnode *np = (sqnode *) malloc(sizeof(sqnode));
  np->deg = deg; 
  np->data = data;  
  np->next = NULL;
  return np;
}

void push(sqnode **topp, sqnode *np) {
  if (*topp == NULL) {
    *topp = np;
    np->next = NULL;
  }
  else {
    np->next = *topp;
    *topp = np;
  }
}

sqnode *pop(sqnode **topp) {
  if (*topp) {
    sqnode *tmp = *topp;
    *topp = tmp->next;
    tmp->next = NULL;
    return tmp;
    
  } else 
  return NULL;
}

void enqueue(sqnode **topp, sqnode **bottom, sqnode *np) {
  if (*topp == NULL) {
    *topp = np;
    *bottom = np;
    np->next = NULL;
  }
  else {
    (*bottom)->next = np;
    *bottom = np;  
  }
}  

sqnode *dequeue(sqnode **frontp, sqnode **rearp) {
  sqnode *ptr = *frontp;
  if (ptr == NULL) return NULL;
  if (ptr == *rearp) {
    *frontp = NULL;
    *rearp = NULL;
  } 
  else {
    *frontp = ptr->next;    
  } 
  return ptr; 
}

void clean(sqnode **topp) {
  sqnode *curr = *topp;
  while (curr) {
    sqnode *tmp = curr;
    curr = curr->next;
    free(tmp);
  }
  *topp = NULL;
}

void tpush(stnode **topp, tnode *tnp) {
  stnode *stnp = (stnode *) malloc(sizeof(stnode));
  stnp->tnp = tnp;
  
  if (*topp)
  stnp->next = *topp;
  else 
  stnp->next = NULL;
  
  *topp = stnp;
}

tnode *tpop(stnode **topp) {
  if (*topp == NULL ) return NULL;
  else {
  stnode *p = *topp;
  tnode *tp = p->tnp;
  *topp = p->next;
  free(p);
  return tp;
  }
}

void serialize(tnode *root, sqnode **frontp, sqnode **rearp) {
  if (root) {  
   serialize(root->left, frontp, rearp);
   serialize(root->right, frontp, rearp); 
   int deg = 0;
   if (root->left != NULL && root->right == NULL)
     deg = 1;
   else if (root->left == NULL && root->right != NULL) 
     deg = 2;
   else if (root->left != NULL && root->right != NULL) 
    deg = 3;

   enqueue(frontp, rearp, new_sqnode(deg, root->data));  
  }
}

void preserialize(tnode *root, PRESERIAL ps[], int *ip) {
  if (root) {
    int i = *ip;
    ps[i].lc = 0;
    ps[i].rc = 0;
    ps[i].data = root->data;
    *ip = *ip+1;
    if (root->left) {
      ps[i].lc = root->left->count;  
      preserialize(root->left, ps, ip);
    }
    if (root->right) {
      ps[i].rc = root->right->count;  
      preserialize(root->right, ps, ip);
    }
  }
}

void display_forward(sqnode *front) {
  while (front) {
    printf("(%d,%d)", front->deg, front->data);
    front = front->next;
  }
}  


/*
tree style
|___1,7
    r___3,3
        r___7,1
        l___6,1
    l___2,3
        r___5,1
        l___4,1

post-order serialization in queue representation
(0,4)(0,5)(3,2)(0,6)(0,7)(3,3)(3,1)
node count: 7

queue to array/stream
[0,4][0,5][3,2][0,6][0,7][3,3][3,1]
deserialize from queue representation
|___1,7
    r___3,3
        r___7,1
        l___6,1
    l___2,3
        r___5,1
        l___4,1

pre-order serialization in array/stream representation
[3,3,1][1,1,2][0,0,4][0,0,5][1,1,3][0,0,6][0,0,7]
deserialize from array representation
|___1,7
    r___3,3
        r___7,1
        l___6,1
    l___2,3
        r___5,1
        l___4,1

clean up

done
*/