/*Source Code From Laure Gonnord and Bernard Carré*/

#include "trees.h"

// construction of a tree
Tree cons(int val, Tree left, Tree right) {
  PtNode new = (PtNode)malloc(sizeof(Node));
  new->val=val;
  new->left=left;
  new->right=right;
  return new;
}

// create an empty tree
Tree mkEmptyTree(){
  return NULL;
}

// t is empty?
bool isEmpty (Tree t) {
  return t==NULL;
}

// t is a leaf?
bool isLeaf (Tree t) {
  return (!isEmpty(t) && isEmpty(t->left) && isEmpty(t->right));
}

// add x in a bst wtr its value.
void add(Tree *p_t, int x) {
    if (*p_t == NULL) {
        *p_t = cons(x, NULL, NULL);
    } else if (x <= (*p_t)->val) {
        add(&(*p_t)->left, x);
    } else {
        add(&(*p_t)->right, x);
    }
}

// build a tree "add"ing values of the file fp
void load_tree(FILE *fp, Tree *p_t) {
    int val;
    while (!feof(fp)) {
        fscanf(fp, "%d ", &val);
        add(p_t, val);
    }

}

// print values of t in ascendant order (left-value-right)
void print_lvr (Tree t) {
    if (t != NULL) {
        print_lvr(t->left);
        printf("%d ", t->val);
        print_lvr(t->right);
    }
}

//Section 1.5
void print_rec_edges(Tree t){
    if (t != NULL) {
        if (t->left != NULL) {
            printf("%d %d\n", t->val, t->left->val);
            print_rec_edges(t->left);
        }
        if (t->right != NULL) {
            printf("%d %d\n", t->val, t->right->val);
            print_rec_edges(t->right);
        }

    }
}

//PART II

// pre: !isEmpty(t) & !isLeaf(t)
// recursively prints arcs of the tree <value,left,right> into the file fp:
// "value -> left;" if exist
// "value -> right;" if exist
// to do...
void recursive_dot(Tree t, FILE *fp) {
    if (t != NULL) {
        if (t->left != NULL) {
            fprintf(fp, "    %d -> %d;\n", t->val, t->left->val);
            recursive_dot(t->left, fp);
        }
        if (t->right != NULL) {
            fprintf(fp, "    %d -> %d;\n", t->val, t->right->val);
            recursive_dot(t->right, fp);
        }

    }
}


// generate a .dot file for the tree
// limits (no arcs) :
//   isEmpty(t) => "empty" digraph
//   isLeaf(t) => only one node
// general case :
//   calls recursive_dot which prints arcs
void generate_dot (Tree t, FILE *fp) {
  fprintf (fp, "digraph G {\n");
  if (!isEmpty(t)) {
    if (isLeaf(t)) {
      fprintf(fp, "\t%d", t->val);
    } else {
      recursive_dot(t,fp);
    }
  }
  fprintf (fp, "}\n");
}