//  main.c
//  trees
//
//  Created by Mahmoud ElMarakshy on 4/28/13.
//  Copyright (c) 2013 Mahmoud ElMarakshy. All rights reserved.
//

#include<stdio.h>
#include<stdio.h>
#include <ctype.h>

struct node{
    char * data;
    struct node *left;
    struct node *right;
    char * id;
    
}*root=NULL,*root2=NULL,*temp;
struct node* insert(struct node *root,char x[],char id[]);
struct node* insert2(struct node *root,char x[],char id[]);
struct node *  delete(struct node*ptr,char a[]);
void traverse(struct node*ptr);
struct node *  Findmin(struct node*ptr);
char* search(struct node *root,char x[]);
char* search2(struct node *ptr,char x[]);
struct node *  delete2(struct node*T,char id[]);
int validname(char x[]);
int validid(char x[]);
void load();


int main(){
    int choice;
    char a[10],id[10];
    // load();
    printf("enter choice(1 to insert , 2 delete by name 6 delete by id , 3 traverse ,4 search by name  search 5 by id ):");
    scanf("%d",&choice);
    
    while(choice!=-1){
        switch (choice) {
            case 1:
                printf("enter name:");
                scanf("%s",a);
                while(!validname(a)){
                    printf("INVALID ,enter name:");
                    scanf("%s",a);
                }
                printf("enter id:");
                scanf("%s",id);
                while(!validid(id)){
                    printf("INVALID ,enter id:");
                    scanf("%s",id);
                }
                root=insert(root,a,id);
                root2=insert2(root2,a,id);
                
                break;
            case 2:
                printf("enter name to delete:");
                scanf("%s",a);
                while(!validname(a)){
                    printf("INVALID ,enter name:");
                    scanf("%s",a);
                }
                delete2(root2,search(root, a));
                delete(root,a);
                break;
            case 3:
                traverse(root);
                printf("tree 2\n");
                traverse(root2);
                
                break;
            case 4:
                printf("enter name to search:");
                scanf("%s",a);
                while(!validname(a)){
                    printf("INVALID ,enter name:");
                    scanf("%s",a);
                }
                search(root,a);
                break;
            case 5:
                printf("enter id to search:");
                scanf("%s",id);
                while(!validid(id)){
                    printf("INVALID ,enter id:");
                    scanf("%s",id);
                }
                search2(root2, id);
                break;
            case 6:
                printf("enter id to delete:");
                scanf("%s",id);
                while(!validid(id)){
                    printf("INVALID ,enter id:");
                    scanf("%s",id);
                }
                delete(root,search2(root2,id));
                delete2(root2, id);
                break;
            default:
                break;
        }
        
        printf("enter choice:");
        scanf("%d",&choice);
    }
    
}

struct node * insert(struct node *root, char x[],char id[])
{int a;
    
    if(!root)
    {
        root=(struct node*)malloc(sizeof(struct node));
        free( root->data );
        free( root->id );// free previously allocated memory, if any
        root->data = strdup( x ); // malloc and copy
        root->id=strdup(id);
        root->left = NULL;
        root->right = NULL;
        //   printf("1\n");
        return(root);
    }
    if((a=strcmp(root->data,x))>0){
        root->left = insert(root->left,x,id);
    }
    else
    {
        if(strcmp(root->data,x)<0)
            root->right = insert(root->right,x,id);
    }
    return(root);
}

struct node * insert2(struct node *root, char x[],char id[])
{
    if(!root)
    {
        root=(struct node*)malloc(sizeof(struct node));
        free( root->data );
        free( root->id );// free previously allocated memory, if any
        root->data = strdup( x ); // malloc and copy
        root->id=strdup(id);
        root->left = NULL;
        root->right = NULL;
        //   printf("1\n");
        return(root);
    }
    printf("string comp %d of %s of %s\n",strcmp(root->id,id),root->id,id);
    if((strcmp(root->id,id))>0){
        root->left = insert(root->left,x,id);
        printf("go left\n");
    }
    else
    {
        if(strcmp(root->id,id)<0){
            printf("go right\n");
            root->right = insert(root->right,x,id);}
    }
    return(root);
}


