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

#define DATA_FILE "data.txt"

struct STUDENT
{
    int id;
    char name[80];
    int take_num;
    int takes[6];
    struct STUDENT* left_next;/*link list*/
    struct STUDENT* right_next;       
};

struct STUDENT* head;
struct STUDENT* current;
struct STUDENT* previous;/*link list*/

/*void init(struct STUDENT students[]);*/
void load(FILE* fp,int select_num);
void make_tree(struct STUDENT* student_ptr,struct STUDENT** head,int select_num);
void traverse_tree(struct STUDENT** head);

int search(struct STUDENT students[],int id);
struct STUDENT* b_search(struct STUDENT* head,int id,char* name,int select_num);
int b_search_name(struct STUDENT students[],char* name,int head,int tail);
int search_by_name(struct STUDENT students[],char* name);

void show(struct STUDENT students[],int id,int index);
int add(struct STUDENT students[],int id,int index,int course);
void save(FILE* fp,struct STUDENT students[]);

int main (void)
{
    FILE *fp;
    struct STUDENT students[256];
    int id=-1;//search by id
    char name[80]={0};//search by name
    int index;
    int course;
    int result;
    int select_num;//save the number selected
    struct STUDENT* consequence;
    
    //init(students);//對id，name做初始化 
    fp=fopen(DATA_FILE,"r");
    
    //load(fp,students);
    //fclose(fp);
    
    printf("please select enter name or enter id:\n");
    printf("enter name 按1，enter id 按2\n");
    //scanf("%d",&select_num);
    select_num=1;
    if(select_num==1)
    {
        load(fp,select_num);
        printf("please enter name:");
        scanf("%s",name); 
        consequence=b_search(head,-1,name,1);
          
        if(consequence==NULL)
        {
            printf("name doesn`t exist,program ends\n");
            exit(1);            
        } 
        //id=name_to_id(students,name);  
        printf("%d ",consequence->id);
        printf("%s",consequence->name);          
    }
    else if(select_num==2)
    {
        load(fp,select_num);
        printf("please enter id:");
        scanf("%d",&id);
                
        index=search(students,id);
        
        if(index==-1)
        {
            printf("id doesn`t exist,program ends\n");
            exit(1);            
        }
    }
    
    while(1)
    {
        show(students,id,index);
        if(students[index].take_num==5)
        {
            printf("all courses are selected,program ends");
            break;                               
        }        
        printf("請輸入課程代號，-1結束選課");
        scanf("%d",&course);
        if(course==-1)
        {
            printf("程式結束\n"); 
            break;             
        }
        
        result=add(students,id,index,course);
        if(result==1)
        {
            printf("選課成功\n");             
        }
        else if(result==2)
        {
            printf("重複選課\n");            
        }
        else if(result==3)
        {
            printf("無此課程\n");     
        }
    }
    
    fp=fopen(DATA_FILE,"w");
    save(fp,students);
    fclose(fp);
    
    
    return 0;
}

/*void init(struct STUDENT students[])
{
    int i,j;
    for(i=1;i<256;i++)
    {
        students[i].id=-1; 
        //students[i].name[80]={0};
        memset(students[i].name,0,sizeof(students[i].name));                
    }     
}*/

void load(FILE* fp,int select_num)
{
    int i,j,k;
    i=0;
    //if(select_num==2)/*enter id*/
    {
        while(!feof(fp))
        {
            i=i+1;
            struct STUDENT* student_ptr=(struct STUDENT*)malloc(sizeof(struct STUDENT));
           // printf("%d\n",i);
            fscanf(fp,"%d",&(student_ptr->id));
            fscanf(fp,"%s",student_ptr->name);
            fscanf(fp,"%d",&(student_ptr->take_num));
           // printf("%d ",student_ptr->id);
           // printf("%d\n",student_ptr->take_num);
            for(j=1;j<=(student_ptr->take_num);j++)
            {
                fscanf(fp,"%d",&(student_ptr->takes[j]));    
                                          
            }
            
            student_ptr->left_next=NULL;
            student_ptr->right_next=NULL;
            
            make_tree(student_ptr,&head,select_num);
            //printf("%d\n",i);       
        } 
        traverse_tree(&head);
    }
    
}

int search(struct STUDENT students[],int id)
{
    int i,index;
    int j;
    struct STUDENT temp;//資料暫存處 
    index=-1;
    /*for(i=1;i<256;i++)
    {
        if(students[i].id==id)
        {
            index=i;
            break;                      
        }                  
    }*/
    
    //insertion sort
    for(i=2;i<256;i++)
    {
        /*temp.id=students[i].id;//暫存資料 
        temp.name=students[i].name;
        temp.take_num=students[i].take_num;
        temp.takes=students[i].takes;*/
        //printf("%d %d\n",i,students[i].id);
        temp=students[i];
        for(j=i-1;j>=1;j--)
        {
            if(students[j].id<temp.id)
                break;
            else if(students[j].id>=temp.id)  
            {
                students[j+1]=students[j];    
            }                    
        } 
        
        if(j==i-1)
            continue;
        else    
            students[j+1]=temp;                 
    }/*insertion sort*/
    
    for(i=1;i<256;i++)
    {
      //printf("%d %d\n",i,students[i].id);               
    }
    //system("pause");
    //binary search student
    //index=b_search(students,id,1,255);
    printf("%d",index);
    return index;
}

