/* modified version of timetable.c to reflect changes in design */

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


#define MAX_ROOMS 20         /* max. valid  rooms   */
#define MAX_COURSES 30       /* max. valid courses  */
#define MAX_TIMES 15         /* max. possible timeslots     */
#define MAX_CAP 300          /* max. allowed room capacity */
#define MIN_CAP 10           /* min. room capacity         */
#define MAX_LN_LENG 80       /* max. input line length   */
#define TRUE 1
#define FALSE 0
#define MAX_COURSENO_SIZE 6  /* max. size of course number string */
#define MAX_TIMESLOT_SIZE 9  /* max. size of time slot string     */ 
#define MAX_ROOMNO_SIZE   4  /* max. size of room no. string      */

typedef char courseno[MAX_COURSENO_SIZE];
typedef char timeslot[MAX_TIMESLOT_SIZE];

typedef struct             /* info about a valid room */
{
	char room_no[MAX_ROOMNO_SIZE];
	int capacity;
}room;

/* A general linked list of integers */
typedef struct LstNode 
{
	int          pref_index;     /* Typically index in some DB will be kept */
	struct LstNode    *next;
}lstnode;

typedef struct                    /* information about the course to be scheduled  */
{
	int cnum;              /* index of the course in CourseDB */
	int enrol;             /* expected enrollment */
	lstnode *prefs;        /* list of valid preferences */
}course;

typedef struct         /* to produce conflict or explanation info */
{
	int err_code;             /* error code */
	int cnum;                 /* index into course no_db */
	int roomno;                 /* index into ClassroomDB */
	lstnode *prefs;
}error;

/* The next 6 data items obtained by parsing file1 */

room       ClassroomDB[MAX_COURSES];     /* valid courses */
courseno   CourseDB[MAX_ROOMS];          /* valid rooms   */
timeslot   TimeslotDB[MAX_TIMES];        /* valid timeslots   */
int          TotRooms;  /* total number of rooms */
int          TotTimes;  /* total number of possible lecture times */
int          TotCourses;/*total courses in file 1 */

course SchCourses[MAX_COURSES]; /* list of courses to be scheduled */
int    TotSchCourses;           /* total number of courses to scheduled */

/* The following 4 pointers are set up after the SchCourses is "sorted"  */
int PgP=0;       /* start of pg_prefs course; Is 0 */
int UgP;         /* first index of ug_prefs courses  */
int PgNP;        /* first index of pg_no_pref courses */
int UgNP;        /* first index of ug_no_pref courses */


int TimeTable[MAX_ROOMS][MAX_TIMES]; /* the rows are indices in ClassroomDB,
                                        columns are indices into TimeslotDB   */
int PgAlloc[MAX_TIMES]; /* Time slots occupied by PG courses. An entry is -ve
			   if not allocated to a PG course, +ve otherwise. Used for
			   checking conflicts while scheduling PG courses */

error ConflLst[MAX_COURSES];  /* expln for unschedualble courses */
error ExplnLst[MAX_COURSES];  /* expln for each unschedualble pref */

int TotConfl = 0;     /* represents last entry in ConflLst */
int TotExpln = 0;     /* represents last entry in ExplnLst */

int line_no=1;
lstnode *form_pref_list();

/************************************************************************************************/

main(argc,argv)
int argc;
char *argv[];
{

        FILE *fd1,*fd2;
	if (argc != 3) {
		printf("usage : schedule file1 file2\n");
		exit(-1);
	}
	/* opening file1 */
	if ((fd1=fopen(argv[1],"r"))== NULL)
	{
		printf("can't open file %s\n",argv[1]);
		exit(-1);
	}
	/* opening file2 */
	if ((fd2=fopen(argv[2],"r"))== NULL)
	{
		printf("can't open file %s\n",argv[2]);
		exit(-1);
	}

	/* get the data from input files */
	get_validated_input(fd1,fd2,TimeslotDB,ClassroomDB,CourseDB,SchCourses);
	schedule(ClassroomDB,TimeslotDB,CourseDB,SchCourses,
	         TimeTable,ConflLst,ExplnLst);     /* schedule courses*/
	print_output(TimeTable,ExplnLst,ConflLst); /* ouput timetable and explanations */

}

/***************************************************************************/


/* This module validates the contents of file1 and file2 and produces
 * lists for valid courses,classrooms,time slots,and courses to be
 * scheduled. Iferrors found in input file format, it exits if 
 * scheduling is not possible, else ignores the erroneous data */

get_validated_input(file1,file2,TimeslotDB,ClassroomDB,CourseDB,SchCourses)
FILE     * file1,
         * file2;
timeslot * TimeslotDB;
room     * ClassroomDB;
courseno * CourseDB;
course   * SchCourses;
{
	FILE *fd;
        
	/* get data from file1 */
	printf("Reading %s.....\n",file1);
	validate_file1(file1,ClassroomDB,CourseDB,TimeslotDB);

	/* get data from file2 */
	printf("Reading %s.....\n",file2);
	validate_file2(file2, SchCourses);
        
	separate_courses(CourseDB,SchCourses);
}

/*------------------------------------------------------------------------*/

/* Top level module to schedule courses. Besides timetable, it
 * gives explanation for courses/prefs which could not be satisfied */

schedule(ClassroomDB,TimeslotDB,CourseDB,SchCourses,
         TimeTable,ConflLst,ExplnLst)
room     * ClassroomDB;
timeslot * TimeslotDB;
courseno * CourseDB;
course   * SchCourses;
int        TimeTable[][MAX_TIMES];
error    * ConflLst;
error    * ExplnLst;

{
	int row,col;

	/* initializing time table & PgAlloc */
	for(row=0;row<MAX_ROOMS;row++)
		for(col=0;col<MAX_TIMES;col++)
		{
			TimeTable[row][col] = -1;
			PgAlloc[col] = -1;
		}

	sched_pg_pref(SchCourses,TimeTable,ExplnLst,ConflLst,PgAlloc);
	sched_ug_pref(SchCourses,PgAlloc, ConflLst,ExplnLst, TimeTable);
	sched_pg_no_pref(SchCourses,ConflLst,&TotConfl,PgAlloc,TimeTable);
	sched_ug_no_pref(SchCourses, ConflLst, TimeTable);

}

