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

struct task;

typedef struct task{
	int taskID;
	int readyTime;
	int executionTime;
	int deadline;
	int processed;
	int slackTime;
	struct task *next;
} task_t;

task_t *taskList;

void addToTaskList(int taskID, int readyTime, int executionTime, int deadline)
{
	task_t *newItem ;
	task_t *taskItem;
	
	newItem = NULL;
	newItem = (task_t*)malloc(sizeof(task_t));
	
	taskItem = taskList;

	if (taskItem == NULL){
		taskList = newItem;
	}
	else {
		while (taskItem->next != NULL)
			taskItem = taskItem->next;
	taskItem->next = newItem;
	}

	newItem->taskID = taskID;
	newItem->readyTime = readyTime;
	newItem->executionTime = executionTime;
	newItem->deadline = deadline;
	newItem->processed = 0;
	newItem->slackTime = 0;
	newItem->next = NULL;

}

int deleteFromList(int taskID)
{
	task_t *taskItem = taskList;
	task_t *prevItem = NULL;
	task_t *followItem = NULL;

	while (taskItem != NULL){
		if (taskItem->taskID == taskID){
			followItem = taskItem->next;

			printf("\t\tP%d is finished and is deleted from the list ", taskItem->taskID);

			free(taskItem);
			
			if (prevItem == NULL) 
				taskList = followItem;
			else
				prevItem->next = followItem;
			
			return(1);
		}

		prevItem = taskItem;
		taskItem = taskItem->next;
	}

	return (0);

}

void clearTaskList(){
	
	task_t *taskItem;
	
	while (taskList != NULL){
		taskItem = taskList;
		taskList= taskList->next;
		free(taskItem);
	}
}

void printTaskIDs(){
	task_t *taskItem = taskList;

	printf("All tasks in the set:    ");

	while (taskItem != NULL){
		printf("P%d;  ", taskItem->taskID);
		taskItem = taskItem->next;
	}
	
	printf("\n");
}

void printReadyTaskIDs(int currentTimestamp){
	task_t *taskItem = taskList;

	printf("Ready tasks in the set:  ");

	while (taskItem != NULL){
		if (taskItem->readyTime<=currentTimestamp)
			printf("P%d;  ", taskItem->taskID);
		taskItem = taskItem->next;
	}
	
	printf("\n");
}

void calculateSlackTimes(int currentTimestamp){
	task_t *taskItem = taskList;

	while (taskItem != NULL){
		/* Calculate the new slack time for the struct taskList and store it in the variable "taskItem.slackTime" */
		/* Only ready tasks can be exemined */
		
		if (taskItem->readyTime<=currentTimestamp)
			taskItem->slackTime = (taskItem->deadline - currentTimestamp) - (taskItem->executionTime - taskItem->processed);

		taskItem = taskItem->next;
	}
}

/* The function prints slack times of the tasks which are ready for execution at the given timestamp */
void printSlackTimes(int currentTimestamp){
	task_t *taskItem = taskList;
	calculateSlackTimes(currentTimestamp);
	
	printf("Current slack times:     ");

	while (taskItem != NULL){
		if (taskItem->readyTime<=currentTimestamp)
			printf("s%d=%d;", taskItem->taskID, taskItem->slackTime);
		taskItem = taskItem->next;
	}
	
	printf("\n");
}

/* The function prints deadlines of the tasks which are ready for execution at the given timestamp */
void printDeadlines(int currentTimestamp){
	task_t *taskItem = taskList;
	
	printf("Deadlines: ");

	while (taskItem != NULL){
		if (taskItem->readyTime<=currentTimestamp)
			printf("d%d=%d;", taskItem->taskID, taskItem->deadline);
		taskItem = taskItem->next;
	}
	
	printf("\n");
}

/* The function returns the pointer to the task with the least slack time */
/* If there are more than one only one, first one, is returned            */
/* Only ready tasks are exemined                                          */
/* Returns the NULL pointer if there are no ready tasks                   */

task_t *getTaskWithLeastSlackTime(int currentTimestamp){
	task_t *taskItem = taskList;
	task_t *taskWithLS = NULL;
	int LS = 100000; /* Very big number */
	
	calculateSlackTimes(currentTimestamp);

	while (taskItem != NULL){
		if ((taskItem->readyTime<=currentTimestamp)&&(taskItem->slackTime<LS)){
			LS = taskItem->slackTime;
			taskWithLS = taskItem;
		}
		taskItem = taskItem->next;
	}
	
	return taskWithLS;

}

/* The function returns the pointer to the task with the earliest deadline */
/* If there are more than one only one, first one, is returned            */
/* Only ready tasks are exemined                                          */
/* Returns the NULL pointer if there are no ready tasks                   */

task_t *getTaskWithEarliestDeadline(int currentTimestamp){
	task_t *taskItem = taskList;
	task_t *taskWithED = NULL;
	int ED = 100000; /* Very big number */

	while (taskItem != NULL){
		if ((taskItem->readyTime<=currentTimestamp)&&(taskItem->deadline<ED)){
			ED = taskItem->deadline;
			taskWithED = taskItem;
		}
		taskItem = taskItem->next;
	}
	
	return taskWithED;

}

