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


//+++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++

#define cellSize 21
#define Groups 4
#define length 13

//+++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++

#define random(num)  (rand()%(num))
#define randomize() srand((unsigned)time(NULL))

//+++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++


typedef struct StudR *Next ; 

typedef struct StudR
		{
			char name[ length ] ; 
			char first[ length ] ;
			char second[ length ] ;
			char third[ length ] ; 
			Next nxt ; 
		} 
Cell ; 

int index_SR[ cellSize ] ; 
Next header[ Groups ] ; 
Next tmpCell[ Groups ] ; 
int remain = cellSize ; 
int cv = 0 ; //sharing var.

//+++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++

void Initalize_SR( Cell sr[] ) ; 
void printSR( Cell sr[] ) ; 
void Swap( int *Lhs , int *Rhs ) ; 
int findSR( Cell sr[] , int level ) ; 
void randSR( Cell sr[] ) ;
void randRemain( Cell sr[] ) ;
void NextSR( Cell sr[] ) ; 
void grouping( Cell sr[] ) ; 
void printG() ; 

//+++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++

void Initialize_SR( Cell sr[] ) 
{
	int i ;
	FILE *fp ; 

	fp = fopen( "StudentInfo.txt" , "r" ) ; 

	while( ! feof( fp ) ) 
		for ( i = 0 ; i < cellSize ; i++ )
		{
			fscanf( fp , "%s" , sr[ i ].name ) ; 
			fscanf( fp , "%s" , sr[ i ].first ) ; 
			fscanf( fp , "%s" , sr[ i ].second ) ; 
			fscanf( fp , "%s" , sr[ i ].third ) ; 
			sr[ i ].nxt = NULL ; 
			index_SR[ i ] = i ; 
		}

	fclose( fp ) ; 
}


void printSR( Cell sr[] ) 
{
	int i ;
	printf( "%13s\t%13s\t%13s\t%13s\n\n" , "Student Name" , "First Choice" , "Second Name" , "Third Name" ) ; 
	

	for ( i = 0 ; i < cellSize ; i++ ) 
		printf( "%13s\t%13s\t%13s\t%13s\n" , sr[ i ].name , sr[ i ].first , sr[ i ].second , sr[ i ].third ) ; 

}


void Swap( int *Lhs , int *Rhs )
{
	int Tmp = *Lhs ; 
	*Lhs = *Rhs ; 
	*Rhs = Tmp ; 
}


int findSR( Cell sr[] , int level )
{
	char target[ length ]  ; 
	int i , status = 0 ; 

	switch( level )
	{
	case 1 :
		strcpy( target , tmpCell[ cv ]->first ) ; 
		break ; 
	case 2 :
		strcpy( target , tmpCell[ cv ]->second ) ; 
		break ; 
	case 3 :
		strcpy( target , tmpCell[ cv ]->third ) ; 
		break ; 
	}

	for ( i = 0 ; i < remain ; i++ )
	{
		if( !( status = strcmp( target , sr[ index_SR[ i ] ].name  ) ) )
		{
			tmpCell[ cv ]->nxt = &sr[ index_SR[ i ] ] ;

			tmpCell[ cv ] = tmpCell[ cv ]->nxt ; 

			Swap( &index_SR[ i ] , &index_SR[ --remain ] ) ; 

			break ; 
		}
	}

	return ( !status ) ; 
}


void randSR( Cell sr[] )
{
	int tmp ; 
	
	randomize() ; 
	
	tmp = random( remain ) ; 

	tmpCell[ cv ]->nxt = &sr[ index_SR[ tmp ] ] ; 

	tmpCell[ cv ] = tmpCell[ cv ]->nxt ; 

	Swap( &index_SR[ tmp ] , &index_SR[ --remain ] ) ;
}


void randRemain( Cell sr[] ) 
{
	int tmp , range = Groups ; 

	if ( !remain ) return ;

	randomize() ; 

	while( remain )
	{
		tmp = random( range ) ; 

		tmpCell[ tmp ]->nxt = &sr[ index_SR[ --remain ] ] ; 

		tmpCell[ tmp ] = tmpCell[ --range ] ; 
	}
}

void NextSR( Cell sr[] )
{
	int wait = cellSize % Groups ; 

	while( remain > wait )
	{
		if ( !findSR( sr , 1 ) )
			if ( !findSR( sr , 2 ) )
				if ( !findSR( sr , 3 ) )
					randSR( sr ) ; 
		
		if ( cv == ( Groups -1 ) ) cv = 0 ; else cv++ ; 
	}
	randRemain( sr ) ; 
}

void grouping( Cell sr[] )
{
	int i , tmp ;

	randomize() ; 

	for ( i = 0 ; i < Groups ; i++ )
	{
		tmp = random( remain ) ; 

		header[ i ] = &sr[ index_SR[ tmp ] ] ; 

		tmpCell[ i ] = header[ i ] ; 

		Swap( &index_SR[ tmp ] , &index_SR[ --remain ] ) ; 

	}

	NextSR( sr ) ; 
}


void printG() 
{
	int i ;

	printf("\n(Fusion Version)\nGrouping Result : \n\n" ) ; 

	for ( i = 0 ; i < Groups ; i++ )
	{
		tmpCell[ i ] = header[ i ] ; 

		printf( "Group [ %d ] : " , i+1 ) ; 

		while( !( tmpCell[ i ] == NULL ) )
		{
			printf( "%s  " , tmpCell[ i ]->name ) ; 

			tmpCell[ i ] = tmpCell[ i ]->nxt ; 
		}
		printf( "\n" ) ; 
	}
}

int main(void)
{
	Cell sr[ cellSize ] ; 

	Initialize_SR( sr ) ; 

	printSR( sr ) ; 

	grouping( sr ) ; 

	printG() ; 

	getch() ; 

}