using namespace std;
#include <iostream>
#include "tree.h"

// AUXILIARY FUNCTIONS

static void print_spaces(int depth) {
  for(int i=0;i<depth;i++) 
      cout << "  ";
}

// MAIN FUNCTIONS


void init(tree & t) {
  t=NULL;
}

int nullp(const tree & t) {
  return (t==NULL);
}

retval insert(tree & t, char v) {
  if (t==NULL) {
    t = new node;
    if (t==NULL)
      return FAIL;
    t->item = v;
    t->left = NULL; 
    t->right = NULL; 
    return OK;
  }
  else if (v <= t->item) 
    return insert(t->left, v);
  else if (v > t->item) 
    return insert(t->right, v);
}

tree & cerca (tree & t,char elem) { 
  if ((t==NULL) || (elem==t->item))
    return t;
  if (elem <= t->item) 
    return cerca(t->left,elem);
  else if (elem > t->item)
    return cerca(t->right,elem);
}

void print_ordered(const tree & t) {
  if (!nullp(t)) {
    print_ordered(t->left);
    cout << t->item << endl;
    print_ordered(t->right);
  }
}

void print_indented(const tree & t) { 
  static int depth=0;
  depth++;
  if (!nullp(t)) {
    print_indented(t->right);
    print_spaces(depth);
    cout << t->item << endl;
    print_indented(t->left);
  }
  depth--;
}


/*******************************************************/

int size(tree t) {
  if(nullp(t))
    return 0;
  else
    return size(t->left) + size(t->right) + 1;
}

tree &min(tree &t) {
  if(nullp(t) || nullp(t->left))
    return t;
  else 
    return min(t->left);
}

tree &max(tree &t) {
  if(nullp(t) || nullp(t->right))
    return t;
  else 
    return max(t->right);
}


retval fill_hole(tree &hole) {
  if(nullp(hole))
    return FAIL;
  else if(nullp(hole->left)) {
    node *tmp = hole;
    hole = hole->right;
    delete tmp;
    return OK;
  } else if(nullp(hole->right)) {
    node *tmp = hole;
    hole = hole->left;
    delete tmp;
    return OK;
  } else if(size(hole->left)>size(hole->right)){
    tree &new_hole = max(hole->left);
    tree tmp = new_hole; 
    new_hole = new_hole->left; 
    hole->item = tmp->item;
    delete tmp;
    return OK;
  } else {
    tree &new_hole = min(hole->right);
    tree tmp = new_hole; 
    new_hole = new_hole->right; 
    hole->item = tmp->item;
    delete tmp;
    return OK;
  }
}


retval remove(tree& t, char c) {
  tree &hole = cerca(t,c);
  return fill_hole(hole);
}