/* 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_ROOMS];     /* valid courses */
courseno   CourseDB[MAX_COURSES];      /* 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;          /* number of the line being read from input file */
/*---------------------------------------------------------------------------------*/
/* function prototypes */
int validate_file2();
int validate_class_rooms();
int validate_dept_courses();
int validate_lec_times();
int sched_pg_no_pref();
int PgNoPrefSchLable();
char *get_next_line();
int chk_dup_room();
int chk_cap();
int chk_fmt_room_no();
int chk_fmt_course_no();
int chk_fmt_time_slot();
int chk_dup_course_no();
int chk_dup_time_slot();
lstnode *form_pref_list();
int chk_file2_header();
course *get_course_info();

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

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 courses */
	schedule(ClassroomDB,TimeslotDB,CourseDB,SchCourses,
	         TimeTable,ConflLst,ExplnLst);     
	/* ouput timetable and explanations */
	print_output(TimeTable,ExplnLst,ConflLst);

}

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


/* 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;       
FILE     * file2;
timeslot * TimeslotDB;
room     * ClassroomDB;
courseno * CourseDB;
course   * SchCourses;
{
        
	/* get data from file1 */
	line_no = 0;
	printf("Reading file1 ... \n");
	validate_file1(file1,ClassroomDB,CourseDB,TimeslotDB);

	/* get data from file2 */
	line_no = 0;
	printf("Reading file2 ...\n");
	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;
{

	if ( (validate_class_rooms(fd,ClassroomDB) < 0) || 
	     (validate_dept_courses(fd,CourseDB) < 0)   ||
	     (validate_lec_times(fd,TimeslotDB) < 0)  )
	{
		printf("input format error -  scheduling aborted\n");
		exit(-1);
        }
	fclose(fd);
}

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

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

	char line[MAX_LN_LENG];
	course  * curr_course;

	TotSchCourses = 0;  /* Total courses to be scheduled */
	get_next_line(fd,line);
        
	if (chk_file2_header(line,line_no) < 0) 
	{
	  printf("input format error - scheduling aborted\n");
	  exit(-1);
         }
        
	while (TotSchCourses<MAX_COURSES) 
	{
		/* no more courses to be  scheduled */
		if (get_next_line(fd,line) == NULL) break;

		if ((curr_course = get_course_info(line)) != NULL)
		{
			SchCourses[TotSchCourses].cnum = curr_course->cnum;
			SchCourses[TotSchCourses].enrol = curr_course->enrol;
			SchCourses[TotSchCourses].prefs = curr_course->prefs;
			TotSchCourses++;
		}
	}

	if (TotSchCourses>MAX_COURSES)
	{       /* more than permissible */
		printf("line# %d : More number of courses than permissible\n",line_no++);
		printf("later ones are ignored\n");
	}
	else if (TotSchCourses == 0) /* no courses */
	{
		printf("no courses to schedule\n");
		printf("scheduling aborted \n");
		exit(-1);
	}
	fclose(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;
{
/* Scans schedule courses and copies different types in corresponding
 * temp data structure, then copies back in order
 */
	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;             /* loop indices */
	int sched_done;      /* set if course is scheduled */
	lstnode * pref_list; /* list of preferences for the current course */
	int course_index;    /* current course  being handled */
	int room_no;         /* index of room with proper capacity */
	int enrol;           /* enrollment of current course */
	int pref_index;      /* preference being handled */ 
	int pref_honored;    /* index of the preference finally given to
				the course */
	int first_pref;      /* index of the first preferences */


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

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

		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_no][pref_index] = course_index;
				sched_done = TRUE;
			}
			pref_list = pref_list->next;
		}   /* while */

		if ( !sched_done)  /* course is not scheduled */
		{
			ConflLst[TotConfl].err_code = 1;
			ConflLst[TotConfl].cnum = course_index;
			ConflLst[TotConfl++].prefs = SchCourses[i].prefs;
		}
		/* first preference not honored */
		else if (pref_honored != first_pref)
		{
			/*  store info about course to print explns later */
			ExplnLst[TotExpln].err_code = pref_honored;
			ExplnLst[TotExpln].prefs = SchCourses[i].prefs;
			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,       /* preference being handled */
	    course_index,     /* current course */
	    enrol,            /* enrollment of curr course */
	    i,j,              /* loop indices */
	    room_no;          /* room with required capacity */
	int num_pg_no_pref,   /* number of pg courses with no preferences */
	    pref_honored,     /* preference being handled */
	    first_pref;       /* index for first preference */
	lstnode *pref_list;   /* list of prefs for curr course */
	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 (i=UgP;i<PgNP;i++)
	{
		course_index = SchCourses[i].cnum;
		enrol = SchCourses[i].enrol;
		if ((room_no = get_room(ClassroomDB,TotRooms,enrol)) < 0)
		{
			ConflLst[TotConfl].cnum = course_index;
			ConflLst[TotConfl++].err_code = 5;
			continue;
		}

		pref_list = SchCourses[i].prefs;
		first_pref = pref_list->pref_index;
		sched_done = FALSE;

		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(j = room_no; j<TotRooms; j++)
					if (TimeTable[j][pref_index] < 0)
					/* slot in the timetable is free */
					{
						TimeTable[j][pref_index] = course_index;
						pref_honored = pref_index;
						sched_done = TRUE;
						break;
					}
			}
			else 
				for (j = room_no;j<TotRooms;j++)
					if ((TimeTable[j][pref_index]<0)&&
					    is_safe_allotment(pref_index,j,TotSchPgNoPref,TimeTable,
					    PgAlloc,SchCourses))
					    /* this schedule does not disturb the no. of
					       pg_no_prefs that can be scheduled before this */
					{
						TimeTable[j][pref_index] = course_index;
						pref_honored = pref_index;
						sched_done = TRUE;
						break;
					}
			pref_list = pref_list->next;
		}   /* while */
		if (!sched_done)
		{
			ConflLst[TotConfl].err_code = 2;
			ConflLst[TotConfl].cnum = course_index;
			ConflLst[TotConfl++].prefs = SchCourses[i].prefs;
		}
		else if (pref_honored != first_pref)
		{
			ExplnLst[TotExpln].err_code = pref_honored;
			ExplnLst[TotExpln].prefs = SchCourses[i].prefs;
			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(SchCourses,ConflLst,TotConfl,PgAlloc,TimeTable)
course *SchCourses;
error  *ConflLst;
int    *TotConfl;
int    *PgAlloc;
int     TimeTable[][MAX_TIMES];
/* schedule pg courses with no preferences */
{
	int course_index,    /* curr course index */
	    enrol,           /* enrollement of course being handled */
	    room_index,      /* curr room index */
	    sched_done,      /* set if course is scheduled */
	    cur_slot;        /* curr preference index */
	int i;               /* loop index */
	int tot_scheduled=0; /* total courses scheduled */ 

	for(i = PgNP;i<UgNP;i++)
	{
		course_index = SchCourses[i].cnum;
		enrol = SchCourses[i].enrol;
		if ((room_index = get_room(ClassroomDB,TotRooms,enrol)) < 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, /* curr course index */
	    enrol,        /* enroll of curr course */
	    cur_slot,     /* curr preference index */
	    sched_done,   /* set if course is scheduled */
	    room_index,   /* curr room */
	    i;            /* loop index */

	for(i=UgNP;i<TotSchCourses;i++)
	{
		course_index=SchCourses[i].cnum;
		enrol=SchCourses[i].enrol;
		if ((room_index = get_room(ClassroomDB,TotRooms,enrol)) < 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)
				/* slot in the timetable empty */
				{
					TimeTable[room_index][cur_slot] = course_index;
					sched_done = TRUE;
					break;
				}
			room_index++;
		}

		if (!sched_done) /* course not scheduled */
		{
			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;   /* number of pg no prefs */
	int SaveSchedule;/* to save entry in the timetable */
	int safe_allot;  /* set if given allotment is safe */

	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;

	/* copy contents of TimeTable and PgAlloc 
	   in temporary locations */
	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 classrooms info, and build ClassroomDB.  
 * Returns -1, if error encountered in the input file, otherwise, 0. 
 * Room records are sorted in the increasing order of capacity
 */

int validate_class_rooms(fd,ClassroomDB)
FILE * fd;              /* input file */
room * ClassroomDB;     /* data base of rooms */
{
	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 */
	if (get_next_line(fd,line) == NULL) rooms_end = TRUE;
        else
	{
        	/* header "rooms" does not exists */
		token=strtok(line," \n\t\f");
		if (strcmp(token,"rooms"))
		{
		 	printf("line#%d: \"rooms\" expected\n",line_no);
		 	return(-1);
		 }
        }
	while ((num_rooms<MAX_ROOMS)&&(!rooms_end))
	{
		if (get_next_line(fd,line) == NULL) break;

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

		/* get the room number */
		token=strtok(line,": \n");
		if (chk_fmt_room_no(token) < 0)
		{
		  printf("line#%d : error in the format of room number \"%s\" \n",
			  line_no,token);
		  return(-1);
		}
		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);
			return(-1);
		}
		capacity=atoi(token);
		if (chk_cap(capacity) < 0)
		{
		 printf("line#%d : room capacity not in the allowed range\n",line_no);
		 return(-1);
		 }

		if (chk_dup_room(ClassroomDB,num_rooms,room_no))
			printf("line# %d : duplicate class room \"%s\" *** ignored\n",line_no,
				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++;
		}
	}

        /* more rooms than permissible */
	if ( !rooms_end)
	{
		printf("more rooms than permissible - excess rooms ignored \n");
		skip_lines(fd);
	}

	if (num_rooms==0)
	{
		printf("No entries of rooms in the input file1\n");
		return(-1);
	}
        
	/* sort the rooms in the descending order of their capacity */
	sort_rooms(ClassroomDB,num_rooms);
	TotRooms=num_rooms;
	return(0);
}

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

/* 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
 */
int 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 */
	if ( get_next_line(fd,line) == NULL )
	{
		printf("no entries of department courses in file1\n");
		return(-1);
	}

       	/* header "rooms" does not exists */
	token=strtok(line," \n\t\f");
	if (strcmp(token,"courses"))
	{
	 	printf("line#%d: \"courses\" expected\n");
	 	return(-1);
	}

	while ( (num_courses<MAX_COURSES)&&(!courses_end) )
	{
		/* get next token in the same line */
		token = strtok((char *)NULL," ,\n");
		if (token == NULL)                 /* no more tokens in the line */
		    if (get_next_line(fd,line) == NULL) /* no more lines in the file */
		    {
		      courses_end = TRUE;
		      break;
		      }
                    else token=strtok(line," ,\n");
                  
                /* "courses end"(;) indicator found */
		end_char = strchr(token,';');
		if (end_char != NULL)
		{
			courses_end = TRUE;
			*end_char = '\0';
			if (*token == NULL) break;
		}

		if (chk_fmt_course_no(token) < 0)
		{
			printf("line#%d : error in the format of course number \"%s\" \n",
				line_no,token);
			return(-1);
                }
		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 */
	if (!courses_end)
	{
		printf("more courses than permissible - later ones are ignored \n");
		skip_lines(fd);
	}
	if (num_courses == 0)
	{
		printf("no entries of courses in the input file\n");
		return(-1);
	}
	TotCourses = num_courses;
	return(0);
}

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

/* 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 non empty line found */
	if ( get_next_line(fd,line) == NULL )
	{
		printf("no entries of lecture times in file1\n");
		return(-1);
	}

       	/* header "times" does not exists */
	token=strtok(line," \n\t\f");
	if (strcmp(token,"times"))
	{
	 	printf("line#%d: \"times\" expected\n");
	 	return(-1);
	}

	while ( (num_times<MAX_TIMES)&&(!slots_end) )
	{
		/* next token in the same line */
		token=strtok((char *)NULL," ,\n");
		if (token == NULL)  /* no more tokens in the same line */
		    /* go to the next line and find another token */ 
		    if  (get_next_line(fd,line) == NULL) 
		    {
		       slots_end = TRUE;
		       break;
		       }
		    else token=strtok(line," ,\n");

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

		if (chk_fmt_time_slot(token) < 0)
		{
			printf("line#%d: error in the format time slot \"%s\"\n",
				line_no,token);
			return(-1);
                }
		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 */
	if (!slots_end)
	{
		printf("more time_slots than permissible - later one are ignored\n");
		skip_lines(fd);
	}

	if (num_times == 0)
	{
		printf("no entries of time slots in the input file\n");
		return(-1);
	}

	TotTimes = num_times;
	return(0);
}

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

/* 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) && (temp_pref->pref_index != pref_honored))
		{
			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 \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 is returned.
 */
char * get_next_line(fd,buffer)
FILE * fd;
char * buffer;
{
	int    ln_found = FALSE; /* set if line is found */
	char   *temp_char;

	while ( !ln_found )
	{
		line_no++;
		/* eof reached */
		if (fgets(buffer,MAX_LN_LENG,fd) == NULL) return(NULL);
		/* removes initial spaces in the line */
		temp_char = buffer;
		while ( (*temp_char != NULL) && isspace(*temp_char) )
			temp_char++;
		if (*temp_char != NULL) ln_found=TRUE;
	}
	strcpy(buffer,temp_char);
	return(buffer);
}

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

/* 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;
/* 
 *  returns -1, if room capacity is not in the allowed range.
 *  otherwise, 0
 */
{
	int flag;
	flag=((capacity>=MIN_CAP)&&(capacity<=MAX_CAP))  ? 0 : -1;
	return(flag);
}

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

int chk_fmt_room_no(room_number)
char *room_number;
/* checks the format of room number
 * returns -1 if any error 
 *          0, otherwise
 */
{
	int i,str_leng;

	str_leng=strlen(room_number);
	if (str_leng>3) return(-1);
	else
		for (i=0;i<str_leng;i++)
			if (!isdigit(room_number[i]))
			return(-1);
        return(0); /* room no in correct format */
}

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

/*  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, d is any digit
 *  returns -1 if any error
 *  returns  0 otherwise
 */
{
	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) return(-1);
	else return(0);
}

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

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
 *   returns -1 if any error 
 *   returns  0 otherwise
 */
{
	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)  return(-1);
	else return(0);
}

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

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);
}


