/* Time-stamp: <Mon Jan 17 2011 14:38:55 Stardate: Stardate: [-28]4307.84 hwloidl>

   Course: Parallel and Distributed Technology
   Class:  C Revision (Part 1)
   Example: tree structures in C

   Compile: gcc -g -o crev2 crev2.c
*/

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

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

/* externs */

/* types */
/* 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 */
void         showArr (int len, int *arr);
struct tree *mkTree(int from, int to, int *arr);
struct tree *readTree(FILE *fin, int n);
void         showTree(int n, struct tree *t);

/* code */
int main (int argc, char **argv) {
  struct tree *t, *ta, *tb;
  t = (struct tree *) malloc(sizeof(struct tree));

  /* build and show a 4-element tree */
  int a[4] = { 1, 2, 3, 4 };
  printf("Tree of consisting of these values:\n");
  showArr(4,a);
  ta = mkTree(0,3,a);
  showTree(0,ta);

  /* check command line */
  if (argc<2) {
    printf("Usage: %s <n1> ...\n", argv[0]);
    printf("       to build a tree, containing integers <n1> ...\n");
    exit(1);
  }

  if (argc>MAX) {
    printf("Can only take up to %d arguments\n", MAX);
    exit(1);
  }

  { /* nested scope */

    /* build and show a 4-element tree */
    int b[MAX];
    int i; /* local */
    printf("Constructing tree out of command line arguments ...\n");
    for (i=1; i<argc; i++) {  /* read tree elements from command line */
      b[i-1] = atoi(argv[i]); /* beware of indexing */
    }
    tb = mkTree(0, argc-2, b);/* build the tree */
    showTree(0, tb);
  }
  /* beware, b doesn't exist here any more */    
}

/* 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;
  }
}

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;
  }
  putc( '\n', stdout);
}

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