/*------------------------------------------------------------------------*/

/* Top level Print module to  produce all outputs */

print_output(TimeTable,ExplnLst,ConflLst)
int TimeTable[][MAX_TIMES];
error *ConflLst;
error *ExplnLst;
{
	print_TimeTable(TimeslotDB,ClassroomDB,CourseDB,TimeTable);
	print_explanation(ExplnLst,CourseDB,TimeslotDB,TimeTable,ClassroomDB);
	print_conflicts(ConflLst,CourseDB);
}

/*------------------------------------------------------------------------*/

/* gets validated data from file1
  * from input file1 */
validate_file1(fd,ClassroomDB,CourseDB,TimeslotDB)
FILE *fd;
room *ClassroomDB;
char *CourseDB;
char *TimeslotDB;
{

	validate_class_rooms(fd,ClassroomDB);
	validate_dept_courses(fd,CourseDB);
	validate_lec_times(fd,TimeslotDB);
	close(fd);
	/*
	display_rooms();
	display_courses();
	display_times();
        */
}

/*------------------------------------------------------------------------*/

validate_file2(fd, SchCourses)
FILE *fd;
course *SchCourses;
{

	char line[MAX_LN_LENG];
	int courses_end=FALSE;
	int course_index;
	char *token;
	int enrol;
	lstnode *pref_list=NULL;

	line_no = 0;
	TotSchCourses = 0;
	get_next_line(fd,line);
        
	/* file does not have any entries */
	if (*line == NULL) { 
		printf("No courses to schedule\n");
		exit(-1);
	}

	/* first token in file is not 'course' */
	token = strtok(line," \t\n");
	if (strcmp(token,"course"))
	{
		printf("line# %d : \"course\" expected \n",line_no);
		printf("scheduling aborted\n");
		exit(-1);
	}

	/* next token should be enrollment */
	token = strtok((char *)NULL," \t\n");
	if ((token != NULL) &&(strcmp(token,"enrollment")))
	{
		printf("line# %d : \"enrollment\" expected \n",line_no);
		printf("scheduling aborted\n");
		exit(-1);
	}
        
	/* next token should be preferences */
	token=strtok((char *)NULL," \t\n");
	if ((token != NULL) &&(strcmp(token,"preferences")))
	{
		printf("line# %d : \"prefrences\" expected \n",line_no);
		printf("scheduling aborted\n");
		exit(-1);
	}

	courses_end = FALSE;
	while ( (!courses_end)&&(TotSchCourses<MAX_COURSES) )
	{
		get_next_line(fd,line);
		if (*line == NULL) break;
		if (feof(fd)) courses_end = TRUE;
 
		/* get the course number */
		token = strtok(line," \t\n");
		course_index=get_course_index(CourseDB,TotCourses,token);
		if (course_index <0)
		{
			printf("line# %d : course number  \"%s\" does not exists *** ignored\n",line_no,token);
			continue;
		}
                
		/* get the expected enrollment */
		token=strtok((char *) NULL," \t\n");
		if (token == NULL)
		{
			printf("line# %d : enrollment expected  **** ignored \n",line_no);
			continue;
		}
		enrol=atoi(token);

		if ((enrol<MIN_CAP)||(enrol>MAX_CAP))
		{
			printf("line# %d : enrollment \"%d\" not in the allowed range  \n",line_no,enrol);
			printf("line# %d : course \"%s\" is ignored\n",line_no,CourseDB[course_index]);
			continue;
		}

		if (chk_dup_sched_course(SchCourses,course_index))
		{
			printf("line# %d : \"%s\" duplicate course *** ignored\n",line_no,CourseDB[course_index]);
			continue;
		}

		strcpy(line,(token+strlen(token)+1));
		/* get the list of preferences fo this course */
		pref_list = form_pref_list(line,TimeslotDB);
		SchCourses[TotSchCourses].cnum = course_index;
		SchCourses[TotSchCourses].enrol = enrol;
		SchCourses[TotSchCourses].prefs = pref_list;
		TotSchCourses++;

	}

	if (TotSchCourses>MAX_COURSES)
	{
		printf("line# %d : More number of courses than permissible\n",line_no++);
		printf("later ones are ignored\n");
	}

	if (TotSchCourses == 0)
	{
		printf("no courses to schedule\n");
		printf("scheduling aborted \n");
		exit(-1);
	}
	close(fd);
}

/*------------------------------------------------------------------------*/

/* Rearrange the courses in the following order:  PG courses with
 * preferences, UG courses with preferences, PG courses with no
 * preferences, UG courses with no preferences */

separate_courses(CourseDB,SchCourses)
courseno *CourseDB;
course   *SchCourses;
{
	course  pg_pref[MAX_COURSES],
	        pg_no_pref[MAX_COURSES],
	        ug_pref[MAX_COURSES],
	        ug_no_pref[MAX_COURSES];

	int pg_pref_i = 0; /* index  of last entry in pg_pref */
	int ug_pref_i = 0;
	int pg_no_pref_i = 0;
	int ug_no_pref_i = 0;

	char temp_char;
	int i,j;

	for (i=0;i<TotSchCourses;i++)
	{
		temp_char=CourseDB[SchCourses[i].cnum][2];
		if (temp_char > '5')    /* pg course */
			if (SchCourses[i].prefs != NULL)  /* preferences given */
				pg_pref[pg_pref_i++]=SchCourses[i];
			else pg_no_pref[pg_no_pref_i++]=SchCourses[i];
		else   /* ug course */
			if (SchCourses[i].prefs != NULL)  /* preferences given */
				ug_pref[ug_pref_i++]=SchCourses[i];
			else ug_no_pref[ug_no_pref_i++]=SchCourses[i];
	}

	/* copy back from temporary storage */
	for (i=0,j=0;i<pg_pref_i;i++,j++)
		SchCourses[j]=pg_pref[i];

	UgP=j;
	for (i=0;i<ug_pref_i;i++,j++)
		SchCourses[j]=ug_pref[i];

	PgNP=j;
	for (i=0;i<pg_no_pref_i;i++,j++)
		SchCourses[j]=pg_no_pref[i];

	UgNP=j;
	for (i=0;i<ug_no_pref_i;i++,j++)
		SchCourses[j]=ug_no_pref[i];
}