/*--------------------------------------------------------------------------------------*/
/* checks the header of file2. 
 * file2 should contain "course_number     enrollment     preferences"
 * as header
 */
int chk_file2_header(line,line_no)
char *line;
int   line_no;
{
	int Error = FALSE;
	char *token1;  /* first token in the input line */
	char *token2;  /* second token */
	char *token3;  /* third token */


	token1 = strtok(line," \t\n");
	token2 = strtok((char *)NULL," \t\n");
	token3 = strtok((char *)NULL," \t\n");

	if ((token1 == NULL) || (token2 == NULL) || (token3 == NULL) )
	    Error = TRUE;
        else if ( strcmp(token1, "course_number") ||
		  strcmp(token2, "enrollment")    ||
		  strcmp(token3, "preferences") )  Error = TRUE;

        if (Error)
	{
	  printf("line#%d: \"course_number\tenrollment\tpreferences\" expected\n",line_no);
	  return(-1);
	  }
        else return(0);
}

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

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_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);
}
/*------------------------------------------------------------------------*/

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);
}


/*-------------------------------------------------------------------------------------*/
/* get course info from the given line
 */
course *get_course_info(line)
char *line;
{
	char *token;
	int course_index;
	int enrol;
	lstnode *pref_list;
	course *course_info;

	/* get the course number */
	token = strtok(line," \t\n");
	if ((course_index=get_course_index(CourseDB,TotCourses,token)) < 0)
	{
		printf("line# %d : course number  \"%s\" does not exists *** ignored\n",line_no,token);
		return(NULL);
	}
                
	/* get the expected enrollment */
	token=strtok((char *) NULL," \t\n");
	if (token == NULL)
	{
		printf("line# %d : enrollment expected  **** course ignored \n",line_no);
		return(NULL);
	}
	enrol=atoi(token);

	if ( chk_cap(enrol) < 0 )
	{
		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]);
		return(NULL);
	}

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

	/* get the remainder of line containing preferences */
	strcpy(line,(token+strlen(token)+1));
	/* get the list of preferences for this course */
	pref_list = form_pref_list(line,TimeslotDB);
	course_info = (course *)malloc(sizeof(course));
	course_info->cnum = course_index;
	course_info->enrol = enrol;
	course_info->prefs  = pref_list;
	return(course_info);
}

/*-------------------------------------------------------------------------------------*/
/* skips the lines in file,
 * until either eof is found, or
 *  	        line ends with ';' 
 */

skip_lines(fd)
FILE *fd;
{
	char  temp_line[MAX_LN_LENG];

	while  ( (fgets(temp_line,MAX_LN_LENG,fd) != NULL) &&
	         (strchr(temp_line,';') == NULL) )
		 line_no++;
}
/*------------------------------------------------------------------------*/

/*   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 */