# EDFscheduler.py: Earliest Deadline First 
# 11/28/2003
# Jiwon Hahn

from sys import *
def load_tasks(taskfile):
	f=open(taskfile)
	data=f.read()
	f.close()

	data = data.split('\n')
	tasks = {}
	maxD = 0
	for i in data:
		i=i.split()
		if len(i) > 3:
			if i[0]=='#': continue
			tasks[i[0]]={'C':int(i[3]), #computation load
				'D':int(i[2]),  #deadline
				'R':int(i[1]), #release time
				'E':0} #executed amount
			if tasks[i[0]]['D']>maxD: 
				maxD = tasks[i[0]]['D']
	#insert idle task
	tasks['idle']={'C':maxD, 'D':maxD+1, 'R':0, 'E':0}
	return tasks, maxD 

def scheduler(tasks, D): 
	queue = [] #initialize task queue
	schedule = [] #output schedule 
	curr = '' #current task
	prev = '' #previous task
	
	#start scheduling...
	for time in range(D): 
		# insert new tasks into the queue
		for t in tasks.keys(): 
			if time == tasks[t]['R']:
				queue.append(t)	
			elif time == tasks[t]['D']:
				if tasks[t]['C']>tasks[t]['E']:
					print_schedule(schedule)
					print 'Scheduling Failed at %d!' %time
					exit(1)
		# select next task to be scheduled
		min = D+2 
		for task in queue: 
				if tasks[task]['D']<min:
					min = tasks[task]['D']
					curr = task
		tasks[curr]['E']+=1
		#dequeue the completed task
		if tasks[curr]['E'] == tasks[curr]['C']: 
			queue.remove(curr)	
		#record to the schedule trace
		if prev != curr:
			if prev in queue and prev !='idle': #previous task is preempted..
				schedule[-1].append('*')
			schedule.append([time, curr])
		prev = curr
	return schedule

def print_schedule(s):
	print ' -----------------------'
	print '|\ttime\ttask\t|'
	print ' -----------------------'
	for i in range(len(s)):
		t = s.pop(0)
		if len(t)==2:
			print '|\t%d\t%s\t|' %(t[0],t[1].strip())
		else:
			print '|\t%d\t%s\t|' %(t[0],t[1].strip()+t[2].strip())
	print ' -----------------------'

if __name__=='__main__':
	if len(argv) < 2:
		print 'Usage: python %s input_file'%argv[0]
		exit(1)
	a,b = load_tasks(argv[1])
	s = scheduler(a,b)
	print_schedule(s)