void printTasksInfo(){

	task_t *taskItem = taskList;
	
	printf("\nInfo about all tasks\n");
	while (taskItem != NULL){
		printf("P%d: r%d=%d; e%d=%d; d%d=%d;\n",taskItem->taskID,taskItem->taskID,taskItem->readyTime,taskItem->taskID,taskItem->executionTime,taskItem->taskID,taskItem->deadline);
		taskItem = taskItem->next;
	}
	
	printf("\n");

}

int checkDeadlineViolationEDF(int currentTimeStep){

	task_t *taskItem = taskList;
	
	while (taskItem != NULL){
		if(taskItem->deadline < currentTimeStep){
			printf("\t\tP%d: deadline violation (d%d=%d)\n",taskItem->taskID,taskItem->taskID,taskItem->deadline);
			return 1;
			}
		taskItem = taskItem->next;
	}
	
	return 0;
}

int checkDeadlineViolationLST(int currentTimeStep){

	task_t *taskItem = taskList;

	calculateSlackTimes(currentTimeStep);
	
	while (taskItem != NULL){
		if(taskItem->slackTime < 0){
			printf("\t\tP%d: deadline violation (s%d=%d) (t=%d)\n",taskItem->taskID,taskItem->taskID,taskItem->slackTime, currentTimeStep);
			return 1;
			}
		taskItem = taskItem->next;
	}
	
	return 0;

}


/* EDF non-preemptive scheduler */

void scheduleEDFnonPreemptive(){

	int currentTimeStep, executionTime;
	task_t *taskInProcess;
	
	printf("EDF non-preemptive scheduler\n\n");
	
	currentTimeStep = 0;
	
	while (taskList != NULL){
	
		printf("t=%d: ",currentTimeStep);
		
		if (getTaskWithEarliestDeadline(currentTimeStep)){
			
			taskInProcess = getTaskWithEarliestDeadline(currentTimeStep);
			executionTime = taskInProcess->executionTime;
			
			/* Check if there are dealines violations ?! */
			if (checkDeadlineViolationEDF(currentTimeStep+executionTime))
				break;
			
			printDeadlines(currentTimeStep);
			printf("\t\tProcess task P%d\n",taskInProcess->taskID);
	
			taskInProcess->processed += executionTime;
			
			/* Delete the completely processed tasks from the list */
			
			if(taskInProcess->processed == taskInProcess->executionTime){
				deleteFromList(taskInProcess->taskID);
				printf(" (t=%d)\n",(currentTimeStep + executionTime));	
			}
				
			/* Modify the currenttime step                                                  */
			/* Next time step is the time where the next scheluling decision has to be made */
				
			currentTimeStep += executionTime;
		} else /* There are no ready tasks right now, go to the next step */ {
				currentTimeStep++;
				printf("There are no ready tasks on this step\n");
			}
	}
}

/* LST non-preemptive scheduler */

void scheduleLSTnonPreemptive(){

	int currentTimeStep, executionTime;
	task_t *taskInProcess;
	
	printf("LST non-priemptive scheduler\n\n");
	
	currentTimeStep = 0;
	
	/* Task 10.1: Implement the EDF non-priemptive scheduler here */
	
	printf("TO DO: 10.1!\n");
}

/* EDF preemptive scheduler */

void scheduleEDFpreemptive(){

	int currentTimeStep, executionTime;
	task_t *taskInProcess;
	int delta = 1;

	printf("EDF priemptive scheduler\n\n");
	
	currentTimeStep = 0;
	
	/* Task 10.2: Implement the EDF priemptive scheduler here */
	
	printf("TO DO: 10.2!\n");
}

/* LST preemptive scheduler */

void scheduleLSTpreemptive(){

	int currentTimeStep, executionTime;
	task_t *taskInProcess;
	int delta = 1;
	
	printf("LST priemptive scheduler\n\n");
	
	currentTimeStep = 0;
	
	/* Task 10.3: Implement the LST priemptive scheduler here */
	
	printf("TO DO: 10.3!\n");
}

void addToTaskListSet1(){

	addToTaskList(1,0,2,8);
	addToTaskList(2,0,3,5);
	addToTaskList(3,0,1,4);
	addToTaskList(4,2,1,4);
}

void addToTaskListSet2(){

	addToTaskList(1,0,2,6);
	addToTaskList(2,0,3,5);
	addToTaskList(3,0,1,4);
	addToTaskList(4,2,1,4);
}

void main()
{		
	taskList = NULL;

	addToTaskListSet1();
	
	printTasksInfo();

	/* EDF non-priemptive scheduler */

	scheduleEDFnonPreemptive();
	
	clearTaskList();

	/****************************************************/
	
	addToTaskListSet1();
	
	printTasksInfo();
	
	/* LST non-priemptive scheduler */

	scheduleLSTnonPreemptive();
	
	clearTaskList();

	/****************************************************/
	
	addToTaskListSet1();
	
	printTasksInfo();
	
	/* EDF preemptive scheduler */

	scheduleEDFpreemptive();
	
	clearTaskList();
	
	/****************************************************/
	
	addToTaskListSet1();
	
	printTasksInfo();
	
	/* LST preemptive scheduler */

	scheduleLSTpreemptive();
	
	clearTaskList();
	
	printf("The End!!!\n");

}