#include <stdlib.h>  
#include <stdio.h>  
#include <time.h>
#include <string.h>
#include "list_of_project.c"

#define student_size 21
#define group_number 7
 
/* This function can randomize the sequence*/
void randomize()
{
  srand((unsigned int)time((time_t *)NULL));
}

/*------------------------------------------------------*/
List Student[student_size];   /* Student link list*/
List Group[group_number];    /* Groups link list*/ 
int student_selected[student_size]; /* check whether the student is selected*/
int remain = student_size ;      /* the remainder of student */ 
/*------------------------------------------------------*/


/*===========Input the information from text file=========*/
void Input_Student_File()
{
  FILE *fp;          /* file pointer*/
  List pS[student_size] , tmpS;  /* pointer variable*/

  int i ,           /*looping variable*/
    index = 0 ,     /* index varible*/
    count = 1;      /* counter varible */
  char Name[20];    /* string variable*/

  /*memory allocation and initialization */
  for ( i = 0 ; i < student_size ; i++)
    {
      Student[i] = (List)malloc(sizeof(struct Student));
      Student[i]->Next = NULL;
      pS[i] = Student[i];
      student_selected[i] = 0;
    }
  
  fp = fopen("StudentInfo.txt" , "r");
  
  /* Read the student information to link list*/
  while( fscanf(fp,"%s",Name)!= EOF )
  {
    tmpS = (List)malloc(sizeof(struct Student));
    strcpy( tmpS->Name , Name);
    tmpS->Next = NULL ;
    
    pS[index]->Next = tmpS;
    pS[index] = tmpS;
    
    if ( count == 4)
	  { index++ ;  count = 0 ; }
    
    count++;
  };
  
  fclose(fp);
}
/*=======================End of input======================*/



/*Search function : find the student according to the algorithm*/
char* search_student( char *name)
{
  int i,k; 
  List pS[student_size];
 
  for(i = 0; i < student_size ; i++)
    {
      pS[i] = Student[i]->Next;
      if (!strcmp(name ,pS[i]->Name ))
	break;
    }
  
  for(k = 0, pS[i] = pS[i]->Next;
      k < student_size && pS[i] != NULL ; k++)
    if (!strcmp( Student[k]->Next->Name ,pS[i]->Name ))
      if( student_selected[k])
	{
	  pS[i] = pS[i]->Next;
	  k = -1;
	}
      else
	{
	  student_selected[k] = 1;
	  return Student[k]->Next->Name;
	}
  

  return "No";
}
/*================End of Search function==================*/



/*random select student if the favourite choices is break*/
char* random_student()
{
  int ran_array[remain]; /*store the student who has not been selected*/
  int i;
  int k = -1;
  
  /*reduce the selected student */
  for (i = 0 ; i < student_size ; i++)
    if(!student_selected[i])
	ran_array[++k] = i ; 
  
  /*random some number between the remain*/
  k = rand() % remain ;
  
  /*get back the random number*/
  i = ran_array[k];

  student_selected[i] = 1;

  return Student[i]->Next->Name;
  
}
/*================End of random student function==================*/


int main()  
{  
  int i,j ;               /*looping variable*/
  int k;                /* store the rand num*/
  int group[group_number];         /* for last random use*/
  List pG[group_number],tmpG;      /* pointer variable */
  char name[20];

  Input_Student_File();
  
  /* Beginning of the grouping process */
  if ( remain >= group_number)
    for( i = 0 ; i < group_number && remain > 0 ; i++)
      {
	Group[i] = (List)malloc(sizeof(struct Student));
	Group[i]->Next = NULL;
	pG[i] = Group[i] ;
	
	tmpG = (List)malloc(sizeof(struct Student));
	tmpG->Next = NULL;
	
	randomize();
	do  
	  {
	    k = rand()% student_size;
	    strcpy(tmpG->Name,Student[k]->Next->Name); 
	  } while( student_selected[k] );
	
	student_selected[k] = 1 ;
	pG[i]->Next = tmpG ;
	pG[i] = tmpG ;
	remain-- ;
      }

  
 if( remain >= group_number )  /* the major part of the grouping process*/
    for (i = 0 ; remain > 0; i++)
      { 
	strcpy(name,search_student(pG[i]->Name));
	
	if( !strcmp("No",name) )
	  {
	    tmpG = (List)malloc(sizeof(struct Student));
	    tmpG->Next = NULL;
	    strcpy(tmpG->Name , random_student());
	    
	    pG[i]->Next = tmpG;
	    pG[i] = tmpG ;
	  }
	else
	  {
	    tmpG = (List)malloc(sizeof(struct Student));
	    tmpG->Next = NULL;
	    strcpy(tmpG->Name ,name);
	    
	    pG[i]->Next = tmpG;
	    pG[i] = tmpG ;
	  }

	remain--;

	/* select 4 times has a loop*/
	if ( i == group_number-1 )
	  if (  remain >= group_number)
	    i = -1;
	  else 
	    break;

      }

 /* The remain is not enough to assign each group averagely*/
  for(i = 0 ; i < group_number ; i++ )
    group[i] = 0;
  
  for(i = 0 ; i < remain ;i++)
    {
      do
	{
	  k = rand()%group_number;
	}while(group[k]);
      
      group[k] = 1;    
    }
     
  for ( i = 0 ;i < group_number ; i++) 
    if(group[i])
      {
	tmpG = (List)malloc(sizeof(struct Student));
	tmpG->Next = NULL;
	strcpy(tmpG->Name ,random_student( ));
	
	pG[i]->Next = tmpG;
	pG[i] = tmpG ;
	remain--;
      }  
 
 
  printf("Student Information:\n\n");
  printf("  Student  First   Second   Third \n");
   for ( i = 0 ; i < student_size ; i++)
    {
      PrintList(Student[i]);
      printf("\n");
      DeleteList(Student[i]); 
    }

  printf("\nAfter the procedure:\n");

  
 for ( i = 0 ; i < group_number ; i++)
    { 
      printf("The Group [%d]: ",i);
      PrintList(Group[i]); 
      printf("\n");
      DeleteList(Group[i]); 
    }

   printf("\n");

 
}