#include <stdio.h>
#include <stdlib.h>
#include "bst.h"
#include "bst-int.h"


int initBST (bst **tree, int (*printfn) (const void *), 
                         int (*comparefn) (const void *, const void *)) {

  if (!comparefn) return BAD_COMPARE_BST;

  *tree = malloc (sizeof(bst));
  (*tree)->root = NULL;
  (*tree)->count = 0;
  
  (*tree)->printfn = printfn;
  (*tree)->comparefn = comparefn;

  return 0;
}


int addBST (bst *tree, const void *item) {

  node *index;
  node *newnode;
  int difference;
  int posnfound;

  /* Preflight */
  if (!tree) return NULL_BST;
  if (!item) return NULL_ITEM_BST;
  
  
  
  /* Special case: Empty tree */
  if (!tree->count) {
    tree->root = malloc (sizeof(node));
    tree->root->item = (void *)item;
    tree->root->left = tree->root->right = NULL;
    
    tree->count = 1;
    
    return 0;
  }
      
   for (index=tree->root, posnfound=0; (!posnfound);         )   {
  
    difference = tree->comparefn (index->item, item);
    switch (difference) {

      case MATCH: return DUPLICATE_ITEM_BST;
    
      case LEFT: if (index->left) index=index->left;
                 else posnfound=1;
                 break;
               
      case RIGHT: if (index->right) index=index->right;
                  else posnfound=1;
                  break;
  
      default: fprintf (stderr, 
         "addBST: Compare function didn't return LEFT, RIGHT, or MATCH\n");
         return BAD_COMPARE_BST;
    }
  }

  /* Actually add the node here */
  newnode = malloc (sizeof(node));
  newnode->item = (void *)item;
  newnode->left = newnode->right = NULL;
  
  if (RIGHT == difference)
    index->right = newnode;
  else
    index->left = newnode;
    
  tree->count++;
  

  return 0;

}

int printBST (const bst *tree) {

  if (!tree) return NULL_BST;
  
  return printRecursiveBST(tree, tree->root);
  
}

static int printRecursiveBST (const bst *tree, const node *root) {

  if (!root) return 0;
  
  /* Go left */
  if (root->left)
    printRecursiveBST(tree, root->left);
  
  tree->printfn (root->item);
  
  /* Go right */
  if (root->right) 
    printRecursiveBST(tree, root->right);
    
  return 0;
  


}