/*------------------------------------------------------------------------*/

/* Schedules the PG courses with preferences - allots highest possible
 * preference (records in PgAlloc also). For prefs it cannot satisy,
 * makes entry in ExplnLst. If it cannot schedule a course, makes entry
 * in ConflLst */

sched_pg_pref(SchCourses,TimeTable,ExplnLst,ConflLst,PgAlloc)
course *SchCourses;
int TimeTable[][MAX_TIMES];
error *ExplnLst;
error *ConflLst;
int *PgAlloc;
{

	int i;
	int sched_done;
	lstnode * pref_list;
	lstnode * temp_pref;
	lstnode * new_pref;
	lstnode * pref_tail;
	int room_index;
	int course_index;
	int enrol;
	int pref_index;
	int pref_honored,
	    first_pref;


	for (i=PgP;i<UgP;i++)
	{
		course_index=SchCourses[i].cnum;
		enrol=SchCourses[i].enrol;
		/* get room with proper capacity */
		room_index=get_room(ClassroomDB,TotRooms,enrol);
		if (room_index <0)
		{
			ConflLst[TotConfl].cnum=course_index;
			ConflLst[TotConfl++].err_code=5;
			continue;
		}

		pref_list=SchCourses[i].prefs;
		first_pref=pref_list->pref_index;
		pref_tail=NULL;

		sched_done=FALSE;
		while ((pref_list != NULL)&&(!sched_done))
		{
			pref_index = pref_list->pref_index;
			if (PgAlloc[pref_index]<0) /* no pg course at this time slot */
			{
				pref_honored = pref_index;
				PgAlloc[pref_index] = course_index;
				TimeTable[room_index][pref_index] = course_index;
				sched_done = TRUE;
			}
			else
			{      /* preserve info about pref to give explantions */
				new_pref = (lstnode *)malloc(sizeof(lstnode));
				new_pref->pref_index = pref_index;
				new_pref->next = NULL;
				if (pref_tail == NULL) pref_tail = temp_pref = new_pref;
				else 
				{
					pref_tail->next = new_pref;
					pref_tail = new_pref;
				}
			}
			pref_list = pref_list->next;
		}   /* while */

		if ( !sched_done)
		{
			ConflLst[TotConfl].err_code = 1;
			ConflLst[TotConfl].cnum = course_index;
			ConflLst[TotConfl++].prefs = temp_pref;
		}
		else if (pref_honored != first_pref)
		{
			ExplnLst[TotExpln].err_code=pref_honored;
			ExplnLst[TotExpln].prefs=temp_pref;
			ExplnLst[TotExpln].cnum=course_index;
			ExplnLst[TotExpln++].roomno=-1;
		}

	}  /* for */

}

/*------------------------------------------------------------------------*/

/* Schedule UG courses with preferences. This is not straighforward.
 * Before alloting a <timeslot, classroom>, it has to check if this
 * allotment is "safe", i.e. the schedulability of PG courses with 
 * no prefs is not disturbed. It does so by first "simulating" a
 * scheduling of pg_no_pref courses to find out how many can be
 * scheduled. An allotment is safe if the same no. can be still
 * scheduled */

sched_ug_pref(SchCourses,PgAlloc, ConflLst,ExplnLst, TimeTable)
course *SchCourses;
int *PgAlloc;
error *ConflLst;
error *ExplnLst;
int TimeTable[][MAX_TIMES];

{
	int pref_index,
	course_index,
	room_index,
	enrol,
	index,
	room_no;
	int num_pg_no_pref,/* number of pg courses with no preferences */
	pref_honored,
	first_pref;
	lstnode *pref_list;
	lstnode *temp_lstnode_ptr,
	        *temp,
	        *pref_tail;
	int sched_done = FALSE;/* set if scheduling is done */
	int TotSchPgNoPref;    /* schedulable pg no prefs   */

        /* number of pg_no_prefs courses that can be scheduled 
	   before ug_prefs are scheduled */
	TotSchPgNoPref = PgNoPrefSchLable(TimeTable,PgAlloc,SchCourses);

	num_pg_no_pref=UgNP-PgNP;
	for (index=UgP;index<PgNP;index++)
	{
		course_index = SchCourses[index].cnum;
		enrol = SchCourses[index].enrol;
		room_no = get_room(ClassroomDB,TotRooms,enrol);
		if (room_no <0)     /* room to accomaodate this course does not exists */
		{
			ConflLst[TotConfl].cnum = course_index;
			ConflLst[TotConfl++].err_code = 5;
			continue;
		}

		pref_list = SchCourses[index].prefs;
		first_pref = pref_list->pref_index;
		sched_done = FALSE;
		pref_tail = NULL;

		while ((pref_list != NULL)&&(!sched_done))
		{
			pref_index = pref_list->pref_index;
			if ((num_pg_no_pref == 0)||     
			    (PgAlloc[pref_index]>=0)) /* this time slot is not
							 useful for pg_no_prefs */
			{
				for(room_index = room_no;room_index<TotRooms;room_index++)
					if (TimeTable[room_index][pref_index]<0)
					/* slot in the timetable is free */
					{
						TimeTable[room_index][pref_index] = course_index;
						pref_honored = pref_index;
						sched_done = TRUE;
						break;
					}
			}
			else 
				for (room_index = room_no;room_index<TotRooms;room_index++)
					if ((TimeTable[room_index][pref_index]<0)&&
					    is_safe_allotment(pref_index,room_index,TotSchPgNoPref,TimeTable,
					    PgAlloc,SchCourses))
					    /* this schedule does not disturb the no. of
					       pg_no_prefs that can be scheduled before this */
					{
						TimeTable[room_index][pref_index] = course_index;
						pref_honored = pref_index;
						sched_done = TRUE;
						break;
					}
			if ( !sched_done )
			{
				/* preserve info about pref. to store it later in 
				   ConflLst or ExplnLst */
				temp = (lstnode *)malloc(sizeof(lstnode));
				temp->pref_index = pref_index;
				temp->next = NULL;
				if (pref_tail == NULL) pref_tail = temp_lstnode_ptr = temp;
				else
				{
					pref_tail->next = temp;
					pref_tail = temp;
				}
			}
			pref_list = pref_list->next;
		}   /* while */
		if (!sched_done)
		{
			ConflLst[TotConfl].err_code = 2;
			ConflLst[TotConfl].cnum = course_index;
			ConflLst[TotConfl++].prefs= temp_lstnode_ptr;
		}
		else if (pref_honored != first_pref)
		{
			ExplnLst[TotExpln].err_code = pref_honored;
			ExplnLst[TotExpln].prefs = temp_lstnode_ptr;
			ExplnLst[TotExpln].cnum = course_index;
			ExplnLst[TotExpln++].roomno = room_no;
		}

	}  /* for */
}

