182 files changed, 4061 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..0d20b64
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1 @@
+*.pyc
diff --git a/README b/README
new file mode 100644
index 0000000..b2da190
--- /dev/null
+++ b/README
@@ -0,0 +1 @@
+See the LITMUS Wiki page for an explanation of this tool.
diff --git a/TODO b/TODO
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/TODO
diff --git a/convert.py b/convert.py
new file mode 100644
index 0000000..1db4ad0
--- /dev/null
+++ b/convert.py
@@ -0,0 +1,102 @@
+#!/usr/bin/env python
+from viz.schedule import *
+from reader.trace_reader import *
+
+"""Class that interprets the raw trace data, outputting it
+to a Python schedule object.
+
+Doesn't do any checking on the logic of the schedule (except to
+check for corrupted data)"""
+
+def get_type(type_num):
+    """Return the binary data type, given the type_num"""
+    return Trace.DATA_TYPES[type_num]
+
+def get_type_num(type):
+    nums = dict(zip(Trace.DATA_TYPES, range(0, 11)))
+    return nums[type]
+
+def _get_job_from_record(sched, record):
+    tname = _pid_to_task_name(record.pid)
+    job_no = record.job
+    if tname not in sched.get_tasks():
+        sched.add_task(Task(tname, []))
+    if job_no not in sched.get_tasks()[tname].get_jobs():
+        sched.get_tasks()[tname].add_job(Job(job_no, []))
+    job = sched.get_tasks()[tname].get_jobs()[job_no]
+    return job
+    
+def convert_trace_to_schedule(stream):
+    """The main function of interest in this module. Coverts a stream of records
+    to a Schedule object."""
+    def noop():
+        pass
+            
+    num_cpus, stream = _find_num_cpus(stream)
+    sched = Schedule('sched', num_cpus)
+    for record in stream:
+        #if record.record_type == 'meta':
+        #    if record.type_name == 'num_cpus':
+        #        sched = Schedule('sched', record.num_cpus)
+        #    continue
+        if record.record_type == 'event':
+            job = _get_job_from_record(sched, record)
+            cpu = record.cpu
+        
+            if not hasattr(record, 'deadline'):
+                record.deadline = None
+                
+            actions = {
+                'name' : (noop),
+                'params' : (noop),
+                'release' : (lambda :
+                (job.add_event(ReleaseEvent(record.when, cpu)),
+                job.add_event(DeadlineEvent(record.deadline, cpu)))),
+                'switch_to' : (lambda :
+                job.add_event(SwitchToEvent(record.when, cpu))),
+                'switch_away' : lambda :
+                job.add_event(SwitchAwayEvent(record.when, cpu)),
+                'assign' : (noop),
+                'completion' : (lambda :
+                job.add_event(CompleteEvent(record.when, cpu))),
+                'block' : (lambda :
+                job.add_event(SuspendEvent(record.when, cpu))),
+                'resume' : (lambda :
+                job.add_event(ResumeEvent(record.when, cpu))),
+                'sys_release' : (noop)
+            }
+        
+            actions[record.type_name]()
+    
+        elif record.record_type == 'error':
+            job = _get_job_from_record(sched, record.job)
+            
+            actions = {
+                'inversion_start' : (lambda :
+                job.add_event(InversionStartEvent(record.job.inversion_start))),
+                'inversion_end' : (lambda :
+                job.add_event(InversionEndEvent(record.job.inversion_end)))
+            }
+        
+            actions[record.type_name]()
+            
+    return sched
+    
+def _pid_to_task_name(pid):
+    """Converts a PID to an appropriate name for a task."""
+    return str(pid)
+          
+def _find_num_cpus(stream):
+    """Determines the number of CPUs used by scanning the binary format."""
+    max = 0
+    stream_list = []
+    for record in stream:
+        stream_list.append(record)
+        if record.record_type == 'event':
+            if record.cpu > max:
+                max = record.cpu
+    
+    def recycle(l):
+        for record in l:
+            yield record
+    return (max + 1, recycle(stream_list))
diff --git a/gedf_test.py b/gedf_test.py
new file mode 100644
index 0000000..8457901
--- /dev/null
+++ b/gedf_test.py
@@ -0,0 +1,163 @@
+###############################################################################
+# 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,record.when,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
diff --git a/litmus01.pdf b/litmus01.pdf
new file mode 100644
index 0000000..4fba2fa
--- /dev/null
+++ b/litmus01.pdf
diff --git a/litmus02.pdf b/litmus02.pdf
new file mode 100644
index 0000000..bcfdcab
--- /dev/null
+++ b/litmus02.pdf
diff --git a/mac b/mac
new file mode 160000
+Subproject cd6e43f37856f7fe6b60e0e2ae45f864a4bd6d6
diff --git a/naive_trace_reader.py b/naive_trace_reader.py
new file mode 100644
index 0000000..0f117b8
--- /dev/null
+++ b/naive_trace_reader.py
@@ -0,0 +1,165 @@
+###############################################################################
+# Description
+###############################################################################
+
+# trace_reader(files) returns an iterator which produces records
+# OUT OF ORDER from the files given. (the param is a list of files.)
+#
+# The non-naive trace_reader has a lot of complex logic which attempts to
+# produce records in order (even though they are being pulled from multiple
+# files which themselves are only approximately ordered). This trace_reader
+# attempts to be as simple as possible and is used in the unit tests to
+# make sure the total number of records read by the normal trace_reader is
+# the same as the number of records read by this one.
+
+###############################################################################
+# Imports
+###############################################################################
+
+import struct
+
+
+###############################################################################
+# Public functions
+###############################################################################
+
+# Generator function returning an iterable over records in a trace file.
+def trace_reader(files):
+    for file in files:
+        f = open(file,'rb')
+        while True:
+            data = f.read(RECORD_HEAD_SIZE)
+            try:
+                type_num = struct.unpack_from('b',data)[0]
+            except struct.error: 
+                break #We read to the end of the file
+            type = _get_type(type_num)
+            try:
+                values = struct.unpack_from(StHeader.format + 
+                    type.format,data)
+                record_dict = dict(zip(type.keys,values))
+            except struct.error:
+                f.close()
+                print "Invalid record detected, stopping."
+                exit()
+                
+            # Convert the record_dict into an object
+            record = _dict2obj(record_dict)
+
+            # Give it a type name (easier to work with than type number)
+            record.type_name = _get_type_name(type_num)
+
+            # All records should have a 'record type' field.
+            # e.g. these are 'event's as opposed to 'error's
+            record.record_type = "event"
+
+            # If there is no timestamp, set the time to 0
+            if 'when' not in record.__dict__.keys():
+                record.when = 0
+
+            yield record
+
+###############################################################################
+# Private functions
+###############################################################################
+
+# Convert a dict into an object
+def _dict2obj(d):
+    class Obj: pass
+    o = Obj()
+    for key in d.keys():
+        o.__dict__[key] = d[key]
+    return o 
+
+###############################################################################
+# Trace record data types and accessor functions
+###############################################################################
+
+# Each class below represents a type of event record. The format attribute
+# specifies how to decode the binary record and the keys attribute
+# specifies how to name the pieces of information decoded. Note that all
+# event records have a common initial 24 bytes, represented by the StHeader
+# class.
+
+RECORD_HEAD_SIZE = 24
+
+class StHeader(object):
+    format =  '<bbhi'
+    formatStr = struct.Struct(format)
+    keys = ['type','cpu','pid','job']
+    message = 'The header.'
+
+class StNameData(object):
+    format =  '16s'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['name']
+    message = 'The name of the executable of this process.'
+
+class StParamData(object):  
+    format =  'IIIc'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['wcet','period','phase','partition']
+    message = 'Regular parameters.'
+
+class StReleaseData(object):
+    format =  'QQ'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','deadline']
+    message = 'A job was/is going to be released.'
+
+#Not yet used by Sched Trace 
+class StAssignedData(object):
+    format =  'Qc'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','target']
+    message = 'A job was assigned to a CPU.'
+
+class StSwitchToData(object):
+    format =  'QI'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','exec_time']
+    message = 'A process was switched to on a given CPU.'
+
+class StSwitchAwayData(object):
+    format =  'QI'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','exec_time']
+    message = 'A process was switched away on a given CPU.'
+
+class StCompletionData(object):
+    format =  'Q3xcc'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','forced?','flags']
+    message = 'A job completed.'
+
+class StBlockData(object):
+    format =  'Q'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when']
+    message = 'A task blocks.'
+
+class StResumeData(object):
+    format =  'Q'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when']
+    message = 'A task resumes.'
+
+class StSysReleaseData(object):
+    format =  'QQ'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','release']
+    message = 'All tasks have checked in, task system released by user'
+
+# Return the binary data type, given the type_num
+def _get_type(type_num):
+    types = [None,StNameData,StParamData,StReleaseData,StAssignedData,
+             StSwitchToData,StSwitchAwayData,StCompletionData,StBlockData,
+             StResumeData,StSysReleaseData]
+    return types[type_num]
+
+# Return the type name, given the type_num (this is simply a convenience to
+#     programmers of other modules)
+def _get_type_name(type_num):
+    type_names = [None,"name","params","release","assign","switch_to",
+        "switch_away","completion","block","resume","sys_release"]
+    return type_names[type_num]
diff --git a/reader/__init__.py b/reader/__init__.py
new file mode 100644
index 0000000..afbfe44
--- /dev/null
+++ b/reader/__init__.py
@@ -0,0 +1,4 @@
+import trace_reader
+import gedf_test
+import sanitizer
+import stats
diff --git a/reader/gedf_test.py b/reader/gedf_test.py
new file mode 100644
index 0000000..e31fb19
--- /dev/null
+++ b/reader/gedf_test.py
@@ -0,0 +1,163 @@
+###############################################################################
+# 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,record.when,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
diff --git a/reader/naive_trace_reader.py b/reader/naive_trace_reader.py
new file mode 100644
index 0000000..0f117b8
--- /dev/null
+++ b/reader/naive_trace_reader.py
@@ -0,0 +1,165 @@
+###############################################################################
+# Description
+###############################################################################
+
+# trace_reader(files) returns an iterator which produces records
+# OUT OF ORDER from the files given. (the param is a list of files.)
+#
+# The non-naive trace_reader has a lot of complex logic which attempts to
+# produce records in order (even though they are being pulled from multiple
+# files which themselves are only approximately ordered). This trace_reader
+# attempts to be as simple as possible and is used in the unit tests to
+# make sure the total number of records read by the normal trace_reader is
+# the same as the number of records read by this one.
+
+###############################################################################
+# Imports
+###############################################################################
+
+import struct
+
+
+###############################################################################
+# Public functions
+###############################################################################
+
+# Generator function returning an iterable over records in a trace file.
+def trace_reader(files):
+    for file in files:
+        f = open(file,'rb')
+        while True:
+            data = f.read(RECORD_HEAD_SIZE)
+            try:
+                type_num = struct.unpack_from('b',data)[0]
+            except struct.error: 
+                break #We read to the end of the file
+            type = _get_type(type_num)
+            try:
+                values = struct.unpack_from(StHeader.format + 
+                    type.format,data)
+                record_dict = dict(zip(type.keys,values))
+            except struct.error:
+                f.close()
+                print "Invalid record detected, stopping."
+                exit()
+                
+            # Convert the record_dict into an object
+            record = _dict2obj(record_dict)
+
+            # Give it a type name (easier to work with than type number)
+            record.type_name = _get_type_name(type_num)
+
+            # All records should have a 'record type' field.
+            # e.g. these are 'event's as opposed to 'error's
+            record.record_type = "event"
+
+            # If there is no timestamp, set the time to 0
+            if 'when' not in record.__dict__.keys():
+                record.when = 0
+
+            yield record
+
+###############################################################################
+# Private functions
+###############################################################################
+
+# Convert a dict into an object
+def _dict2obj(d):
+    class Obj: pass
+    o = Obj()
+    for key in d.keys():
+        o.__dict__[key] = d[key]
+    return o 
+
+###############################################################################
+# Trace record data types and accessor functions
+###############################################################################
+
+# Each class below represents a type of event record. The format attribute
+# specifies how to decode the binary record and the keys attribute
+# specifies how to name the pieces of information decoded. Note that all
+# event records have a common initial 24 bytes, represented by the StHeader
+# class.
+
+RECORD_HEAD_SIZE = 24
+
+class StHeader(object):
+    format =  '<bbhi'
+    formatStr = struct.Struct(format)
+    keys = ['type','cpu','pid','job']
+    message = 'The header.'
+
+class StNameData(object):
+    format =  '16s'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['name']
+    message = 'The name of the executable of this process.'
+
+class StParamData(object):  
+    format =  'IIIc'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['wcet','period','phase','partition']
+    message = 'Regular parameters.'
+
+class StReleaseData(object):
+    format =  'QQ'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','deadline']
+    message = 'A job was/is going to be released.'
+
+#Not yet used by Sched Trace 
+class StAssignedData(object):
+    format =  'Qc'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','target']
+    message = 'A job was assigned to a CPU.'
+
+class StSwitchToData(object):
+    format =  'QI'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','exec_time']
+    message = 'A process was switched to on a given CPU.'
+
+class StSwitchAwayData(object):
+    format =  'QI'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','exec_time']
+    message = 'A process was switched away on a given CPU.'
+
+class StCompletionData(object):
+    format =  'Q3xcc'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','forced?','flags']
+    message = 'A job completed.'
+
+class StBlockData(object):
+    format =  'Q'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when']
+    message = 'A task blocks.'
+
+class StResumeData(object):
+    format =  'Q'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when']
+    message = 'A task resumes.'
+
+class StSysReleaseData(object):
+    format =  'QQ'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','release']
+    message = 'All tasks have checked in, task system released by user'
+
+# Return the binary data type, given the type_num
+def _get_type(type_num):
+    types = [None,StNameData,StParamData,StReleaseData,StAssignedData,
+             StSwitchToData,StSwitchAwayData,StCompletionData,StBlockData,
+             StResumeData,StSysReleaseData]
+    return types[type_num]
+
+# Return the type name, given the type_num (this is simply a convenience to
+#     programmers of other modules)
+def _get_type_name(type_num):
+    type_names = [None,"name","params","release","assign","switch_to",
+        "switch_away","completion","block","resume","sys_release"]
+    return type_names[type_num]
diff --git a/reader/runtests.py b/reader/runtests.py
new file mode 100755
index 0000000..88dddf4
--- /dev/null
+++ b/reader/runtests.py
@@ -0,0 +1,47 @@
+#!/usr/bin/python
+
+###############################################################################
+# Description
+###############################################################################
+
+# Unit Tests
+
+
+###############################################################################
+# Imports
+###############################################################################
+
+import trace_reader
+import naive_trace_reader
+import os
+
+###############################################################################
+# Trace files
+###############################################################################
+
+files = [
+'./sample_traces/st-g6-0.bin',
+'./sample_traces/st-g6-1.bin',
+'./sample_traces/st-g6-2.bin',
+'./sample_traces/st-g6-3.bin',
+]
+
+###############################################################################
+# Tests
+###############################################################################
+
+# Does our fancy trace reader get the same number of files as our naive one?
+# (See naive_trace_reader.py for further explanation)
+def test1():
+    stream = trace_reader.trace_reader(files)
+    num_records = len(list(stream))
+    stream = naive_trace_reader.trace_reader(files)
+    naive_num_records = len(list(stream))
+
+    # We need a +1 here because the fancy reader produces a 'meta' record
+    # indicating the number of CPUs
+    if num_records != naive_num_records + 1:
+        return "[FAIL]"
+    return "[SUCCESS]"
+
+print "Test 1: %s" % (test1())
diff --git a/reader/sample_script.py b/reader/sample_script.py
new file mode 100755
index 0000000..f7e9297
--- /dev/null
+++ b/reader/sample_script.py
@@ -0,0 +1,41 @@
+#!/usr/bin/python
+
+# This is a sample script for using the tool. I would recommend copying
+# this and modifying it to suit your needs for a particular test. Make
+# sure you redirect the output to a file (e.g. ./sample_script.py > output).
+
+# Import the modules we need. You should not need to know about
+# their internals.
+import trace_reader
+import sanitizer
+import gedf_test
+import stats
+import stdout_printer
+
+# Specify your trace files
+g6 = [
+'../sample_traces/st-g6-0.bin',
+'../sample_traces/st-g6-1.bin',
+'../sample_traces/st-g6-2.bin',
+'../sample_traces/st-g6-3.bin',
+]
+
+# Here is an example of a custom filter function.
+# It will remove from the error stream all inversion_end records indicating
+# an inversion of less than 4000000 time units. Thus, you can grep through
+# the output looking 'Inversion end' and find only errors for particularly
+# long inversions. This is commented out in the pipeline (below) since you
+# probably don't want it in general.
+def my_filter(record):
+    if record.record_type == 'error' and record.type_name == 'inversion_end':
+        if record.job.inversion_end - record.job.inversion_start < 4000000:
+            return False
+    return True
+
+# Pipeline
+stream = trace_reader.trace_reader(g6)   # Read events from traces
+stream = sanitizer.sanitizer(stream)     # Remove garbage events
+stream = gedf_test.gedf_test(stream)     # Produce G-EDF error records
+stream = stats.stats(stream)             # Produce a statistics record
+#stream = filter(my_filter, stream)      # Filter some records before printing
+stdout_printer.stdout_printer(stream)    # Print records to stdout
diff --git a/reader/sample_script.py~ b/reader/sample_script.py~
new file mode 100644
index 0000000..c3b7843
--- /dev/null
+++ b/reader/sample_script.py~
@@ -0,0 +1,41 @@
+#!/usr/bin/python
+
+# This is a sample script for using the tool. I would recommend copying
+# this and modifying it to suit your needs for a particular test. Make
+# sure you redirect the output to a file (e.g. ./sample_script.py > output).
+
+# Import the modules we need. You should not need to know about
+# their internals.
+import trace_reader
+import sanitizer
+import gedf_test
+import stats
+import stdout_printer
+
+# Specify your trace files
+g6 = [
+'./sample_traces/st-g6-0.bin',
+'./sample_traces/st-g6-1.bin',
+'./sample_traces/st-g6-2.bin',
+'./sample_traces/st-g6-3.bin',
+]
+
+# Here is an example of a custom filter function.
+# It will remove from the error stream all inversion_end records indicating
+# an inversion of less than 4000000 time units. Thus, you can grep through
+# the output looking 'Inversion end' and find only errors for particularly
+# long inversions. This is commented out in the pipeline (below) since you
+# probably don't want it in general.
+def my_filter(record):
+    if record.record_type == 'error' and record.type_name == 'inversion_end':
+        if record.job.inversion_end - record.job.inversion_start < 4000000:
+            return False
+    return True
+
+# Pipeline
+stream = trace_reader.trace_reader(g6)   # Read events from traces
+stream = sanitizer.sanitizer(stream)     # Remove garbage events
+stream = gedf_test.gedf_test(stream)     # Produce G-EDF error records
+stream = stats.stats(stream)             # Produce a statistics record
+#stream = filter(my_filter, stream)      # Filter some records before printing
+stdout_printer.stdout_printer(stream)    # Print records to stdout
diff --git a/reader/sanitizer.py b/reader/sanitizer.py
new file mode 100644
index 0000000..79315cc
--- /dev/null
+++ b/reader/sanitizer.py
@@ -0,0 +1,53 @@
+###############################################################################
+# Description
+###############################################################################
+
+# Sanitize input. (There are a number of goofy issues with the sched_trace
+# output.)
+
+###############################################################################
+# Public functions
+###############################################################################
+
+def sanitizer(stream):
+
+    job_2s_released = [] # list of tasks which have released their job 2s
+    jobs_switched_to = []
+
+    for record in stream:
+
+        # Ignore records which are not events (e.g. the num_cpus record)
+        if record.record_type != 'event':
+            yield record
+            continue
+
+        # All records with job < 2 are garbage
+        if record.job < 2:
+            continue
+
+        # Some records with job == 2 are garbage
+        if record.job==2:
+
+            # There is a duplicate release of every job 2
+            # This will throw away the second one
+            if record.type_name == 'release':
+                if record.pid in job_2s_released:
+                    continue
+                else:
+                    job_2s_released.append(record.pid)
+
+            # Job 2 has a resume that is garbage
+            if record.type_name == 'resume':
+                continue
+
+        # By default, the switch_away for a job (after it has completed)
+        # is maked as being for job+1, which has never been switched to.
+        # We can correct this if we note which jobs really
+        # have been switched to.
+        if record.type_name == 'switch_to':
+            jobs_switched_to.append((record.pid,record.job))
+        if record.type_name == 'switch_away':
+            if (record.pid,record.job) not in jobs_switched_to:
+                record.job -= 1
+        
+        yield record
diff --git a/reader/stats.py b/reader/stats.py
new file mode 100644
index 0000000..34a842f
--- /dev/null
+++ b/reader/stats.py
@@ -0,0 +1,39 @@
+###############################################################################
+# Description
+###############################################################################
+# Compute and produce statistics
+
+
+###############################################################################
+# Public Functions
+###############################################################################
+
+def stats(stream):
+    min_inversion = -1
+    max_inversion = -1
+    sum_inversions = 0
+    num_inversions = 0
+    for record in stream:
+        if record.type_name == 'inversion_end':
+            length = record.job.inversion_end - record.job.inversion_start
+            if length > 0:
+                num_inversions += 1
+                if length > max_inversion:
+                    max_inversion = length
+                if length < min_inversion or min_inversion == -1:
+                    min_inversion = length
+                sum_inversions += length
+        yield record
+    if num_inversions > 0:
+        avg_inversion = int(sum_inversions / num_inversions)
+    else:
+        avg_inversion = 0
+    class Obj(object): pass
+    rec = Obj()
+    rec.record_type = "meta"
+    rec.type_name = "stats"
+    rec.num_inversions = num_inversions 
+    rec.min_inversion = min_inversion
+    rec.max_inversion = max_inversion
+    rec.avg_inversion = avg_inversion
+    yield rec
diff --git a/reader/stdout_printer.py b/reader/stdout_printer.py
new file mode 100644
index 0000000..f8d9a84
--- /dev/null
+++ b/reader/stdout_printer.py
@@ -0,0 +1,69 @@
+###############################################################################
+# Description
+###############################################################################
+
+# Prints records to standard out
+
+###############################################################################
+# Public functions
+###############################################################################
+
+def stdout_printer(stream):
+    for record in stream:
+        if record.record_type == "event":
+            _print_event(record)
+        elif record.record_type == "meta" and record.type_name == "stats":
+            _print_stats(record)
+        elif record.record_type == "error" and record.type_name == 'inversion_start':
+            _print_inversion_start(record)
+        elif record.record_type == "error" and record.type_name == 'inversion_end':
+            _print_inversion_end(record)
+        else:
+            continue
+        print ""
+
+###############################################################################
+# Private functions
+###############################################################################
+
+def _print_event(record):
+    print "Job: %d.%d" % (record.pid,record.job)
+    print "Type: %s" % (record.type_name)
+    print "Time: %d" % (record.when)
+
+def _print_inversion_start(record):
+    print "Type: %s" % ("Inversion start")
+    print "Time: %d" % (record.job.inversion_start)
+    print "Job: %d.%d" % (record.job.pid,record.job.job)
+    print "Deadline: %d" % (record.job.deadline)
+    print "Eligible: ",
+    for job in record.eligible:
+        print str(job) + " ",
+    print
+    print "On CPU: ",
+    for job in record.on_cpu:
+        print str(job) + " ",
+    print #newline
+
+def _print_inversion_end(record):
+    print "Type: %s" % ("Inversion end")
+    print "Time: %d" % (record.job.inversion_end)
+    print "Duration: %d" % (
+        record.job.inversion_end - record.job.inversion_start)
+    print "Job: %d.%d" % (record.job.pid,record.job.job)
+    print "Deadline: %d" % (record.job.deadline)
+    print "Eligible: ",
+    for job in record.eligible:
+        print str(job) + " ",
+    print
+    print "On CPU: ",
+    for job in record.on_cpu:
+        print str(job) + " ",
+    print #newline
+
+def _print_stats(record):
+    print "Inversion statistics" 
+    print "Num inversions: %d" % (record.num_inversions)
+    print "Min inversion: %d" % (record.min_inversion)
+    print "Max inversion: %d" % (record.max_inversion)
+    print "Avg inversion: %d" % (record.avg_inversion)
diff --git a/reader/test.py b/reader/test.py
new file mode 100755
index 0000000..b260314
--- /dev/null
+++ b/reader/test.py
@@ -0,0 +1,15 @@
+#!/usr/bin/python
+
+import cairo
+
+if __name__ == '__main__':
+    surface = cairo.ImageSurface(cairo.FORMAT_ARGB32, 500, 500)
+    ctx = cairo.Context(surface)
+    ctx.move_to(10, 10)
+    ctx.line_to(-100, 10)
+    ctx.set_line_width(2)
+    
+    ctx.move_to(10, 10)
+    ctx.line_to(20, 10)
+    ctx.stroke()
+    surface.write_to_png('test.png')
diff --git a/reader/trace_reader.py b/reader/trace_reader.py
new file mode 100644
index 0000000..a4ff964
--- /dev/null
+++ b/reader/trace_reader.py
@@ -0,0 +1,245 @@
+###############################################################################
+# Description
+###############################################################################
+
+# trace_reader(files) returns an iterator which produces records
+# in order from the files given. (the param is a list of files.)
+#
+# Each record is just a Python object. It is guaranteed to have the following 
+# attributes:
+#   - 'pid': pid of the task
+#   - 'job': job number for that task
+#   - 'cpu', given by LITMUS
+#   - 'when', given by LITMUS as a timestamp. LITMUS does not provide a
+#       timestamp for all records. In this case, when is set to 0.
+#   - 'type', a numerical value given by LITMUS
+#   - 'type_name', a human-readable name defined in this module
+#   - 'record_type', set to 'event' by this module (to distinguish from, e.g.,
+#       error records produced elsewhere).
+#   - Possible additional attributes, depending on the type of record.
+#
+# To find out exactly what attributes are set for each record type, look at
+#     the trace-parsing information at the bottom of this file.
+
+###############################################################################
+# Imports
+###############################################################################
+
+import struct
+
+
+###############################################################################
+# Public functions
+###############################################################################
+
+# Generator function returning an iterable over records in a trace file.
+def trace_reader(files):
+
+    # Yield a record indicating the number of CPUs, used by the G-EDF test
+    class Obj: pass
+    record = Obj()
+    record.record_type = "meta"
+    record.type_name = "num_cpus"
+    record.num_cpus = len(files)
+    yield record
+
+    # Create iterators for each file and a buffer to store records in
+    file_iters = [] # file iterators
+    file_iter_buff = [] # file iterator buffers
+    for file in files:
+        file_iter = _get_file_iter(file)
+        file_iters.append(file_iter)
+        file_iter_buff.append([file_iter.next()])
+
+    # We keep 100 records in each buffer and then keep the buffer sorted
+    # This is because records may have been recorded slightly out of order
+    # This cannot guarantee records are produced in order, but it makes it
+    # overwhelmingly probably.
+    for x in range(0,len(file_iter_buff)):
+        for y in range(0,100):
+            file_iter_buff[x].append(file_iters[x].next()) 
+    for x in range(0,len(file_iter_buff)):
+        file_iter_buff[x] = sorted(file_iter_buff[x],key=lambda rec: rec.when)
+
+    # Remember the time of the last record. This way, we can make sure records
+    # truly are produced in monotonically increasing order by time and terminate
+    # fatally if they are not.
+    last_time = None
+
+    # Keep pulling records as long as we have a buffer
+    while len(file_iter_buff) > 0:
+
+        # Select the earliest record from those at the heads of the buffers
+        earliest = -1
+        buff_to_refill = -1
+        for x in range(0,len(file_iter_buff)):
+            if earliest==-1 or file_iter_buff[x][0].when < earliest.when:
+                earliest = file_iter_buff[x][0]
+                buff_to_refill = x
+
+        # Take it out of the buffer
+        del file_iter_buff[buff_to_refill][0]
+
+        # Try to append a new record to the buffer (if there is another) and
+        #     then keep the buffer sorted
+        try:
+            file_iter_buff[buff_to_refill].append(file_iters[buff_to_refill].next())
+            file_iter_buff[buff_to_refill] = sorted(file_iter_buff[buff_to_refill],
+                key=lambda rec: rec.when)
+
+        # If there aren't any more records, fine. Unless the buffer is also empty.
+        # If that is the case, delete the buffer.
+        except StopIteration:
+            if len(file_iter_buff[buff_to_refill]) < 1:
+                del file_iter_buff[buff_to_refill]
+                del file_iters[buff_to_refill]
+
+        # Check for monotonically increasing time
+        if last_time is not None and earliest.when < last_time:
+            exit("FATAL ERROR: trace_reader.py: out-of-order record produced")
+        else:
+            last_time = earliest.when
+
+        # Yield the record
+        yield earliest 
+
+###############################################################################
+# Private functions
+###############################################################################
+
+# Returns an iterator to pull records from a file
+def _get_file_iter(file):
+    f = open(file,'rb')
+    while True:
+        data = f.read(RECORD_HEAD_SIZE)
+        try:
+            type_num = struct.unpack_from('b',data)[0]
+        except struct.error: 
+            break #We read to the end of the file
+        type = _get_type(type_num)
+        try:
+            values = struct.unpack_from(StHeader.format + 
+                type.format,data)
+            record_dict = dict(zip(type.keys,values))
+        except struct.error:
+            f.close()
+            print "Invalid record detected, stopping."
+            exit()
+
+        # Convert the record_dict into an object
+        record = _dict2obj(record_dict)
+
+        # Give it a type name (easier to work with than type number)
+        record.type_name = _get_type_name(type_num)
+
+        # All records should have a 'record type' field.
+        # e.g. these are 'event's as opposed to 'error's
+        record.record_type = "event"
+
+        # If there is no timestamp, set the time to 0
+        if 'when' not in record.__dict__.keys():
+            record.when = 0
+
+        yield record
+
+# Convert a dict into an object
+def _dict2obj(d):
+    class Obj(object): pass
+    o = Obj()
+    for key in d.keys():
+        o.__dict__[key] = d[key]
+    return o 
+
+###############################################################################
+# Trace record data types and accessor functions
+###############################################################################
+
+# Each class below represents a type of event record. The format attribute
+# specifies how to decode the binary record and the keys attribute
+# specifies how to name the pieces of information decoded. Note that all
+# event records have a common initial 24 bytes, represented by the StHeader
+# class.
+
+RECORD_HEAD_SIZE = 24
+
+class StHeader:
+    format =  '<bbhi'
+    formatStr = struct.Struct(format)
+    keys = ['type','cpu','pid','job']
+    message = 'The header.'
+
+class StNameData:
+    format =  '16s'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['name']
+    message = 'The name of the executable of this process.'
+
+class StParamData:  
+    format =  'IIIc'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['wcet','period','phase','partition']
+    message = 'Regular parameters.'
+
+class StReleaseData:
+    format =  'QQ'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','deadline']
+    message = 'A job was/is going to be released.'
+
+#Not yet used by Sched Trace 
+class StAssignedData:
+    format =  'Qc'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','target']
+    message = 'A job was assigned to a CPU.'
+
+class StSwitchToData:
+    format =  'QI'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','exec_time']
+    message = 'A process was switched to on a given CPU.'
+
+class StSwitchAwayData:
+    format =  'QI'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','exec_time']
+    message = 'A process was switched away on a given CPU.'
+
+class StCompletionData:
+    #format =  'Q3x?c'
+    format = 'Q3xcc'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','forced?','flags']
+    message = 'A job completed.'
+
+class StBlockData:
+    format =  'Q'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when']
+    message = 'A task blocks.'
+
+class StResumeData:
+    format =  'Q'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when']
+    message = 'A task resumes.'
+
+class StSysReleaseData:
+    format =  'QQ'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','release']
+    message = 'All tasks have checked in, task system released by user'
+
+# Return the binary data type, given the type_num
+def _get_type(type_num):
+    types = [None,StNameData,StParamData,StReleaseData,StAssignedData,
+             StSwitchToData,StSwitchAwayData,StCompletionData,StBlockData,
+             StResumeData,StSysReleaseData]
+    return types[type_num]
+
+# Return the type name, given the type_num (this is simply a convenience to
+#     programmers of other modules)
+def _get_type_name(type_num):
+    type_names = [None,"name","params","release","assign","switch_to",
+        "switch_away","completion","block","resume","sys_release"]
+    return type_names[type_num]
diff --git a/runtests.py b/runtests.py
new file mode 100755
index 0000000..88dddf4
--- /dev/null
+++ b/runtests.py
@@ -0,0 +1,47 @@
+#!/usr/bin/python
+
+###############################################################################
+# Description
+###############################################################################
+
+# Unit Tests
+
+
+###############################################################################
+# Imports
+###############################################################################
+
+import trace_reader
+import naive_trace_reader
+import os
+
+###############################################################################
+# Trace files
+###############################################################################
+
+files = [
+'./sample_traces/st-g6-0.bin',
+'./sample_traces/st-g6-1.bin',
+'./sample_traces/st-g6-2.bin',
+'./sample_traces/st-g6-3.bin',
+]
+
+###############################################################################
+# Tests
+###############################################################################
+
+# Does our fancy trace reader get the same number of files as our naive one?
+# (See naive_trace_reader.py for further explanation)
+def test1():
+    stream = trace_reader.trace_reader(files)
+    num_records = len(list(stream))
+    stream = naive_trace_reader.trace_reader(files)
+    naive_num_records = len(list(stream))
+
+    # We need a +1 here because the fancy reader produces a 'meta' record
+    # indicating the number of CPUs
+    if num_records != naive_num_records + 1:
+        return "[FAIL]"
+    return "[SUCCESS]"
+
+print "Test 1: %s" % (test1())
diff --git a/sample_script.py b/sample_script.py
new file mode 100755
index 0000000..c3b7843
--- /dev/null
+++ b/sample_script.py
@@ -0,0 +1,41 @@
+#!/usr/bin/python
+
+# This is a sample script for using the tool. I would recommend copying
+# this and modifying it to suit your needs for a particular test. Make
+# sure you redirect the output to a file (e.g. ./sample_script.py > output).
+
+# Import the modules we need. You should not need to know about
+# their internals.
+import trace_reader
+import sanitizer
+import gedf_test
+import stats
+import stdout_printer
+
+# Specify your trace files
+g6 = [
+'./sample_traces/st-g6-0.bin',
+'./sample_traces/st-g6-1.bin',
+'./sample_traces/st-g6-2.bin',
+'./sample_traces/st-g6-3.bin',
+]
+
+# Here is an example of a custom filter function.
+# It will remove from the error stream all inversion_end records indicating
+# an inversion of less than 4000000 time units. Thus, you can grep through
+# the output looking 'Inversion end' and find only errors for particularly
+# long inversions. This is commented out in the pipeline (below) since you
+# probably don't want it in general.
+def my_filter(record):
+    if record.record_type == 'error' and record.type_name == 'inversion_end':
+        if record.job.inversion_end - record.job.inversion_start < 4000000:
+            return False
+    return True
+
+# Pipeline
+stream = trace_reader.trace_reader(g6)   # Read events from traces
+stream = sanitizer.sanitizer(stream)     # Remove garbage events
+stream = gedf_test.gedf_test(stream)     # Produce G-EDF error records
+stream = stats.stats(stream)             # Produce a statistics record
+#stream = filter(my_filter, stream)      # Filter some records before printing
+stdout_printer.stdout_printer(stream)    # Print records to stdout
diff --git a/sample_traces/.runtests.py.swp b/sample_traces/.runtests.py.swp
new file mode 100644
index 0000000..d9a9acd
--- /dev/null
+++ b/sample_traces/.runtests.py.swp
diff --git a/sample_traces/st-g6-0.bin b/sample_traces/st-g6-0.bin
new file mode 100644
index 0000000..cebc7fd
--- /dev/null
+++ b/sample_traces/st-g6-0.bin
diff --git a/sample_traces/st-g6-1.bin b/sample_traces/st-g6-1.bin
new file mode 100644
index 0000000..a51cce9
--- /dev/null
+++ b/sample_traces/st-g6-1.bin
diff --git a/sample_traces/st-g6-2.bin b/sample_traces/st-g6-2.bin
new file mode 100644
index 0000000..5d76010
--- /dev/null
+++ b/sample_traces/st-g6-2.bin
diff --git a/sample_traces/st-g6-3.bin b/sample_traces/st-g6-3.bin
new file mode 100644
index 0000000..471fc8d
--- /dev/null
+++ b/sample_traces/st-g6-3.bin
diff --git a/sanitizer.py b/sanitizer.py
new file mode 100644
index 0000000..79315cc
--- /dev/null
+++ b/sanitizer.py
@@ -0,0 +1,53 @@
+###############################################################################
+# Description
+###############################################################################
+
+# Sanitize input. (There are a number of goofy issues with the sched_trace
+# output.)
+
+###############################################################################
+# Public functions
+###############################################################################
+
+def sanitizer(stream):
+
+    job_2s_released = [] # list of tasks which have released their job 2s
+    jobs_switched_to = []
+
+    for record in stream:
+
+        # Ignore records which are not events (e.g. the num_cpus record)
+        if record.record_type != 'event':
+            yield record
+            continue
+
+        # All records with job < 2 are garbage
+        if record.job < 2:
+            continue
+
+        # Some records with job == 2 are garbage
+        if record.job==2:
+
+            # There is a duplicate release of every job 2
+            # This will throw away the second one
+            if record.type_name == 'release':
+                if record.pid in job_2s_released:
+                    continue
+                else:
+                    job_2s_released.append(record.pid)
+
+            # Job 2 has a resume that is garbage
+            if record.type_name == 'resume':
+                continue
+
+        # By default, the switch_away for a job (after it has completed)
+        # is maked as being for job+1, which has never been switched to.
+        # We can correct this if we note which jobs really
+        # have been switched to.
+        if record.type_name == 'switch_to':
+            jobs_switched_to.append((record.pid,record.job))
+        if record.type_name == 'switch_away':
+            if (record.pid,record.job) not in jobs_switched_to:
+                record.job -= 1
+        
+        yield record
diff --git a/stats.py b/stats.py
new file mode 100644
index 0000000..34a842f
--- /dev/null
+++ b/stats.py
@@ -0,0 +1,39 @@
+###############################################################################
+# Description
+###############################################################################
+# Compute and produce statistics
+
+
+###############################################################################
+# Public Functions
+###############################################################################
+
+def stats(stream):
+    min_inversion = -1
+    max_inversion = -1
+    sum_inversions = 0
+    num_inversions = 0
+    for record in stream:
+        if record.type_name == 'inversion_end':
+            length = record.job.inversion_end - record.job.inversion_start
+            if length > 0:
+                num_inversions += 1
+                if length > max_inversion:
+                    max_inversion = length
+                if length < min_inversion or min_inversion == -1:
+                    min_inversion = length
+                sum_inversions += length
+        yield record
+    if num_inversions > 0:
+        avg_inversion = int(sum_inversions / num_inversions)
+    else:
+        avg_inversion = 0
+    class Obj(object): pass
+    rec = Obj()
+    rec.record_type = "meta"
+    rec.type_name = "stats"
+    rec.num_inversions = num_inversions 
+    rec.min_inversion = min_inversion
+    rec.max_inversion = max_inversion
+    rec.avg_inversion = avg_inversion
+    yield rec
diff --git a/stdout_printer.py b/stdout_printer.py
new file mode 100644
index 0000000..f8d9a84
--- /dev/null
+++ b/stdout_printer.py
@@ -0,0 +1,69 @@
+###############################################################################
+# Description
+###############################################################################
+
+# Prints records to standard out
+
+###############################################################################
+# Public functions
+###############################################################################
+
+def stdout_printer(stream):
+    for record in stream:
+        if record.record_type == "event":
+            _print_event(record)
+        elif record.record_type == "meta" and record.type_name == "stats":
+            _print_stats(record)
+        elif record.record_type == "error" and record.type_name == 'inversion_start':
+            _print_inversion_start(record)
+        elif record.record_type == "error" and record.type_name == 'inversion_end':
+            _print_inversion_end(record)
+        else:
+            continue
+        print ""
+
+###############################################################################
+# Private functions
+###############################################################################
+
+def _print_event(record):
+    print "Job: %d.%d" % (record.pid,record.job)
+    print "Type: %s" % (record.type_name)
+    print "Time: %d" % (record.when)
+
+def _print_inversion_start(record):
+    print "Type: %s" % ("Inversion start")
+    print "Time: %d" % (record.job.inversion_start)
+    print "Job: %d.%d" % (record.job.pid,record.job.job)
+    print "Deadline: %d" % (record.job.deadline)
+    print "Eligible: ",
+    for job in record.eligible:
+        print str(job) + " ",
+    print
+    print "On CPU: ",
+    for job in record.on_cpu:
+        print str(job) + " ",
+    print #newline
+
+def _print_inversion_end(record):
+    print "Type: %s" % ("Inversion end")
+    print "Time: %d" % (record.job.inversion_end)
+    print "Duration: %d" % (
+        record.job.inversion_end - record.job.inversion_start)
+    print "Job: %d.%d" % (record.job.pid,record.job.job)
+    print "Deadline: %d" % (record.job.deadline)
+    print "Eligible: ",
+    for job in record.eligible:
+        print str(job) + " ",
+    print
+    print "On CPU: ",
+    for job in record.on_cpu:
+        print str(job) + " ",
+    print #newline
+
+def _print_stats(record):
+    print "Inversion statistics" 
+    print "Num inversions: %d" % (record.num_inversions)
+    print "Min inversion: %d" % (record.min_inversion)
+    print "Max inversion: %d" % (record.max_inversion)
+    print "Avg inversion: %d" % (record.avg_inversion)
diff --git a/trace_reader.py b/trace_reader.py
new file mode 100644
index 0000000..a4ff964
--- /dev/null
+++ b/trace_reader.py
@@ -0,0 +1,245 @@
+###############################################################################
+# Description
+###############################################################################
+
+# trace_reader(files) returns an iterator which produces records
+# in order from the files given. (the param is a list of files.)
+#
+# Each record is just a Python object. It is guaranteed to have the following 
+# attributes:
+#   - 'pid': pid of the task
+#   - 'job': job number for that task
+#   - 'cpu', given by LITMUS
+#   - 'when', given by LITMUS as a timestamp. LITMUS does not provide a
+#       timestamp for all records. In this case, when is set to 0.
+#   - 'type', a numerical value given by LITMUS
+#   - 'type_name', a human-readable name defined in this module
+#   - 'record_type', set to 'event' by this module (to distinguish from, e.g.,
+#       error records produced elsewhere).
+#   - Possible additional attributes, depending on the type of record.
+#
+# To find out exactly what attributes are set for each record type, look at
+#     the trace-parsing information at the bottom of this file.
+
+###############################################################################
+# Imports
+###############################################################################
+
+import struct
+
+
+###############################################################################
+# Public functions
+###############################################################################
+
+# Generator function returning an iterable over records in a trace file.
+def trace_reader(files):
+
+    # Yield a record indicating the number of CPUs, used by the G-EDF test
+    class Obj: pass
+    record = Obj()
+    record.record_type = "meta"
+    record.type_name = "num_cpus"
+    record.num_cpus = len(files)
+    yield record
+
+    # Create iterators for each file and a buffer to store records in
+    file_iters = [] # file iterators
+    file_iter_buff = [] # file iterator buffers
+    for file in files:
+        file_iter = _get_file_iter(file)
+        file_iters.append(file_iter)
+        file_iter_buff.append([file_iter.next()])
+
+    # We keep 100 records in each buffer and then keep the buffer sorted
+    # This is because records may have been recorded slightly out of order
+    # This cannot guarantee records are produced in order, but it makes it
+    # overwhelmingly probably.
+    for x in range(0,len(file_iter_buff)):
+        for y in range(0,100):
+            file_iter_buff[x].append(file_iters[x].next()) 
+    for x in range(0,len(file_iter_buff)):
+        file_iter_buff[x] = sorted(file_iter_buff[x],key=lambda rec: rec.when)
+
+    # Remember the time of the last record. This way, we can make sure records
+    # truly are produced in monotonically increasing order by time and terminate
+    # fatally if they are not.
+    last_time = None
+
+    # Keep pulling records as long as we have a buffer
+    while len(file_iter_buff) > 0:
+
+        # Select the earliest record from those at the heads of the buffers
+        earliest = -1
+        buff_to_refill = -1
+        for x in range(0,len(file_iter_buff)):
+            if earliest==-1 or file_iter_buff[x][0].when < earliest.when:
+                earliest = file_iter_buff[x][0]
+                buff_to_refill = x
+
+        # Take it out of the buffer
+        del file_iter_buff[buff_to_refill][0]
+
+        # Try to append a new record to the buffer (if there is another) and
+        #     then keep the buffer sorted
+        try:
+            file_iter_buff[buff_to_refill].append(file_iters[buff_to_refill].next())
+            file_iter_buff[buff_to_refill] = sorted(file_iter_buff[buff_to_refill],
+                key=lambda rec: rec.when)
+
+        # If there aren't any more records, fine. Unless the buffer is also empty.
+        # If that is the case, delete the buffer.
+        except StopIteration:
+            if len(file_iter_buff[buff_to_refill]) < 1:
+                del file_iter_buff[buff_to_refill]
+                del file_iters[buff_to_refill]
+
+        # Check for monotonically increasing time
+        if last_time is not None and earliest.when < last_time:
+            exit("FATAL ERROR: trace_reader.py: out-of-order record produced")
+        else:
+            last_time = earliest.when
+
+        # Yield the record
+        yield earliest 
+
+###############################################################################
+# Private functions
+###############################################################################
+
+# Returns an iterator to pull records from a file
+def _get_file_iter(file):
+    f = open(file,'rb')
+    while True:
+        data = f.read(RECORD_HEAD_SIZE)
+        try:
+            type_num = struct.unpack_from('b',data)[0]
+        except struct.error: 
+            break #We read to the end of the file
+        type = _get_type(type_num)
+        try:
+            values = struct.unpack_from(StHeader.format + 
+                type.format,data)
+            record_dict = dict(zip(type.keys,values))
+        except struct.error:
+            f.close()
+            print "Invalid record detected, stopping."
+            exit()
+
+        # Convert the record_dict into an object
+        record = _dict2obj(record_dict)
+
+        # Give it a type name (easier to work with than type number)
+        record.type_name = _get_type_name(type_num)
+
+        # All records should have a 'record type' field.
+        # e.g. these are 'event's as opposed to 'error's
+        record.record_type = "event"
+
+        # If there is no timestamp, set the time to 0
+        if 'when' not in record.__dict__.keys():
+            record.when = 0
+
+        yield record
+
+# Convert a dict into an object
+def _dict2obj(d):
+    class Obj(object): pass
+    o = Obj()
+    for key in d.keys():
+        o.__dict__[key] = d[key]
+    return o 
+
+###############################################################################
+# Trace record data types and accessor functions
+###############################################################################
+
+# Each class below represents a type of event record. The format attribute
+# specifies how to decode the binary record and the keys attribute
+# specifies how to name the pieces of information decoded. Note that all
+# event records have a common initial 24 bytes, represented by the StHeader
+# class.
+
+RECORD_HEAD_SIZE = 24
+
+class StHeader:
+    format =  '<bbhi'
+    formatStr = struct.Struct(format)
+    keys = ['type','cpu','pid','job']
+    message = 'The header.'
+
+class StNameData:
+    format =  '16s'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['name']
+    message = 'The name of the executable of this process.'
+
+class StParamData:  
+    format =  'IIIc'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['wcet','period','phase','partition']
+    message = 'Regular parameters.'
+
+class StReleaseData:
+    format =  'QQ'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','deadline']
+    message = 'A job was/is going to be released.'
+
+#Not yet used by Sched Trace 
+class StAssignedData:
+    format =  'Qc'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','target']
+    message = 'A job was assigned to a CPU.'
+
+class StSwitchToData:
+    format =  'QI'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','exec_time']
+    message = 'A process was switched to on a given CPU.'
+
+class StSwitchAwayData:
+    format =  'QI'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','exec_time']
+    message = 'A process was switched away on a given CPU.'
+
+class StCompletionData:
+    #format =  'Q3x?c'
+    format = 'Q3xcc'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','forced?','flags']
+    message = 'A job completed.'
+
+class StBlockData:
+    format =  'Q'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when']
+    message = 'A task blocks.'
+
+class StResumeData:
+    format =  'Q'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when']
+    message = 'A task resumes.'
+
+class StSysReleaseData:
+    format =  'QQ'
+    formatStr = struct.Struct(StHeader.format + format)
+    keys = StHeader.keys + ['when','release']
+    message = 'All tasks have checked in, task system released by user'
+
+# Return the binary data type, given the type_num
+def _get_type(type_num):
+    types = [None,StNameData,StParamData,StReleaseData,StAssignedData,
+             StSwitchToData,StSwitchAwayData,StCompletionData,StBlockData,
+             StResumeData,StSysReleaseData]
+    return types[type_num]
+
+# Return the type name, given the type_num (this is simply a convenience to
+#     programmers of other modules)
+def _get_type_name(type_num):
+    type_names = [None,"name","params","release","assign","switch_to",
+        "switch_away","completion","block","resume","sys_release"]
+    return type_names[type_num]
diff --git a/traces/g1.pdf b/traces/g1.pdf
new file mode 100644
index 0000000..c9ee920
--- /dev/null
+++ b/traces/g1.pdf
diff --git a/traces/g2.pdf b/traces/g2.pdf
new file mode 100644
index 0000000..a807c9f
--- /dev/null
+++ b/traces/g2.pdf
diff --git a/traces/g3.pdf b/traces/g3.pdf
new file mode 100644
index 0000000..3bb4e78
--- /dev/null
+++ b/traces/g3.pdf
diff --git a/traces/g4.pdf b/traces/g4.pdf
new file mode 100644
index 0000000..867f413
--- /dev/null
+++ b/traces/g4.pdf
diff --git a/traces/g5.pdf b/traces/g5.pdf
new file mode 100644
index 0000000..c12ebde
--- /dev/null
+++ b/traces/g5.pdf
diff --git a/traces/g6.pdf b/traces/g6.pdf
new file mode 100644
index 0000000..3c8d667
--- /dev/null
+++ b/traces/g6.pdf
diff --git a/traces/heavy.ts b/traces/heavy.ts
new file mode 100644
index 0000000..8df12a0
--- /dev/null
+++ b/traces/heavy.ts
@@ -0,0 +1,9 @@
+#EXE=200
+#PER=300
+EXE=17
+PER=30
+
+for i in `seq 1 6`
+do
+        rt_launch -w $EXE $PER run
+done
diff --git a/traces/heavy2.ts b/traces/heavy2.ts
new file mode 100644
index 0000000..23d5e0f
--- /dev/null
+++ b/traces/heavy2.ts
@@ -0,0 +1,7 @@
+EXE=18
+PER=30
+
+for i in `seq 1 6`
+do
+        rtspin -w $EXE $PER 3 &
+done
diff --git a/traces/light.ts b/traces/light.ts
new file mode 100644
index 0000000..db961b2
--- /dev/null
+++ b/traces/light.ts
@@ -0,0 +1,9 @@
+#EXE=200
+#PER=300
+EXE=2
+PER=11
+
+for i in `seq 1 18`
+do
+        rt_launch -w $EXE $PER run
+done
diff --git a/traces/medium.ts b/traces/medium.ts
new file mode 100644
index 0000000..a800180
--- /dev/null
+++ b/traces/medium.ts
@@ -0,0 +1,7 @@
+EXE=2
+PER=12
+
+for i in `seq 1 6`
+do
+        rt_launch -w $EXE $PER run
+done
diff --git a/traces/mixed.ts b/traces/mixed.ts
new file mode 100644
index 0000000..1258d1a
--- /dev/null
+++ b/traces/mixed.ts
@@ -0,0 +1,15 @@
+#EXE=200
+#PER=300
+EXE=2
+PER=11
+
+for i in `seq 10 20`
+do
+        rtspin -w $EXE $i 2 &
+done
+
+EXE=17
+for i in 31 32 33
+do
+        rtspin -w $EXE $i 2 &
+done
diff --git a/traces/st-g1-0.bin b/traces/st-g1-0.bin
new file mode 100644
index 0000000..a88bd3e
--- /dev/null
+++ b/traces/st-g1-0.bin
diff --git a/traces/st-g1-1.bin b/traces/st-g1-1.bin
new file mode 100644
index 0000000..8439bb8
--- /dev/null
+++ b/traces/st-g1-1.bin
diff --git a/traces/st-g1-2.bin b/traces/st-g1-2.bin
new file mode 100644
index 0000000..371bf49
--- /dev/null
+++ b/traces/st-g1-2.bin
diff --git a/traces/st-g1-3.bin b/traces/st-g1-3.bin
new file mode 100644
index 0000000..fa59c60
--- /dev/null
+++ b/traces/st-g1-3.bin
diff --git a/traces/st-g3-0.bin b/traces/st-g3-0.bin
new file mode 100644
index 0000000..37fdbb3
--- /dev/null
+++ b/traces/st-g3-0.bin
diff --git a/traces/st-g3-1.bin b/traces/st-g3-1.bin
new file mode 100644
index 0000000..583e1ec
--- /dev/null
+++ b/traces/st-g3-1.bin
diff --git a/traces/st-g3-2.bin b/traces/st-g3-2.bin
new file mode 100644
index 0000000..d93c7ee
--- /dev/null
+++ b/traces/st-g3-2.bin
diff --git a/traces/st-g3-3.bin b/traces/st-g3-3.bin
new file mode 100644
index 0000000..21e0de7
--- /dev/null
+++ b/traces/st-g3-3.bin
diff --git a/traces/st-g4-0.bin b/traces/st-g4-0.bin
new file mode 100644
index 0000000..c52ed7b
--- /dev/null
+++ b/traces/st-g4-0.bin
diff --git a/traces/st-g4-1.bin b/traces/st-g4-1.bin
new file mode 100644
index 0000000..77fea28
--- /dev/null
+++ b/traces/st-g4-1.bin
diff --git a/traces/st-g4-2.bin b/traces/st-g4-2.bin
new file mode 100644
index 0000000..4d5d3cd
--- /dev/null
+++ b/traces/st-g4-2.bin
diff --git a/traces/st-g4-3.bin b/traces/st-g4-3.bin
new file mode 100644
index 0000000..1cd7ee4
--- /dev/null
+++ b/traces/st-g4-3.bin
diff --git a/traces/st-g5-0.bin b/traces/st-g5-0.bin
new file mode 100644
index 0000000..c576250
--- /dev/null
+++ b/traces/st-g5-0.bin
diff --git a/traces/st-g5-1.bin b/traces/st-g5-1.bin
new file mode 100644
index 0000000..90c4960
--- /dev/null
+++ b/traces/st-g5-1.bin
diff --git a/traces/st-g5-2.bin b/traces/st-g5-2.bin
new file mode 100644
index 0000000..a06aa10
--- /dev/null
+++ b/traces/st-g5-2.bin
diff --git a/traces/st-g5-3.bin b/traces/st-g5-3.bin
new file mode 100644
index 0000000..561b776
--- /dev/null
+++ b/traces/st-g5-3.bin
diff --git a/traces/st-g6-0.bin b/traces/st-g6-0.bin
new file mode 100644
index 0000000..cebc7fd
--- /dev/null
+++ b/traces/st-g6-0.bin
diff --git a/traces/st-g6-1.bin b/traces/st-g6-1.bin
new file mode 100644
index 0000000..a51cce9
--- /dev/null
+++ b/traces/st-g6-1.bin
diff --git a/traces/st-g6-2.bin b/traces/st-g6-2.bin
new file mode 100644
index 0000000..5d76010
--- /dev/null
+++ b/traces/st-g6-2.bin
diff --git a/traces/st-g6-3.bin b/traces/st-g6-3.bin
new file mode 100644
index 0000000..471fc8d
--- /dev/null
+++ b/traces/st-g6-3.bin
diff --git a/traces/st-heavy-0.bin b/traces/st-heavy-0.bin
new file mode 100644
index 0000000..7a86776
--- /dev/null
+++ b/traces/st-heavy-0.bin
diff --git a/traces/st-heavy-1.bin b/traces/st-heavy-1.bin
new file mode 100644
index 0000000..9b8d976
--- /dev/null
+++ b/traces/st-heavy-1.bin
diff --git a/traces/st-heavy-2.bin b/traces/st-heavy-2.bin
new file mode 100644
index 0000000..eb59023
--- /dev/null
+++ b/traces/st-heavy-2.bin
diff --git a/traces/st-heavy-3.bin b/traces/st-heavy-3.bin
new file mode 100644
index 0000000..06f73b5
--- /dev/null
+++ b/traces/st-heavy-3.bin
diff --git a/traces/st-heavy2-0.bin b/traces/st-heavy2-0.bin
new file mode 100644
index 0000000..4931d70
--- /dev/null
+++ b/traces/st-heavy2-0.bin
diff --git a/traces/st-heavy2-1.bin b/traces/st-heavy2-1.bin
new file mode 100644
index 0000000..fbe14a0
--- /dev/null
+++ b/traces/st-heavy2-1.bin
diff --git a/traces/st-heavy2-2.bin b/traces/st-heavy2-2.bin
new file mode 100644
index 0000000..d8edc0a
--- /dev/null
+++ b/traces/st-heavy2-2.bin
diff --git a/traces/st-heavy2-3.bin b/traces/st-heavy2-3.bin
new file mode 100644
index 0000000..c173014
--- /dev/null
+++ b/traces/st-heavy2-3.bin
diff --git a/traces/st-heavy3-0.bin b/traces/st-heavy3-0.bin
new file mode 100644
index 0000000..4af21ed
--- /dev/null
+++ b/traces/st-heavy3-0.bin
diff --git a/traces/st-heavy3-1.bin b/traces/st-heavy3-1.bin
new file mode 100644
index 0000000..b62ffac
--- /dev/null
+++ b/traces/st-heavy3-1.bin
diff --git a/traces/st-heavy3-2.bin b/traces/st-heavy3-2.bin
new file mode 100644
index 0000000..39a12e6
--- /dev/null
+++ b/traces/st-heavy3-2.bin
diff --git a/traces/st-heavy3-3.bin b/traces/st-heavy3-3.bin
new file mode 100644
index 0000000..ae4a6a4
--- /dev/null
+++ b/traces/st-heavy3-3.bin
diff --git a/traces/st-mac-0.bin b/traces/st-mac-0.bin
new file mode 100644
index 0000000..7bac67d
--- /dev/null
+++ b/traces/st-mac-0.bin
diff --git a/traces/st-mac-1.bin b/traces/st-mac-1.bin
new file mode 100644
index 0000000..a8a2f7e
--- /dev/null
+++ b/traces/st-mac-1.bin
diff --git a/traces/st-mac-test-0.bin b/traces/st-mac-test-0.bin
new file mode 100644
index 0000000..06e8403
--- /dev/null
+++ b/traces/st-mac-test-0.bin
diff --git a/traces/st-mac2-0.bin b/traces/st-mac2-0.bin
new file mode 100644
index 0000000..5afe202
--- /dev/null
+++ b/traces/st-mac2-0.bin
diff --git a/traces/st-s1-0.bin b/traces/st-s1-0.bin
new file mode 100644
index 0000000..5ad50f9
--- /dev/null
+++ b/traces/st-s1-0.bin
diff --git a/traces/st-s1-1.bin b/traces/st-s1-1.bin
new file mode 100644
index 0000000..7554c44
--- /dev/null
+++ b/traces/st-s1-1.bin
diff --git a/traces/st-s1-2.bin b/traces/st-s1-2.bin
new file mode 100644
index 0000000..047248c
--- /dev/null
+++ b/traces/st-s1-2.bin
diff --git a/traces/st-s1-3.bin b/traces/st-s1-3.bin
new file mode 100644
index 0000000..039e1a9
--- /dev/null
+++ b/traces/st-s1-3.bin
diff --git a/traces/st-s2-0.bin b/traces/st-s2-0.bin
new file mode 100644
index 0000000..639c561
--- /dev/null
+++ b/traces/st-s2-0.bin
diff --git a/traces/st-s2-1.bin b/traces/st-s2-1.bin
new file mode 100644
index 0000000..36f0254
--- /dev/null
+++ b/traces/st-s2-1.bin
diff --git a/traces/st-s2-2.bin b/traces/st-s2-2.bin
new file mode 100644
index 0000000..777c1f4
--- /dev/null
+++ b/traces/st-s2-2.bin
diff --git a/traces/st-s2-3.bin b/traces/st-s2-3.bin
new file mode 100644
index 0000000..917cb86
--- /dev/null
+++ b/traces/st-s2-3.bin
diff --git a/traces/st-x10-0.bin b/traces/st-x10-0.bin
new file mode 100644
index 0000000..a372e75
--- /dev/null
+++ b/traces/st-x10-0.bin
diff --git a/traces/st-x10-1.bin b/traces/st-x10-1.bin
new file mode 100644
index 0000000..bcf8d01
--- /dev/null
+++ b/traces/st-x10-1.bin
diff --git a/traces/st-x10-2.bin b/traces/st-x10-2.bin
new file mode 100644
index 0000000..3149ca8
--- /dev/null
+++ b/traces/st-x10-2.bin
diff --git a/traces/st-x10-3.bin b/traces/st-x10-3.bin
new file mode 100644
index 0000000..cf899fd
--- /dev/null
+++ b/traces/st-x10-3.bin
diff --git a/traces/st-x11-0.bin b/traces/st-x11-0.bin
new file mode 100644
index 0000000..8404d49
--- /dev/null
+++ b/traces/st-x11-0.bin
diff --git a/traces/st-x11-1.bin b/traces/st-x11-1.bin
new file mode 100644
index 0000000..67e9063
--- /dev/null
+++ b/traces/st-x11-1.bin
diff --git a/traces/st-x11-2.bin b/traces/st-x11-2.bin
new file mode 100644
index 0000000..a16c740
--- /dev/null
+++ b/traces/st-x11-2.bin
diff --git a/traces/st-x11-3.bin b/traces/st-x11-3.bin
new file mode 100644
index 0000000..cbc4c54
--- /dev/null
+++ b/traces/st-x11-3.bin
diff --git a/traces/st-x12-0.bin b/traces/st-x12-0.bin
new file mode 100644
index 0000000..66a9995
--- /dev/null
+++ b/traces/st-x12-0.bin
diff --git a/traces/st-x12-1.bin b/traces/st-x12-1.bin
new file mode 100644
index 0000000..515f953
--- /dev/null
+++ b/traces/st-x12-1.bin
diff --git a/traces/st-x12-2.bin b/traces/st-x12-2.bin
new file mode 100644
index 0000000..c21fce8
--- /dev/null
+++ b/traces/st-x12-2.bin
diff --git a/traces/st-x12-3.bin b/traces/st-x12-3.bin
new file mode 100644
index 0000000..bc7be12
--- /dev/null
+++ b/traces/st-x12-3.bin
diff --git a/traces/st-x13-0.bin b/traces/st-x13-0.bin
new file mode 100644
index 0000000..023e917
--- /dev/null
+++ b/traces/st-x13-0.bin
diff --git a/traces/st-x13-1.bin b/traces/st-x13-1.bin
new file mode 100644
index 0000000..6072f16
--- /dev/null
+++ b/traces/st-x13-1.bin
diff --git a/traces/st-x13-2.bin b/traces/st-x13-2.bin
new file mode 100644
index 0000000..c59a852
--- /dev/null
+++ b/traces/st-x13-2.bin
diff --git a/traces/st-x13-3.bin b/traces/st-x13-3.bin
new file mode 100644
index 0000000..295de3a
--- /dev/null
+++ b/traces/st-x13-3.bin
diff --git a/traces/st-x14-0.bin b/traces/st-x14-0.bin
new file mode 100644
index 0000000..19808b3
--- /dev/null
+++ b/traces/st-x14-0.bin
diff --git a/traces/st-x14-1.bin b/traces/st-x14-1.bin
new file mode 100644
index 0000000..34b3e63
--- /dev/null
+++ b/traces/st-x14-1.bin
diff --git a/traces/st-x14-2.bin b/traces/st-x14-2.bin
new file mode 100644
index 0000000..055851c
--- /dev/null
+++ b/traces/st-x14-2.bin
diff --git a/traces/st-x14-3.bin b/traces/st-x14-3.bin
new file mode 100644
index 0000000..9ade092
--- /dev/null
+++ b/traces/st-x14-3.bin
diff --git a/traces/st-x15-0.bin b/traces/st-x15-0.bin
new file mode 100644
index 0000000..ce0b025
--- /dev/null
+++ b/traces/st-x15-0.bin
diff --git a/traces/st-x15-1.bin b/traces/st-x15-1.bin
new file mode 100644
index 0000000..1b2c23e
--- /dev/null
+++ b/traces/st-x15-1.bin
diff --git a/traces/st-x15-2.bin b/traces/st-x15-2.bin
new file mode 100644
index 0000000..9da74e5
--- /dev/null
+++ b/traces/st-x15-2.bin
diff --git a/traces/st-x15-3.bin b/traces/st-x15-3.bin
new file mode 100644
index 0000000..9645cd9
--- /dev/null
+++ b/traces/st-x15-3.bin
diff --git a/traces/st-x16-0.bin b/traces/st-x16-0.bin
new file mode 100644
index 0000000..175e14a
--- /dev/null
+++ b/traces/st-x16-0.bin
diff --git a/traces/st-x16-1.bin b/traces/st-x16-1.bin
new file mode 100644
index 0000000..73a1ae5
--- /dev/null
+++ b/traces/st-x16-1.bin
diff --git a/traces/st-x16-2.bin b/traces/st-x16-2.bin
new file mode 100644
index 0000000..8fcb27e
--- /dev/null
+++ b/traces/st-x16-2.bin
diff --git a/traces/st-x16-3.bin b/traces/st-x16-3.bin
new file mode 100644
index 0000000..6f1d246
--- /dev/null
+++ b/traces/st-x16-3.bin
diff --git a/traces/st-x17-0.bin b/traces/st-x17-0.bin
new file mode 100644
index 0000000..c03c249
--- /dev/null
+++ b/traces/st-x17-0.bin
diff --git a/traces/st-x17-1.bin b/traces/st-x17-1.bin
new file mode 100644
index 0000000..c0ea44d
--- /dev/null
+++ b/traces/st-x17-1.bin
diff --git a/traces/st-x17-2.bin b/traces/st-x17-2.bin
new file mode 100644
index 0000000..2da0356
--- /dev/null
+++ b/traces/st-x17-2.bin
diff --git a/traces/st-x17-3.bin b/traces/st-x17-3.bin
new file mode 100644
index 0000000..207d1a7
--- /dev/null
+++ b/traces/st-x17-3.bin
diff --git a/traces/st-x18-0.bin b/traces/st-x18-0.bin
new file mode 100644
index 0000000..2ed81f1
--- /dev/null
+++ b/traces/st-x18-0.bin
diff --git a/traces/st-x18-1.bin b/traces/st-x18-1.bin
new file mode 100644
index 0000000..dd791c1
--- /dev/null
+++ b/traces/st-x18-1.bin
diff --git a/traces/st-x18-2.bin b/traces/st-x18-2.bin
new file mode 100644
index 0000000..f90d9ab
--- /dev/null
+++ b/traces/st-x18-2.bin
diff --git a/traces/st-x18-3.bin b/traces/st-x18-3.bin
new file mode 100644
index 0000000..944156a
--- /dev/null
+++ b/traces/st-x18-3.bin
diff --git a/traces/st-x19-0.bin b/traces/st-x19-0.bin
new file mode 100644
index 0000000..1aeea29
--- /dev/null
+++ b/traces/st-x19-0.bin
diff --git a/traces/st-x19-1.bin b/traces/st-x19-1.bin
new file mode 100644
index 0000000..9e2129a
--- /dev/null
+++ b/traces/st-x19-1.bin
diff --git a/traces/st-x19-2.bin b/traces/st-x19-2.bin
new file mode 100644
index 0000000..e9cd71b
--- /dev/null
+++ b/traces/st-x19-2.bin
diff --git a/traces/st-x19-3.bin b/traces/st-x19-3.bin
new file mode 100644
index 0000000..530523d
--- /dev/null
+++ b/traces/st-x19-3.bin
diff --git a/traces/st-x2-0.bin b/traces/st-x2-0.bin
new file mode 100644
index 0000000..e24dcab
--- /dev/null
+++ b/traces/st-x2-0.bin
diff --git a/traces/st-x2-1.bin b/traces/st-x2-1.bin
new file mode 100644
index 0000000..4a66180
--- /dev/null
+++ b/traces/st-x2-1.bin
diff --git a/traces/st-x2-2.bin b/traces/st-x2-2.bin
new file mode 100644
index 0000000..76cde24
--- /dev/null
+++ b/traces/st-x2-2.bin
diff --git a/traces/st-x2-3.bin b/traces/st-x2-3.bin
new file mode 100644
index 0000000..faa0b90
--- /dev/null
+++ b/traces/st-x2-3.bin
diff --git a/traces/st-x3-0.bin b/traces/st-x3-0.bin
new file mode 100644
index 0000000..60107c7
--- /dev/null
+++ b/traces/st-x3-0.bin
diff --git a/traces/st-x3-1.bin b/traces/st-x3-1.bin
new file mode 100644
index 0000000..7a5fe39
--- /dev/null
+++ b/traces/st-x3-1.bin
diff --git a/traces/st-x3-2.bin b/traces/st-x3-2.bin
new file mode 100644
index 0000000..1d40df6
--- /dev/null
+++ b/traces/st-x3-2.bin
diff --git a/traces/st-x3-3.bin b/traces/st-x3-3.bin
new file mode 100644
index 0000000..afba2e1
--- /dev/null
+++ b/traces/st-x3-3.bin
diff --git a/traces/st-x4-0.bin b/traces/st-x4-0.bin
new file mode 100644
index 0000000..260bec7
--- /dev/null
+++ b/traces/st-x4-0.bin
diff --git a/traces/st-x4-1.bin b/traces/st-x4-1.bin
new file mode 100644
index 0000000..17669ae
--- /dev/null
+++ b/traces/st-x4-1.bin
diff --git a/traces/st-x4-2.bin b/traces/st-x4-2.bin
new file mode 100644
index 0000000..a02713f
--- /dev/null
+++ b/traces/st-x4-2.bin
diff --git a/traces/st-x4-3.bin b/traces/st-x4-3.bin
new file mode 100644
index 0000000..db5e880
--- /dev/null
+++ b/traces/st-x4-3.bin
diff --git a/traces/st-x5-0.bin b/traces/st-x5-0.bin
new file mode 100644
index 0000000..6fb2ac3
--- /dev/null
+++ b/traces/st-x5-0.bin
diff --git a/traces/st-x5-1.bin b/traces/st-x5-1.bin
new file mode 100644
index 0000000..6466f25
--- /dev/null
+++ b/traces/st-x5-1.bin
diff --git a/traces/st-x5-2.bin b/traces/st-x5-2.bin
new file mode 100644
index 0000000..93915e9
--- /dev/null
+++ b/traces/st-x5-2.bin
diff --git a/traces/st-x5-3.bin b/traces/st-x5-3.bin
new file mode 100644
index 0000000..69fb611
--- /dev/null
+++ b/traces/st-x5-3.bin
diff --git a/traces/st-x6-0.bin b/traces/st-x6-0.bin
new file mode 100644
index 0000000..ed18dae
--- /dev/null
+++ b/traces/st-x6-0.bin
diff --git a/traces/st-x6-1.bin b/traces/st-x6-1.bin
new file mode 100644
index 0000000..4689df1
--- /dev/null
+++ b/traces/st-x6-1.bin
diff --git a/traces/st-x6-2.bin b/traces/st-x6-2.bin
new file mode 100644
index 0000000..0977d93
--- /dev/null
+++ b/traces/st-x6-2.bin
diff --git a/traces/st-x6-3.bin b/traces/st-x6-3.bin
new file mode 100644
index 0000000..3b2cdc9
--- /dev/null
+++ b/traces/st-x6-3.bin
diff --git a/traces/st-x7-0.bin b/traces/st-x7-0.bin
new file mode 100644
index 0000000..2d11122
--- /dev/null
+++ b/traces/st-x7-0.bin
diff --git a/traces/st-x7-1.bin b/traces/st-x7-1.bin
new file mode 100644
index 0000000..4e13060
--- /dev/null
+++ b/traces/st-x7-1.bin
diff --git a/traces/st-x7-2.bin b/traces/st-x7-2.bin
new file mode 100644
index 0000000..07768b8
--- /dev/null
+++ b/traces/st-x7-2.bin
diff --git a/traces/st-x7-3.bin b/traces/st-x7-3.bin
new file mode 100644
index 0000000..b3e71da
--- /dev/null
+++ b/traces/st-x7-3.bin
diff --git a/traces/st-x9-0.bin b/traces/st-x9-0.bin
new file mode 100644
index 0000000..be09f48
--- /dev/null
+++ b/traces/st-x9-0.bin
diff --git a/traces/st-x9-1.bin b/traces/st-x9-1.bin
new file mode 100644
index 0000000..19b14e8
--- /dev/null
+++ b/traces/st-x9-1.bin
diff --git a/traces/st-x9-2.bin b/traces/st-x9-2.bin
new file mode 100644
index 0000000..dcbb59c
--- /dev/null
+++ b/traces/st-x9-2.bin
diff --git a/traces/st-x9-3.bin b/traces/st-x9-3.bin
new file mode 100644
index 0000000..1aea9a2
--- /dev/null
+++ b/traces/st-x9-3.bin
diff --git a/traces/st-xxx-0.bin b/traces/st-xxx-0.bin
new file mode 100644
index 0000000..1b661a5
--- /dev/null
+++ b/traces/st-xxx-0.bin
diff --git a/traces/st-xxx-1.bin b/traces/st-xxx-1.bin
new file mode 100644
index 0000000..d82d027
--- /dev/null
+++ b/traces/st-xxx-1.bin
diff --git a/traces/st-xxx-2.bin b/traces/st-xxx-2.bin
new file mode 100644
index 0000000..d3586e9
--- /dev/null
+++ b/traces/st-xxx-2.bin
diff --git a/traces/st-xxx-3.bin b/traces/st-xxx-3.bin
new file mode 100644
index 0000000..5d9168c
--- /dev/null
+++ b/traces/st-xxx-3.bin
diff --git a/traces/st0.fg b/traces/st0.fg
new file mode 100644
index 0000000..4008086
--- /dev/null
+++ b/traces/st0.fg
diff --git a/traces/st1.fg b/traces/st1.fg
new file mode 100644
index 0000000..5d5c5ae
--- /dev/null
+++ b/traces/st1.fg
diff --git a/traces/stg20.bin b/traces/stg20.bin
new file mode 100644
index 0000000..a12ca3e
--- /dev/null
+++ b/traces/stg20.bin
diff --git a/traces/stg21.bin b/traces/stg21.bin
new file mode 100644
index 0000000..b0ab240
--- /dev/null
+++ b/traces/stg21.bin
diff --git a/traces/stg22.bin b/traces/stg22.bin
new file mode 100644
index 0000000..1d1a0a5
--- /dev/null
+++ b/traces/stg22.bin
diff --git a/traces/stg23.bin b/traces/stg23.bin
new file mode 100644
index 0000000..fed856f
--- /dev/null
+++ b/traces/stg23.bin
diff --git a/traces/test.pdf b/traces/test.pdf
new file mode 100644
index 0000000..e0c2850
--- /dev/null
+++ b/traces/test.pdf
diff --git a/traces/x11.pdf b/traces/x11.pdf
new file mode 100644
index 0000000..6c909a9
--- /dev/null
+++ b/traces/x11.pdf
diff --git a/traces/x12.pdf b/traces/x12.pdf
new file mode 100644
index 0000000..0d16db3
--- /dev/null
+++ b/traces/x12.pdf
diff --git a/traces/x13.pdf b/traces/x13.pdf
new file mode 100644
index 0000000..fb527ce
--- /dev/null
+++ b/traces/x13.pdf
diff --git a/traces/x14.pdf b/traces/x14.pdf
new file mode 100644
index 0000000..f22df22
--- /dev/null
+++ b/traces/x14.pdf
diff --git a/traces/x15.pdf b/traces/x15.pdf
new file mode 100644
index 0000000..a2da624
--- /dev/null
+++ b/traces/x15.pdf
diff --git a/traces/x16.pdf b/traces/x16.pdf
new file mode 100644
index 0000000..bc19a32
--- /dev/null
+++ b/traces/x16.pdf
diff --git a/traces/x17.pdf b/traces/x17.pdf
new file mode 100644
index 0000000..b74b90f
--- /dev/null
+++ b/traces/x17.pdf
diff --git a/traces/x18.pdf b/traces/x18.pdf
new file mode 100644
index 0000000..6d8feb0
--- /dev/null
+++ b/traces/x18.pdf
diff --git a/traces/x19.pdf b/traces/x19.pdf
new file mode 100644
index 0000000..60c0af0
--- /dev/null
+++ b/traces/x19.pdf
diff --git a/visualizer.py b/visualizer.py
new file mode 100755
index 0000000..80c2af9
--- /dev/null
+++ b/visualizer.py
@@ -0,0 +1,31 @@
+#!/usr/bin/python
+
+"""Runs the visualizer."""
+
+import convert
+import reader
+import viz
+
+import gtk
+
+path = 'sample_traces/'
+
+trace_list = [
+path + 'st-g6-0.bin',
+path + 'st-g6-1.bin',
+path + 'st-g6-2.bin',
+path + 'st-g6-3.bin'
+]
+        
+if __name__ == '__main__':
+    stream = reader.trace_reader.trace_reader(trace_list)
+    stream = reader.sanitizer.sanitizer(stream)
+    stream = reader.gedf_test.gedf_test(stream)
+    sched = convert.convert_trace_to_schedule(stream)
+    sched.scan(10000000)
+    renderer = viz.renderer.Renderer(sched)
+    renderer.prepare_task_graph(attrs=viz.format.GraphFormat(time_per_maj=10000000))
+        
+    viz.viewer.MainWindow(renderer)
+    gtk.main()
+    
diff --git a/viz/__init__.py b/viz/__init__.py
new file mode 100644
index 0000000..ef409f6
--- /dev/null
+++ b/viz/__init__.py
@@ -0,0 +1,10 @@
+import viewer
+import renderer
+import format
+import gobject
+import gtk
+
+gobject.signal_new('set-scroll-adjustments', viewer.GraphArea, gobject.SIGNAL_RUN_FIRST,
+                       None, (gtk.Adjustment, gtk.Adjustment))
+gobject.signal_new('update-event-description', viewer.GraphArea, gobject.SIGNAL_RUN_FIRST,
+                       None, (gobject.TYPE_PYOBJECT, gobject.TYPE_PYOBJECT))
diff --git a/viz/draw.py b/viz/draw.py
new file mode 100644
index 0000000..c3ab756
--- /dev/null
+++ b/viz/draw.py
@@ -0,0 +1,1254 @@
+#!/usr/bin/python
+
+import math
+import cairo
+import os
+
+import util
+import schedule
+from format import *
+
+def snap(pos):
+    """Takes in an x- or y-coordinate ``pos'' and snaps it to the pixel grid.
+    This is necessary because integer coordinates in Cairo actually denote
+    the spaces between pixels, not the pixels themselves, so if we draw a
+    line of width 1 on integer coordinates, it will come out blurry unless we shift it,
+    since the line will get distributed over two pixels. We actually apply this to all
+    coordinates to make sure everything is aligned."""
+    return pos - 0.5
+
+class Surface(object):
+    def __init__(self, fname='temp', ctx=None):
+        self.virt_x = 0
+        self.virt_y = 0
+        self.surface = None
+        self.width = 0
+        self.height = 0
+        self.fname = fname
+        self.ctx = ctx
+    
+    def renew(self, width, height):
+        raise NotImplementedError
+    
+    def change_ctx(self, ctx):
+        self.ctx = ctx
+            
+    def get_fname(self):
+        return self.fname
+        
+    def write_out(self, fname):
+        raise NotImplementedError
+    
+    def pan(self, x, y, width, height):
+        """A surface might actually represent just a ``window'' into
+        what we are drawing on. For instance, if we are scrolling through
+        a graph, then the surface represents the area in the GUI window,
+        not the entire graph (visible or not). So this method basically
+        moves the ``window's'' upper-left corner to (x, y), and resizes
+        the dimensions to (width, height)."""
+        self.virt_x = x
+        self.virt_y = y
+        self.width = width
+        self.height = height
+        
+    def get_real_coor(self, x, y):
+        """Translates the coordinates (x, y)
+        in the ``theoretical'' plane to the true (x, y) coordinates on this surface
+        that we should draw to. Note that these might actually be outside the
+        bounds of the surface,
+        if we want something outside the surface's ``window''."""
+        return (x - self.virt_x, y - self.virt_y)
+            
+class SVGSurface(Surface):
+    def renew(self, width, height):
+        iwidth = int(math.ceil(width))
+        iheight = int(math.ceil(height))
+        self.surface = cairo.SVGSurface(self.fname, iwidth, iheight)
+        self.ctx = cairo.Context(self.surface)
+        
+    def write_out(self, fname):
+        os.execl('cp', self.fname, fname)
+    
+class ImageSurface(Surface):
+    def renew(self, width, height):
+        iwidth = int(math.ceil(width))
+        iheight = int(math.ceil(height))
+        self.surface = cairo.ImageSurface(cairo.FORMAT_ARGB32, iwidth, iheight)
+        self.ctx = cairo.Context(self.surface)
+            
+    def write_out(self, fname):
+        if self.surface is None:
+            raise ValueError('Don\'t own surface, can\'t write to to file')
+        
+        self.surface.write_to_png(fname)
+
+class Pattern(object):
+    DEF_STRIPE_SIZE = 10
+    
+    def __init__(self, color_list, stripe_size=DEF_STRIPE_SIZE):
+        self.color_list = color_list
+        self.stripe_size = stripe_size
+         
+    def render_on_canvas(self, canvas, x, y, width, height, fade=False):
+        if len(self.color_list) == 1:
+            if fade:
+                canvas.fill_rect_fade(x, y, width, height, (1.0, 1.0, 1.0), \
+                    self.color_list[0])
+            else:
+                canvas.fill_rect(x, y, width, height, self.color_list[0])
+            
+        else:
+            n = 0
+            bottom = y + height
+            while y < bottom:
+                linear = cairo.LinearGradient(x, y, x + width, math.min(y + self.stripe_size, bottom))
+                i = n % len(self.color_list)
+                if fade:
+                    canvas.fill_rect_fade(x, y, width, min(self.stripe_size, bottom - y), (1.0, 1.0, 1.0), \
+                        self.color_list[i])
+                else:
+                    canvas.fill_rect(x, y, width, min(self.stripe_size, bottom - y), self.color_list[i])
+                
+                y += self.stripe_size
+                n += 1
+        
+class Canvas(object):
+    """This is a basic class that stores and draws on a Cairo surface,
+    using various primitives related to drawing a real-time graph (up-arrows,
+    down-arrows, bars, ...).
+    
+    This is the lowest-level representation (aside perhaps from the Cairo
+    surface itself) of a real-time graph. It allows the user to draw
+    primitives at certain locations, but for the most part does not know
+    anything about real-time scheduling, just how to draw the basic parts
+    that make up a schedule graph. For that, see Graph or its descendants."""
+    
+    BOTTOM_LAYER = 0
+    MIDDLE_LAYER = 1
+    TOP_LAYER = 2
+    
+    LAYERS = (BOTTOM_LAYER, MIDDLE_LAYER, TOP_LAYER)
+    
+    SQRT3 = math.sqrt(3.0)
+    
+    def __init__(self, width, height, item_clist, bar_plist, surface):
+        """Creates a new Canvas of dimensions (width, height). The
+        parameters ``item_plist'' and ``bar_plist'' each specify a list
+        of patterns to choose from when drawing the items on the y-axis
+        or filling in bars, respectively."""
+        
+        self.surface = surface
+        
+        self.width = int(math.ceil(width))
+        self.height = int(math.ceil(height))
+        self.item_clist = item_clist
+        self.bar_plist = bar_plist
+        
+        self.selectable_regions = {}
+        
+        self.scale = 1.0
+
+    # clears the canvas.
+    def clear(self):
+        raise NotImplementedError
+    
+    def scaled(self, *coors):
+        return [coor * self.scale for coor in coors]
+
+    def draw_rect(self, x, y, width, height, color, thickness):
+        """Draws a rectangle somewhere (border only)."""
+        raise NotImplementedError
+    
+    def fill_rect(self, x, y, width, height, color):
+        """Draws a filled rectangle somewhere. ``color'' is a 3-tuple."""
+        raise NotImplementedError
+    
+    def fill_rect_fade(self, x, y, width, height, lcolor, rcolor):
+        """Draws a rectangle somewhere, filled in with the fade."""
+        raise NotImplementedError
+            
+    def draw_line(self, p0, p1, color, thickness):
+        """Draws a line from p0 to p1 with a certain color and thickness."""
+        raise NotImplementedError
+        
+    def draw_polyline(self, coor_list, color, thickness):
+        """Draws a polyline, where coor_list = [(x_0, y_0), (x_1, y_1), ... (x_m, y_m)]
+        specifies a polyline from (x_0, y_0) to (x_1, y_1), etc."""
+        raise NotImplementedError
+    
+    def fill_polyline(self, coor_list, color, thickness):
+        """Draws a polyline (probably a polygon) and fills it."""
+        raise NotImplementedError
+            
+    def draw_label(self, text, x, y, fopts=GraphFormat.DEF_FOPTS_LABEL, halign=AlignMode.LEFT, valign=AlignMode.BOTTOM):
+        """Draws text at a position with a certain alignment."""
+        raise NotImplementedError   
+    
+    def draw_label_with_sscripts(self, text, supscript, subscript, x, y, \
+                                 textfopts=GraphFormat.DEF_FOPTS_LABEL,
+                                 sscriptfopts=GraphFormat.DEF_FOPTS_LABEL_SSCRIPT, \
+                                 halign=AlignMode.LEFT, valign=AlignMode.BOTTOM):
+        """Draws text at a position with a certain alignment, along with optionally a superscript and
+        subscript (which are None if either is not used.)"""
+        raise NotImplementedError
+    
+    def draw_y_axis(self, x, y, height):
+        """Draws the y-axis, starting from the bottom at the point x, y."""
+        self.surface.ctx.set_source_rgb(0.0, 0.0, 0.0)
+        
+        self.draw_line((x, y), (x, y - height), (0.0, 0.0, 0.0), GraphFormat.AXIS_THICKNESS)
+        
+    def draw_y_axis_labels(self, x, y, height, item_list, item_size, fopts=None):
+        """Draws the item labels on the y-axis. ``item_list'' is the list
+        of strings to print, while item_size gives the vertical amount of
+        space that each item shall take up, in pixels."""
+        if fopts is None:
+            fopts = GraphFormat.DEF_FOPTS_ITEM
+        
+        x -= GraphFormat.Y_AXIS_ITEM_GAP
+        y -= height - item_size / 2.0
+        
+        orig_color = fopts.color
+        for ctr, item in enumerate(item_list):
+            fopts.color = self.get_item_color(ctr)
+            self.draw_label(item, x, y, fopts, AlignMode.RIGHT, AlignMode.CENTER)
+            y += item_size
+        
+        fopts.color = orig_color
+        
+    def draw_x_axis(self, x, y, start_tick, end_tick, maj_sep, min_per_maj):
+        """Draws the x-axis, including all the major and minor ticks (but not the labels).
+        ``num_maj'' gives the number of major ticks, ``maj_sep'' the number of pixels between
+        major ticks, and ``min_per_maj'' the number of minor ticks between two major ticks
+        (including the first major tick)"""
+        self.draw_line((x, y), (x + GraphFormat.X_AXIS_MEASURE_OFS, y),
+                       (0.0, 0.0, 0.0), GraphFormat.AXIS_THICKNESS)
+        x += GraphFormat.X_AXIS_MEASURE_OFS + start_tick * maj_sep
+
+        for i in range(start_tick, end_tick + 1):
+            self.draw_line((x, y), (x, y + GraphFormat.MAJ_TICK_SIZE),
+                           (0.0, 0.0, 0.0), GraphFormat.AXIS_THICKNESS)
+            
+            if (i < end_tick):
+                for j in range(0, min_per_maj):
+                    self.draw_line((x, y), (x + maj_sep / min_per_maj, y),
+                        (0.0, 0.0, 0.0), GraphFormat.AXIS_THICKNESS)
+                    
+                    x += 1.0 * maj_sep / min_per_maj
+                    if j < min_per_maj - 1:
+                        self.draw_line((x, y), (x, y + GraphFormat.MIN_TICK_SIZE),
+                        (0.0, 0.0, 0.0), GraphFormat.AXIS_THICKNESS)
+        
+    def draw_x_axis_labels(self, x, y, start_tick, end_tick, maj_sep, min_per_maj, start=0, incr=1, show_min=False, \
+                           majfopts=GraphFormat.DEF_FOPTS_MAJ, minfopts=GraphFormat.DEF_FOPTS_MIN):
+        """Draws the labels for the x-axis. (x, y) should give the origin.
+        how far down you want the text. ``incr'' gives the increment per major
+        tick. ``start'' gives the value of the first tick. ``show_min'' specifies
+        whether to draw labels at minor ticks."""
+            
+        x += GraphFormat.X_AXIS_MEASURE_OFS + start_tick * maj_sep
+        y += GraphFormat.X_AXIS_LABEL_GAP + GraphFormat.MAJ_TICK_SIZE
+        
+        minincr = incr / (min_per_maj * 1.0)
+        
+        cur = start * 1.0
+        
+        for i in range(start_tick, end_tick + 1):    
+            text = util.format_float(cur, 2)
+            self.draw_label(text, x, y, majfopts, AlignMode.CENTER, AlignMode.TOP)
+            
+            if (i < end_tick):
+                if show_min:
+                    for j in range(0, min_per_maj):
+                        x += 1.0 * maj_sep / min_per_maj
+                        cur += minincr
+                        text = util.format_float(cur, 2)
+                    
+                        if j < min_per_maj - 1:
+                            self.draw_label(text, x, y, minfopts, AlignMode.CENTER, AlignMode.TOP)
+                else:
+                    x += maj_sep
+                    cur += incr
+    
+    def draw_grid(self, x, y, height, start_tick, end_tick, start_item, end_item, maj_sep, item_size, \
+                  min_per_maj=None, show_min=False):
+        """Draws a grid dividing along the item boundaries and the major ticks.
+        (x, y) gives the origin. ``show_min'' specifies whether to draw vertical grid lines at minor ticks.
+        ``start_tick'' and ``end_tick'' give the major ticks to start and end at for drawing vertical lines.
+        ``start_item'' and ``end_item'' give the item boundaries to start and end drawing horizontal lines."""
+        if start_tick > end_tick or start_item > end_item:
+            raise ValueError('start must be less than end')
+            
+        line_width = (end_tick - start_tick) * maj_sep
+        line_height = (end_item - start_item) * item_size
+        
+        origin = (x, y)
+        
+        # draw horizontal lines first
+        x = origin[0] + GraphFormat.X_AXIS_MEASURE_OFS + start_tick * maj_sep 
+        y = origin[1] - height + start_item * item_size
+        for i in range(start_item, end_item + 1):
+            self.draw_line((x, y), (x + line_width, y), GraphFormat.GRID_COLOR, GraphFormat.GRID_THICKNESS)
+            y += item_size
+        
+        x = origin[0] + GraphFormat.X_AXIS_MEASURE_OFS + start_tick * maj_sep 
+        y = origin[1] - height + start_item * item_size
+        
+        if show_min:
+            for i in range(0, (end_tick - start_tick) * min_per_maj + 1):
+                self.draw_line((x, y), (x, y + line_height), GraphFormat.GRID_COLOR, GraphFormat.GRID_THICKNESS)
+                x += maj_sep * 1.0 / min_per_maj
+        else:
+            for i in range(start_tick, end_tick + 1):
+                self.draw_line((x, y), (x, y + line_height), GraphFormat.GRID_COLOR, GraphFormat.GRID_THICKNESS)
+                x += maj_sep
+    
+    def draw_bar(self, x, y, width, height, n, selected):
+        """Draws a bar with a certain set of dimensions, using pattern ``n'' from the
+        bar pattern list."""
+        
+        color, thickness = {False : (GraphFormat.BORDER_COLOR, GraphFormat.BORDER_THICKNESS),
+                            True : (GraphFormat.HIGHLIGHT_COLOR, GraphFormat.BORDER_THICKNESS * 2.0)}[selected]
+                            
+        # use a pattern to be pretty
+        self.get_bar_pattern(n).render_on_canvas(self, x, y, width, height, True)
+        self.draw_rect(x, y, width, height, color, thickness)
+    
+    def add_sel_bar(self, x, y, width, height, event):
+        self.add_sel_region(SelectableRegion(x, y, width, height, event))
+        
+    def draw_mini_bar(self, x, y, width, height, n, selected):
+        """Like the above, except it draws a miniature version. This is usually used for
+        secondary purposes (i.e. to show jobs that _should_ have been running at a certain time).
+        
+        Of course we don't enforce the fact that this is mini, since the user can pass in width
+        and height (but the mini bars do look slightly different: namely the borders are a different
+        color)"""
+        
+        color, thickness = {False : (GraphFormat.LITE_BORDER_COLOR, GraphFormat.BORDER_THICKNESS),
+                            True : (GraphFormat.HIGHLIGHT_COLOR, GraphFormat.BORDER_THICKNESS * 1.5)}[selected]
+        
+        self.get_bar_pattern(n).render_on_canvas(self, x, y, width, height, True)
+        self.draw_rect(x, y, width, height, color, thickness)
+        
+    def add_sel_mini_bar(self, x, y, width, height, event):
+        self.add_sel_region(SelectableRegion(x, y, width, height, event))
+                                
+    def draw_completion_marker(self, x, y, height, selected):
+        """Draws the symbol that represents a job completion, using a certain height."""
+        
+        color = {False : GraphFormat.BORDER_COLOR, True : GraphFormat.HIGHLIGHT_COLOR}[selected]
+        self.draw_line((x - height * GraphFormat.TEE_FACTOR / 2.0, y),
+                       (x + height * GraphFormat.TEE_FACTOR / 2.0, y),
+                       color, GraphFormat.BORDER_THICKNESS)
+        self.draw_line((x, y), (x, y + height), color, GraphFormat.BORDER_THICKNESS)
+    
+    def add_sel_completion_marker(self, x, y, height, event):
+        self.add_sel_region(SelectableRegion(x - height * GraphFormat.TEE_FACTOR / 2.0, y,
+            height * GraphFormat.TEE_FACTOR, height, event))
+                       
+    def draw_release_arrow_big(self, x, y, height, selected):
+        """Draws a release arrow of a certain height: (x, y) should give the top
+        (northernmost point) of the arrow. The height includes the arrowhead."""
+        big_arrowhead_height = GraphFormat.BIG_ARROWHEAD_FACTOR * height
+        
+        color = {False : GraphFormat.BORDER_COLOR, True : GraphFormat.HIGHLIGHT_COLOR}[selected]
+        colors = [(1.0, 1.0, 1.0), color]
+        draw_funcs = [self.__class__.fill_polyline, self.__class__.draw_polyline]
+        for i in range(0, 2):
+            color = colors[i]
+            draw_func = draw_funcs[i]
+            
+            draw_func(self, [(x, y), (x - big_arrowhead_height / Canvas.SQRT3, y + big_arrowhead_height), \
+                       (x + big_arrowhead_height / Canvas.SQRT3, y + big_arrowhead_height), (x, y)], \
+                       color, GraphFormat.BORDER_THICKNESS)
+        
+        self.draw_line((x, y + big_arrowhead_height), (x, y + height), color, GraphFormat.BORDER_THICKNESS)
+    
+    def add_sel_release_arrow_big(self, x, y, height, event):
+        self.add_sel_arrow_big(x, y, height, event)
+            
+    def draw_deadline_arrow_big(self, x, y, height, selected):
+        """Draws a release arrow: x, y should give the top (northernmost
+        point) of the arrow. The height includes the arrowhead."""
+        big_arrowhead_height = GraphFormat.BIG_ARROWHEAD_FACTOR * height
+        
+        color = {False : GraphFormat.BORDER_COLOR, True : GraphFormat.HIGHLIGHT_COLOR}[selected]
+        colors = [(1.0, 1.0, 1.0), color]
+        draw_funcs = [self.__class__.fill_polyline, self.__class__.draw_polyline]
+        for i in range(0, 2):
+            color = colors[i]
+            draw_func = draw_funcs[i]
+            
+            draw_func(self, [(x, y + height), (x - big_arrowhead_height / Canvas.SQRT3, \
+                        y + height - big_arrowhead_height), \
+                        (x + big_arrowhead_height / Canvas.SQRT3, \
+                        y + height - big_arrowhead_height), \
+                        (x, y + height)], color, GraphFormat.BORDER_THICKNESS)
+        
+        self.draw_line((x, y), (x, y + height - big_arrowhead_height),
+                       color, GraphFormat.BORDER_THICKNESS)
+    
+    def add_sel_deadline_arrow_big(self, x, y, height, event):
+        self.add_sel_arrow_big(x, y, height, event)
+    
+    def add_sel_arrow_big(self, x, y, height, event):
+        big_arrowhead_height = GraphFormat.BIG_ARROWHEAD_FACTOR * height
+        
+        self.add_sel_region(SelectableRegion(x - big_arrowhead_height / Canvas.SQRT3,
+            y, 2.0 * big_arrowhead_height / Canvas.SQRT3, height, event))
+                        
+    def draw_release_arrow_small(self, x, y, height, selected):
+        """Draws a small release arrow (most likely coming off the x-axis, although
+        this method doesn't enforce this): x, y should give the top of the arrow"""
+        small_arrowhead_height = GraphFormat.SMALL_ARROWHEAD_FACTOR * height
+        
+        color = {False : GraphFormat.BORDER_COLOR, True : GraphFormat.HIGHLIGHT_COLOR}[selected]
+        
+        self.draw_line((x, y), (x - small_arrowhead_height, y + small_arrowhead_height), \
+                       color, GraphFormat.BORDER_THICKNESS)
+        self.draw_line((x, y), (x + small_arrowhead_height, y + small_arrowhead_height), \
+                       color, GraphFormat.BORDER_THICKNESS)
+        self.draw_line((x, y), (x, y + height), color, GraphFormat.BORDER_THICKNESS)
+    
+    def add_sel_release_arrow_small(self, x, y, height, event):
+        self.add_sel_arrow_small(x, y, height, event)
+        
+    def draw_deadline_arrow_small(self, x, y, height, selected):
+        """Draws a small deadline arrow (most likely coming off the x-axis, although
+        this method doesn't enforce this): x, y should give the top of the arrow"""
+        small_arrowhead_height = GraphFormat.SMALL_ARROWHEAD_FACTOR * height
+        
+        color = {False : GraphFormat.BORDER_COLOR, True : GraphFormat.HIGHLIGHT_COLOR}[selected]
+        
+        self.draw_line((x, y), (x, y + height), color, GraphFormat.BORDER_THICKNESS)
+        self.draw_line((x - small_arrowhead_height, y + height - small_arrowhead_height), \
+                       (x, y + height), color, GraphFormat.BORDER_THICKNESS)
+        self.draw_line((x + small_arrowhead_height, y + height - small_arrowhead_height), \
+                       (x, y + height), color, GraphFormat.BORDER_THICKNESS)
+        
+    def add_sel_deadline_arrow_small(self, x, y, height, event):
+        self.add_sel_arrow_small(x, y, height, event)
+    
+    def add_sel_arrow_small(self, x, y, height, event):
+        small_arrowhead_height = GraphFormat.SMALL_ARROWHEAD_FACTOR * height
+        
+        self.add_sel_region(SelectableRegion(x - small_arrowhead_height, y,
+            small_arrowhead_height * 2.0, height, event))
+            
+    def draw_suspend_triangle(self, x, y, height, selected):
+        """Draws the triangle that marks a suspension. (x, y) gives the topmost (northernmost) point
+        of the symbol."""
+        
+        color = {False : GraphFormat.BORDER_COLOR, True : GraphFormat.HIGHLIGHT_COLOR}[selected]
+        colors = [(0.0, 0.0, 0.0), color]
+        
+        draw_funcs = [self.__class__.fill_polyline, self.__class__.draw_polyline]
+        for i in range(0, 2):
+            color = colors[i]
+            draw_func = draw_funcs[i]
+            draw_func(self, [(x, y), (x + height / 2.0, y + height / 2.0), (x, y + height), (x, y)], \
+                      color, GraphFormat.BORDER_THICKNESS)
+    
+    def add_sel_suspend_triangle(self, x, y, height, event):
+        self.add_sel_region(SelectableRegion(x, y, height / 2.0, height, event))
+        
+    def draw_resume_triangle(self, x, y, height, selected):
+        """Draws the triangle that marks a resumption. (x, y) gives the topmost (northernmost) point
+        of the symbol."""
+        
+        color = {False : GraphFormat.BORDER_COLOR, True : GraphFormat.HIGHLIGHT_COLOR}[selected]
+        colors = [(1.0, 1.0, 1.0), color]
+        
+        draw_funcs = [self.__class__.fill_polyline, self.__class__.draw_polyline]
+        for i in range(0, 2):
+            color = colors[i]
+            draw_func = draw_funcs[i]
+            draw_func(self, [(x, y), (x - height / 2.0, y + height / 2.0), (x, y + height), (x, y)], \
+                      color, GraphFormat.BORDER_THICKNESS)
+    
+    def add_sel_resume_triangle(self, x, y, height, event):
+        self.add_sel_region(SelectableRegion(x - height / 2.0, y, height / 2.0, height, event))
+        
+    def clear_selectable_regions(self):
+        self.selectable_regions = {}
+        
+    def add_sel_region(self, region):
+        self.selectable_regions[region.get_event()] = region
+        
+    def get_selected_regions(self, real_x, real_y):
+        x = real_x + self.surface.virt_x
+        y = real_y + self.surface.virt_y
+    
+        selected = {}
+        for event in self.selectable_regions:
+            region = self.selectable_regions[event]
+            if region.contains(x, y):
+                selected[event] = region
+        
+        return selected
+        
+    def whiteout(self):
+        """Overwrites the surface completely white, but technically doesn't delete anything"""
+        self.fill_rect(self.surface.virt_x, self.surface.virt_y, self.surface.width,
+                       self.surface.height, (1.0, 1.0, 1.0))
+            
+    def get_item_color(self, n):
+        """Gets the nth color in the item color list, which are the colors used to draw the items
+        on the y-axis. Note that there are conceptually infinitely
+        many patterns because the patterns repeat -- that is, we just mod out by the size of the pattern
+        list when indexing."""
+        return self.item_clist[n % len(self.item_clist)]
+    
+    def get_bar_pattern(self, n):
+        """Gets the nth pattern in the bar pattern list, which is a list of surfaces that are used to
+        fill in the bars. Note that there are conceptually infinitely
+        many patterns because the patterns repeat -- that is, we just mod out by the size of the pattern
+        list when indexing."""
+        return self.bar_plist[n % len(self.bar_plist)]
+
+class CairoCanvas(Canvas):
+    """This is a basic class that stores and draws on a Cairo surface,
+    using various primitives related to drawing a real-time graph (up-arrows,
+    down-arrows, bars, ...).
+    
+    This is the lowest-level non-abstract representation
+    (aside perhaps from the Cairo surface itself) of a real-time graph.
+    It allows the user to draw primitives at certain locations, but for
+    the most part does not know anything about real-time scheduling,
+    just how to draw the basic parts that make up a schedule graph.
+    For that, see Graph or its descendants."""
+    
+    #def __init__(self, fname, width, height, item_clist, bar_plist, surface):
+    #    """Creates a new Canvas of dimensions (width, height). The
+    #    parameters ``item_plist'' and ``bar_plist'' each specify a list
+    #    of patterns to choose from when drawing the items on the y-axis
+    #    or filling in bars, respectively."""
+        
+    #    super(CairoCanvas, self).__init__(fname, width, height, item_clist, bar_plist, surface)
+    
+    #def clear(self):
+    #    self.surface = self.SurfaceType(self.width, self.height, self.fname)
+    #    self.whiteout()
+        
+    def get_surface(self):
+        """Gets the Surface that we are drawing on in its current state."""
+        return self.surface
+    
+    def _rect_common(self, x, y, width, height, color, thickness):
+        x, y, width, height = self.scaled(x, y, width, height)
+        x, y = self.surface.get_real_coor(x, y)
+        self.surface.ctx.rectangle(snap(x), snap(y), width, height)
+        self.surface.ctx.set_line_width(thickness * self.scale)
+        self.surface.ctx.set_source_rgb(color[0], color[1], color[2])
+        
+    def draw_rect(self, x, y, width, height, color, thickness):
+        self._rect_common(x, y, width, height, color, thickness)
+        self.surface.ctx.stroke()
+    
+    def fill_rect(self, x, y, width, height, color):
+        self._rect_common(x, y, width, height, color, 1)
+        self.surface.ctx.fill()
+    
+    def fill_rect_fade(self, x, y, width, height, lcolor, rcolor):
+        """Draws a rectangle somewhere, filled in with the fade."""
+        x, y, width, height = self.scaled(x, y, width, height)
+        x, y = self.surface.get_real_coor(x, y)
+        
+        linear = cairo.LinearGradient(snap(x), snap(y), \
+                                      snap(x + width), snap(y + height))
+        linear.add_color_stop_rgb(0.0, lcolor[0], lcolor[1], lcolor[2])
+        linear.add_color_stop_rgb(1.0, rcolor[0], rcolor[1], rcolor[2])
+        self.surface.ctx.set_source(linear)
+        self.surface.ctx.rectangle(snap(x), snap(y), width, height)
+        self.surface.ctx.fill()
+            
+    def draw_line(self, p0, p1, color, thickness):
+        """Draws a line from p0 to p1 with a certain color and thickness."""
+        p0 = self.scaled(p0[0], p0[1])
+        p0 = self.surface.get_real_coor(p0[0], p0[1])
+        p1 = self.scaled(p1[0], p1[1])
+        p1 = self.surface.get_real_coor(p1[0], p1[1])
+        self.surface.ctx.move_to(p0[0], p0[1])
+        self.surface.ctx.line_to(p1[0], p1[1])
+        self.surface.ctx.set_source_rgb(color[0], color[1], color[2])
+        self.surface.ctx.set_line_width(thickness * self.scale)
+        self.surface.ctx.stroke()
+        
+    def _polyline_common(self, coor_list, color, thickness):
+        real_coor_list = [self.surface.get_real_coor(coor[0], coor[1]) for coor in coor_list]
+        self.surface.ctx.move_to(real_coor_list[0][0], real_coor_list[0][1])
+        for coor in real_coor_list[1:]:
+            self.surface.ctx.line_to(coor[0], coor[1])
+        
+        self.surface.ctx.set_line_width(thickness)    
+        self.surface.ctx.set_source_rgb(color[0], color[1], color[2])
+        
+    def draw_polyline(self, coor_list, color, thickness):
+        self._polyline_common(coor_list, color, thickness)
+        self.surface.ctx.stroke()
+        
+    def fill_polyline(self, coor_list, color, thickness):
+        self._polyline_common(coor_list, color, thickness)
+        self.surface.ctx.fill()
+     
+    def _draw_label_common(self, text, x, y, fopts, x_bearing_factor, \
+                           f_descent_factor, width_factor, f_height_factor):
+        """Helper function for drawing a label with some alignment. Instead of taking in an alignment,
+        it takes in the scale factor for the font extent parameters, which give the raw data of how much to adjust
+        the x and y parameters. Only should be used internally."""
+        x, y = self.scaled(x, y)
+        x, y = self.surface.get_real_coor(x, y)
+        
+        self.surface.ctx.set_source_rgb(0.0, 0.0, 0.0)
+            
+        self.surface.ctx.select_font_face(fopts.name, cairo.FONT_SLANT_NORMAL, cairo.FONT_WEIGHT_BOLD)
+        self.surface.ctx.set_font_size(fopts.size)
+        
+        fe = self.surface.ctx.font_extents()
+        f_ascent, f_descent, f_height = fe[:3]
+        
+        te = self.surface.ctx.text_extents(text)
+        x_bearing, y_bearing, width, height = te[:4]
+        
+        actual_x = x - x_bearing * x_bearing_factor - width * width_factor
+        actual_y = y - f_descent * f_descent_factor + f_height * f_height_factor
+        
+        self.surface.ctx.set_source_rgb(fopts.color[0], fopts.color[1], fopts.color[2])
+        
+        self.surface.ctx.move_to(snap(actual_x), snap(actual_y))
+                
+        self.surface.ctx.show_text(text)
+        
+    def draw_label(self, text, x, y, fopts=GraphFormat.DEF_FOPTS_LABEL, halign=AlignMode.LEFT, valign=AlignMode.BOTTOM):
+        """Draws a label with the given parameters, with the given horizontal and vertical justification. One can override
+        the color from ``fopts'' by passing something in to ``pattern'', which overrides the color with an arbitrary
+        pattern."""
+        x_bearing_factor, f_descent_factor, width_factor, f_height_factor = 0.0, 0.0, 0.0, 0.0
+        halign_factors = {AlignMode.LEFT : (0.0, 0.0), AlignMode.CENTER : (1.0, 0.5), AlignMode.RIGHT : (1.0, 1.0)}
+        if halign not in halign_factors:
+            raise ValueError('Invalid alignment value')
+        x_bearing_factor, width_factor = halign_factors[halign]
+        
+        valign_factors = {AlignMode.BOTTOM : (0.0, 0.0), AlignMode.CENTER : (1.0, 0.5), AlignMode.TOP : (1.0, 1.0)}
+        if valign not in valign_factors:
+            raise ValueError('Invalid alignment value')
+        f_descent_factor, f_height_factor = valign_factors[valign]
+            
+        self._draw_label_common(text, x, y, fopts, x_bearing_factor, \
+                f_descent_factor, width_factor, f_height_factor)    
+    
+    def draw_label_with_sscripts(self, text, supscript, subscript, x, y, \
+                                 textfopts=GraphFormat.DEF_FOPTS_LABEL, sscriptfopts=GraphFormat.DEF_FOPTS_LABEL_SSCRIPT, \
+                                halign=AlignMode.LEFT, valign=AlignMode.BOTTOM):
+        """Draws a label, but also optionally allows a superscript and subscript to be rendered."""
+        self.draw_label(text, x, y, textfopts, halign, valign)
+        
+        self.surface.ctx.set_source_rgb(0.0, 0.0, 0.0)
+        self.surface.ctx.select_font_face(textfopts.name, cairo.FONT_SLANT_NORMAL, cairo.FONT_WEIGHT_BOLD)
+        self.surface.ctx.set_font_size(textfopts.size)
+        te = self.surface.ctx.text_extents(text)
+        fe = self.surface.ctx.font_extents()
+        if supscript is not None:
+            f_height = fe[2]
+            x_advance = te[4]
+            xtmp = x + x_advance
+            ytmp = y
+            ytmp = y - f_height / 4.0
+            self.draw_label(supscript, xtmp, ytmp, sscriptfopts, halign, valign)
+        if subscript is not None:
+            f_height = fe[2]
+            x_advance = te[4]
+            xtmp = x + x_advance
+            ytmp = y
+            ytmp = y + f_height / 4.0
+            self.draw_label(subscript, xtmp, ytmp, sscriptfopts, halign, valign)
+        
+# represents a selectable region of the graph
+class SelectableRegion(object):
+    def __init__(self, x, y, width, height, event):
+        self.x = x
+        self.y = y
+        self.width = width
+        self.height = height
+        self.event = event
+    
+    def get_dimensions(self):
+        return (self.x, self.y, self.width, self.height)
+        
+    def get_event(self):
+        return self.event
+    
+    def contains(self, x, y):
+        return self.x <= x <= self.x + self.width and self.y <= y <= self.y + self.height
+        
+class Graph(object):
+    DEF_BAR_PLIST = [Pattern([(0.0, 0.9, 0.9)]), Pattern([(0.9, 0.3, 0.0)]), Pattern([(0.9, 0.7, 0.0)]),
+                     Pattern([(0.0, 0.0, 0.8)]), Pattern([(0.0, 0.2, 0.9)]), Pattern([(0.0, 0.6, 0.6)]),
+                     Pattern([(0.75, 0.75, 0.75)])]
+    DEF_ITEM_CLIST = [(0.3, 0.0, 0.0), (0.0, 0.3, 0.0), (0.0, 0.0, 0.3), (0.3, 0.3, 0.0), (0.0, 0.3, 0.3),
+                      (0.3, 0.0, 0.3)]
+    
+    def __init__(self, CanvasType, surface, start_time, end_time, y_item_list, attrs=GraphFormat(),
+                 item_clist=DEF_ITEM_CLIST, bar_plist=DEF_BAR_PLIST):
+        if start_time > end_time:
+            raise ValueError("Litmus is not a time machine")
+        
+        self.attrs = attrs
+        self.start_time = start_time
+        self.end_time = end_time
+        self.y_item_list = y_item_list
+        self.num_maj = int(math.ceil((self.end_time - self.start_time) * 1.0 / self.attrs.time_per_maj)) + 1
+    
+        width = self.num_maj * self.attrs.maj_sep + GraphFormat.X_AXIS_MEASURE_OFS + GraphFormat.WIDTH_PAD
+        height = (len(self.y_item_list) + 1) * self.attrs.y_item_size + GraphFormat.HEIGHT_PAD
+
+        # We need to stretch the width in order to fit the y-axis labels. To do this we need
+        # the extents information, but we haven't set up a surface yet, so we just use a
+        # temporary one.
+        extra_width = 0.0
+        dummy_surface = surface.__class__()
+        dummy_surface.renew(10, 10)
+        
+        dummy_surface.ctx.select_font_face(self.attrs.item_fopts.name, cairo.FONT_SLANT_NORMAL, cairo.FONT_WEIGHT_BOLD)
+        dummy_surface.ctx.set_font_size(self.attrs.item_fopts.size)
+        for item in self.y_item_list:
+            dummy_surface.ctx.set_source_rgb(0.0, 0.0, 0.0)
+            te = dummy_surface.ctx.text_extents(item)
+            cur_width = te[2]
+            if cur_width > extra_width:
+                extra_width = cur_width
+            
+        width += extra_width
+        self.origin = (extra_width + GraphFormat.WIDTH_PAD / 2.0, height - GraphFormat.HEIGHT_PAD / 2.0)
+        
+        self.width = width
+        self.height = height
+        
+        #if surface.ctx is None:
+        #    surface.renew(width, height)
+        
+        self.canvas = CanvasType(width, height, item_clist, bar_plist, surface)
+    
+    def get_selected_regions(self, real_x, real_y):
+        return self.canvas.get_selected_regions(real_x, real_y)
+                
+    def get_width(self):
+        return self.width
+        
+    def get_height(self):
+        return self.height
+    
+    def get_attrs(self):
+        return self.attrs
+    
+    def update_view(self, x, y, width, height, ctx):
+        """Proxy into the surface's pan."""
+        self.canvas.surface.pan(x, y, width, height)
+        self.canvas.surface.change_ctx(ctx)
+    
+    def _get_time_xpos(self, time):
+        """get x so that x is at instant ``time'' on the graph"""
+        return self.origin[0] + GraphFormat.X_AXIS_MEASURE_OFS + 1.0 * (time - self.start_time) / self.attrs.time_per_maj * self.attrs.maj_sep
+    
+    def _get_item_ypos(self, item_no):
+        """get y so that y is where the top of a bar would be in item #n's area"""
+        return self.origin[1] - self._get_y_axis_height() + self.attrs.y_item_size * (item_no + 0.5 - GraphFormat.BAR_SIZE_FACTOR / 2.0)     
+    
+    def _get_bar_width(self, start_time, end_time):
+        return 1.0 * (end_time - start_time) / self.attrs.time_per_maj * self.attrs.maj_sep
+    
+    def _get_bar_height(self):
+        return self.attrs.y_item_size * GraphFormat.BAR_SIZE_FACTOR
+    
+    def _get_mini_bar_height(self):
+        return self.attrs.y_item_size * GraphFormat.MINI_BAR_SIZE_FACTOR
+        
+    def _get_mini_bar_ofs(self):
+        return self.attrs.y_item_size * (GraphFormat.MINI_BAR_SIZE_FACTOR + GraphFormat.BAR_MINI_BAR_GAP_FACTOR)
+        
+    def _get_y_axis_height(self):
+        return (len(self.y_item_list) + 1) * self.attrs.y_item_size
+    
+    def _get_bottom_tick(self, time):
+        return int(math.floor((time - self.start_time) / self.attrs.time_per_maj))
+    
+    def _get_top_tick(self, time):
+        return int(math.ceil((time - self.start_time) / self.attrs.time_per_maj))
+        
+    def get_surface(self):
+        """Gets the underlying surface."""
+        return self.canvas.get_surface()
+    
+    def xcoor_to_time(self, x):
+        #x = self.origin[0] + GraphFormat.X_AXIS_MEASURE_OFS + (time - self.start) / self.attrs.time_per_maj * self.attrs.maj_sep
+        return (x - self.origin[0] - GraphFormat.X_AXIS_MEASURE_OFS) / self.attrs.maj_sep \
+                * self.attrs.time_per_maj + self.start_time
+    
+    def ycoor_to_item_no(self, y):
+        return int((y - self.origin[1] + self._get_y_axis_height()) // self.attrs.y_item_size) 
+    
+    def get_offset_params(self):
+        start_time = self.xcoor_to_time(self.canvas.surface.virt_x)
+        end_time = self.xcoor_to_time(self.canvas.surface.virt_x + self.canvas.surface.width)
+        
+        start_item = self.ycoor_to_item_no(self.canvas.surface.virt_y)
+        end_item = 1 + self.ycoor_to_item_no(self.canvas.surface.virt_y + self.canvas.surface.height)
+        
+        return (start_time, end_time, start_item, end_item)
+    
+    def draw_skeleton(self, start_time, end_time, start_item, end_item):
+        self.draw_grid_at_time(start_time, end_time, start_item, end_item)
+        self.draw_x_axis_with_labels_at_time(start_time, end_time)
+        self.draw_y_axis_with_labels()
+            
+    def render_surface(self, sched, list_type):
+        raise NotImplementedError
+    
+    def render_all(self, schedule):
+        raise NotImplementedError
+    
+    def render_events(self, event_list):
+        for layer in Canvas.LAYERS:
+            prev_events = {}
+            for event in event_list:
+                event.render(self, layer, prev_events)
+                        
+    def draw_axes(self, x_axis_label, y_axis_label):
+        """Draws and labels the axes according to the parameters that we were initialized
+        with."""    
+        self.draw_grid_at_time(self.start_time, self.end_time, 0, len(self.attrs.y_item_list) - 1)
+        
+        self.canvas.draw_x_axis(self.origin[0], self.origin[1], self.num_maj, self.attrs.maj_sep, self.attrs.min_per_maj)
+        self.canvas.draw_y_axis(self.origin[0], self.origin[1], self._get_y_axis_height())
+        self.canvas.draw_x_axis_labels(self.origin[0], self.origin[1], 0, self.num_maj - 1,\
+                                self.attrs.maj_sep, self.attrs.min_per_maj, self.start_time, \
+                                self.attrs.time_per_maj, self.attrs.show_min, self.attrs.majfopts, self.attrs.minfopts)
+        self.canvas.draw_y_axis_labels(self.origin[0], self.origin[1], self._get_y_axis_height(), self.y_item_list, \
+                                       self.attrs.y_item_size, self.attrs.item_fopts)
+    
+    def draw_grid_at_time(self, start_time, end_time, start_item, end_item):
+        """Draws the grid, but only in a certain time and item range."""
+        start_tick = max(0, self._get_bottom_tick(start_time))
+        end_tick = min(self.num_maj - 1, self._get_top_tick(end_time))
+        
+        start_item = max(0, start_item)
+        end_item = min(len(self.y_item_list), end_item)
+        
+        self.canvas.draw_grid(self.origin[0], self.origin[1], self._get_y_axis_height(),
+                              start_tick, end_tick, start_item, end_item, self.attrs.maj_sep, self.attrs.y_item_size, \
+                              self.attrs.min_per_maj, True)
+    
+    def draw_x_axis_with_labels_at_time(self, start_time, end_time):
+        start_tick = max(0, self._get_bottom_tick(start_time))
+        end_tick = min(self.num_maj - 1, self._get_top_tick(end_time))
+                                      
+        self.canvas.draw_x_axis(self.origin[0], self.origin[1], start_tick, end_tick, \
+                                self.attrs.maj_sep, self.attrs.min_per_maj)
+        self.canvas.draw_x_axis_labels(self.origin[0], self.origin[1], start_tick, \
+                                end_tick, self.attrs.maj_sep, self.attrs.min_per_maj,
+                                self.start_time + start_tick * self.attrs.time_per_maj,
+                                self.attrs.time_per_maj, False)
+                                
+    def draw_y_axis_with_labels(self):
+        self.canvas.draw_y_axis(self.origin[0], self.origin[1], self._get_y_axis_height())
+        self.canvas.draw_y_axis_labels(self.origin[0], self.origin[1], self._get_y_axis_height(), \
+                                       self.y_item_list, self.attrs.y_item_size)
+            
+    def draw_suspend_triangle_at_time(self, time, task_no, cpu_no, selected=False):
+        """Draws a suspension symbol for a certain task at an instant in time."""
+        raise NotImplementedError
+    
+    def add_sel_suspend_triangle_at_time(self, time, task_no, cpu_no, event):
+        """Same as above, except instead of drawing adds a selectable region at
+        a certain time."""
+        raise NotImplementedError
+    
+    def draw_resume_triangle_at_time(self, time, task_no, cpu_no, selected=False):
+        """Draws a resumption symbol for a certain task at an instant in time."""
+        raise NotImplementedError
+    
+    def add_sel_resume_triangle_at_time(self, time, task_no, cpu_no, event):
+        """Same as above, except instead of drawing adds a selectable region at
+        a certain time."""
+        raise NotImplementedError
+            
+    def draw_completion_marker_at_time(self, time, task_no, cpu_no, selected=False):
+        """Draws a completion marker for a certain task at an instant in time."""
+        raise NotImplementedError
+    
+    def add_sel_completion_marker_at_time(self, time, task_no, cpu_no, event):
+        """Same as above, except instead of drawing adds a selectable region at
+        a certain time."""
+        raise NotImplementedError
+            
+    def draw_release_arrow_at_time(self, time, task_no, job_no, selected=False):
+        """Draws a release arrow at a certain time for some task and job"""
+        raise NotImplementedError
+    
+    def add_sel_release_arrow_at_time(self, time, task_no, event):
+        """Same as above, except instead of drawing adds a selectable region at
+        a certain time."""
+        raise NotImplementedError
+            
+    def draw_deadline_arrow_at_time(self, time, task_no, job_no, selected=False):
+        """Draws a deadline arrow at a certain time for some task and job"""
+        raise NotImplementedError
+    
+    def add_sel_deadline_arrow_at_time(self, time, task_no, event):
+        """Same as above, except instead of drawing adds a selectable region at
+        a certain time."""
+        raise NotImplementedError
+        
+    def draw_bar_at_time(self, start_time, end_time, task_no, cpu_no, job_no=None):
+        """Draws a bar over a certain time period for some task, optionally labelling it."""
+        raise NotImplementedError
+        
+    def add_sel_bar_at_time(self, start_time, end_time, task_no, cpu_no, event):
+        """Same as above, except instead of drawing adds a selectable region at
+        a certain time."""
+        raise NotImplementedError
+    
+    def draw_mini_bar_at_time(self, start_time, end_time, task_no, cpu_no, job_no=None):
+        """Draws a mini bar over a certain time period for some task, optionally labelling it."""
+        raise NotImplementedError
+        
+    def add_sel_mini_bar_at_time(self, start_time, end_time, task_no, cpu_no, event):
+        """Same as above, except instead of drawing adds a selectable region at
+        a certain time."""
+        raise NotImplementedError
+            
+class TaskGraph(Graph):
+    def render_surface(self, sched):
+        self.canvas.whiteout()
+        self.canvas.clear_selectable_regions()
+        
+        start_time, end_time, start_item, end_item = self.get_offset_params()
+        
+        self.draw_skeleton(start_time, end_time, start_item, end_item)
+        
+        for layer in Canvas.LAYERS:
+            prev_events = {}
+            for event in sched.get_time_slot_array().iter_over_period(
+                        start_time, end_time, start_item, end_item,
+                        schedule.TimeSlotArray.TASK_LIST, schedule.EVENT_LIST):
+                event.render(self, layer, prev_events)
+                    
+    def draw_suspend_triangle_at_time(self, time, task_no, cpu_no, selected=False):
+        height = self._get_bar_height() * GraphFormat.BLOCK_TRIANGLE_FACTOR
+        x = self._get_time_xpos(time)
+        y = self._get_item_ypos(task_no) + self._get_bar_height() / 2.0 - height / 2.0
+        self.canvas.draw_suspend_triangle(x, y, height, selected)
+    
+    def add_sel_suspend_triangle_at_time(self, time, task_no, cpu_no, event):
+        height = self._get_bar_height() * GraphFormat.BLOCK_TRIANGLE_FACTOR
+        x = self._get_time_xpos(time)
+        y = self._get_item_ypos(task_no) + self._get_bar_height() / 2.0 - height / 2.0
+        
+        self.canvas.add_sel_suspend_triangle(x, y, height, event)
+        
+    def draw_resume_triangle_at_time(self, time, task_no, cpu_no, selected=False):
+        height = self._get_bar_height() * GraphFormat.BLOCK_TRIANGLE_FACTOR
+        x = self._get_time_xpos(time)
+        y = self._get_item_ypos(task_no) + self._get_bar_height() / 2.0 - height / 2.0
+        
+        self.canvas.draw_resume_triangle(x, y, height, selected)
+    
+    def add_sel_resume_triangle_at_time(self, time, task_no, cpu_no, event):
+        height = self._get_bar_height() * GraphFormat.BLOCK_TRIANGLE_FACTOR
+        x = self._get_time_xpos(time)
+        y = self._get_item_ypos(task_no) + self._get_bar_height() / 2.0 - height / 2.0
+        
+        self.canvas.add_sel_resume_triangle(x, y, height, event)
+        
+    def draw_completion_marker_at_time(self, time, task_no, cpu_no, selected=False):
+        height = self._get_bar_height() * GraphFormat.COMPLETION_MARKER_FACTOR
+        x = self._get_time_xpos(time)
+        y = self._get_item_ypos(task_no) + self._get_bar_height() - height
+        
+        self.canvas.draw_completion_marker(x, y, height, selected)
+    
+    def add_sel_completion_marker_at_time(self, time, task_no, cpu_no, event):
+        height = self._get_bar_height() * GraphFormat.COMPLETION_MARKER_FACTOR
+        
+        x = self._get_time_xpos(time)
+        y = self._get_item_ypos(task_no) + self._get_bar_height() - height
+        
+        self.canvas.add_sel_completion_marker(x, y, height, event)
+            
+    def draw_release_arrow_at_time(self, time, task_no, job_no=None, selected=False):
+        height = self._get_bar_height() * GraphFormat.BIG_ARROW_FACTOR
+        
+        x = self._get_time_xpos(time)
+        y = self._get_item_ypos(task_no) + self._get_bar_height() - height
+        
+        self.canvas.draw_release_arrow_big(x, y, height, selected)
+    
+    def add_sel_release_arrow_at_time(self, time, task_no, event):
+        height = self._get_bar_height() * GraphFormat.BIG_ARROW_FACTOR
+        
+        x = self._get_time_xpos(time)
+        y = self._get_item_ypos(task_no) + self._get_bar_height() - height
+        
+        self.canvas.add_sel_release_arrow_big(x, y, height, event)
+        
+    def draw_deadline_arrow_at_time(self, time, task_no, job_no=None, selected=False):
+        height = self._get_bar_height() * GraphFormat.BIG_ARROW_FACTOR
+        
+        x = self._get_time_xpos(time)
+        y = self._get_item_ypos(task_no)
+        
+        self.canvas.draw_deadline_arrow_big(x, y, height, selected)
+    
+    def add_sel_deadline_arrow_at_time(self, time, task_no, event):
+        height = self._get_bar_height() * GraphFormat.BIG_ARROW_FACTOR
+        
+        x = self._get_time_xpos(time)
+        y = self._get_item_ypos(task_no)
+        
+        self.canvas.add_sel_deadline_arrow_big(x, y, height, event)
+        
+    def draw_bar_at_time(self, start_time, end_time, task_no, cpu_no, job_no=None, selected=False):
+        if start_time > end_time:
+            raise ValueError("Litmus is not a time machine")
+            
+        x = self._get_time_xpos(start_time)
+        y = self._get_item_ypos(task_no)
+        width = self._get_bar_width(start_time, end_time)
+        height = self._get_bar_height()
+        
+        self.canvas.draw_bar(x, y, width, height, cpu_no, selected)
+        
+        # if a job number is specified, we want to draw a superscript and subscript for the task and job number, respectively
+        if job_no is not None:
+            x += GraphFormat.BAR_LABEL_OFS
+            y += self.attrs.y_item_size * GraphFormat.BAR_SIZE_FACTOR / 2.0
+            self.canvas.draw_label_with_sscripts('T', str(task_no), str(job_no), x, y, \
+                GraphFormat.DEF_FOPTS_BAR, GraphFormat.DEF_FOPTS_BAR_SSCRIPT, AlignMode.LEFT, AlignMode.CENTER)
+    
+    def add_sel_bar_at_time(self, start_time, end_time, task_no, cpu_no, event):
+        if start_time > end_time:
+            raise ValueError("Litmus is not a time machine")
+            
+        x = self._get_time_xpos(start_time)
+        y = self._get_item_ypos(task_no)
+        width = self._get_bar_width(start_time, end_time)
+        height = self._get_bar_height()
+        
+        self.canvas.add_sel_bar(x, y, width, height, event)
+    
+    def draw_mini_bar_at_time(self, start_time, end_time, task_no, cpu_no, job_no=None, selected=False):
+        if start_time > end_time:
+            raise ValueError("Litmus is not a time machine")
+            
+        x = self._get_time_xpos(start_time)
+        y = self._get_item_ypos(task_no) - self._get_mini_bar_ofs()
+        width = self._get_bar_width(start_time, end_time)
+        height = self._get_mini_bar_height()
+        
+        self.canvas.draw_mini_bar(x, y, width, height, cpu_no, selected)
+        
+        if job_no is not None:
+            x += GraphFormat.MINI_BAR_LABEL_OFS
+            y += self.attrs.y_item_size * GraphFormat.MINI_BAR_SIZE_FACTOR / 2.0
+            self.canvas.draw_label_with_sscripts('T', str(task_no), str(job_no), x, y, \
+                GraphFormat.DEF_FOPTS_MINI_BAR, GraphFormat.DEF_FOPTS_MINI_BAR_SSCRIPT, AlignMode.LEFT, AlignMode.CENTER)
+                
+    def add_sel_mini_bar_at_time(self, start_time, end_time, task_no, cpu_no, event):
+        x = self._get_time_xpos(start_time)
+        y = self._get_item_ypos(task_no) - self._get_mini_bar_ofs()
+        width = self._get_bar_width(start_time, end_time)
+        height = self._get_mini_bar_height()
+        
+        self.canvas.add_sel_mini_bar(x, y, width, height, event)
+        
+class CpuGraph(Graph):
+    def render_surface(self, sched):
+        self.canvas.whiteout()
+        self.canvas.clear_selectable_regions()
+        
+        start_time, end_time, start_item, end_item = self.get_offset_params()
+        
+        self.draw_skeleton(start_time, end_time, start_item, end_item)
+        
+        event_list = dict(schedule.EVENT_LIST)
+        
+        del event_list[schedule.ReleaseEvent]
+        del event_list[schedule.DeadlineEvent]
+        
+        for layer in Canvas.LAYERS:
+            prev_events = {}
+            for event in sched.get_time_slot_array().iter_over_period(
+                        start_time, end_time, start_item, end_item,
+                        schedule.TimeSlotArray.CPU_LIST, schedule.EVENT_LIST):
+                event.render(self, layer, prev_events)
+        
+        if end_item >= len(self.y_item_list):
+            # we are far down enough that we should render the releases and deadlines
+            for layer in Canvas.LAYERS:
+                prev_events = {}
+                for event in sched.get_time_slot_array().iter_over_period(
+                        start_time, end_time, start_item, end_item,
+                        schedule.TimeSlotArray.CPU_LIST,
+                        (schedule.ReleaseEvent, schedule.DeadlineEvent)):
+                    event.render(self, layer, prev_events)
+                
+    def render(self, schedule, start_time=None, end_time=None):
+        if end_time < start_time:
+            raise ValueError('start must be less than end')
+            
+        if start_time is None:
+            start_time = self.start
+        if end_time is None:
+            end_time = self.end
+        start_slot = self.get_time_slot(start_time)
+        end_slot = min(len(self.time_slots), self.get_time_slot(end_time) + 1)
+        
+        for layer in Canvas.LAYERS:
+            prev_events = {}
+            for i in range(start_slot, end_slot):
+                for event in self.time_slots[i]:
+                    event.render(graph, layer, prev_events)
+                    
+    def draw_suspend_triangle_at_time(self, time, task_no, cpu_no, selected=False):
+        height = self._get_bar_height() * GraphFormat.BLOCK_TRIANGLE_FACTOR
+        x = self._get_time_xpos(time)
+        y = self._get_item_ypos(cpu_no) + self._get_bar_height() / 2.0 - height / 2.0
+        self.canvas.draw_suspend_triangle(x, y, height, selected)
+    
+    def add_sel_suspend_triangle_at_time(self, time, task_no, cpu_no, event):
+        height = self._get_bar_height() * GraphFormat.BLOCK_TRIANGLE_FACTOR
+        x = self._get_time_xpos(time)
+        y = self._get_item_ypos(cpu_no) + self._get_bar_height() / 2.0 - height / 2.0
+        
+        self.canvas.add_sel_suspend_triangle(x, y, height, event)
+        
+    def draw_resume_triangle_at_time(self, time, task_no, cpu_no, selected=False):
+        height = self._get_bar_height() * GraphFormat.BLOCK_TRIANGLE_FACTOR
+        x = self._get_time_xpos(time)
+        y = self._get_item_ypos(cpu_no) + self._get_bar_height() / 2.0 - height / 2.0
+        
+        self.canvas.draw_resume_triangle(x, y, height, selected)
+    
+    def add_sel_resume_triangle_at_time(self, time, task_no, cpu_no, event):
+        height = self._get_bar_height() * GraphFormat.BLOCK_TRIANGLE_FACTOR
+        x = self._get_time_xpos(time)
+        y = self._get_item_ypos(cpu_no) + self._get_bar_height() / 2.0 - height / 2.0
+        
+        self.canvas.add_sel_suspend_triangle(x, y, height, event)
+        
+    def draw_completion_marker_at_time(self, time, task_no, cpu_no, selected=False):
+        height = self._get_bar_height() * GraphFormat.COMPLETION_MARKER_FACTOR
+        x = self._get_time_xpos(time)
+        y = self._get_item_ypos(cpu_no) + self._get_bar_height() - height
+        
+        self.canvas.draw_completion_marker(x, y, height, selected)
+    
+    def add_sel_completion_marker_at_time(self, time, task_no, cpu_no, event):
+        height = self._get_bar_height() * GraphFormat.BLOCK_TRIANGLE_FACTOR
+        x = self._get_time_xpos(time)
+        y = self._get_item_ypos(cpu_no) + self._get_bar_height() / 2.0 - height / 2.0
+        
+        self.canvas.add_sel_completion_marker(x, y, height, event)
+            
+    def draw_release_arrow_at_time(self, time, task_no, job_no=None, selected=False):
+        if job_no is None and task_no is not None:
+            raise ValueError("Must specify a job number along with the task number")
+            
+        height = self._get_bar_height() * GraphFormat.SMALL_ARROW_FACTOR
+        
+        x = self._get_time_xpos(time)
+        y = self.origin[1] - height
+        
+        self.canvas.draw_release_arrow_small(x, y, height, selected)
+    
+        if task_no is not None:
+            y -= GraphFormat.ARROW_LABEL_OFS
+            self.canvas.draw_label_with_sscripts('T', str(task_no), str(job_no), x, y, \
+                                          GraphFormat.DEF_FOPTS_ARROW, GraphFormat.DEF_FOPTS_ARROW_SSCRIPT, \
+                                          AlignMode.CENTER, AlignMode.BOTTOM)
+    
+    def add_sel_release_arrow_at_time(self, time, task_no, event):
+        height = self._get_bar_height() * GraphFormat.BIG_ARROW_FACTOR
+        
+        x = self._get_time_xpos(time)
+        y = self.origin[1] - height
+        
+        self.canvas.add_sel_release_arrow_small(x, y, height, event)
+            
+    def draw_deadline_arrow_at_time(self, time, task_no, job_no=None, selected=False):
+        if job_no is None and task_no is not None:
+            raise ValueError("Must specify a job number along with the task number")
+            
+        height = self._get_bar_height() * GraphFormat.SMALL_ARROW_FACTOR
+        
+        x = self._get_time_xpos(time)
+        y = self.origin[1] - height
+        
+        self.canvas.draw_deadline_arrow_small(x, y, height, selected)
+    
+        if task_no is not None:
+            y -= GraphFormat.ARROW_LABEL_OFS
+            self.canvas.draw_label_with_sscripts('T', str(task_no), str(job_no), x, y, \
+                                          GraphFormat.DEF_FOPTS_ARROW, GraphFormat.DEF_FOPTS_ARROW_SSCRIPT, \
+                                          AlignMode.CENTER, AlignMode.BOTTOM)
+    
+    def add_sel_deadline_arrow_at_time(self, time, task_no, event):
+        height = self._get_bar_height() * GraphFormat.BIG_ARROW_FACTOR
+        
+        x = self._get_time_xpos(time)
+        y = self.origin[1] - height
+        
+        self.canvas.add_sel_deadline_arrow_small(x, y, height, event)
+        
+    def draw_bar_at_time(self, start_time, end_time, task_no, cpu_no, job_no=None, selected=False):
+        if start_time > end_time:
+            raise ValueError("Litmus is not a time machine")
+            
+        x = self._get_time_xpos(start_time)
+        y = self._get_item_ypos(cpu_no)
+        width = self._get_bar_width(start_time, end_time)
+        height = self._get_bar_height()
+        
+        self.canvas.draw_bar(x, y, width, height, task_no, selected)
+        
+        # if a job number is specified, we want to draw a superscript and subscript for the task and job number, respectively
+        if job_no is not None:
+            x += GraphFormat.BAR_LABEL_OFS
+            y += self.attrs.y_item_size * GraphFormat.BAR_SIZE_FACTOR / 2.0
+            self.canvas.draw_label_with_sscripts('T', str(task_no), str(job_no), x, y, \
+                                                 GraphFormat.DEF_FOPTS_BAR, GraphFormat.DEF_FOPTS_BAR_SSCRIPT, \
+                                                 AlignMode.LEFT, AlignMode.CENTER)
+    
+    def add_sel_bar_at_time(self, start_time, end_time, task_no, cpu_no, event):
+        x = self._get_time_xpos(start_time)
+        y = self._get_item_ypos(cpu_no)
+        width = self._get_bar_width(start_time, end_time)
+        height = self._get_bar_height()
+        
+        self.canvas.add_sel_region(SelectableRegion(x, y, width, height, event))
+    
+    def draw_mini_bar_at_time(self, start_time, end_time, task_no, cpu_no, job_no=None, selected=False):
+        if start_time > end_time:
+            raise ValueError("Litmus is not a time machine")
+            
+        x = self._get_time_xpos(start_time)
+        y = self._get_item_ypos(cpu_no) - self._get_mini_bar_ofs()
+        width = self._get_bar_width(start_time, end_time)
+        height = self._get_mini_bar_height()
+        
+        self.canvas.draw_mini_bar(x, y, width, height, cpu_no, selected)
+        
+        if job_no is not None:
+            x += GraphFormat.MINI_BAR_LABEL_OFS
+            y += self.attrs.y_item_size * GraphFormat.MINI_BAR_SIZE_FACTOR / 2.0
+            self.canvas.draw_label_with_sscripts('T', str(task_no), str(job_no), x, y, \
+                GraphFormat.DEF_FOPTS_MINI_BAR, GraphFormat.DEF_FOPTS_MINI_BAR_SSCRIPT, AlignMode.LEFT, AlignMode.CENTER)
+                
+    def add_sel_mini_bar_at_time(self, start_time, end_time, task_no, cpu_no, event):
+        x = self._get_time_xpos(start_time)
+        y = self._get_item_ypos(cpu_no) - self._get_mini_bar_ofs()
+        width = self._get_bar_width(start_time, end_time)
+        height = self._get_mini_bar_height()
+        
+        self.canvas.add_sel_mini_bar(x, y, width, height, cpu_no, selected)
diff --git a/viz/format.py b/viz/format.py
new file mode 100644
index 0000000..fed39f0
--- /dev/null
+++ b/viz/format.py
@@ -0,0 +1,92 @@
+"""Various formatting parameters intended to be accessible by the client."""
+
+class FontOptions(object):
+    """Class for combining assorted simple font options."""
+    def __init__(self, name, size, color):
+        self.name = name
+        self.size = size
+        self.color = color
+
+class AlignMode(object):
+    """Type that specifies the way something (probably text)
+    should be aligned, horizontally and/or vertically."""
+    LEFT = 0
+    CENTER = 1
+    RIGHT = 2
+    
+    BOTTOM = 3
+    TOP = 4
+        
+class GraphFormat(object):
+    """Container class for a bunch of optional and non-optional attributes to configure the appearance of the graph
+    (because it would be annoying to just have these all as raw arguments to the Graph constructor, and many people
+    probably don't care about most of them anyway)."""
+    
+    GRID_COLOR = (0.7, 0.7, 0.7)
+    HIGHLIGHT_COLOR = (0.8, 0.0, 0.0)
+    BORDER_COLOR = (0.0, 0.0, 0.0)
+    LITE_BORDER_COLOR = (0.4, 0.4, 0.4)
+    
+    BORDER_THICKNESS = 1
+    GRID_THICKNESS = 1
+    AXIS_THICKNESS = 1
+    
+    X_AXIS_MEASURE_OFS = 30
+    X_AXIS_LABEL_GAP = 10
+    Y_AXIS_ITEM_GAP = 10
+    MAJ_TICK_SIZE = 20
+    MIN_TICK_SIZE = 12
+    
+    BIG_ARROWHEAD_FACTOR = 0.2
+    SMALL_ARROWHEAD_FACTOR = 0.3
+    TEE_FACTOR = 0.3
+    
+    DEF_FOPTS_LABEL = FontOptions("Times", 16, (0.0, 0.0, 0.0))
+    DEF_FOPTS_LABEL_SSCRIPT = FontOptions("Times", 8, (0.0, 0.0, 0.0))
+    DEF_FOPTS_MAJ = FontOptions("Times", 14, (0.1, 0.1, 0.1))
+    DEF_FOPTS_MIN = FontOptions("Times", 9, (0.1, 0.1, 0.1)) 
+    DEF_FOPTS_ITEM = FontOptions("Times", 20, (0.0, 0.5, 0.1))
+    DEF_FOPTS_BAR = FontOptions("Times", 14, (0.0, 0.0, 0.0))
+    DEF_FOPTS_BAR_SSCRIPT = FontOptions("Times", 7, (0.0, 0.0, 0.0))
+    DEF_FOPTS_MINI_BAR = FontOptions("Times", 11, (0.0, 0.0, 0.0))
+    DEF_FOPTS_MINI_BAR_SSCRIPT = FontOptions("Times", 7, (0.0, 0.0, 0.0))
+    DEF_FOPTS_ARROW = FontOptions("Times", 12, (0.0, 0.0, 0.0))
+    DEF_FOPTS_ARROW_SSCRIPT = FontOptions("Times", 7, (0.0, 0.0, 0.0))
+    
+    LEFT_SIDE_PAD = 30
+    WIDTH_PAD = 50
+    HEIGHT_PAD = 150
+    Y_ITEM_PAD_FACTOR = 0.5
+    
+    DEF_TIME_PER_MAJ = 10
+    DEF_MAJ_SEP = 200
+    DEF_MIN_PER_MAJ = 5
+    DEF_Y_ITEM_SIZE = 50
+    
+    AXIS_LABEL_VERT_OFS = 30
+    BAR_SIZE_FACTOR = 0.4
+    MINI_BAR_SIZE_FACTOR = 0.2
+    BAR_MINI_BAR_GAP_FACTOR = 0.1
+                
+    BAR_LABEL_OFS = 2
+    MINI_BAR_LABEL_OFS = 1
+    ARROW_LABEL_OFS = 2
+    
+    BLOCK_TRIANGLE_FACTOR = 0.7
+    BIG_ARROW_FACTOR = 1.6
+    SMALL_ARROW_FACTOR = 0.6
+    COMPLETION_MARKER_FACTOR = 1.6
+    
+    def __init__(self, time_per_maj=DEF_TIME_PER_MAJ, maj_sep=DEF_MAJ_SEP, \
+    min_per_maj=DEF_MIN_PER_MAJ, y_item_size=DEF_Y_ITEM_SIZE, bar_fopts=DEF_FOPTS_BAR, \
+    item_fopts=DEF_FOPTS_ITEM, show_min=False, majfopts=DEF_FOPTS_MAJ, \
+    minfopts=DEF_FOPTS_MIN):
+        self.time_per_maj = time_per_maj
+        self.maj_sep = maj_sep
+        self.min_per_maj = min_per_maj
+        self.y_item_size = y_item_size
+        self.item_fopts = item_fopts
+        self.bar_fopts = bar_fopts
+        self.show_min = show_min
+        self.majfopts = majfopts
+        self.minfopts = minfopts
diff --git a/viz/renderer.py b/viz/renderer.py
new file mode 100644
index 0000000..d94129c
--- /dev/null
+++ b/viz/renderer.py
@@ -0,0 +1,40 @@
+#!/usr/bin/python
+from schedule import *
+from draw import *
+
+"""The renderer, a glue object which converts a schedule to its representation
+on a graph."""
+        
+class Renderer(object):
+    def __init__(self, schedule):
+        self.schedule = schedule
+    
+    def prepare_task_graph(self, SurfaceType=ImageSurface, attrs=GraphFormat()):
+        """Outputs the fully-rendered graph (y-axis = tasks) to a Cairo ImageSurface"""
+        item_list = self.get_task_item_list()
+        start, end = self.schedule.get_time_bounds()
+        self.graph = TaskGraph(CairoCanvas, SurfaceType(), start, end, item_list, attrs)
+    
+    def prepare_cpu_graph(self, SurfaceType=ImageSurface, attrs=GraphFormat()):
+        item_list = ['CPU %d' % i for i in range(0, self.schedule.get_num_cpus())]
+        start, end = self.schedule.get_time_bounds()
+        self.graph = CpuGraph(CairoCanvas, SurfaceType(), start, end, item_list, attrs)
+
+    def render_graph_full(self):
+        """Does the heavy lifting for rendering a task or CPU graph, by scanning the schedule
+        and drawing it piece by piece"""
+        #graph.draw_axes('Time', '')
+        self.schedule.render(self.graph)
+    
+    def write_out(self, fname):
+        self.graph.surface.write_out(fname)
+        
+    def get_graph(self):
+        return self.graph
+    
+    def get_schedule(self):
+        return self.schedule
+        
+    def get_task_item_list(self):
+        return [task.get_name() for task in self.schedule.get_task_list()]
+    
diff --git a/viz/schedule.py b/viz/schedule.py
new file mode 100644
index 0000000..f842c8d
--- /dev/null
+++ b/viz/schedule.py
@@ -0,0 +1,571 @@
+#!/usr/bin/env python
+
+"""The data structures to store a schedule (task system), along with all
+the job releases and other events that have occurred for each task. This gives
+a high-level representation of a schedule that can be converted to, say, a
+graphic."""
+
+from draw import *
+import util
+
+class TimeSlotArray(object):
+    """Represents another way of organizing the events. This structure organizes events by
+    the (approximate) time at which they occur. Events that occur at approximately the same
+    time are assigned the same ``slot'', and each slot organizes its events by task number
+    as well as by CPU."""
+    
+    TASK_LIST = 0
+    CPU_LIST = 1
+    
+    def __init__(self, start, end, time_per_maj, num_tasks, num_cpus):
+        self.start = start
+        self.end = end
+        self.time_per_maj = time_per_maj
+        self.list_sizes = { TimeSlotArray.TASK_LIST : num_tasks, TimeSlotArray.CPU_LIST : num_cpus }
+        self.array = [{TimeSlotArray.TASK_LIST : [{} for i in range(0, num_tasks)], \
+                       TimeSlotArray.CPU_LIST : [{} for i in range (0, num_cpus)]} \
+                       for i in range(0, (end - start) // self.time_per_maj + 1)]
+    
+    def get_time_slot(self, time):
+        return int((time - self.start) // self.time_per_maj)
+            
+    def add_event_to_time_slot(self, event):
+        task_no = event.get_job().get_task().get_task_no()
+        cpu = event.get_cpu()
+        time_slot = self.get_time_slot(event.get_time())
+        
+        self.array[time_slot][TimeSlotArray.TASK_LIST][task_no][event.__class__] = event
+        self.array[time_slot][TimeSlotArray.CPU_LIST][cpu][event.__class__] = event
+        
+        span_events = { SwitchAwayEvent : IsRunningDummy, InversionEndEvent : InversionDummy}
+        
+        for span_event in span_events:
+            if isinstance(event, span_event) and not event.is_erroneous():
+                start_slot = self.get_time_slot(event.corresp_start_event.get_time())
+                end_slot = self.get_time_slot(event.get_time())
+                for slot in range(start_slot + 1, end_slot):
+                    dummy = span_events[span_event](task_no, cpu)
+                    dummy.corresp_start_event = event.corresp_start_event
+                    self.array[slot][TimeSlotArray.TASK_LIST][task_no][dummy.__class__] = dummy
+                    self.array[slot][TimeSlotArray.CPU_LIST][cpu][dummy.__class__] = dummy
+            
+    def iter_over_period(self, start, end, start_no, end_no, list_type, event_types):
+        if start > end:
+            raise ValueError('Litmus is not a time machine')
+        if start_no > end_no:
+            raise ValueError('start no should be less than end no')
+        
+        start_slot = max(0, self.get_time_slot(start))
+        end_slot = min(len(self.array), self.get_time_slot(end) + 2)
+        
+        start_no = max(0, start_no)
+        end_no = min(self.list_sizes[list_type] - 1, end_no)
+        
+        for slot in range(start_slot, end_slot):
+            for no in range(start_no, end_no + 1):
+                for type in event_types:
+                    if type in self.array[slot][list_type][no]:
+                        yield self.array[slot][list_type][no][type]
+    
+class Schedule(object):
+    """The total schedule (task system), consisting of a certain number of
+    tasks."""
+    
+    def __init__(self, name, num_cpus, task_list=[]):
+        self.name = name
+        self.tasks = {}
+        self.task_list = []
+        self.time_slot_array = None
+        self.cur_task_no = 0
+        self.num_cpus = num_cpus
+        for task in task_list:
+            self.add_task(task)
+    
+    def set_time_params(self, time_per_maj=None):
+        if self.get_task_list() is None:
+            return (0, 0)
+        
+        def find_extreme_time_sched(sched, cmp):
+            def find_extreme_time_task(task, cmp):
+                def find_extreme_time_job(job, cmp):
+                    extreme_time = None
+                    for time in job.get_events():
+                        if extreme_time is None or cmp(time, extreme_time) < 0:
+                            extreme_time = time
+                    return extreme_time
+                
+                extreme_time = None
+                for job_no in task.get_jobs():
+                    time = find_extreme_time_job(task.get_jobs()[job_no], cmp)
+                    if time is not None and (extreme_time is None or cmp(time, extreme_time) < 0):
+                        extreme_time = time    
+                return extreme_time
+            
+            extreme_time = None
+            for task in sched.get_task_list():
+                time = find_extreme_time_task(task, cmp)
+                if time is not None and (extreme_time is None or cmp(time, extreme_time) < 0):
+                    extreme_time = time
+                    
+            return extreme_time
+                
+        def earliest_cmp(x, y):
+            diff = x - y
+            if diff > 0.0:
+                return 1
+            elif diff == 0.0:
+                return 0
+            elif diff < 0.0:
+                return -1
+                
+        def latest_cmp(x, y):
+            diff = x - y
+            if diff < 0.0:
+                return 1
+            elif diff == 0.0:
+                return 0
+            elif diff > 0.0:
+                return -1
+        
+        self.start = find_extreme_time_sched(self, earliest_cmp)
+        self.end = find_extreme_time_sched(self, latest_cmp)
+        self.time_per_maj = time_per_maj
+        self.time_slot_array = None
+        if self.time_per_maj is not None:
+            self.time_slot_array = TimeSlotArray(self.start, self.end, time_per_maj, \
+                                                 len(self.task_list), self.num_cpus)
+    
+    def get_time_slot_array(self):
+        return self.time_slot_array
+    
+    def get_time_bounds(self):
+        return (self.start, self.end)
+        
+    def scan(self, time_per_maj):
+        self.set_time_params(time_per_maj)
+        
+        # we scan the graph task by task, and job by job
+        switches = {}
+        for event in EVENT_LIST:
+            switches[event] = None
+        for task_no, task in enumerate(self.get_task_list()):
+            cur_cpu = [Event.NO_CPU]
+            for job_no in sorted(task.get_jobs().keys()):
+                job = task.get_jobs()[job_no]    
+                for event_time in sorted(job.get_events().keys()):
+                    # could have multiple events at the same time (unlikely but possible)
+                    for event in job.get_events()[event_time]:
+                        print "task, job, event:", task.name, job.job_no, event.__class__.__name__
+                        event.scan(cur_cpu, switches)
+        
+    def add_task(self, task):
+        if task.name in self.tasks:
+            raise ValueError("task already in list!")
+        self.tasks[task.name] = task
+        self.task_list.append(task)
+        task.schedule = self
+        task.task_no = self.cur_task_no
+        self.cur_task_no += 1
+    
+    def get_tasks(self):
+        return self.tasks
+        
+    def get_task_list(self):
+        return self.task_list
+    
+    def get_name(self):
+        return self.name
+    
+    def get_num_cpus(self):
+        return self.num_cpus
+                    
+class Task(object):
+    """Represents a task, including the set of jobs that were run under
+    this task."""
+    
+    def __init__(self, name, job_list=[]):
+        self.name = name
+        self.jobs = {}
+        self.task_no = None
+        self.schedule = None
+        for job in job_list:
+            self.add_job(job)
+        
+    def add_job(self, job):
+        if job.job_no in self.jobs:
+            raise ScheduleError("a job is already being released at this time for this task")
+        self.jobs[job.job_no] = job
+        job.task = self
+    
+    def get_schedule(self):
+        return self.schedule
+        
+    def get_jobs(self):
+        return self.jobs
+    
+    def get_task_no(self):
+        return self.task_no
+        
+    def get_name(self):
+        return self.name
+            
+class Job(object):
+    """Represents a job, including everything that happens related to the job"""
+    def __init__(self, job_no, event_list=[]):
+        self.job_no = job_no
+        self.events = {}
+        self.task = None
+        for event in event_list:
+            self.add_event(event)
+        
+    def add_event(self, event):
+        if event.time not in self.events:
+            self.events[event.time] = []
+        self.events[event.time].append(event)
+        event.job = self
+    
+    def get_events(self):
+        return self.events
+    
+    def get_task(self):
+        return self.task
+    
+    def get_job_no(self):
+        return self.job_no
+
+class DummyEvent(object):
+    """Represents some event that occurs, but might not actually be
+    a full-fledged ``event'' in the schedule. It might instead be a dummy
+    event added by the application to speed things up or keep track of
+    something. Such an event won't be added to the schedule tree, but
+    might appear in the time slot array."""
+
+    def __init__(self, time, cpu):
+        self.time = time
+        self.cpu = cpu
+        self.job = None
+        self.layer = None
+    
+    def __str__(self):
+        return '[Dummy Event]'
+            
+    def get_time(self):
+        return self.time
+        
+    def get_cpu(self):
+        return self.cpu
+        
+    def get_job(self):
+        return self.job
+    
+    def get_layer(self):
+        return self.layer
+        
+    def render(self, graph, layer, prev_events):
+        """Method that the visualizer calls to tell the event to render itself
+        Obviously only implemented by subclasses (actual event types)"""
+        raise NotImplementdError
+        
+class Event(DummyEvent):
+    """Represents an event that occurs while a job is running (e.g. get scheduled
+    on a CPU, block, ...)"""
+    NO_CPU = -1
+    NUM_DEC_PLACES = 2
+    
+    def __init__(self, time, cpu):
+        super(Event, self).__init__(time, cpu)
+        self.erroneous = False
+        self.selected = False
+    
+    def __str__(self):
+        return '[Event]'
+    
+    def _common_str(self):
+        job = self.get_job()
+        task = job.get_task()
+        return ' for task ' + str(task.get_name()) + ': (TASK, JOB)=' + str((task.get_task_no(), \
+            job.get_job_no())) + ', CPU=' + str(self.get_cpu())
+            
+    def is_erroneous(self):
+        """An erroneous event is where something with the event is not quite right,
+        something significantly wrong that we don't have logical information telling
+        us how we should render the event."""
+        return self.erroneous
+    
+    def is_selected(self):
+        """Returns whether the event has been selected by the user. (needed for rendering)"""
+        return self.selected
+    
+    def set_selected(self, sel):
+        """Sets the event's state to selected."""
+        self.selected = sel
+            
+    def scan(self, cur_cpu, switches):
+        """Part of the procedure that walks through all the events and sets
+        some parameters that are unknown at first. For instance, a SwitchAwayEvent
+        should know when the previous corresponding SwitchToEvent occurred, but
+        the data does not tell us this, so we have to figure that out on our own
+        by scanning through the events. ``cur_cpu'' gives the current CPU at this
+        time in the scan, and ``switches'' gives the last time a certain switch
+        (e.g. SwitchToEvent, InversionStartEvent) occurred"""
+        
+        self.get_job().get_task().get_schedule().get_time_slot_array().add_event_to_time_slot(self)
+
+class ErrorEvent(Event):
+    pass
+                
+class SuspendEvent(Event):
+    def __init__(self, time, cpu):
+        super(SuspendEvent, self).__init__(time, cpu)
+        self.layer = Canvas.MIDDLE_LAYER
+    
+    def __str__(self):
+        return 'Suspend' + self._common_str() + ', TIME=' + util.format_float(self.get_time(), Event.NUM_DEC_PLACES)
+            
+    def scan(self, cur_cpu, switches):
+        if self.get_cpu() != cur_cpu[0]:
+            self.erroneous = True
+            print "suspending on a CPU different from the CPU we are on!"
+        super(SuspendEvent, self).scan(cur_cpu, switches)
+            
+    def render(self, graph, layer, prev_events):
+        if layer == self.layer:
+            prev_events[self] = None
+            graph.draw_suspend_triangle_at_time(self.get_time(), self.get_job().get_task().get_task_no(),
+                                                self.get_cpu(), self.is_selected())
+            graph.add_sel_suspend_triangle_at_time(self.get_time(), self.get_job().get_task().get_task_no(),
+                                                self.get_cpu(), self)
+        
+class ResumeEvent(Event):
+    def __init__(self, time, cpu):
+        super(ResumeEvent, self).__init__(time, cpu)
+        self.layer = Canvas.MIDDLE_LAYER
+    
+    def __str__(self):
+        return 'Resume' + self._common_str() + ', TIME=' + util.format_float(self.get_time(), Event.NUM_DEC_PLACES)
+            
+    def scan(self, cur_cpu, switches):
+        if cur_cpu[0] != Event.NO_CPU and cur_cpu[0] != self.get_cpu():
+            self.erroneous = True
+            print "Resuming when currently scheduled on a CPU, but on a different CPU from the current CPU!"
+        super(ResumeEvent, self).scan(cur_cpu, switches)
+        
+    def render(self, graph, layer, prev_events):
+        if layer == self.layer:
+            prev_events[self] = None
+            graph.draw_resume_triangle_at_time(self.get_time(), self.get_job().get_task().get_task_no(),
+                                               self.get_cpu(), self.is_selected())
+            graph.add_sel_resume_triangle_at_time(self.get_time(), self.get_job().get_task().get_task_no(),
+                                                self.get_cpu(), self)
+        
+class CompleteEvent(Event):
+    def __init__(self, time, cpu):
+        super(CompleteEvent, self).__init__(time, cpu)
+        self.layer = Canvas.TOP_LAYER
+    
+    def __str__(self):
+        return 'Complete' + self._common_str() + ', TIME=' + util.format_float(self.get_time(), Event.NUM_DEC_PLACES)
+            
+    def scan(self, cur_cpu, switches):
+        super(CompleteEvent, self).scan(cur_cpu, switches)
+    
+    def render(self, graph, layer, prev_events):
+        if layer == Canvas.TOP_LAYER:
+            prev_events[self] = None
+            graph.draw_completion_marker_at_time(self.get_time(), self.get_job().get_task().get_task_no(),
+                                                 self.get_cpu(), self.is_selected())
+            graph.add_sel_completion_marker_at_time(self.get_time(), self.get_job().get_task().get_task_no(),
+                                                self.get_cpu(), self)
+
+        
+class SwitchAwayEvent(Event):
+    def __init__(self, time, cpu):
+        super(SwitchAwayEvent, self).__init__(time, cpu)
+        self.layer = Canvas.BOTTOM_LAYER
+    
+    def __str__(self):
+        if self.corresp_start_event is None:
+            return 'Switch Away (w/o Switch To)' + self._common_str() + 'TIME=' \
+                   + self.get_time()
+        return str(self.corresp_start_event)
+            
+    def scan(self, cur_cpu, switches):
+        old_cur_cpu = cur_cpu[0]
+        
+        self.corresp_start_event = switches[SwitchToEvent]
+        
+        cur_cpu[0] = Event.NO_CPU
+        switches[SwitchToEvent] = None
+        
+        if self.corresp_start_event is not None:
+            self.corresp_start_event.corresp_end_event = self
+            
+        if self.get_cpu() != old_cur_cpu:
+            self.erroneous = True
+            print "switching away from a CPU different from the CPU we are currently on"
+        if self.corresp_start_event is None:
+            self.erroneous = True
+            print "switch away was not matched by a corresponding switch to"
+        elif self.get_time() < self.corresp_start_event.get_time():
+            self.erroneous = True
+            print "switching away from a processor before we switched to it?!"
+        
+        super(SwitchAwayEvent, self).scan(cur_cpu, switches)
+            
+    def render(self, graph, layer, prev_events):
+        if self.corresp_start_event is None or self.corresp_start_event in prev_events:
+            return # erroneous switch away or already rendered
+        self.corresp_start_event.render(graph, layer, prev_events)
+        
+class SwitchToEvent(Event):
+    def __init__(self, time, cpu):
+        super(SwitchToEvent, self).__init__(time, cpu)
+        self.layer = Canvas.BOTTOM_LAYER
+        
+    def __str__(self):
+        if self.corresp_end_event is None:
+            return 'Switch To (w/o Switch Away)' + self._common_str() + ', TIME=' \
+                   + self.get_time()
+        return 'Scheduled' + self._common_str() + ', START=' \
+               + util.format_float(self.get_time(), Event.NUM_DEC_PLACES) \
+               + ', END=' + util.format_float(self.corresp_end_event.get_time(), Event.NUM_DEC_PLACES)
+        
+    def scan(self, cur_cpu, switches):
+        old_cur_cpu = cur_cpu[0]
+        cur_cpu[0] = self.get_cpu()
+        switches[SwitchToEvent] = self
+        self.corresp_end_event = None
+        
+        if old_cur_cpu != Event.NO_CPU:
+            self.erroneous = True
+            print "currently scheduled somewhere, can't switch to a CPU"
+                            
+        super(SwitchToEvent, self).scan(cur_cpu, switches)
+    
+    def render(self, graph, layer, prev_events):
+        if self.is_erroneous():
+            return # erroneous switch to
+        if layer == Canvas.BOTTOM_LAYER:
+            prev_events[self] = None
+            cpu = self.get_cpu()
+            task_no = self.get_job().get_task().get_task_no()
+            graph.draw_bar_at_time(self.get_time(), self.corresp_end_event.get_time(),
+                                   task_no, cpu, self.get_job().get_job_no(), self.is_selected())
+            graph.add_sel_bar_at_time(self.get_time(), self.corresp_end_event.get_time(),
+                                     task_no, cpu, self)
+        
+class ReleaseEvent(Event):
+    def __init__(self, time, cpu):
+        super(ReleaseEvent, self).__init__(time, cpu)
+        self.layer = Canvas.TOP_LAYER
+    
+    def __str__(self):
+        return 'Release' + self._common_str() + ', TIME=' + util.format_float(self.get_time(), Event.NUM_DEC_PLACES)
+        
+    def scan(self, cur_cpu, switches):
+        super(ReleaseEvent, self).scan(cur_cpu, switches)
+        
+    def render(self, graph, layer, prev_events):
+        prev_events[self] = None
+        if layer == Canvas.TOP_LAYER:
+            graph.draw_release_arrow_at_time(self.get_time(), self.get_job().get_task().get_task_no(),
+                                             self.get_job().get_job_no(), self.is_selected())
+            graph.add_sel_release_arrow_at_time(self.get_time(), self.get_job().get_task().get_task_no(),
+                                             self)
+                                             
+class DeadlineEvent(Event):
+    def __init__(self, time, cpu):
+        super(DeadlineEvent, self).__init__(time, cpu)
+        self.layer = Canvas.TOP_LAYER
+    
+    def __str__(self):
+        return 'Deadline' + self._common_str() + ', TIME=' + util.format_float(self.get_time(), Event.NUM_DEC_PLACES)
+            
+    def scan(self, cur_cpu, switches):
+        super(DeadlineEvent, self).scan(cur_cpu, switches)
+        
+    def render(self, graph, layer, prev_events):
+        prev_events[self] = None
+        if layer == Canvas.TOP_LAYER:
+            graph.draw_deadline_arrow_at_time(self.get_time(), self.get_job().get_task().get_task_no(),
+                                              self.get_job().get_job_no(), self.is_selected())
+            graph.add_sel_deadline_arrow_at_time(self.get_time(), self.get_job().get_task().get_task_no(),
+                                              self)
+
+class InversionStartEvent(ErrorEvent):
+    def __init__(self, time):
+        super(InversionStartEvent, self).__init__(time, Event.NO_CPU)
+        self.layer = Canvas.BOTTOM_LAYER
+    
+    def __str__(self):
+        if self.corresp_end_event is None:
+            print 'Inversion Start (w/o Inversion End)' + self._common_str() \
+                  + ', TIME=' + util.format_float(self.get_time(), Event.NUM_DEC_PLACES)
+        return 'Priority Inversion' + self._common_str() + ', START=' \
+               + util.format_float(self.get_time(), Event.NUM_DEC_PLACES) \
+               + ', END=' + util.format_float(self.corresp_end_event.get_time(), Event.NUM_DEC_PLACES)
+        
+    def scan(self, cur_cpu, switches):
+        switches[InversionStartEvent] = self
+        self.corresp_end_event = None
+        
+        # the corresp_end_event should already be set
+        super(InversionStartEvent, self).scan(cur_cpu, switches)
+    
+    def render(self, graph, layer, prev_events):
+        if layer == Canvas.BOTTOM_LAYER:
+            prev_events[self] = None
+            cpu = self.get_cpu()
+            task_no = self.get_job().get_task().get_task_no()
+            graph.draw_mini_bar_at_time(self.get_time(), self.corresp_end_event.get_time(),
+                                   task_no, cpu, self.get_job().get_job_no(), self.is_selected())
+            graph.add_sel_mini_bar_at_time(self.get_time(), self.corresp_end_event.get_time(),
+                                     task_no, cpu, self)
+
+class InversionEndEvent(ErrorEvent):
+    def __init__(self, time):
+        super(InversionEndEvent, self).__init__(time, Event.NO_CPU)
+        self.layer = Canvas.BOTTOM_LAYER
+    
+    def __str__(self):
+        if self.corresp_start_event is None:
+            print 'Inversion End (w/o Inversion Start)' + self._common_str() \
+                  + ', TIME=' + util.format_float(self.get_time(), Event.NUM_DEC_PLACES)
+        
+        return str(self.corresp_start_event)
+                      
+    def scan(self, cur_cpu, switches):
+        self.corresp_start_event = switches[InversionStartEvent]
+        
+        cur_cpu[0] = Event.NO_CPU
+        switches[InversionStartEvent] = None
+        
+        if self.corresp_start_event is not None:
+            self.corresp_start_event.corresp_end_event = self
+            
+        if self.corresp_start_event is None:
+            self.erroneous = True
+            print "inversion end was not matched by a corresponding inversion start"
+        
+        super(InversionEndEvent, self).scan(cur_cpu, switches)
+        
+    def render(self, graph, layer, prev_events):
+        if self.corresp_start_event is None or self.corresp_start_event in prev_events:
+            return # erroneous inversion end or already rendered
+        self.corresp_start_event.render(graph, layer, prev_events)
+        
+class InversionDummy(DummyEvent):
+    def render(self, graph, layer, prev_events):
+        if self.corresp_start_event in prev_events:
+            return # we have already been rendered
+        self.corresp_start_event.render(graph, layer, prev_events)
+        
+class IsRunningDummy(DummyEvent):
+    def render(self, graph, layer, prev_events):
+        if self.corresp_start_event in prev_events:
+            return # we have already been rendered
+        self.corresp_start_event.render(graph, layer, prev_events)
+
+EVENT_LIST = {SuspendEvent : None, ResumeEvent : None, CompleteEvent : None, SwitchAwayEvent : None,
+              SwitchToEvent : None, ReleaseEvent : None, DeadlineEvent : None, IsRunningDummy : None,
+              InversionStartEvent : None, InversionEndEvent : None, InversionDummy : None}
diff --git a/viz/util.py b/viz/util.py
new file mode 100644
index 0000000..3111f39
--- /dev/null
+++ b/viz/util.py
@@ -0,0 +1,9 @@
+#!/usr/bin/python
+
+"""Miscellanious utility functions that don't fit anywhere."""
+
+def format_float(num, numplaces):
+    if abs(round(num, numplaces) - round(num, 0)) == 0.0:
+        return '%.0f' % float(num)
+    else:
+        return ('%.' + numplaces + 'f') % round(float(num), numplaces)
diff --git a/viz/viewer.py b/viz/viewer.py
new file mode 100644
index 0000000..a695473
--- /dev/null
+++ b/viz/viewer.py
@@ -0,0 +1,193 @@
+#!/usr/bin/python
+
+"""GUI stuff."""
+
+from schedule import *
+from renderer import *
+
+import pygtk
+import gtk
+import gobject
+    
+class GraphArea(gtk.DrawingArea):
+    DAREA_WIDTH_REQ = 500
+    DAREA_HEIGHT_REQ = 300
+    HORIZ_PAGE_SCROLL_FACTOR = 4.8
+    HORIZ_STEP_SCROLL_FACTOR = 0.8
+    VERT_PAGE_SCROLL_FACTOR = 3.0
+    VERT_STEP_SCROLL_FACTOR = 0.5
+    
+    def __init__(self, renderer):
+        super(GraphArea, self).__init__()
+        
+        self.renderer = renderer
+        
+        self.cur_x = 0
+        self.cur_y = 0
+        self.width = 0
+        self.height = 0
+        
+        self.now_selected = []
+        
+        self.set_set_scroll_adjustments_signal('set-scroll-adjustments')
+        
+        self.add_events(gtk.gdk.BUTTON_PRESS_MASK | gtk.gdk.POINTER_MOTION_MASK | gtk.gdk.POINTER_MOTION_HINT_MASK)
+        
+        self.connect('expose-event', self.expose)
+        self.connect('size-allocate', self.size_allocate)
+        self.connect('set-scroll-adjustments', self.set_scroll_adjustments)
+        self.connect('button-press-event', self.button_press)
+        self.connect('motion-notify-event', self.motion_notify)
+        
+        self.set_size_request(GraphArea.DAREA_WIDTH_REQ, GraphArea.DAREA_HEIGHT_REQ)
+        
+    def expose(self, widget, event, data=None):
+        ctx = widget.window.cairo_create()
+        graph = self.renderer.get_graph()
+        graph.update_view(self.cur_x, self.cur_y, self.width, self.height, ctx)
+        graph.render_surface(self.renderer.get_schedule())
+        
+    def set_scroll_adjustments(self, widget, horizontal, vertical, data=None):
+        graph = self.renderer.get_graph()
+        width = graph.get_width()
+        height = graph.get_height()
+        
+        self.horizontal = horizontal
+        self.vertical = vertical
+        self.config_scrollbars(self.cur_x, self.cur_y)
+                                 
+        self.horizontal.connect('value-changed', self.horizontal_value_changed)
+        self.vertical.connect('value-changed', self.vertical_value_changed)
+        
+    def horizontal_value_changed(self, adjustment):
+        self.cur_x = min(adjustment.value, self.renderer.get_graph().get_width())
+        self.cur_x = max(adjustment.value, 0.0)
+        
+        rect = gtk.gdk.Rectangle(0, 0, self.width, self.height)
+        self.window.invalidate_rect(rect, True)
+    
+    def vertical_value_changed(self, adjustment):
+        self.cur_y = min(adjustment.value, self.renderer.get_graph().get_height())
+        self.cur_y = max(adjustment.value, 0.0)
+        
+        rect = gtk.gdk.Rectangle(0, 0, self.width, self.height)
+        self.window.invalidate_rect(rect, True)
+            
+    def size_allocate(self, widget, allocation):
+        self.width = allocation.width
+        self.height = allocation.height
+        self.config_scrollbars(self.cur_x, self.cur_y)
+
+    def config_scrollbars(self, hvalue, vvalue):
+        graph = self.renderer.get_graph()
+        width = graph.get_width()
+        height = graph.get_height()
+        
+        if self.horizontal is not None:
+            self.horizontal.set_all(hvalue, 0.0, width, graph.get_attrs().maj_sep * GraphArea.HORIZ_STEP_SCROLL_FACTOR,
+                                 graph.get_attrs().maj_sep * GraphArea.HORIZ_PAGE_SCROLL_FACTOR, self.width)
+        if self.vertical is not None:
+            self.vertical.set_all(vvalue, 0.0, height, graph.get_attrs().y_item_size * GraphArea.VERT_STEP_SCROLL_FACTOR,
+                                graph.get_attrs().y_item_size * GraphArea.VERT_PAGE_SCROLL_FACTOR, self.height) 
+    
+    def _find_max_layer(self, regions):
+        max_layer = Canvas.BOTTOM_LAYER
+        for event in regions:
+            if event.get_layer() > max_layer:
+                max_layer = event.get_layer()
+        return max_layer
+        
+    def motion_notify(self, widget, motion_event, data=None):
+        msg = None
+        
+        graph = self.renderer.get_graph()
+        just_selected = graph.get_selected_regions(motion_event.x, motion_event.y)
+        if not just_selected:
+            msg = ''
+            the_event = None
+        else:
+            max_layer = self._find_max_layer(just_selected)
+        
+            for event in just_selected:
+                if event.get_layer() == max_layer:
+                    the_event = event
+                    break
+            
+            msg = str(the_event)
+        
+        self.emit('update-event-description', the_event, msg)
+            
+    def button_press(self, widget, button_event, data=None):
+        graph = self.renderer.get_graph()
+        
+        if button_event.button == 1:
+            just_selected = graph.get_selected_regions(button_event.x, button_event.y)
+            
+            max_layer = self._find_max_layer(just_selected)
+            
+            # only select those events which were in the top layer (it's
+            # not intuitive to click something and then have something
+            # below it get selected). Also, clicking something that
+            # is selected deselects it
+            new_now_selected = {}
+            for event in just_selected:
+                if event.get_layer() == max_layer:
+                    if not event.is_selected():
+                        new_now_selected[event] = None
+                    event.set_selected(not event.is_selected())
+                    break
+            
+            for event in self.now_selected:
+                if event not in new_now_selected:
+                    event.set_selected(False)
+                    
+            self.now_selected = new_now_selected
+            
+            rect = gtk.gdk.Rectangle(0, 0, self.width, self.height)
+            self.window.invalidate_rect(rect, True)
+                
+class GraphWindow(gtk.ScrolledWindow):    
+    def __init__(self, renderer):
+        super(GraphWindow, self).__init__(None, None)
+        
+        self.garea = GraphArea(renderer)
+        self.add(self.garea)
+        self.garea.show()
+    
+    def get_graph_area(self):
+        return self.garea
+                        
+class MainWindow(object):
+    def __init__(self, renderer):
+        self.window = gtk.Window(gtk.WINDOW_TOPLEVEL)
+        
+        self.window.connect('delete_event', self.delete_event)
+        self.window.connect('destroy', self.destroy)
+        
+        self.vbox = gtk.VBox(False, 0)
+        
+        self.gwindow = GraphWindow(renderer)
+        self.gwindow.get_graph_area().connect('update-event-description',
+            self.update_event_description)
+        self.gwindow.show()
+        
+        self.desc_label = gtk.Label('')
+        self.desc_label.set_justify(gtk.JUSTIFY_LEFT)
+        self.desc_label.show()
+        
+        self.vbox.pack_start(self.gwindow, True, True, 0)
+        self.vbox.pack_start(self.desc_label, False, False, 0)
+        self.vbox.show()
+        
+        self.window.add(self.vbox)
+        self.window.show()
+   
+    def update_event_description(self, widget, event, msg):
+        self.desc_label.set_text(msg)
+    
+    def delete_event(self, widget, event, data=None):
+        return False
+        
+    def destroy(self, widget, data=None):
+        gtk.main_quit()
+