/*
 *  sjf.c
 *  Shortest Job First Scheduler simulation
 *
 *  Big-picture strategy:
 *
 *  Use the same data structures as for FCFS but through the interface supplied.
 *  Start from the head of the list and search for the process which has the
 *  shortest burst time and which has arrived by the current time.
 *
 *  Rationale:
 *
 *  Sorting or other apparently smarter techniques aren't clearly a win as we
 *  don't know up front (without some processing) whether the process with the
 *  shortest burst time will go next, because it hasn't necessaily arrived. The
 *  time saving is minor from sorting, unless an O(n log n) sort is used, anyway.
 *
 *  Created by Philip Machanick on Sat 12 Mar 2005.
 *  Copyright (c) 2005 School of ITEE, University of Queensland. All rights reserved.
 *
 */
 
#include "constants.h"
#include "scheduletypes.h"
#include "sjf.h"

#include <stdio.h>
#include <stdlib.h> // for exit

// only because we want to fake the new stuff by borrowing from FCFS:
#include "fcfs.h"


// In this implementation this is not needed
void* initSJF (unsigned size) {
	return newScheduleList ();
	//fprintf (stderr, "should have initialised SJF data structure: remove this line once done\n");	
}

// cheat: use the same data structure
void copyToSJF (void* destination, unsigned id, unsigned arrival, unsigned burst) {
	copyToScheduleList (destination, id, arrival, burst);
}

// look for the shortest burst time in processes which have arrived by the current
// simulated time
static struct ListElement * findNextSchedule (ScheduleList *schedule, unsigned currentTime, unsigned *startTime)  {
	
	struct ListElement *currentNode = getNext (schedule, NULL),
		*previousToChosen = NULL;
	if (currentNode) { // non-empty list
		struct ListElement *chosenElement = currentNode, *previous = NULL;
		struct Schedule *currentSchedule = scheduleValue (currentNode);

		unsigned arrival = getArrive (currentSchedule), burst = getBurst (currentSchedule),
			thisStartTime  = (arrival < currentTime) ? currentTime : arrival;
		unsigned minFinish = thisStartTime + burst;
		
		*startTime = thisStartTime;
		// now find next process arrived by current time with shortest burst
		// stop if reach end of list
		while (arrival <= currentTime && currentNode) {
			unsigned finish = thisStartTime + burst;
			if (finish < minFinish) {
				minFinish = finish;
				chosenElement = currentNode;
				previousToChosen = previous;
				*startTime = thisStartTime;
			}
			previous = currentNode;
			currentNode = getNext (schedule, currentNode);
			if (currentNode) {
				currentSchedule = scheduleValue (currentNode);
				arrival = getArrive (currentSchedule);
				thisStartTime = (arrival < currentTime) ? currentTime : arrival;
				burst = getBurst (currentSchedule);
			}
		}
		if (chosenElement)
			deleteFromSchedule (schedule, chosenElement, previousToChosen);
		return chosenElement;
	}
	return NULL;
}

// Not too different from FCFS -- main difference is in calling findNextSchedule
// rather than taking the first schedule off the list
void scheduleSJF (void *untypedSchedule) {
	ScheduleList *schedule = (ScheduleList*) untypedSchedule;
	unsigned currentTime = 0, waitTime = 0, numberSchedules = 0, startTime;

	struct ListElement * nextSchedule =
		findNextSchedule (schedule, currentTime, &startTime);
	
	do {
		if (nextSchedule) {
			struct Schedule *this = scheduleValue (nextSchedule);
			if (this) {
				unsigned pid = getID (this), arrival = getArrive (this), burst = getBurst (this);
				unsigned thisWait = (arrival < currentTime) ? currentTime - arrival : 0;
				waitTime += thisWait;
				currentTime = startTime + burst;
				numberSchedules ++;		
				printf ("process %u scheduled at time = %u, burst time = %u; waited time = %u.\n",
					pid, startTime, burst, thisWait);
				// can't access this schedule data beyond this point so deallocate
				free (this);

			} else {
					fprintf (stderr, "ERROR: empty schedule in list element in scheduleSJF\n");
					exit (BADLIST);
			}
		}
		// can't access nextSchedule after this so deallocate it
		free (nextSchedule);
		nextSchedule = findNextSchedule (schedule, currentTime, &startTime);
	} while (nextSchedule);
	
	// at this point the outer container is no longer needed, so it should be deallocated
	// ask a service routine to do this, since we can't be sure it's just a pointer
	// and doesn't have any other hidden data unknown to us
	
	deallocateScheduleList (&untypedSchedule);
	
	if (numberSchedules)
		printf ("\n%u processes scheduled, average wait time = %f; total elapsed time = %u.\n",
			numberSchedules, (float)waitTime / (float)numberSchedules, currentTime);
	else
		printf ("No processes scheduled.\n");
}

// since the format is the same entrust printing to the FCFS scheduler code
void printSJFSchedules (void *aList) {
	printSchedules ((ScheduleList*) aList);
}