/*------------------------------------------------------------------------*/
/* Schedule PG courses with no preferences specified; Returns the 
 * number of courses it is able to schedule */
int sched_pg_no_pref(sched_db,ConflLst,TotConfl,PgAlloc,TimeTable)
course *sched_db;
error  *ConflLst;
int    *TotConfl;
int    *PgAlloc;
int     TimeTable[][MAX_TIMES];
/* schedule pg courses with no preferences */
{
	int course_index,
	enrol,
	room_index,
	sched_done,
	cur_slot;
	int i;
	int tot_scheduled=0;

	for(i = PgNP;i<UgNP;i++)
	{
		course_index = SchCourses[i].cnum;
		enrol = SchCourses[i].enrol;
		room_index = get_room(ClassroomDB,TotRooms,enrol);
		if (room_index <0)
		{
			ConflLst[(*TotConfl)].cnum = course_index;
			ConflLst[(*TotConfl)++].err_code = 5;
			continue;
		}

		sched_done = FALSE;
		while((room_index<TotRooms)&&(!sched_done))
		{
			for(cur_slot = 0; cur_slot<TotTimes; cur_slot++)
				if ((PgAlloc[cur_slot]<0)&&
				    (TimeTable[room_index][cur_slot]<0))
				    /* slot in the timetable is empty and no other pg
				       course is scheduled at this time slot */
				{
					TimeTable[room_index][cur_slot] = course_index;
					PgAlloc[cur_slot] = course_index;
					tot_scheduled++;
					sched_done = TRUE;
					break;
				}
			room_index++;
		}

		if (!sched_done)
		{
			ConflLst[(*TotConfl)].err_code=3;
			ConflLst[(*TotConfl)++].cnum=course_index;
		}

	}
	return(tot_scheduled);
}

/*------------------------------------------------------------------------*/

/* Schedule the UG courses with no preferences */
sched_ug_no_pref(SchCourses, ConflLst, TimeTable)
course *SchCourses;
int     TimeTable[][MAX_TIMES];
error  *ConflLst;
{
	/* schedule ug SchCourses with no preferences */
	int course_index,
	enrol,
	cur_slot,
	sched_done,
	room_index,
	i;

	for(i=UgNP;i<TotSchCourses;i++)
	{
		course_index=SchCourses[i].cnum;
		enrol=SchCourses[i].enrol;
		room_index=get_room(ClassroomDB,TotRooms,enrol);
		if (room_index <0)
		{
			ConflLst[TotConfl].cnum=course_index;
			ConflLst[TotConfl++].err_code=5;
			continue;
		}

		sched_done=FALSE;
		while ((room_index<TotRooms)&&(!sched_done))
		{
			for (cur_slot = 0;cur_slot<TotTimes;cur_slot++)
				if (TimeTable[room_index][cur_slot]<0)
				{
					TimeTable[room_index][cur_slot] = course_index;
					sched_done = TRUE;
					break;
				}
			room_index++;
		}

		if (!sched_done)
		{
			ConflLst[TotConfl].err_code = 4;
			ConflLst[TotConfl++].cnum = course_index;
		}

	}  /* for */
}


/*------------------------------------------------------------------------*/

/* Checks if an allotment for a UG course with preference is safe, i.e.
 * it does not violate the schedulability of PG courses with no preferences
 * that are yet to be scheduled */

int is_safe_allotment(time_slot,roomno,SchedPgNoPrefs,TimeTable,PgAlloc,SchCourse)
int time_slot,roomno,SchedPgNoPrefs;
int TimeTable[][MAX_TIMES];
int *PgAlloc;
course *SchCourse;

{
	int PgNoPrefs;
	int SaveSchedule;
	int safe_allot;

	SaveSchedule = TimeTable[roomno][time_slot]; /* always -1 */
	TimeTable[roomno][time_slot] = 0;            /* assigning some alotment in this slot */
	/* how many pg_no_prefs can be scheduled  after filling the above
	   entry in the timetable */
	PgNoPrefs = PgNoPrefSchLable(TimeTable,PgAlloc,SchCourse);
	TimeTable[roomno][time_slot] = SaveSchedule; /* restore back the old entry */

	/* check whether the number of pg_no_prefs courses that can be
	   scheduled is same as before */
	safe_allot = (PgNoPrefs == SchedPgNoPrefs);

	return(safe_allot);

}

/*------------------------------------------------------------------------*/

/* find how many pg_no_prefs courses can be scheduled using the given 
   status of the timetable */

int PgNoPrefSchLable(TimeTable,PgAlloc,SchCourse)
int TimeTable[][MAX_TIMES];
int *PgAlloc;
course *SchCourse;
{
	int t_PgAlloc[MAX_TIMES];
	int t_TimeTable[MAX_ROOMS][MAX_TIMES];
	error t_conflict[MAX_COURSES];
	int t_confl_index;
	int TotPgNoPref;
	int i,j;

	for (i=0;i<TotTimes;i++)
		t_PgAlloc[i]=PgAlloc[i];
	for (i=0;i<TotRooms;i++)
		for (j=0; j<TotTimes; j++)
			t_TimeTable[i][j]=TimeTable[i][j];
	t_confl_index=0;

	TotPgNoPref= sched_pg_no_pref(SchCourse,t_conflict,&t_confl_index,t_PgAlloc,t_TimeTable);


	return(TotPgNoPref);

}

/*------------------------------------------------------------------------*/