int search_by_name(struct STUDENT students[],char* name)
{
    int i,j,index=-1;
    int comp_result;
    struct STUDENT temp;
    /*for(i=1;i<256;i++)
    {
        if(strcmp(students[i].name,name)==0)
        {
            index=i;
            break;                                    
        }                  
    }   */
    
    /*sorting string by bubble sort*/
    for(j=255;j>=2;j--)
    {
        for(i=1;i<j;i++)
        {
            comp_result=strcmp(students[i].name,students[i+1].name); 
            if(comp_result==1)
            {
                temp=students[i];
                students[i]=students[i+1];
                students[i+1]=temp;                  
            }
            else if(comp_result==0||comp_result==-1)
                continue;
                    
        } 
    }
    for(i=1;i<256;i++)
    {
      //printf("%d %s\n",i,students[i].name);               
    }
    index=b_search_name(students,name,1,255);
    //printf("%d",index);
    //system("pause");
    return index;
}


void show(struct STUDENT students[],int id,int index)
{
    int i;
    printf("您已選以下課程:\n");
    for(i=1;i<=students[index].take_num;i++)
    {
        printf("%d",students[index].takes[i]);
        printf(" ");                                         
    }     
    printf("\n");
}

int add(struct STUDENT students[],int id,int index,int course)
{
    int i;
    if(course>=101&&course<=105)
    {
        for(i=1;i<=students[index].take_num;i++)
        {
            if(students[index].takes[i]==course)
                return 2;                                        
        }  
        students[index].takes[i]=course;
        students[index].take_num=students[index].take_num+1;
        return 1;                          
    }    
    return 3;
}

void save(FILE* fp,struct STUDENT students[])
{
    int i,j;
    for(i=1;i<256;i++)
    {
        if(students[i].id!=-1)
        {
            fprintf(fp,"%d",students[i].id);
            fprintf(fp,"\t");
            fprintf(fp,"%s",students[i].name);
            fprintf(fp,"\t");
            fprintf(fp,"%d",students[i].take_num);
            fprintf(fp,"\t");
            for(j=1;j<=students[i].take_num;j++)
            {
                fprintf(fp,"%d",students[i].takes[j]);
                fprintf(fp,"\t");                                    
            }                 
            fprintf(fp,"\n");     
        }                  
    }     
}

struct STUDENT* b_search(struct STUDENT* head,int id,char* name,int select_num)
{
    //printf("%d ",select_num);
    if(select_num==1)
    {    
        if(head==NULL)
        {
            printf("%s",head->name);
            return NULL;               
        }
        else if(head!=NULL)
        {
            if(strcmp((head)->name,name)>0)
            {
                b_search(head->left_next,-1,name,1);
            }         
            else if(strcmp((head)->name,name)<0)
            {
                b_search(head->right_next,-1,name,1);
            }
            else if(strcmp((head)->name,name)==0)
            {
                printf("%s %d ",head->name,head->id);
                return head;     
            }
        }
    }
    
}

int b_search_name(struct STUDENT students[],char* name,int head,int tail)
{
    int comp_result;
    int index=-1;
    if(head==tail)
    {
        if(strcmp(name,students[head].name)==0)
            return head;
        else
            return index;              
    }
    
        comp_result=strcmp(name,students[(head+tail)/2].name);
        
        if(comp_result<0)
        {
            index=b_search_name(students,name,head,(head+tail)/2);  
            return index;                
        } 
        else if(comp_result==0)
        {
            return (head+tail)/2;     
        }   
        else if(comp_result>0)
        {
            index=b_search_name(students,name,((head+tail)/2)+1,tail);   
            return index;               
        }
}

void make_tree(struct STUDENT* student_ptr,struct STUDENT** head,int select_num)
{
     if(select_num==1)
     {
         if(*head==NULL)                 
         {
             *head=student_ptr;                                
         }
         else if(*head!=NULL)
         {
             if(strcmp((*head)->name,student_ptr->name)>0)
             {
                 make_tree(student_ptr,&((*head)->left_next),select_num);                                           
             }     
             else if(strcmp((*head)->name,student_ptr->name)<=0)
             {
                 make_tree(student_ptr,&((*head)->right_next),select_num);     
             }
         }
     }
     else if(select_num==2)
     {   
        if(*head==NULL)
        {
            *head=student_ptr;
           // printf("%d\n",(*head)->id);
            /*current=student_ptr; 
            previous=student_ptr;*/                 
        }
        else if(*head!=NULL)
        {
            if((*head)->id>=student_ptr->id)
            {
                /*previous=current;
                current=head->left_next;*/
                if((*head)->left_next==NULL)
                {
                    (*head)->left_next=student_ptr;                 
                }
                else if((*head)->left_next!=NULL)
                {
                    make_tree(student_ptr,&((*head)->left_next),select_num);
                }                         
            }
            else if((*head)->id<student_ptr->id)
            {
                if((*head)->right_next==NULL)
                {
                    (*head)->right_next=student_ptr;                          
                }     
                else if((*head)->right_next!=NULL)
                {
                    make_tree(student_ptr,&((*head)->right_next),select_num);     
                }
            }     
        }  
     } 
    //printf("%s %d\n",head->name,head->id);
}

void traverse_tree(struct STUDENT** head)
{
    if(*head==NULL)
    {
        return;              
    }
    else
    {
        printf("%s %d\n",(*head)->name,(*head)->id);
        traverse_tree(&((*head)->left_next));
        traverse_tree(&((*head)->right_next));  
    }   
}