/* program to demonstrate the use of binary trees
by C.J.Noble. Some changes carried out by R. Kay.  
*/

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

struct nodule { 
  char name[20];
  int mark;
  struct nodule *left;
  struct nodule *right;
};
typedef struct nodule node;

node *root, *item; 
node *getentry(void); 
node *insert(node*,node*); 
node *delete(node*,char*); 
node *rearrange(node*);

int menu(void);
void display(node*); 
void chop(char*);

int main(void){ 
  int notend=1;
  char student[20];
  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"); fflush(stdin);
        scanf("%s",student); chop(student); fflush(stdin);
        root=delete(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;
}

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);
    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);
}

void chop(char* strptr){ /* removes newline from end of string */
  int lenstr;  
  lenstr=strlen(strptr);
  if(strptr[lenstr-1] == '\n')
    strptr[lenstr-1] = '\0';
}

node *getentry(void){ /* creates node in inputs data */
  node *details; 
  details=(node*)malloc(sizeof(node));
  printf("\nenter name\n"); fflush(stdin);
  scanf("%s",details->name);
  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;
}

node *startwas; /* use of global variable to enable communication of
                   identity of rightmost node of left subtree between
		   delete() and rearrange(). This is considered to be
		   a fast and dirty hack which violates modular design
		   but which speeded development of the most
                   difficult part of this program. Suggest use of
                   an iterative function to identify the parent node of
                   the rightmost node of left subtree to refactor this bit. */

node *rearrange(node* leftsubtree){ 
        /* function to handle case where node has two branches */
  if (leftsubtree->right!=NULL) /* find rightmost node of leftsubtree */
    leftsubtree->right=rearrange(leftsubtree->right);
  else { /* replace node to be deleted by rightmost node */
    strcpy(startwas->name,leftsubtree->name);
    startwas->mark=leftsubtree->mark;
    startwas=leftsubtree;
    leftsubtree=leftsubtree->left;
  }
  return leftsubtree;
}

node *delete(node* start, char* entry){ 
        /* deletes node with name==entry*/
  int x;
  if (start==NULL){  /* key not in list */
    printf("not in the list\n");
    return start;
  }
  x=strcmp(start->name,entry); /* find the node */
  if (x>0) /* key is less than node */
    start->left=delete(start->left,entry);
  else if(x<0) /* key is greater than node */
    start->right=delete(start->right,entry);
  else { /* delete the node called start */
    startwas=start; /* used in free later */
    if(start->right==NULL)
      start=start->left;
    else if(start->left==NULL)
      start=start->right;
    else
      start->left=rearrange(start->left);
    printf("disposed of %s\n",entry);
    free(startwas);
  }
  return start;
}