/* Get validated classroom info, and build ClassroomDB.  If any 
 *error is encountered, it continues parsing, ignoring that 
 * room no. Room records are sorted in increasing order of capacity */

validate_class_rooms(fd,ClassroomDB)
FILE * fd;              /* input file */
room * ClassroomDB; /* data base of rooms */
/* Input parametres : fd
		           Output parametres : ClassroomDB */
{

	char line[MAX_LN_LENG];
	char *token;
	char *room_no;
	int capacity;
	char *end_char;
	int rooms_end = FALSE;/*set if all rooms are read */
	int num_rooms = 0;    /* number of rooms in the file */

	/* no non empty lines in the file */
	get_next_line(fd,line);
	if (*line == NULL) {
		printf("input file is empty\n");
		exit(-1);
	}

        /* header "rooms" does not exists */
	token=strtok(line," \n\t\f");
	if (strcmp(token,"rooms")) input_error(line_no,token);

	while ((num_rooms<MAX_ROOMS)&&(!rooms_end))
	{
		get_next_line(fd,line);
		if ( *line =='\0') break; /* no more non empty lines */

		end_char=strchr(line,';');
		if (end_char != NULL)    /* rooms end indicator found */
		{
			rooms_end=TRUE;
			*end_char='\0';
			if (*line == NULL) break;
		}

		/* get the room number */
		token=strtok(line,": \n");
		chk_fmt_room_no(token); /* aborts, if there is any format error */
		room_no=token;
		/* get the room capacity */
		token=strtok((char *)NULL," \n\t\f");
		if (token==NULL) {
			printf("Line# %d : room capacity is not given \n",line_no);
			exit(-1);
		}
		capacity=atoi(token);
		chk_cap(capacity); /* aborts if capacity is not in specified range */

		if (chk_dup_room(ClassroomDB,num_rooms,room_no))
			printf("line# %d : duplicate class room \"%s\" *** ignored\n",line_no,room_no);
		else
		{       /* store room info in the database */
			strcpy(ClassroomDB[num_rooms].room_no,room_no);
			ClassroomDB[num_rooms].capacity=capacity;
			num_rooms++;
		}
	}

	if (feof(fd))
	{
		printf("no entries of courses, and lecture times in the input file \n");
		printf("scheduling aborted \n");
		exit(-1);
	}
        /* more rooms than permissible */
	while ( !rooms_end)
	{
		get_next_line(fd,line);
		if (*line == '\0') break; /* eof found */
		end_char=strchr(line,';');
		if (end_char != NULL)     /* last room found */
		{
			*end_char='\0';
			rooms_end=TRUE;
		}
		printf("more rooms than permissible room  %s is ignored\n",line);
	}

	if (num_rooms==0)
	{
		printf("There are no correct entries of rooms in the input file1\n");
		printf("scheduling aborted\n");
		exit(-1);
	}
        
	/* sort the rooms in the descending order of their capacity */
	sort_rooms(ClassroomDB,num_rooms);
	TotRooms=num_rooms;
}

/*------------------------------------------------------------------------*/

/* Get validated list of courses from File 1*/
/* reads valid dept courses from the input file to
 * CourseDB and also total number of courses through
 * TotCourses */
validate_dept_courses(fd,CourseDB)
FILE     *fd;
courseno *CourseDB;
/* Input parametres : fd
			  Output parametres : CourseDB,TotCourses
			  */
{
	char line[MAX_LN_LENG];
	char *token;
	char *course_no;
	char *end_char;
	int  courses_end = FALSE;/* set if all courses are read */
	int  num_courses = 0;    /* total number of courses in the file1 */

	/* no non empty line found */
	get_next_line(fd,line);
	if (*line == NULL) {
		printf("info about valid courses & time slots does not exists \n");
		exit(-1);
	}

	/* check for "courses" header */
	token = strtok(line," \n\t\f");
	if (strcmp(token,"courses")) input_error(line_no,token);

	while ( (num_courses<MAX_COURSES)&&(!courses_end) )
	{
		/* no more non empty lines */
		token = strtok((char *)NULL," ,\n");
		if (token == NULL)
		{
			get_next_line(fd,line);
			token=strtok(line," ,\n");
		}
                  
                /* "courses end"(;) indicator found */
		if ( token == NULL) break; /* eof found */
		end_char = strchr(token,';');
		if (end_char != NULL)
		{
			courses_end = TRUE;
			*end_char = '\0';
			if (*token == NULL) break;
		}

		chk_fmt_course_no(token);
		course_no = token;
		if (chk_dup_course_no(CourseDB,num_courses,course_no))
			printf("line# %d : duplicate course number \"%s\" **** ignored\n",line_no,course_no);
		else
		{
			/* store the course info in database */
			strcpy((CourseDB+num_courses),course_no);
			num_courses++;
		}
	}

	/* more rooms than permissible */
	while (!courses_end)
	{
		token = strtok((char *)NULL," ,\n");
		if (token == NULL)
		{
			get_next_line(fd,line);
			token = strtok(line," ,\n");
		}
		if (token == NULL) break;
		end_char = strchr(token,';');
		if (end_char != NULL)
		{
			*end_char = '\0';
			courses_end = TRUE;
			if (*token == NULL) break;
		}
		printf("line# %d : more courses than permissible %s *** ignored\n",line_no,token);
	}
	if (token == NULL)
	{
		printf("no entries of lecture times in the file \n");
		printf("scheduling aborted\n");
		exit(-1);
	}
	if (num_courses == 0)
	{
		printf("There are no correct entries of courses in the input file\n");
		printf("scheduling aborted\n");
		exit(-1);
	}
	TotCourses = num_courses;
}

/*------------------------------------------------------------------------*/