void traverse(struct node*ptr){
    if(ptr!=NULL){
        traverse(ptr->left);
        printf("%s  %s\n",ptr->data,ptr->id);
        traverse(ptr->right);
    }
}
struct node *  delete(struct node*T,char a[])
{
    if(T==NULL) ; // element is not found in the tree
    else if(strcmp(a,T->data)<0)
        T->left = delete(T->left,a);
    else if(strcmp(a,T->data)>0)
        T->right = delete(T->right,a);
    else if((T->left)!=NULL && (T->right)!=NULL) { // node with 2 children
        temp = Findmin(T->right);
        T->data = temp->data;
        T->id= temp->id;
        T->right = delete(T->right,T->data); }
    else {
        temp = T;
        if(T->left==NULL)
            T = T->right;
        else if(T->right==NULL)
            T = T->left;
        // free(temp);
    }
    return T; }

struct node *  Findmin(struct node*ptr){
    if((ptr->left)==NULL){
        // printf("min is :%s",ptr->data);
        return ptr;
    }
    else
        return Findmin(ptr->left);
    
}



char * search(struct node *ptr,char x[])
{
    while (ptr!=NULL) {
        
        if(strcmp(x,ptr->data)==0){
            printf("found data is :%s %s\n",ptr->data,ptr->id);
            return ptr->id;
        }
        else{
            if(strcmp(x,ptr->data)<0)
                ptr=ptr->left;
            else
                ptr=ptr->right;
        }
    }
    printf("not found\n");
    return NULL;
}
char* search2(struct node *ptr,char x[])
{
    while (ptr!=NULL) {
        
        if(strcmp(x,ptr->id)==0){
            printf("found data is :%s %s\n",ptr->data,ptr->id);
            
            return ptr->data;
        }
        else{
            if(strcmp(x,ptr->id)<0)
                ptr=ptr->left;
            else
                ptr=ptr->right;
        }
    }
    printf("not found\n");
    return NULL;
}
struct node *  delete2(struct node*T,char id[])
{
    
    
    if(T==NULL) ; // element is not found in the tree
    else if(strcmp(id,T->id)<0)
        T->left = delete(T->left,id);
    else if(strcmp(id,T->id)>0)
        T->right = delete(T->right,id);
    else if((T->left)!=NULL && (T->right)!=NULL) { // node with 2 children
        temp = Findmin(T->right);
        T->data = temp->data;
        T->id= temp->id;
        T->right = delete(T->right,T->data); }
    else {
        temp = T;
        if(T->left==NULL)
            T = T->right;
        else if(T->right==NULL)
            T = T->left;
        // free(temp);
    }
    return T;
}
void load()
{
    FILE * ptr;
    char  data[10];
    char path[10];
    char id[10];
    printf("enter path of file:");
    scanf("%s",path);
    if((ptr=fopen("/Users/mahmoudelmarakshy/Documents/proj/Mah.txt","r"))==NULL)
    {
        printf("invalid file\n");
    }
    else
    {
        while(!feof(ptr))
        {
            fscanf(ptr,"%[^,],%s\n",data,id);
            root=insert(root,data,id);
            root2=insert2(root2,data,id);

        }
        
        printf("FILE FOUND\n");
        printf("FILE LOADED\n");
        
    }
}
int validname(char a[]){int c,flag=0;
    for(c=0; (a[c])!='\0'; c++)
    {
        if(isdigit(a[c]))
            flag=1;
    }
    if (flag==1)
    {
        return 0;
    }
    else
        return 1;
}
int validid(char a[]){int c,flag=0;
    for(c=0; (a[c])!='\0'; c++)
    {
        if(isalpha(a[c]))
            flag=1;
    }
    if (flag==1)
    {
        return 0;
    }
    else
        return 1;
}