/* 
 * Code example for CP264 Data Structures II
 * min-heap by linked binary tree representation
 * HBF
*/
#include <stdio.h>
#include <stdlib.h>

/* heap node structure for complete binary tree representation */
typedef struct btnode {
  int key;      // the key 
  int data;     // the data 
  struct btnode *left;
  struct btnode *right;
} tnode;

tnode *new_node(int key, int data);
void insert(tnode **rootp, int *count, tnode *x);
void delete(tnode **rootp, int *count);

/* stack structure is used to remember the root to current node for the heapify up operation */
typedef struct stnode {
  tnode *tnp;
  struct stnode *next;
} snode;
void push(snode **topp, tnode *pdata); 
void pop(snode **topp);
void clean_stack(snode **topp);

void print_tree(tnode*, int);
void clean_tree(tnode**);

int main() {
  tnode *root = NULL;
  int count = 0;
  
  printf("min-heap by linked binary tree representation\n");
  int i;
  for (i=0; i<16; i++) {
   insert(&root, &count, new_node(i, i*i));
  }
  printf("complete binary tree after heap insertions\n");
  print_tree(root, 0);
  
  for (i=0; i<8; i++) {
     delete(&root, &count);
  }
  printf("complete binary tree after heap deletion (delete min)\n");
  print_tree(root, 0);
  
  clean_tree(&root);
  return 0;
}

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

void insert(tnode **rootp, int *countp, tnode *x) {
  int count = *countp;
  int key = x->key;
  int data = x->data;
  
  if (count == 0) {
    *rootp = x;  
    *countp = 1;
  }
  else {
    tnode *root = *rootp;  
    int g[20] = {0};
    int len = 0;
    while (count > 0) {
      g[len] = count % 2;
      len++;
      count = (count - 1) /2;      
    }

    snode *top = NULL;
    push(&top, root);
	
	//get the path code to the new insert position
    int i;
    for (i=len-1; i>0; i--) {
      if (g[i] == 1) {
        root = root->left;
      }
      else {
        root = root->right;     
      }
      push(&top, root);
    }    
     
    // link x to the parent 	 
    if (g[0] == 1) 
       top->tnp->left = x;
    else 
      top->tnp->right = x;

    //heapify up
    tnode *y = x;   
    while (top && top->tnp->key < key) {
	  // simple swap by value copying
      y->key = top->tnp->key;
	  y->data = top->tnp->data;
	  
      top->tnp->key = key;
	  top->tnp->data = data;
	  
	  // it's better to swap the nodes by re-linking
	  
      y = top->tnp;
      pop(&top);
    } 
    clean_stack(&top);
     
    *countp = *countp + 1;
  }
}

void delete(tnode **rootp, int *countp) {
  tnode *root = *rootp;  
  if (root == NULL) return;
  
  int count = *countp - 1;
  int key;
  int data;  
  
  //get the path code to the last node
  int g[20] = {0};
    int len = 0;
    while (count > 0) {
    g[len] = count % 2;
    len++;
    count = (count - 1) /2;      
  }
   
   // find the parent of last node   
  tnode *x = root;
  int i;
  for (i=len-1; i>0; i--) {
    if (g[i] == 1) {
      x = x->left;
    }
	else {
      x = x->right;     
    }
  }  
    
   // find the last node, get its value and delete it
  tnode *y;
  if (g[0] == 1) {
    y = x->left;
	x->left = NULL;
  } else {
    y = x->right;
    x->right = NULL;
  }
  
  key = y->key;
  data = y->data;
  
  free(y);  
  
  //reset the root key and data
  (*rootp)->key = key;
  (*rootp)->data = data;
  
  // heapify down  
  y = *rootp;    
  int a, b, c; // variables for key comparing
  while (y && (y->left || y->right) ) {
    if (y->left && y->right) {
      a = y->left->key;
      b = y->right->key;
      c = (a<b)? b:a;
                     
      if (key < c) {
        
        if (c == a) {
		  // swap with left child	
		  y->key = c; 
		  y->data = y->left->data;
		  
          y->left->key = key;
		  y->left->data = data;
		  
		  // move to left child
          y = y->left;
        } 
        else {
		  // swap with right child	
		  y->key = c; 
		  y->data = y->right->data;	
          
		  y->right->key = key;
		  y->right->data = data;
          
		  // move to right child
		  y = y->right;
        }        
      }
      else
        break;       
    } 
    else {  // only have left child
      if ( key < y->left->key ) {
		// swap   
        y->key = y->left->key;
		y->data = y->left->data;
		
        y->left->key = key;
		y->left->data = data;
		
		// move to left child
        y = y->left;
       }
       else 
         break;
    }
  }    
 
  *countp = *countp - 1;   
}

// stack functions adapted and modified from a6q3
void push(snode **topp, tnode *pdata) {
  snode *snp = (snode*) malloc(sizeof(snode));
  snp->tnp = pdata;
  snp->next = NULL;
  if (*topp == NULL) {
    *topp = snp;
  } else {
    snp->next = *topp;
    *topp = snp;
  }
}

void pop(snode **topp) {
  if (*topp != NULL) {
      snode *snp = *topp;
    *topp = snp->next;
    free(snp);
  }
}

void clean_stack(snode **topp) {
  snode* snp = *topp, *temp;
  while (snp != NULL) { 
    temp = snp; 
    snp = snp -> next;
    free(temp);
  }
  *topp = NULL;
}

// recursive algorithm
void print_tree(tnode *root,  int prelen) {
  int i;
  if (root != NULL) {
    for (i = 0; i < prelen; i++)
      printf("%c", ' ');
    printf("%s", "|___");
    printf("%d %d\n", root->key, root->data);
    print_tree(root->right, prelen + 4);  
    print_tree(root->left, prelen + 4);
  }
}

// recursive algorithm
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;
}


/*
min-heap by linked binary tree representation
complete binary tree after heap insertions
|___15 225
    |___13 169
        |___12 144
            |___11 121
            |___4 16
        |___10 100
            |___5 25
            |___1 1
    |___14 196
        |___8 64
            |___7 49
            |___2 4
        |___9 81
            |___3 9
            |___6 36
                |___0 0
complete binary tree after heap deletion (delete min)
|___7 49
    |___5 25
        |___4 16
        |___1 1
    |___6 36
        |___2 4
        |___3 9
            |___0 0
*/