/* Get validated time slots from File 1*/
validate_lec_times(fd,TimeslotDB)
FILE     * fd;
timeslot * TimeslotDB;      /* valid lecture time slots */
{
	char line[MAX_LN_LENG];
	char *token;
	char *time_slot;
	char *end_char;
	int  slots_end = FALSE;
	int  num_times = 0;

	/* no more non empty lines */
	get_next_line(fd,line);
	if (*line == NULL) {
		printf("No info about valid time slots \n");
		exit(-1);
	}

	/* check for "times" header */
	token=strtok(line," \n\t\f");
	if (strcmp(token,"times")) input_error(line_no,token);

	while ( (num_times<MAX_COURSES)&&(!slots_end) )
	{
		/* no more non empty lines */
		token=strtok((char *)NULL," ,\n");
		if (token == NULL)
		{
			get_next_line(fd,line);
			token=strtok(line," ,\n");
		}
		if ( token == NULL) break; /* eof found */

		/* time slots end indicator found */
		end_char=strchr(token,';');
		if (end_char != NULL)
		{
			slots_end = TRUE;
			*end_char = '\0';
			if (*token == NULL) break;
		}

		chk_fmt_time_slot(token);
		time_slot = token;
		if (chk_dup_time_slot(TimeslotDB,num_times,time_slot))
			printf("line# %d : duplicate time slot \"%s\" **** ignored\n",time_slot);
		else
		{
			/* store the info in database */
			strcpy(TimeslotDB+num_times,time_slot);
			num_times++;
		}
	}

	/* mor time slots than permissible */
	while (!slots_end)
	{
		token = strtok((char *)NULL," ,\n");
		if (token == NULL)
		{
			get_next_line(fd,line);
			token=strtok(line," ,\n");
		}
		if (token == NULL) break;

		end_char = strchr(token,';');
		if (end_char != NULL)
		{
			*end_char = '\0';
			slots_end = TRUE;
		}
		printf("line# %d : more time_slots than permissible %s *** ignored\n",line_no,token);

	}

	if (num_times == 0)
	{
		printf("There are no correct entries of time slots in the input file\n");
		printf("scheduling aborted\n");
		exit(-1);
	}

	TotTimes = num_times;
}

/*---------------------------------------------------------------------------------------------*/

/* Forms a list of validated preferences in the given order  */
lstnode *form_pref_list(line,TimeslotDB)
char *line;
timeslot *TimeslotDB;
{
	lstnode     *pref_tail,*pref_list;
	lstnode     *new_pref;
	char        *token;
	int         pref_index;
	int         num_of_pref;

	num_of_pref = 0;
	pref_tail = pref_list = NULL;
	token = strtok(line," ,;\n\t");

	while ( (token != NULL)&&(num_of_pref < 5) )
	{
		pref_index = get_slot_index(TimeslotDB,TotTimes,token);
		if (pref_index<0)
			printf("Line# %d : time slot \"%s\" does not exists *** ignored\n",line_no,token);
		else
		{
			num_of_pref++;
			new_pref = (lstnode *)malloc(sizeof(lstnode));
			new_pref->pref_index = pref_index;
			new_pref->next = NULL;

			if (pref_tail == NULL) pref_tail = pref_list = new_pref;
			else 
			{
				pref_tail->next = new_pref;
				pref_tail = new_pref;
			}

		}
		token = strtok((char *)NULL," ,;\t\n");

	}

	if ((token != NULL)&&(num_of_pref>4))
	{
		printf("line# %d : more preferences than allowed\n",line_no);
		printf("          time slots from \"%s\" are ignored\n",token);
	}
	return(pref_list);
}

/*------------------------------------------------------------------------*/

/* outputs the time table in tabular form as
 * room numbers into rows and time slots into columns */
print_TimeTable(TimeslotDB,ClassroomDB,CourseDB,TimeTable)
timeslot *TimeslotDB;
room *ClassroomDB;
courseno *CourseDB;
int TimeTable[][MAX_TIMES];
{
	int i,j,breadth,space;

	breadth = (TotTimes+1) * 12;
	space = (breadth-10)/2;
	printf("\n");

	/* initial spaces before 'TIME TABLE' */
	if (space >0) for (i=0;i<space;i++) printf(" ");
	printf("TIME TABLE\n");

	for (i=0;i<breadth;i++) printf("_");
	printf("\n");

	printf("|rooms/times|");
	for (i=0;i<TotTimes;i++) printf(" %9s |",TimeslotDB[i]);
	printf("\n");

	for (i=0;i<breadth;i++) printf("-");
	printf("\n");

	for (i=0;i<TotRooms;i++)
	{
		printf("|    %3s    |",ClassroomDB[i].room_no);

		for (j=0;j<TotTimes;j++)
			if (TimeTable[i][j]<0) printf("           |");
			else printf("   %5s   |",CourseDB[TimeTable[i][j]]);

		printf("\n");
	}


	for (i=0;i<breadth;i++) printf("-");
	printf("\n");

}

/*------------------------------------------------------------------------*/

/* Print the reasons why higher prefs for a course could not be honoured */
print_explanation(ExplnLst,CourseDB,TimeslotDB,TimeTable,ClassroomDB)
error    *ExplnLst;
courseno *CourseDB;
timeslot *TimeslotDB;
int       TimeTable[][MAX_TIMES];
room *ClassroomDB;
{
	int room_index,
	    i,pref_honored;
	lstnode *temp_pref;

	if (TotExpln<1) return;
	printf("\n\t\t\tExplanation Report\n");
	printf("\t-----------------------------------------------\n\n");

	for (i=0;i<TotExpln;i++)
	{
		printf("%s :\n",CourseDB[ExplnLst[i].cnum]);
		temp_pref=ExplnLst[i].prefs;
		room_index=ExplnLst[i].roomno;
		pref_honored=ExplnLst[i].err_code;

		while (temp_pref != NULL)
		{
			printf("\t%8s : ",TimeslotDB[temp_pref->pref_index]);
			if (room_index <0)
				printf("Conflicting with course %s\n",
				    CourseDB[PgAlloc[temp_pref->pref_index]]);
			else printf("Room with proper capacity not found\n");
			temp_pref=temp_pref->next;
		}

		if ((room_index >= 0)&&
		    (TimeTable[room_index][pref_honored]!=ExplnLst[i].cnum))
		{
			printf("\t     %s :\n",TimeslotDB[pref_honored]);
			while (TimeTable[room_index][pref_honored] != ExplnLst[i].cnum)
			{
				printf("\t\t     room#%s :",ClassroomDB[room_index].room_no);
				printf("conflicting with course %s\n",
				    CourseDB[TimeTable[room_index][pref_honored]]);
				room_index++;
			}
		}

	}
	printf("\n");

}

