/* Course: Parallel and Distributed Technology
   Class:  C Revision (Part 1)
   Exercise 2: tree operations, using tree type from above class

  2a: Write a function that checks, whether a tree is balanced.
  2b: Write a function \ttt{struct node *readTree(FILE *fin, int n)}
   that reads \ttt{n} integer values from a file and builds a balanced tree.
  2c: Write a function \ttt{void insert(struct node *t, int n)} that
   inserts a value \ttt{n} into a tree, whose leaves are sorted in
   ascending order.
  2d: For an input array of length $n$, how much space does such a tree consume?
  2e: Change the tree data structure, to use a more efficient
   representation of the \ttt{tag}.

*/

/* includes */
#include <stdio.h>
#include <stdlib.h>

/* max number of arguments to read from the command line */
#define MAX 99

/* externs */

/* types */
typedef enum { False = 0, True = 1 } Bool;
/* enumeration of possible tags of type int  */
/* Exercise: use a less wasteful representation */
typedef enum { Leaf = 0, Branch = 1 } Tag;
/* define composition of a branch */
struct branch {struct tree *left, *right;};
/* define alternatives of a node */
union node {struct branch b; int value;};
/* define a tree as a tagged node */
struct tree { Tag tag; union node n; };

/* prototypes */
struct tree *mkTree(int from, int to, int *arr);
struct tree *readTree(FILE *fin, int n);
void         showTree(int n, struct tree *t);
Bool         insert(struct tree *t, int n);
Bool         isBalanced(struct tree *t);
void         showArr (int len, int *arr);

/* inlining (small) functions generates more efficient code */
static inline int          max(int m, int n);

/* code */
int main (int argc, char **argv) {
  struct tree *t, *t1;
  FILE * fd;

  if (argc<3) {
    printf("Usage: %s <FILE> <N> ...\n", argv[0]);
    printf("       to build a tree, containing integers in file <FILE>, then inserting <N> into the tree ...\n");
    exit(1);
  }

  /* build and show a 4-element tree */
  int a[4] = { 1, 2, 4, 8 };
  t = mkTree(0,3,a);
  printf("Tree containing these values\n");
  showArr(4,a);
  printf("is:\n");
  showTree(0,t);
  printf("This tree is %s balanced\n", (isBalanced(t)) ? "" : "NOT");

  printf("Reading tree from file %s ...\n", argv[1]);
  fd = fopen(argv[1], "r");
  t1 = readTree(fd, 5);
  fclose(fd);

  showTree(0,t1);
  printf("This tree is %s balanced\n", (isBalanced(t1)) ? "" : "NOT");

  { int i = 2; /* index of first element to insert */
    int x;
    
    while (i<argc) {
      x = atoi(argv[i]);
      printf("Inserting value %d in this tree ...\n", x);
      insert(t1,x);
      showTree(0,t1);
      printf("This tree is %s balanced\n", (isBalanced(t1)) ? "" : "NOT");
      i++;
    }
  }
  // printf("depth of left subtree: %d\n", depth(t1->n.b.left));
  // printf("depth of right subtree: %d\n", depth(t1->n.b.right));

  return 0;
}

/* build a balanced tree from an array segment */
struct tree *
mkTree(int from, int to, int *arr) {
  if (from>to) {
    return (struct tree *)NULL;
  } else if (from==to) {
    struct tree *t;
    t = (struct tree *) malloc(sizeof(struct tree));    
    t->tag = Leaf; 
    t->n.value = arr[from];
    return t;
  } else {
    struct tree *t, *left, *right;
    int mid = (from + to) / 2;
    t = (struct tree *) malloc(sizeof(struct tree));    
    left  = mkTree(from,mid,arr);
    right = mkTree(mid+1,to,arr);
    t->tag = Branch;
    t->n.b.left = left;
    t->n.b.right = right;
    return t;
  }
}

static inline int
max(int m, int n) { return (m>n) ? m : n; }

int
depth(struct tree *t) {
  switch (t->tag) {
  case Leaf: return 1;
  case Branch: return 1+(max(depth(t->n.b.left), depth(t->n.b.right)));
  default: exit(1); // error
  }
}

Bool
isBalanced(struct tree *t) {
  switch (t->tag) {
  case Leaf: return 1;
  case Branch: return (abs(depth(t->n.b.left)-depth(t->n.b.right))<=1);
  default: exit(1); // error
  }
}

Bool
insert(struct tree *t, int n) {
  switch (t->tag) {
  case Leaf: 
    if (t->n.value < n) { // backtrack
      return False; // didn't add value
    } else { // insert value, by generating a branch
      int val = t->n.value;
      struct tree *t_left, *t_right;
      /* new leaf, containing the value being inserted */
      t_left = (struct tree *) malloc(sizeof(struct tree));    
      t_left->tag = Leaf; 
      t_left->n.value = n;
      /* new leaf, with current value  */
      t_right = (struct tree *) malloc(sizeof(struct tree));    
      t_right->tag = Leaf; 
      t_right->n.value = val;
      /* update current node */
      /* luckily a (struct node) contains enough space for a Branch */
      /* otherwise this would corrupt the memory */
      t->tag = Branch;
      t->n.b.left = t_left;
      t->n.b.right = t_right;
      return True; // added value
    }      
    break;
  case Branch:
    if (insert(t->n.b.left,n)) {
      return True;
    } else {
      return insert(t->n.b.right,n);
    }
    break;
  default: exit(1); // error
  }
}

void
showTree(int n, struct tree *t) {
  int i;
  for (i=0; i<n; i++)
    putc( ' ', stdout);
  switch (t->tag) {
  case Leaf: 
    printf("%d", t->n.value);
    break;
  case Branch:
    putc( '.', stdout);
    putc( '\n', stdout);
    showTree(n+1, t->n.b.left);
    showTree(n+1, t->n.b.right);
    break;
  default: exit(1); // error
  }
  putc( '\n', stdout);
}

struct tree *
readTree(FILE *fin, int n) {
 int i;
 int a[MAX];

 for(i=0;i<n;i++)
   fscanf(fin,"%d",&a[i]);

 return mkTree(0, n-1, a);
}

struct tree *
readTree0(FILE *fin) {
 int n;
 int i;
 int a[MAX];

 fscanf(fin,"%d",&n); // number of values
 for(i=0;i<n;i++)
   fscanf(fin,"%d",&a[i]);

 return mkTree(0, n, a);
}

void showArr (int len, int *arr) {
  int i;
  printf("Array at %p: \n", arr);
  for (i=0; i<len; i++) {
    printf("%d: %d\n", i, arr[i]);
  }
}