# MLFQ scheduler implementation

from collections import deque
import logging


class MLFQ_job:
    def __init__(self, jid):
        self.jid = jid
        self.quanta_index = 0
    def __repr__(self):
        return ( 'job {}, quanta_index {}'.format(self.jid, self.quanta_index))

class MLFQScheduler:
    def __init__(self, quanta):
        self.queue_lengths = []
        self.preempts = dict()
        self.quanta = quanta
        self.queues = dict()
        self.io = dict()
        self.running = None
        for q in quanta:
            self.queues[q] = deque()

    # called when a job is first created -- the job is assumed
    # to be ready at this point (note: job_ready will not be called
    # for a job's first CPU burst)
    def job_created(self, jid):
        printer = self.print_state('job_created',jid, self)
        job = MLFQ_job(jid)
        self.queues[self.quanta[job.quanta_index]].appendleft(job)
        self.preempts[jid] = 0

    # called when a job becomes ready after an I/O burst completes
    def job_ready(self, jid):
        printer = self.print_state('job_ready',jid, self)
        job = self.io.pop(jid, None)
        new_q = max(0,job.quanta_index - 1)
        job.quanta_index = new_q
        self.queues[self.quanta[job.quanta_index]].appendleft(job)
        self.queue_lengths.append([len(self.queues[q]) for q in self.quanta])

    # called when a job's current CPU burst runs to the end of its
    # allotted time quantum without completing -- the job is
    # still in the ready state
    def job_quantum_expired(self, jid):
        assert jid == self.running.jid
        printer = self.print_state('job_quantum_expired',jid, self)
        new_q = min(len(self.quanta) - 1, self.running.quanta_index + 1)
        job = self.running
        job.quanta_index = new_q
        self.queues[self.quanta[new_q]].appendleft(job)
        self.running = None
        self.queue_lengths.append([len(self.queues[q]) for q in self.quanta])
    
    # called when a job is preempted mid-quantum due to our
    # returning True to `needs_resched` -- the job is still in
    # the ready state
    def job_preempted(self, jid):
        assert self.running.jid == jid
        printer = self.print_state('job_preempted',jid, self)
        self.queues[self.quanta[self.running.quanta_index]].appendleft(self.running)
        self.running = None
        self.preempts[jid] += 1
        self.queue_lengths.append([len(self.queues[q]) for q in self.quanta])

    # called after a job completes its final CPU burst -- the job
    # will never become ready again
    def job_terminated(self, jid):
        printer = self.print_state('job_terminated',jid, self)
        self.running = None
        pass

    # called when a job completes its CPU burst within the current
    # time quantum and has moved into its I/O burst -- the job is
    # currently blocked
    def job_blocked(self, jid):
        printer = self.print_state('job_blocked',jid, self)
        self.io[jid] = self.running
        self.running = None

    # called by the simulator after new jobs have been made ready.
    # we should return True here if we have a more deserving job and
    # want the current job to be preempted; otherwise return False
    def needs_resched(self):
        if self.running.quanta_index != 0:
            for q in self.quanta[:self.running.quanta_index]:
                if len(self.queues[q]) > 0:
                    return True
        return False

    # return a two-tuple containing the job ID and time quantum for
    # the next job to be scheduled; if there is no ready job,
    # return (None, 0)
    def next_job_and_quantum(self):
        printer = self.print_state('next_job_and_quantum',None, self)
        for q in self.quanta:
            if len(self.queues[q]) != 0:
                self.running = self.queues[q].pop()
                return (self.running.jid, self.quanta[self.running.quanta_index])
        return (None, 0)

    # called by the simulator after all jobs have terminated -- we
    # should at this point compute and print out well-formatted
    # scheduler statistics
    def print_report(self):
        print()
        print('  JID | # Preempts')
        print('------------------')
        for jid in sorted(self.preempts.keys()):
            print('{:5d} | {:10d}'.format(jid, self.preempts[jid]))
        print()

        print('Queue | Avg length')
        print('------------------')
        sums = [sum(i) for i in zip(*self.queue_lengths)]
        avg = [float(x)/len(self.queue_lengths) for x in sums]
        for (a,q) in zip(avg, self.quanta):
            print("{:5d} | {:.2f}".format(q,a))
        print()

    class print_state:
        def __init__(self, method, jid, state):
            self.method = method
            self.jid = jid
            self.state = state
            logging.info('****')
            logging.info('%s',method)
            self._print()
        def __del__(self):
            logging.info('+++++')
            self._print()
            logging.info('****')
        def _print(self):
            if self.jid:
                logging.info('	JID: %d',self.jid)
            logging.info('	 ------ Queues ------ ')
            for q in self.state.quanta:
                logging.info('		%d %s',q, self.state.queues[q].__repr__())
            logging.info('	 ------ Blocked ------ ')
            logging.info('	%s',self.state.io.__repr__())
            logging.info('	 ------ Running ------ ')
            logging.info('	%s',self.state.running.__repr__())