/*------------------------------------------------------------------------*/

/* Print the list of courses that are not scheduled in the final table,
 * and specify the conflicts that prevented their scheduling */

print_conflicts(ConflLst,CourseDB)
error *ConflLst;
courseno *CourseDB;
{
	int i;
	lstnode *temp;

	if (TotConfl <1) return;
	printf("\n\t\t\tConflict Report\n");
	printf("\t-----------------------------------------------\n\n");
	for (i=0;i<TotConfl;i++)
	{
		printf("%s : \n",CourseDB[ConflLst[i].cnum]);
		switch( ConflLst[i].err_code)
		{
		case 1   :
			temp = ConflLst[i].prefs;
			while (temp != NULL)
			{
				printf("\t %s : ",TimeslotDB[temp->pref_index]);
				printf("conflicting with course %s \n",
				    CourseDB[PgAlloc[temp->pref_index]]);
				temp = temp->next;
			}
			break;
		case 2    :
			temp = ConflLst[i].prefs;
			while (temp != NULL)
			{
				printf("\t %s : ",TimeslotDB[temp->pref_index]);
				printf("Room with proper capacity not found\n");
				temp = temp->next;
			}
			break;
		case 3    :
			printf("\tExcess PG course : no time slot available\n");
			break;
		case 4     :
			printf("\tNo free room with required capacity available\n");
			break;
		case 5     :
			printf("\tIgnored : No room with adequate capacity for this enrollment\n");
			break;
		case 6      :
			printf("\tIgnored : course repeated more than once in file2\n");
			break;
		}
		printf("\n");
	}
}


/***************************************************************************
 *                   Utility routines                                      *
 ***************************************************************************/

/* 
 * returns first non empty line from the input file. 
 * returns null string if eof is encountered & no non
 * empty line is found.
 * All the initial spaces before a line are removed.
 * The last character of the string will be '\n' if is 
 * a non empty line.
 */
get_next_line(fd,buffer)
char *buffer;
FILE *fd;
{
	int ln_found = FALSE;
	char *temp_char;

	*buffer = '\0';
	while ( !ln_found )
	{
		line_no++;
		fgets(buffer,MAX_LN_LENG,fd);
		temp_char=buffer;
		/* removes initial spaces */
		while ( (*temp_char != NULL) && isspace(*temp_char) )
			temp_char++;
		if ((*temp_char != NULL) || feof(fd) ) ln_found=TRUE;
	}
	if (buffer != temp_char) strcpy(buffer,temp_char);
}

/*------------------------------------------------------------------------*/

/* Checks if the room_no given already exists in the ClassroomDB */
int chk_dup_room(ClassroomDB,TotRooms,room_number)
room * ClassroomDB;
int        TotRooms;
char     * room_number;
/* check, whether the given room number already
   exists in the data base. returns TRUE if so,
   otherwise false */
{
	int i;
	for (i=0;i<TotRooms;i++)
		if (strcmp(ClassroomDB[i].room_no,room_number)==0) break;
	if (i<TotRooms) return(TRUE);
	else return(FALSE);
}

/*------------------------------------------------------------------------*/

int chk_cap(capacity)
int capacity;
/*  checks whether room capacity is in allowed range.
 *  aborts with error message,if not so */
{
	int flag;

	flag=((capacity>=MIN_CAP)&&(capacity<=MAX_CAP))  ? TRUE :FALSE;
	if (!flag)
	{
		printf("line# %d : error in room capacity \"%d\" \n",line_no,capacity);
		printf("scheduling aborted \n");
		exit(-1);
	}
}

/*------------------------------------------------------------------------*/

chk_fmt_room_no(room_number)
char *room_number;
/* checks the format of room number 
   aborts with error message,if it is not 
   in correct format.
   */
{
	int i,str_leng;
	int fmt_error=FALSE;

	str_leng=strlen(room_number);
	if (str_leng>3) fmt_error=TRUE;
	else
		for (i=0;i<str_leng;i++)
			if (!isdigit(room_number[i]))
			{
				fmt_error=TRUE;
				break;
			}
	if (fmt_error)
	{
		printf("line# %d : error in the format of room number \"%s\"\n",line_no,room_number);
		printf("scheduling aborted\n");
		exit(-1);
	}
}

/*------------------------------------------------------------------------*/

/*  sorts the rooms in the ascending oreder of
 *  their capacity */

sort_rooms(ClassroomDB,TotRooms)
room * ClassroomDB;
int        TotRooms;
{
	room temp_room;
	int i,j;

	for (i=0;i<(TotRooms-1);i++)
		for (j=i+1;j<TotRooms;j++)
			if (ClassroomDB[i].capacity>ClassroomDB[j].capacity)
			{
				strcpy(temp_room.room_no,ClassroomDB[i].room_no);
				temp_room.capacity=ClassroomDB[i].capacity;
				strcpy(ClassroomDB[i].room_no,ClassroomDB[j].room_no);
				ClassroomDB[i].capacity=ClassroomDB[j].capacity;
				strcpy(ClassroomDB[j].room_no,temp_room.room_no);
				ClassroomDB[j].capacity=temp_room.capacity;
			}
}

/*------------------------------------------------------------------------*/

chk_fmt_course_no(course_no)
char *course_no;
/*  checks the format of course number i.e csddd
    aborts, if any error found */
{
	int str_leng;
	int fmt_error = FALSE;

	str_leng = strlen(course_no);
	if (str_leng != 5) fmt_error=TRUE;
	else if ( strncmp(course_no,"cs",2) != 0 ) fmt_error = TRUE;
	else if ( !isdigit(course_no[2]) ) fmt_error = TRUE;
	else if ( !isdigit(course_no[3]) ) fmt_error = TRUE;
	else if ( !isdigit(course_no[4]) ) fmt_error = TRUE;

	if (fmt_error)
	{
		printf("line #%d : error in the format of course number \"%s\"\n",line_no,course_no);
		printf("scheduling aborted\n");
		exit(-1);
	}
}

/*------------------------------------------------------------------------*/

