/* program to demonstrate the use of binary trees.
 * Original code by C.J.Noble. Delete function refactored by 
 * R.Kay 29/1/2009 */

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

#define MAX_NAME 30

struct nodule { 
  char name[MAX_NAME];
  int mark;
  struct nodule *left;
  struct nodule *right;
};
typedef struct nodule NODE;

NODE *getentry(void); /* inputs node details */ 
NODE *insert(NODE* start,NODE* entry); /* inserts node */ 
void find_del(NODE** start,char *entry);  /* finds node to be deleted */
NODE **whichcase(NODE **start,int *dcase); /* reports deletion case 1 - 4 */
void delet(NODE **start,NODE **spare,int dcase); /* performs deletion */

int menu(void); /* shows menu gets option */
void display(NODE* start); /* displays records */ 
void pause(void); /* pauses output */
void chop(char *str); /* removes \n from input */

int main(void){ 
  NODE *root, *item; 
  int notend=1;
  char student[MAX_NAME];
  root =  NULL;
  do {
    switch (menu()){ /* select case based on return value of menu() */
      case 1: { /* insert */
        item=getentry();
        root=insert(root,item);
        break;
      } case 2: { /* delete */
	printf("\nenter name\n");
        fgets(student,MAX_NAME,stdin);
        chop(student);
        fflush(stdin);
        find_del(&root,student);
        break;
      } case 3: { /* display */
        if (root != NULL){
          printf("root name is %s\n\n",root->name);
          printf("  name            marks\n");
          printf("  ----            -----\n");
          display(root); /* getting a paged listing is a student exercise */
        } else  
          printf("the list is empty\n");
          break;        
      } case 4: notend=0; /* quit */ 
    }
  } while (notend);
  return 0;
}

void chop(char *str){
  int lenname;
  lenname=strlen(str);
  if(str[lenname-1] == '\n') /* strip \n */
    str[lenname-1] = '\0';
}

void pause(void){
  printf("press enter to continue\n");
  getchar();
  fflush(stdin);
}

int menu(void){ /* gets menu option from user */
  int choice;
  do {
    printf("1 insert record\n");
    printf("2 delete record\n");
    printf("3 display records\n");
    printf("4 end\n\n");
    printf("enter choice\n");
    scanf("%d",&choice);
    getchar(); /* fflush(stdin) ? */
  } while(choice<1 || choice>4);
  return choice;
}

void display(NODE *start){ /* displays all nodes in tree recursively */ 
  if(start->left!=NULL)
    display(start->left);
  printf("%-20s %5d\n",start->name,start->mark);
  if(start->right!=NULL)
    display(start->right);
}

NODE *getentry(void){ /* creates node in inputs data */
  NODE *details;
  details=(NODE*)malloc(sizeof(NODE));
  printf("\nenter name\n");
  fflush(stdin);
  fgets(details->name,30,stdin);
  chop(details->name);
  fflush(stdin);
  printf("\nenter mark\n");
  scanf("%d",&(details->mark));
  fflush(stdin);
  details->left=details->right=NULL;
  return details; /* returns location of node */
}

NODE *insert(NODE* start, NODE* entry){ /* inserts node in sorted position */
  if(start==NULL)
    start=entry; /* leaf node at this point in tree */
  else 
    if(strcmp(start->name, entry->name)>0) 
         /* if start point > entry point insert on left of start */
      start->left=insert(start->left, entry);
    else /* insert on the right */
      start->right=insert(start->right,entry);
  return start;
}

void find_del(NODE** start, char *entry){ 
        /* finds node to be deleted with name of entry*/
  NODE **spare=NULL; /* node to be freed */
  int x, dcase;
  if (*start==NULL){  /* key searched for not in list */
    printf("not in the list\n");
    return;
  }
  x=strcmp((*start)->name,entry); /* find the node */
  if (x>0) /* key is less than node */
    find_del(&((*start)->left),entry);
  else if(x<0) /* key is greater than node */
    find_del(&((*start)->right),entry);
  else { /* start contains data to be deleted */
    spare=whichcase(start,&dcase); /* report deletion case 1 - 4 */
    delet(start,spare,dcase); /* perform deletion */
    printf("disposed of %s\n",entry);
  }
  return;
}

void delet(NODE **start,NODE **spare,int dcase){
    NODE *tmp;
    tmp=*spare; /* so can free it later */
    if(dcase == 3 || dcase == 4) { /* relocate data from spare to start */
      strcpy((*start)->name,(*spare)->name);
      (*start)->mark=(*spare)->mark;
    }
    if((*start)->right==NULL){ /* cases 1 or 2 */
      *start=(*start)->left; /* NULL branch in case 1, link around in case 2 */
    } else if((*start)->left==NULL){ /* cases 1 or 2 */
      *start=(*start)->right; /* NULL branch in case 1, link around in case 2 */
    } else if(dcase==3){ /* RNLS is leaf, nullify its parent right link*/
      *spare=NULL;
    } else { /* dcase==4 RNLS has left branch, link around it */
      *spare=(*spare)->left;
    }
    free(tmp);
    return;
}

NODE **whichcase(NODE **start, int *dcase){ 
  /* reports deletion case 1 - 4. 
   * returns address of node to be deleted by ref. */
  NODE **tmp;
  /* dcase 1 */
  if( (*start)->left==NULL && (*start)->right==NULL){
    printf("case 1: leaf node\n");
    *dcase=1;
    return start;
  /* case 2 */ 
  } else if( (*start)->left==NULL || (*start)->right==NULL){
    printf("case 2: node with only 1 branch\n");
    *dcase=2;
    return start;
  } else { 
    /* find rightmost node of left subtree */
    tmp=&(*start)->left; /* looking at left subtree */
    while((*tmp)->right) /* go right until no right branch */
      tmp=&((*tmp)->right);
    if((*tmp)->left){
      printf("case 4: RNLS has a (left) branch \n");
      *dcase=4;
      return tmp;
    } else { 
      printf("case 3: RNLS is a leaf\n");
      *dcase=3;
      return tmp;
    }
  }
}