###############################################################################
# Description
###############################################################################

# G-EDF Test

###############################################################################
# Imports
###############################################################################

import copy


###############################################################################
# Public Functions
###############################################################################

def gedf_test(stream):

    # Two lists to model the system: tasks occupying a CPU and tasks eligible
    # to do so. Also, m = the number of CPUs.
    eligible = []
    on_cpu = []
    m = None

    # Time of the last record we saw. Only run the G-EDF test when the time
    # is updated.
    last_time = None

    for record in stream:
        if record.record_type != "event":
            if record.record_type == "meta" and record.type_name == "num_cpus":
                m = record.num_cpus
            continue

        # Check for inversion starts and ends and yield them.
        # Only to the check when time has moved forward.
        # (It is common to have records with simultaneous timestamps.)
        if last_time is not None and last_time != record.when:
            errors = _gedf_check(eligible,on_cpu,last_time,m)
            for error in errors:
                yield error

        # Add a newly-released Job to the eligible queue
        if record.type_name == 'release':
            eligible.append(Job(record))

        # Move a Job from the eligible queue to on_cpu
        elif record.type_name == 'switch_to':
            pos = _find_job(record,eligible)
            job = eligible[pos]
            del eligible[pos]
            on_cpu.append(job)

        # Mark a Job as completed.
        # The only time a Job completes when it is not on a
        # CPU is when it is the last job of the task.
        elif record.type_name == 'completion':
            pos = _find_job(record,on_cpu)
            if pos is not None:
                on_cpu[pos].is_complete = True
            else:
                pos = _find_job(record,eligible)
                del eligible[pos]

        # A job is switched away from a CPU. If it has
        # been marked as complete, remove it from the model.
        elif record.type_name == 'switch_away':
            pos = _find_job(record,on_cpu)
            job = on_cpu[pos]
            del on_cpu[pos]
            if job.is_complete == False:
                eligible.append(job)

        last_time = record.when
        yield record

###############################################################################
# Private Functions
###############################################################################

# Internal representation of a Job
class Job(object):
    def __init__(self, record):
        self.pid = record.pid
        self.job = record.job
        self.deadline = record.deadline
        self.is_complete = False
        self.inversion_start = None
        self.inversion_end = None
    def __str__(self):
        return "(%d.%d:%d)" % (self.pid,self.job,self.deadline)

# G-EDF errors: the start or end of an inversion
class Error(object):
    def __init__(self, job, eligible, on_cpu):
        self.job = copy.copy(job)
        self.eligible = copy.copy(eligible)
        self.on_cpu = copy.copy(on_cpu)
        self.record_type = 'error'
        if job.inversion_end is None:
            self.type_name = 'inversion_start'
        else:
            self.type_name = 'inversion_end'

# Returns the position of a Job in a list, or None
def _find_job(record,list):
    for i in range(0,len(list)):
        if list[i].pid == record.pid and list[i].job == record.job:
            return i
    return None

# Return records for any inversion_starts and inversion_ends
def _gedf_check(eligible,on_cpu,when,m):

    # List of error records to be returned
    errors = []

    # List of all jobs that are not complete
    all = []
    for x in on_cpu:
        if x.is_complete is not True:
            all.append(x)
    all += eligible

    # Sort by on_cpu and then by deadline. sort() is guaranteed to be stable.
    # Thus, this gives us jobs ordered by deadline with preference to those
    # actually running.
    all.sort(key=lambda x: 0 if (x in on_cpu) else 1)
    all.sort(key=lambda x: x.deadline)

    # Check those that actually should be running
    for x in range(0,min(m,len(all))):
        job = all[x]

        # It's not running and an inversion_start has not been recorded
        if job not in on_cpu and job.inversion_start is None:
            job.inversion_start = when
            errors.append(Error(job, eligible, on_cpu))

        # It is running and an inversion_start exists (i.e. it it still
        # marked as being inverted)
        elif job in on_cpu and job.inversion_start is not None:
            job.inversion_end = when
            errors.append(Error(job, eligible, on_cpu))
            job.inversion_start = None
            job.inversion_end = None

    # Check those that actually should not be running
    for x in range(m,len(all)):
        job = all[x]

        # It actually is running. We don't care.

        # It isn't running, but an inversion_start exists (i.e. it is still
        # marked as being inverted)
        if job not in on_cpu and job.inversion_start is not None:
            job.inversion_end = when
            errors.append(Error(job, eligible, on_cpu))
            job.inversion_start = None
            job.inversion_end = None

    return errors