int chk_dup_course_no(CourseDB,TotCourses,course_number)
courseno * CourseDB;
int        TotCourses;
char     * course_number;
{
	int i;

	for (i=0;i<TotCourses;i++)
		if (strcmp(CourseDB+i,course_number)==0) break;

	if (i<TotCourses) return(TRUE);
	else return(FALSE);
}


/*------------------------------------------------------------------------*/

chk_fmt_time_slot(time_slot)
char *time_slot;
/*   checks the format of given time slots
     aborts if any error is found */
{
	int str_leng,i = 0;
	int fmt_error = FALSE;
	char time[6];
	char temp_slot[9];
	char *temp_str,*temp_char;

	strcpy(temp_slot,time_slot);
	str_leng=strlen(temp_slot);
	fmt_error = ((str_leng <3)||(str_leng>8));

	if (!fmt_error)
	{
		temp_str=temp_slot;
		while ( !isdigit(*temp_str) ) temp_str++;
		strcpy(time,temp_str);
		*temp_str = '\0';
		if (strcmp(temp_slot,"MWF")&&strcmp(temp_slot,"TT")) fmt_error = TRUE;
		else 
		{
			temp_char = strchr(time,':');
			if (temp_char != NULL) *temp_char = '9'; /* any digit */
			while (time[i] != NULL)
				if (!isdigit(time[i++])) fmt_error = TRUE;
		}
	}
	if (fmt_error)
	{
		printf("line# %d : error in the format of time slot \"%s\"\n",line_no,time_slot);
		printf("scheduling is aborted\n");
		exit(-1);
	}
}

/*------------------------------------------------------------------------*/

int chk_dup_time_slot(TimeslotDB,TotTimes,time_slot)
timeslot * TimeslotDB;
int        TotTimes;
char     * time_slot;
{
	int i;
	for (i=0;i<TotTimes;i++)
		if (strcmp(TimeslotDB+i,time_slot)==0) break;
	if (i<TotTimes) return(TRUE);
	else return(FALSE);
}


/*------------------------------------------------------------------------*/

int get_course_index(CourseDB,TotCourses,course_no)
courseno * CourseDB;   /* courses data base */
int        TotCourses; /* total number of courses in the data base */
char     * course_no;  /* course number whose index is to be found */
/* 
  returns index of the given course number in the data base 
  returns -1 if that course does not exist */
{
	int index;
	for (index=0;index<TotCourses;index++)
		if (strcmp(CourseDB+index,course_no)==0) return(index);
	return(-1);
}

/*------------------------------------------------------------------------*/

int get_room_index(ClassroomDB,TotRooms,room_no)
room *ClassroomDB;  /* rooms data base */
int TotRooms;           /* total number of rooms in the data base */
char *room_no;          /* room number whose index is to be found */
/* 
  returns index of the given room number in the data base 
  returns -1 if that room does not exist */
{
	int index;
	for (index = 0;index < TotRooms;index++)
		if (strcmp(ClassroomDB[index].room_no,room_no) == 0) return(index);
	return(-1);
}

/*------------------------------------------------------------------------*/

int get_slot_index(TimeslotDB,TotTimes,time_slot)
timeslot * TimeslotDB;   /* rooms data base */
int        TotTimes;      /* total number of rooms in the data base */
char     * time_slot;     /* room number whose index is to be found */
/* 
  returns index of the given time slot  in the data base 
  returns -1 if that time slot does not exist */
{
	int index;
	for (index = 0;index < TotTimes;index++)
		if (strcmp(TimeslotDB+index,time_slot) == 0) return(index);
	return(-1);
}

/*------------------------------------------------------------------------*/

int chk_dup_sched_course(SchCourses,sched_course_index)
course * SchCourses;
int      sched_course_index;
{
	int i;

	for (i = 0;i<TotSchCourses;i++)
		if (SchCourses[i].cnum == sched_course_index) break;
	if (i<TotSchCourses) return(TRUE);
	else return(FALSE);
}
/*------------------------------------------------------------------------*/

input_error(ln_number,token_string)
int ln_number;
char *token_string;
{
	printf("line# %d : \"%s\" not expected\n",ln_number,token_string);
	exit(-1);
}

/*------------------------------------------------------------------------*/

int get_room(ClassroomDB,TotRooms,enrol)
room *ClassroomDB;
int TotRooms;
int enrol;
/*  finds a room with least capacity that can
    accomodate given enrollment, and returns
    it's index.
    Returns -1 if no room with proper capacity is
    found  */
{
	int i;

	for (i=0;i<TotRooms;i++)
		if (ClassroomDB[i].capacity>=enrol) return(i);
	return(-1);
}


/*------------------------------------------------------------------------*/

/*   following routines are for debugging purpose only */
display_rooms()
{
	int i;
	for (i=0;i<TotRooms;i++)
	{

		printf("room number %s\n",ClassroomDB[i].room_no);
		printf("capacity %d\n\n",ClassroomDB[i].capacity);
	}
}
/*------------------------------------------------------------------------*/
display_courses()
{
	int i;
	for (i=0;i<TotCourses;i++)
		printf("course number %s\n",CourseDB[i]);
}
/*------------------------------------------------------------------------*/
display_times()
{
	int i;
	for (i=0;i<TotTimes;i++)
		printf("lecture time %s \n",TimeslotDB[i]);
}
/*------------------------------------------------------------------------*/
display_pref(pref_list)
lstnode * pref_list;
{
	lstnode * temp_pref;

	temp_pref=pref_list;
	while(temp_pref != NULL)
	{
		printf(" prefrence %s \n",TimeslotDB[temp_pref->pref_index]);
		temp_pref=temp_pref->next;
	}
}
/*------------------------------------------------------------------------*/
display_scheds()
{
	int i;

	printf("total courses %d\n",TotSchCourses);
	printf("ug start %d\n",UgP);
	printf("pg no prefstart %d\n",PgNP);
	printf("ug no prefstart %d\n",UgNP);

	for (i=0;i<TotSchCourses;i++)
	{
		printf(" course number %s enroll %d \n",CourseDB[SchCourses[i].cnum],
		    SchCourses[i].enrol);
		display_pref(SchCourses[i].prefs);
	}
}
/* routines till here for debugging purpose */