#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct btree_struct {
  char key[255], data[255];
  struct btree_struct *left, *right;
  };

typedef struct btree_struct btree;

int getData(char* k, btree *node, char **d);
int insert(char* k, char* d, btree **node);
int delete(char* k, btree **node);
void printMenu();
char chooseCmd();

int main(){
  btree *root = NULL;
  char* n;
  int ok;
  char name[50];
  char phonenumber[50];
  
  char* phonen = phonenumber;
  int stop = 0;
  while (!stop)
  {
    printMenu();
    switch ((unsigned int) chooseCmd())
    {
      case 'a':
	    printf("Please enter the name: ");
	    scanf("%s",&name);
		printf("Please enter the number: ");
		scanf("%s",&phonenumber);
		ok = insert(name, phonenumber, &root);
		printf("%s added: %d\n", name, ok);
        break;
      case 'r':
        printf("Please enter the name: ");
	    scanf("%s",&name);
		ok = delete(name, &root);
        break;
      case 's':
        {
          printf("Please enter the name: ");
	      scanf("%s",&name);
		  ok = getData(name, root, &phonen);
		  if(ok) {
			printf("%s has number %s.\n", name, phonen);
		  } else {
			printf("%s was not found.\n", name);
          }
		  break;
        }
      case 'q':
        stop = 1;
        break;
      default:
        break;
    }
  }

  return 0;
}

void printMenu()
{
  fprintf(stdout,"\n*** List Menu ****************************\n");
  fprintf(stdout, "*  [a] Add an entry to the phonebook      *\n");
  fprintf(stdout, "*  [r] Remove an entry from the phonebook *\n");
  fprintf(stdout, "*  [s] Search an entry from the phonebook *\n");
  fprintf(stdout, "*  [q] Quit the program                   *\n");
  fprintf(stdout, "*******************************************\n");
  fprintf(stdout,"\n");
}

char chooseCmd()
{
  char c = '\0';
  char* s = NULL;
  do
  {
    fprintf(stdout, "Make your selection: ");
    while ((c = getchar()) == '\n');
  } while ( !strchr("arsq",c) );
  printf("char %c\n",c);
  return c;
}



/*
 * Checks whether a given key k occurs in the tree starting at node, and
 * returns the respective data element.
 * Parameters:
 *  key: key to search for
 *  node: of tree to be checked
 *  d: pointer to an integer, filled with data if k found
 * Returns: 1 if the respective key was found, 0 otherwise
 */ 
int getData(char* key, btree *node, char** d){
  int comparison = 0;
  if (node == NULL) { /* not found */
    d = NULL; 
    return 0;
    }
  else if (!(comparison = strcmp(node->key,key))) { /* key found */
    *d = node->data;
    return 1;
    }
  else if (comparison < 0) /* if key occurs, it must be in right subtree */
    return getData(key, node-> right, d);
  else /* if key occurs, it must be in left subtree */
    return getData(key, node-> left, d);
}

/*
 * Inserts the pair (k, d) into the tree starting at node.
 * Parameters:
 *  k: key to be inserted
 *  d: respective data
 *  node: root of the subtree where the element should be added
 * Returns: 0 if an element with this key already exists, and the new
 *          element was not added; 1 otherwise.
 */
int insert(char* k, char* d, btree **node) {
  int comparison = 0;
  btree *n = *node, *newnode = NULL, *parent = NULL;

  /* create new node */
  newnode = (btree*) malloc(sizeof(btree));
  strcpy(newnode->key,k);
  strcpy(newnode->data,d);

  /* search for place to insert */
  while (n != NULL) {
    if (!(comparison = strcmp(n->key, k))) {/* key already exists -> fail */
      return 0;
    } else { 
      parent = n;
      if (comparison < 0)
        n = n->right;
      else
        n = n->left; 
      }
  }
  if (parent == NULL) /* insert at root */
    *node = newnode;
  else /* attach as child node */
  if (parent->key < k)
    parent->right = newnode;
  else
    parent->left = newnode;
  return 1;
}

/*
 * Deletes the key k in the tree starting at node.
 * Parameters:
 *  k: key to be inserted
 *  node: root of the subtree where the element should be added
 * Returns: 0 if the key was  not found; 1 otherwise.
 *          The subtree of node is altered such that k is removed.
 */
int delete(char* k, btree **node) {
  int comparison;
  btree *n = *node, *parent = NULL;

  /* search for key in tree */
  while ((n != NULL) && ((comparison = strcmp(n->key,k)) != 0)) {
    parent = n;
    if (comparison < 0) {
      n = n->left;
    } else if (comparison > 0) {
      n = n->right; 
    }
  }

  /* if key was not found, fail */
  if (n == NULL) 
    return 0;

  /* otherwise, n is the node to be deleted */
  /* special case 0: delete root in a single-node tree */
  if (parent == NULL) {
    *node = NULL;
  /* easy case 1: no left child */
  } else if (n->left == NULL)
    if (k <= parent->key)
      parent->left = n->right;
    else
      parent->right = n->right;
  /* easy case 2: no right child */
  else if (n->right == NULL) {
    if (k <= parent->key)
      parent->left = n->left;
    else
      parent->right = n->left;
  /* case 3: n is inner node */
  } else {
    /* search predecessor node pred */
    btree *pred = n->left;
    btree *pred_parent = n;
    while (pred->right != NULL){
      pred_parent = pred;
      pred = pred->right;
    }
    /* pred is direct predecessor of n in tree */
    pred_parent->right = NULL; /* delete pred at original place */
    /* copy pred key and data to n */
    strcpy(n->key,pred->key);
    strcpy(n->data,pred->data);
  } 
  return 1;   
}