Merge branch 'master' of ssh://cvs.cs.unc.edu/cvs/proj/litmus/repo/unit-trace into wip-gary

Conflicts:
	unit_trace/viz/draw.py
	unit_trace/viz/schedule.py
	unit_trace/viz/viewer.py

19 files changed, 1815 insertions, 529 deletions

diff --git a/README b/README
deleted file mode 100644
index 4c1b772..0000000
--- a/README
+++ /dev/null
@@ -1,105 +0,0 @@
-See the LITMUS Wiki page for a general explanation of this tool.
-
-unit_trace consists of two modules and a core. The ``core'' is basically
-a bunch of code, implemented as Python iterators, which converts the
-raw trace data into a sequence of record objects, implemented in
-Python. The modules are:
-
-1) A simple module that outputs the contents of each record to
-stdout. This module, along with most of the core, can be found in the
-reader/ directory. There is a sample script -- look at
-sample_script.py in the reader/ directory (it's pretty
-self-explanatory). Note that Mac is the one who coded most of the
-this, though I can probably try to answer any questions about it since
-I've had to go in there from time to time.
-
-2) The visualizer. Now, the GUI as it stands is very basic -- it's
-basically just a shell for the core visualizer component. How to open
-a file is obvious -- but note that you can open several files at a
-time (since more often than not a trace consists of more than one
-file, typically one for each CPU).
-
-Most of the code for this is in the viz/ directory, but to run it, the
-file you want to execute is visualizer.py (in the main directory).
-
-A few notes on how to use the GUI:
-
--- How to scroll is pretty obvious, though I still need to implement
-   keypresses (very trivial, but when making a GUI component from
-   scratch it always seems like there are a million little things that
-   you need to do :)
-
--- You can view either by task or by CPU; click the tabs at the top.
-
--- Mousing over the items (not the axes, though, since those are
-   pretty self-explanatory) gives you information about the item that
-   you moused over, displayed at the bottom.
-
--- You can select items. You can click them individually, one at a
-   time, or you can drag or ctrl-click to select multiple.
-
--- What you have selected is independent of what mode (task or CPU)
-   you are operating in. So if you are curious, say, when a certain
-   job is running compared to other jobs on the same CPU, you can
-   click a job in task mode and then switch to CPU mode, and it will
-   remain selected.
-
--- Right-click to get a menu of all the items you have selected (in
-   the future this menu will be clickable, so that you can get the
-   information about an item in its own window).
-
--- It is a bit laggy when lots of stuff is on the screen at once. This
-   should be fairly easy to optimize, if I have correctly identified
-   the problem, but it's not a huge issue (it's not _that_ slow).
-
-But wait, there's more:
-
--- As of now unit-trace has no way to determine the algorithm that was
-   used on the trace you're loading. This is important since certain
-   sections of code work only with G-EDF in particular. The point of
-   having this special code is either to filter out bogus data or to
-   generate extra information about the schedule (e.g. priority
-   inversions). Of course, you can leave these extra steps out and
-   it will still work, but you might get extra ``bogus'' information
-   generated by the tracer or you might not get all the information
-   you want.
-
--- To add or remove these extra steps, take a look at visualizer.py
-   and sample_script.py. You will see some code like this:
-
-   stream = reader.trace_reader.trace_reader(file_list)
-   #stream = reader.sanitizer.sanitizer(stream)
-   #stream = reader.gedf_test.gedf_test(stream)
-   
-   Uncommenting those lines will run the extra steps in the pipeline.
-   The sanitizer filters out some bogus data (stuff like ``pid 0''),
-   but so far it's only been coded for a select number of traces.
-   gedf_test generates extra information about G-EDF schedules
-   (the traces that are named st-g?-?.bin). If you try to run
-   gedf_test on anything else, it will most likely fail.
-
--- What traces are you going to use? Well, you will probably want to
-   use your own, but there are some samples you can try in the traces/
-   directory (a couple of them do give error messages, however).
-
-How to install:
-
-You should type
-
-git clone -b wip-gary ssh://cvs.cs.unc.edu/cvs/proj/litmus/repo/unit-trace.git
-
-to check out the repository. Note that you shouldn't check out the
-master branch, as it's pretty outdated. It's all Python so far, so no
-compiling or anything like that is necessary.
-
-Requirements:
-
-You're going to need Python 2.5 to run this. You'll also need to
-install the pycairo and pygtk libraries. If anyone has questions about
-how to do this or what these are, ask me.
-
-Miscellanies:
-
-Of course, let me know if you find any bugs (I'm sure there are
-plenty, though, since this is fairly alpha software), if you're
-unable to run it, or if you have any questions.
\ No newline at end of file
diff --git a/TODO b/TODO
index 9a50974..e69de29 100644
--- a/TODO
+++ b/TODO
@@ -1,6 +0,0 @@
-- Mac
-    - Bug report: If one trace file is empty, reader screws up.
-- Gary
-    - Allow interval to be specified for visualizer
-    - Only pull records on demand, if possible
-    - Bug report: per CPU view button does not exist in Mac's window manager(s)
diff --git a/doc/LICENSE b/doc/LICENSE
new file mode 100644
index 0000000..30a9810
--- /dev/null
+++ b/doc/LICENSE
@@ -0,0 +1,22 @@
+Copyright (c) 2010, UNC Real-Time Systems Group
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright notice,
+      this list of conditions and the following disclaimer.
+    * Redistributions in binary form must reproduce the above copyright notice,
+      this list of conditions and the following disclaimer in the documentation
+      and/or other materials provided with the distribution.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
diff --git a/doc/header.html b/doc/header.html
index 58dc0da..b53a7a3 100644
--- a/doc/header.html
+++ b/doc/header.html
@@ -23,6 +23,10 @@
         margin-top: 50px;
         text-align: center;
     }
+    h3 {
+        margin-top: 30px;
+        text-align: center;
+    }
     codeblock {
         padding: 0px 15px;
         margin: 5px 0 15px;
diff --git a/doc/index.txt b/doc/index.txt
index 78551c9..9360e40 100644
--- a/doc/index.txt
+++ b/doc/index.txt
@@ -10,103 +10,157 @@ information about scheduler behavior.
 </span>
 
 ## About This Document ##
-This document contains instructions for people who want to use and/or contribute to Unit-Trace.
-It is the complete documentation for Unit-Trace.
+This document is both the offical Unit-Trace website and the complete Unit-Trace documentation.
 
-## Architecture ##
-Before trying to use Unit-Trace, it will help to understand the architecture of Unit-Trace.
+## Obtaining Unit-Trace ##
+The latest public release of Unit-Trace (currently 2010.1) is available at:<br>
+[http://cs.unc.edu/~mollison/unit-trace/unit-trace.tar.gz][release]
 
-Unit-Trace performs various options on **trace files**. Oftentimes, when scheduler tracing takes
-place, multiple trace files are generated for each experiment (e.g. one per CPU). We call a
-related group of trace files a **trace**.
+Members of UNC's Real-Time Group should obtain Unit-Trace using:<br>
+<codeblock>git clone ssh://cvs.cs.unc.edu/cvs/proj/litmus/repo/unit-trace.git</codeblock>
 
-The user interacts with the tool using `unit-trace`, a Python script which is to be installed
-on the local executable path.
-`unit-trace` invokes operations provided by the `unit_trace` Python module, which is installed
-in the local `site_packages` directory (the default install location for Python modules).
+## Installing Unit-Trace ##
+Dependencies: Python 2.6; for the visualizer, pygtk and pycairo.
 
-The `unit_trace` module provides submodule(s) for parsing trace files into a **stream** of Python objects (which we call **records**).
-This stream is then passed from one `unit_trace` submodule to the next (like a pipe), undergoing
-various transformations in the process, and ultimately arriving at one or more output submodules.
-Intermediate modules generally add records; for example, the `gedf_test` module adds records to indicate
-priority inversions, which can be treated appropriately by output submodules.
+Unit-Trace consists of a Python module called `unit_trace` (encapsulated in the `unit_trace` directory) and a font-end script called `unit-trace`.
 
-This architecture provides a clean and easy-to-use interface for both users and contributors.
-The stream is implemented using Python iterators.
-This allows records are evaluated lazily (i.e. on an as-needed basis), making it possible to pull into memory only
-the records that are needed, and only as long as they are needed.
-This is important for dealing with very large traces.
+You can use `install.py` to install Unit-Trace, or install manually by copying the `unit-trace` script and the `unit_trace` directory
+to `~/bin`.
 
-## Obtaining Unit-Trace ##
-Members of UNC's Real-Time Group can obtain Unit-Trace using:  
-<codeblock>git clone ssh://cvs.cs.unc.edu/cvs/proj/litmus/repo/unit-trace.git</codeblock>
+Make sure `~/bin` is on your `PATH`.
 
-## Installing Unit-Trace ##
-Unit-Trace is based on Python 2.6, so make sure that is available on your system.
+## Using Unit-Trace ##
+Command line usage:<br>
+<codeblock>unit-trace &lt;one or more trace files&gt; [flags]</codeblock>.  
 
-Unit-Trace can be installed manually by copying the `unit-trace` script and `unit_trace` Python module, as described previously.
-Alternatively, you can use `sudo install.py` to (re)install Unit-Trace.
+Each flag turns on or off a unit-trace submodule. The available submodules are
+given below.
+
+You can specify module flags in any order.
+
+For a quick usage reference (including a list of modules), type `unit-trace` on the command line, without any arguments.
+
+### Example Use Case ###
+Let's assume you're in a directory with a bunch of trace files with
+the extension `.bin`. 
+Each trace file is assumed to be the trace of a single CPU, and all trace files in the directory are from the same experimental run.
+(The sample_traces directory, included with Unit Trace, will work for this example.)
+
+Suppose you want to get a list of the 10 longest priority inversions in a LITMUS<sup>RT</sup>trace.
+Use the following command:<br>
+<codeblock>unit-trace *.bin -c -g -i 10</codeblock>.
+
+Now, suppose you want to visualize one of those priority inversions.
+Given in the output for each one are the event IDs at the beginning and end of the priority inversion.
+Use the following command:<br>
+<codeblock>unit-trace *.bin -e &lt;the first event ID&gt; -l &lt;the second event ID&gt; -v</codeblock>.
+
+Note that if the visualizer stops at the second specified event (which it will), any tasks running at that point will appear to
+keep running forever. If you specify a slightly later second event ID (e.g. 100 greater than the actual one), this won't affect
+the jobs you're actually interested in.
+
+Now, suppose you want to see specific textual output for all events. (You could also specify a range if you wanted to.)<br>
+<codeblock>unit-trace *.bin -o > output</codeblock>
+
+This example provides a basic overview of what you can do with Unit-Trace. Detailed information about all available submodules is provided in
+the next section.
+
+## List of Submodules ##
+
+There are five basic kinds of submodules.
+
+- Input submodules, which read trace files
+- Filter submodules, which filter out event records
+- Test submodules, which perform some kind of test
+- Output modules, which display the results
+- Miscellaneous
+
+All submodules are listed and summarized in the tables below.
+Some submodules have further documentation, appearing later in this document.
 
-## Using Unit-Trace ##
-Type `unit-trace` (without options) to view usage information.
-
-In summary, trace files must be specified.
-Flags are used to enable any desired submodules.
-Some flags have accompanying parameter(s) that are passed to the submodule.
-The order in which submodules process records is pre-determined by the `unit-trace` script,
-so the user can specify flags on the command line in any order.
-
-## Example/Use Case ##
-Suppose that Alice wants to perform G-EDF testing on the LITMUS<sup>RT</sup> traces included in the sample_traces/ folder.
-
-The LITMUS<sup>RT</sup> tracing mechanism outputs superfluous events at the beginning of the trace that will not appear "correct" for
-G-EDF testing (for example, multiple job releases that never complete, indicating the initialization of a task).
-Alice uses the following command to print out (-o) the first 50 records (-m 50), looking for the end of the bogus records:  
-<codeblock>unit-trace -m 50 -o *.bin</codeblock>.
-
-Seeing that she hasn't yet reached useful records, she uses the following command to print out (-o) 50 records (-m 50), skipping the
-first 50 (-s 50).  
-<codeblock>unit-trace -m 50 -s 50 -o *.bin</codeblock>.  
-She is able to see that meaningful releases begin at time `37917282934190`.
-
-She now commences G-EDF testing (-g), starting at the time of interest (-e <earliest time>).
-Because of the lengthy output to be expected, she redirects to standard out.
-She also uses the -c option to clean up additional records that are known to be erroneous, and
-will break the G-EDF tester.  
-<codeblock>unit-trace -c -e 37917282934190 -g -o *.bin > output</codeblock>.
-
-OK, everything worked. Alice can now grep through the output file and see priority inversions.
-She sees a particularly long priority inversion, and decides to generate a visualization (-v) of part of the schedule.  
-<codeblock>unit-trace -c -e 37918340000000 -l 37919000000000 -v *.bin</codeblock>.  
-(NOTE: Currently, this still shows the entire schedule, which likely won't be feasible for larger traces and is a bug.)
-
-## Submodules ##
 ### Input Submodules ###
 <table border=1>
-<tr><td>Name</td><td>Flag</td><td>Options</td><td>Description</td></tr>
-<tr><td>trace_parser</td><td>(on by default)</td><td>(None)</td><td>Parses LITMUS<sup>RT</sup> traces</td></tr>
+<tr><td>Name</td><td>Flag</td><td>Parameters</td><td>Description</td></tr>
+<tr>
+<td>trace_parser</td>
+<td>always on, unless/until modules for other trace formats are contributed</td>
+<td>(None)</td><td>Parses LITMUS<sup>RT</sup> traces</td></tr>
 </table>
-### Intermediate Submodules ###
+### Filter Submodules ###
 <table border=1>
-<tr><td>Name</td><td>Flag</td><td>Options</td><td>Description</td></tr>
-<tr><td>earliest</td><td>-e</td><td>time</td><td>Filters out records before the given time</td></tr>
-<tr><td>latest</td><td>-l</td><td>time</td><td>Filters out records after the given time</td></tr>
+<tr><td>Name</td><td>Flag</td><td>Parameters</td><td>Description</td></tr>
+<tr><td>earliest</td><td>-e</td><td>time</td><td>Filters out records before the given event ID. (Event IDs are assigned in order of event record timestamp, and are displayed by the `stdio_printer` submodule.)</td></tr>
+<tr><td>latest</td><td>-l</td><td>time</td><td>Filters out records after the given event ID.</td></tr>
 <tr><td>skipper</td><td>-s</td><td>number n</td><td>Skips the first n records</td></tr>
 <tr><td>maxer</td><td>-m</td><td>number n</td><td>Allows at most n records to be parsed</td></tr>
-<tr><td>sanitizer</td><td>-c</td><td>(None)</td><td>Cleans up LITMUS<sup>RT</sup> traces for G-EDF testing.</td></tr>
-<tr><td>progress</td><td>-p</td><td>(None)</td><td>Outputs progress info (e.g number of records parsed so far, total time to process trace) to std error.</td></tr>
-<tr><td>stats</td><td>-i</td><td>(None)</td><td>Outputs statistics about G-EDF inversions. To be deprecated (incorporated into G-EDF tester).</td></tr>
+<tr><td>sanitizer</td><td>-c</td><td>(None)</td><td>Modifies LITMUS<sup>RT</sup> traces. To be used in conjunction with the G-EDF tester. To summarize, LITMUS<sup>RT</sup> traces have some bogus records that need to be removed or altered in order for a (potentially) valid schedule to be represented.</td></tr>
+</table>
+### Test Submodules ###
+<table border=1>
+<tr><td>Name</td><td>Flag</td><td>Options</td><td>Description</td></tr>
 <tr><td>gedf_test</td><td>-g</td><td>(None)</td><td>Performs G-EDF testing.</td></tr>
 </table>
 ### Output Submodules ###
 <table border=1>
 <tr><td>Name</td><td>Flag</td><td>Options</td><td>Description</td></tr>
-<tr><td>stdout_printer</td><td>-o</td><td>(None)</td><td>Prints records to standard out</td></tr>
-<tr><td>visualizer</td><td>-v</td><td>(None)</td><td>Visualizes records</td></tr>
+<tr><td>stdout_printer</td><td>-o</td><td>(None)</td><td>Prints records to standard out. You should probably redirect the output to a file when you use this.</td></tr>
+<tr><td>visualizer</td><td>-v</td><td>(None)</td><td>Visualizes records. You should probably use filters in conjunction with this submodule. Otherwise, it'll take forever to render, and do you <i>really</i> want to visualize the <i>entire</i> trace, anyway?</td></tr>
+<tr><td>gedf_inversion_stat_printer</td><td>-i</td><td>number n</td><td>Outputs statistics about G-EDF inversions, and the n longest inversions. (You can specify n as 0 if you want.)</td></tr>
+</table>
+### Miscellaneous Submodules ###
+<table border=1>
+<tr><td>Name</td><td>Flag</td><td>Options</td><td>Description</td></tr>
+<tr><td>progress</td><td>-p</td><td>(None)</td><td>Outputs progress info (e.g number of records parsed so far, total time to process trace) to std error.</td></tr>
 </table>
 
+## Specific Submodule Documentation ##
+
+Here, documentation is provided for submodules for which relevant information is not considered to be self-evident.
+
+(So far, it hasn't been necessary to add anything here, but once questions arise, it will become clear which submodules need to be documented more fully.)
+
+## Gotchas ##
+
+Here, documentation is provided for potentially confusing topics that are not documented elsewhere.
+
+### A Note on Time ###
+
+In general, Unit-Trace is agnostic about the units of time used in the trace files.
+This is not expected to change in the future.
+The exception is output modules.
+Currently, some output modules assume time is in nanoseconds; they convert it into milliseconds and print the 'ms' unit indicator, where convenient.
+This behavior may have to be modified in the future if non-nanosecond trace files are used.
+
+## Known Bugs ##
+
+Here, documentation of known bugs is provided.
+
+(No known bugs right now --- but there may be some hiding...)
+
+
 ## Development ##
-TODO: Information on how to contribute will be documented thoroughly here.
+Please send patches to [Mac Mollison][mac] or, if you are in the `litmus` group at UNC, just work with the git repo directly.
+
+The following "rules" are currently in place:
+
+- Please follow PEP 8 style guidelines when possible.
+- Update the documentation when you do something that makes it obsolete or incomplete
+- Don't break the overall architecture (described below)
+
+### Architecture ###
+If you are interested in contributing to Unit-Trace, you probably ought to know a bit about its overall architecture.
+
+Generally speaking, each Unit-Trace submodules is a Python generator. It accepts a Python iterator object as input and returns a Python iterator
+object as output. (You may want to look up the relevant Python terminology.)
+
+The exceptions are input submodules, which do not take any input other than a list of trace files, and the output submodules, which do not return
+iterator objects.
+
+The `unit-trace` script connects together the desired modules (i.e. those specified on the command line) using Python iterators.
+
+This architecture provides two advantages.
+First, because Python iterators are evaluated lazily, it is not necessary to read an entire trace file into memory in order to run `unit-trace` on it.
+Second, it provides an easy-to-understand programming model.
 
 ## Documentation ##
 The source code for this page is included in the `doc` folder that comes with Unit-Trace.
@@ -114,6 +168,9 @@ Contributors are required to make appropriate amendments to this documentation.
 
 The source is stored in [Markdown format][markdown] in the file `index.txt` and can be built into HTML with `make`.
 
+## License ##
+Unit-Trace is released under the [Simplified BSD License][license].
+
 ## Credits ##
 This project was created by and is maintained by the [Real-Time Systems Group][group] at the [University of North Carolina at Chapel Hill][uncch],
 [Department of Computer Science][csdept]. A detailed explanation of the tool is available in [this paper][ospert_paper], from 
@@ -130,3 +187,6 @@ We hope to have additional contributors in the future.
 [ospert_paper]: http://www.cs.unc.edu/%7Eanderson/papers/ospert09.pdf
 [ospert]: http://www.artist-embedded.org/artist/Overview,1750.html
 [markdown]: http://daringfireball.net/projects/markdown/
+[mac]: mailto:mollison@cs.unc.edu
+[license]: LICENSE
+[release]: http://cs.unc.edu/~mollison/unit-trace/unit-trace.tar.gz
diff --git a/install.py b/install.py
index 935c7df..520a347 100755
--- a/install.py
+++ b/install.py
@@ -4,13 +4,12 @@
 # Description
 ################################################################################
 
-# This script installes (or re-installs) the unit_trace Python module, so that 
-# the unit_trace library can be imported with `import unit_trace` by a Python 
+# This script installes (or re-installs) the unit_trace Python module, so that
+# the unit_trace library can be imported with `import unit_trace` by a Python
 # script, from anywhere on the system.
 
-# The installation merely consists of copying the unit_trace directory to
-# the default site_packages directory (which is the appropriate place to
-# install Python packages).
+# The installation merely copies the unit-trace script and the unit_trace
+# folder to ~/bin. You can also do this manually if you want to.
 
 # We do not use the Distutils system, provided by Python, because that
 # is less convenient :-)
@@ -30,7 +29,8 @@ import os
 ################################################################################
 
 # Determine destination directory for unit_trace module
-dst = os.path.join(sys.prefix,'lib/python2.6/site-packages/unit_trace')
+dst = '~/bin/unit_trace'
+dst = os.path.expanduser(dst)
 
 try:
     # If the destination exists
@@ -40,17 +40,16 @@ try:
     # Copy source to destination
     shutil.copytree('unit_trace', dst)
 except:
-    print("Error occurred. Make sure you run the script as root/with sudo.")
+    print "Unexpected error:", sys.exc_info()
     exit()
 
 # Determine destination directory for unit-trace script
-dst = '/usr/bin/unit-trace'
+dst = '~/bin/unit-trace'
+dst = os.path.expanduser(dst)
 try:
     shutil.copyfile('unit-trace', dst)
     # Keep same permissions
     shutil.copystat('unit-trace', dst)
 except:
-    print("Error occurred. Make sure you run the script as root/with sudo.")
+    print "Unexpected error:", sys.exc_info()
     exit()
-
-
diff --git a/runtests.py b/runtests.py
deleted file mode 100755
index 88dddf4..0000000
--- a/runtests.py
+++ /dev/null
@@ -1,47 +0,0 @@
-#!/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/unit-trace b/unit-trace
index 5328b99..a146874 100755
--- a/unit-trace
+++ b/unit-trace
@@ -15,7 +15,7 @@ import unit_trace
 from unit_trace import trace_reader
 from unit_trace import sanitizer
 from unit_trace import gedf_test
-from unit_trace import stats
+from unit_trace import gedf_inversion_stat_printer
 from unit_trace import stdout_printer
 from unit_trace import viz
 from unit_trace import progress
@@ -36,8 +36,8 @@ parser.add_option("-p", "--progress", action="store_true", dest="progress",
     default=False, help="Show parsing progress")
 parser.add_option("-g", "--gedf", action="store_true", dest="gedf",
     default=False, help="Run G-EDF test")
-parser.add_option("-i", "--info", action="store_true", dest="info",
-    default=False, help="Show statistical info")
+parser.add_option("-i", "--info", dest="num_inversions", default=-1, type=int,
+    help="Print the n longest inversions, plus statistical info")
 parser.add_option("-o", "--stdout", action="store_true", dest="stdout",
     default=False, help="Use stdout_printer")
 parser.add_option("-v", "--visual", action="store_true", dest="visualize",
@@ -90,10 +90,6 @@ if options.progress is True:
 if options.gedf is True:
     stream = gedf_test.gedf_test(stream)
 
-# Produce a statistics record
-if options.info is True:
-    stream = stats.stats(stream)
-
 # Filter some records out
 #def my_filter(record):
 #    if record.record_type == 'error' and record.type_name == 'inversion_end':
@@ -102,13 +98,25 @@ if options.info is True:
 #    return True
 #stream = filter(my_filter, stream)
 
-# Output
-if options.stdout is True and options.visualize is True:
-    import itertools
-    stream1, stream2 = itertools.tee(stream,2)
+# Tee by the number of possible outputs
+# This might cause a performance bottleneck that could be eliminated by
+# checking how many we actually need :-)
+import itertools
+stream1, stream2, stream3 = itertools.tee(stream,3)
+
+# Call standard out printer
+if options.stdout is True:
     stdout_printer.stdout_printer(stream1)
-    viz.visualizer.visualizer(stream2) 
-elif options.stdout is True:
-    stdout_printer.stdout_printer(stream)
-elif options.visualize is True:
-    viz.visualizer.visualizer(stream)
+
+# Print G_EDF inversion statistics
+if options.num_inversions > -1:
+    if options.gedf is not True:
+        import sys
+        sys.stderr.write("You must enable the G-EDF test module to print" +
+            " G-EDF inversion statistics\n")
+    else:
+        gedf_inversion_stat_printer.gedf_inversion_stat_printer(stream2,options.num_inversions)
+
+# Call visualizer
+if options.visualize is True:
+    viz.visualizer.visualizer(stream3)
diff --git a/unit_trace/earliest.py b/unit_trace/earliest.py
index eaf0cf8..03e08d7 100644
--- a/unit_trace/earliest.py
+++ b/unit_trace/earliest.py
@@ -11,11 +11,12 @@
 def earliest(stream, earliest):
     for record in stream:
         if record.record_type=="event":
-            if record.when < earliest:
+            if record.id < earliest:
                 pass
             else:
                 yield record
                 break
-        yield record
+        else:
+            yield record
     for record in stream:
         yield record
diff --git a/unit_trace/gedf_inversion_stat_printer.py b/unit_trace/gedf_inversion_stat_printer.py
new file mode 100644
index 0000000..c35632a
--- /dev/null
+++ b/unit_trace/gedf_inversion_stat_printer.py
@@ -0,0 +1,82 @@
+###############################################################################
+# Description
+###############################################################################
+# Compute and print G-EDF inversion statistics
+
+
+###############################################################################
+# Public Functions
+###############################################################################
+
+def gedf_inversion_stat_printer(stream,num):
+
+    # State
+    min_inversion = -1
+    max_inversion = -1
+    sum_inversions = 0
+    num_inversions = 0
+    longest_inversions = []
+
+    # Iterate over records, updating state
+    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
+                if len(longest_inversions) == num:
+                    if num==0:
+                        continue
+                    si = longest_inversions[0]
+                    if length > (si.job.inversion_end -
+                        si.job.inversion_start):
+                        longest_inversions.append(record)
+                        longest_inversions = _sort_longest_inversions(
+                            longest_inversions)
+                        del longest_inversions[0]
+                else:
+                    longest_inversions.append(record)
+                    longest_inversions = _sort_longest_inversions(
+                        longest_inversions)
+
+    # We've seen all records.
+    # Further update state
+    if num_inversions > 0:
+        avg_inversion = int(sum_inversions / num_inversions)
+    else:
+        avg_inversion = 0
+
+    # Print out our information
+    # NOTE: Here, we assume nanoseconds as the time unit.
+    # May have to be changed in the future.
+    print "Num inversions: %d" % (num_inversions)
+    print "Min inversion: %f ms" % (float(min_inversion) / 1000000)
+    print "Max inversion: %f ms" % (float(max_inversion) / 1000000)
+    print "Avg inversion: %f ms" % (float(avg_inversion) / 1000000)
+    for inv in longest_inversions:
+        print ""
+        print "Inversion record IDs: (%d, %d)" % (inv.inversion_start_id,
+            inv.id)
+        print("Triggering Event IDs: (%d, %d)" %
+            (inv.inversion_start_triggering_event_id,
+            inv.triggering_event_id))
+        print "Time: %d" % (inv.job.inversion_end)
+        # NOTE: Here, we assume nanoseconds as the time unit.
+        # May have to be changed in the future.
+        print "Duration: %f ms" % (
+            float(inv.job.inversion_end - inv.job.inversion_start) / 1000000)
+        print "Job: %d.%d" % (inv.job.pid,inv.job.job)
+        print "Deadline: %d" % (inv.job.deadline)
+        print ""
+
+
+def _sort_longest_inversions(longest_inversions):
+    """ Sort longest inversions"""
+    def sortkey(x):
+        return x.job.inversion_end - x.job.inversion_start
+    longest_inversions.sort(key=sortkey)
+    return longest_inversions
diff --git a/unit_trace/gedf_test.py b/unit_trace/gedf_test.py
index 8457901..478a852 100644
--- a/unit_trace/gedf_test.py
+++ b/unit_trace/gedf_test.py
@@ -9,6 +9,7 @@
 ###############################################################################
 
 import copy
+import sys
 
 
 ###############################################################################
@@ -17,39 +18,54 @@ import copy
 
 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
+    # System model
+    on_cpu = []     # Tasks on a CPU
+    off_cpu = []    # Tasks not on a CPU
+    m = None        # CPUs
 
     # Time of the last record we saw. Only run the G-EDF test when the time
     # is updated.
     last_time = None
 
+    # First event for the latest timestamp. This is used to match up
+    # inversion starts and ends with the first event from the previous
+    # timestamp, which is the first event that could have triggered
+    # the inversion start or end.
+    first_event_this_timestamp = 0
+
     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
 
+        # Bookkeeping iff the timestamp has moved forward.
         # 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.)
+        # (It is common to have records with simultaneous timestamps,
+        # so we only check when the time has moved forward)
+        # Also, need to update the first_event_this_timestamp variable
         if last_time is not None and last_time != record.when:
-            errors = _gedf_check(eligible,on_cpu,record.when,m)
+            errors = _gedf_check(off_cpu,on_cpu,last_time,m,
+                first_event_this_timestamp)
+            first_event_this_timestamp = record.id
             for error in errors:
                 yield error
 
-        # Add a newly-released Job to the eligible queue
+        # Add a newly-released Job to the off_cpu queue
         if record.type_name == 'release':
-            eligible.append(Job(record))
+            off_cpu.append(Job(record))
 
-        # Move a Job from the eligible queue to on_cpu
+        # Move a Job from the off_cpu queue to on_cpu
         elif record.type_name == 'switch_to':
-            pos = _find_job(record,eligible)
-            job = eligible[pos]
-            del eligible[pos]
+            pos = _find_job(record,off_cpu)
+            if pos is None:
+                msg = "Event %d tried to switch to a job that was not on the"
+                msg += " off_cpu queue\n"
+                msg = msg % (record.id)
+                sys.stderr.write(msg)
+                exit()
+            job = off_cpu[pos]
+            del off_cpu[pos]
             on_cpu.append(job)
 
         # Mark a Job as completed.
@@ -60,17 +76,41 @@ def gedf_test(stream):
             if pos is not None:
                 on_cpu[pos].is_complete = True
             else:
-                pos = _find_job(record,eligible)
-                del eligible[pos]
+                pos = _find_job(record,off_cpu)
+                del off_cpu[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)
+            if pos is None:
+                msg = ("Event %d tried to switch to switch away a job" +
+                    " that was not running\n")
+                msg = msg % (record.id)
+                sys.stderr.write(msg)
+                exit()
             job = on_cpu[pos]
             del on_cpu[pos]
             if job.is_complete == False:
-                eligible.append(job)
+                off_cpu.append(job)
+
+        # A job has been blocked.
+        elif record.type_name == 'block':
+            pos = _find_job(record,on_cpu)
+            # What if the job is blocked AFTER being switched away?
+            # This is a bug in some versions of LITMUS.
+            if pos is None:
+                pos = _find_job(record,off_cpu)
+                job = off_cpu[pos]
+            else:
+                job = on_cpu[pos]
+            job.is_blocked = True
+
+        # A job is resumed
+        elif record.type_name == 'resume':
+            pos = _find_job(record,off_cpu)
+            job = off_cpu[pos]
+            job.is_blocked = False
 
         last_time = record.when
         yield record
@@ -86,22 +126,33 @@ class Job(object):
         self.job = record.job
         self.deadline = record.deadline
         self.is_complete = False
+        self.is_blocked = False
         self.inversion_start = None
         self.inversion_end = None
+        self.inversion_start_id = None
+        self.inversion_start_triggering_event_id = 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):
+    id = 0
+    def __init__(self, job, off_cpu, on_cpu,first_event_this_timestamp):
+        Error.id += 1
+        self.id = Error.id
         self.job = copy.copy(job)
-        self.eligible = copy.copy(eligible)
+        self.off_cpu = copy.copy(off_cpu)
         self.on_cpu = copy.copy(on_cpu)
         self.record_type = 'error'
+        self.triggering_event_id = first_event_this_timestamp
         if job.inversion_end is None:
             self.type_name = 'inversion_start'
+            job.inversion_start_id = self.id
+            job.inversion_start_triggering_event_id = self.triggering_event_id
         else:
             self.type_name = 'inversion_end'
+            self.inversion_start_id = job.inversion_start_id
+            self.inversion_start_triggering_event_id = job.inversion_start_triggering_event_id
 
 # Returns the position of a Job in a list, or None
 def _find_job(record,list):
@@ -111,17 +162,20 @@ def _find_job(record,list):
     return None
 
 # Return records for any inversion_starts and inversion_ends
-def _gedf_check(eligible,on_cpu,when,m):
+def _gedf_check(off_cpu,on_cpu,when,m,first_event_this_timestamp):
 
     # List of error records to be returned
     errors = []
 
-    # List of all jobs that are not complete
+    # List of all jobs that are contending for the CPU (neither complete nor
+    # blocked)
     all = []
     for x in on_cpu:
-        if x.is_complete is not True:
+        if x.is_complete is not True and x.is_blocked is not True:
+            all.append(x)
+    for x in off_cpu:
+        if x.is_blocked 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
@@ -129,35 +183,45 @@ def _gedf_check(eligible,on_cpu,when,m):
     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
+    # Check those that actually should be running, to look for priority
+    # inversions
     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))
+            errors.append(Error(job, off_cpu, on_cpu,
+                first_event_this_timestamp))
 
         # 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))
+            errors.append(Error(job, off_cpu, on_cpu,
+                first_event_this_timestamp))
             job.inversion_start = None
             job.inversion_end = None
 
-    # Check those that actually should not be running
+    # Check those that actually should not be running, to record the end of any
+    # priority inversions
     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))
+            errors.append(Error(job, off_cpu, on_cpu,
+                first_event_this_timestamp))
             job.inversion_start = None
             job.inversion_end = None
 
+    # Look for priority inversions among blocked tasks and end them
+    all = filter(lambda x:x.is_blocked and x.inversion_start is not None,
+        on_cpu + off_cpu)
+    for job in all:
+        job.inversion_end = when
+        errors.append(Error(job, off_cpu, on_cpu,
+            first_event_this_timestamp))
+        job.inversion_start = None
+        job.inversion_end = None
+
     return errors
diff --git a/unit_trace/latest.py b/unit_trace/latest.py
index 4abd3a2..38676a0 100644
--- a/unit_trace/latest.py
+++ b/unit_trace/latest.py
@@ -11,7 +11,7 @@
 def latest(stream, latest):
     for record in stream:
         if record.record_type=="event":
-            if record.when > latest:
+            if record.id > latest:
                 break
             else:
                 yield record
diff --git a/unit_trace/naive_trace_reader.py b/unit_trace/naive_trace_reader.py
deleted file mode 100644
index 0f117b8..0000000
--- a/unit_trace/naive_trace_reader.py
+++ /dev/null
@@ -1,165 +0,0 @@
-###############################################################################
-# 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/unit_trace/progress.py b/unit_trace/progress.py
index d987ecd..d0f0482 100644
--- a/unit_trace/progress.py
+++ b/unit_trace/progress.py
@@ -25,7 +25,7 @@ def progress(stream):
 
     start_time = 0
     count = 0
-    
+
     for record in stream:
         if record.record_type=="event":
             count += 1
diff --git a/unit_trace/sanitizer.py b/unit_trace/sanitizer.py
index 79315cc..598379a 100644
--- a/unit_trace/sanitizer.py
+++ b/unit_trace/sanitizer.py
@@ -49,5 +49,5 @@ def sanitizer(stream):
         if record.type_name == 'switch_away':
             if (record.pid,record.job) not in jobs_switched_to:
                 record.job -= 1
-        
+
         yield record
diff --git a/unit_trace/stats.py b/unit_trace/stats.py
deleted file mode 100644
index 34a842f..0000000
--- a/unit_trace/stats.py
+++ /dev/null
@@ -1,39 +0,0 @@
-###############################################################################
-# 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/unit_trace/stdout_printer.py b/unit_trace/stdout_printer.py
index f8d9a84..b70b31a 100644
--- a/unit_trace/stdout_printer.py
+++ b/unit_trace/stdout_printer.py
@@ -27,17 +27,20 @@ def stdout_printer(stream):
 ###############################################################################
 
 def _print_event(record):
+    print "Event ID: %d" % (record.id)
     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 "Inversion Record IDs: (%d, U)" % (record.id)
+    print "Triggering Event IDs: (%d, U)" % (record.triggering_event_id)
     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 "Off CPU: ",
+    for job in record.off_cpu:
         print str(job) + " ",
     print
     print "On CPU: ",
@@ -47,23 +50,23 @@ def _print_inversion_start(record):
 
 def _print_inversion_end(record):
     print "Type: %s" % ("Inversion end")
+    print "Inversion record IDs: (%d, %d)" % (record.inversion_start_id,
+        record.id)
+    print("Triggering Event IDs: (%d, %d)" %
+        (record.inversion_start_triggering_event_id,
+        record.triggering_event_id))
     print "Time: %d" % (record.job.inversion_end)
-    print "Duration: %d" % (
-        record.job.inversion_end - record.job.inversion_start)
+    # NOTE: Here, we assume nanoseconds as the time unit.
+    # May have to be changed in the future.
+    print "Duration: %f ms" % (
+        float(record.job.inversion_end - record.job.inversion_start)/1000000)
     print "Job: %d.%d" % (record.job.pid,record.job.job)
     print "Deadline: %d" % (record.job.deadline)
-    print "Eligible: ",
-    for job in record.eligible:
+    print "Off CPU: ",
+    for job in record.off_cpu:
         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/unit_trace/trace_reader.py b/unit_trace/trace_reader.py
index 44a3c75..a4c3c05 100644
--- a/unit_trace/trace_reader.py
+++ b/unit_trace/trace_reader.py
@@ -5,7 +5,7 @@
 # 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 
+# 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
@@ -58,15 +58,28 @@ def trace_reader(files):
     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
+        try:
+            file_iter_buff.append([file_iter.next()])
+        # What if there isn't a single valid record in a trace file?
+        # file_iter.next() will raise a StopIteration that we need to catch
+        except:
+            # Forget that file iter
+            file_iters.pop()
+
+    # We keep 200 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.
+    # The 'try' and 'except' catches the case where there are less than 200
+    # records in a file (throwing a StopIteration) which otherwise would
+    # propogate up and cause the trace_reader generator itself to throw a
+    # StopIteration.
     for x in range(0,len(file_iter_buff)):
-        for y in range(0,100):
-            file_iter_buff[x].append(file_iters[x].next()) 
+        try:
+            for y in range(0,200):
+                file_iter_buff[x].append(file_iters[x].next())
+        except StopIteration:
+            pass
     for x in range(0,len(file_iter_buff)):
         file_iter_buff[x] = sorted(file_iter_buff[x],key=lambda rec: rec.when)
 
@@ -75,6 +88,9 @@ def trace_reader(files):
     # fatally if they are not.
     last_time = None
 
+    # We want to give records ID numbers so users can filter by ID
+    id = 0
+
     # Keep pulling records as long as we have a buffer
     while len(file_iter_buff) > 0:
 
@@ -109,8 +125,12 @@ def trace_reader(files):
         else:
             last_time = earliest.when
 
+        # Give the record an id number
+        id += 1
+        earliest.id = id
+
         # Yield the record
-        yield earliest 
+        yield earliest
 
 ###############################################################################
 # Private functions
@@ -123,17 +143,23 @@ def _get_file_iter(file):
         data = f.read(RECORD_HEAD_SIZE)
         try:
             type_num = struct.unpack_from('b',data)[0]
-        except struct.error: 
+        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 = _get_type(type_num)
+        except:
+            sys.stderr.write("Skipping record with invalid type num: %d\n" %
+                (type_num))
+            continue
+        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()
+            sys.stderr.write("Skipping record that does not match proper" +
+                " struct formatting\n")
+            continue
 
         # Convert the record_dict into an object
         record = _dict2obj(record_dict)
@@ -157,7 +183,7 @@ def _dict2obj(d):
     o = Obj()
     for key in d.keys():
         o.__dict__[key] = d[key]
-    return o 
+    return o
 
 ###############################################################################
 # Trace record data types and accessor functions
@@ -183,7 +209,7 @@ class StNameData:
     keys = StHeader.keys + ['name']
     message = 'The name of the executable of this process.'
 
-class StParamData:  
+class StParamData:
     format =  'IIIc'
     formatStr = struct.Struct(StHeader.format + format)
     keys = StHeader.keys + ['wcet','period','phase','partition']
@@ -195,7 +221,7 @@ class StReleaseData:
     keys = StHeader.keys + ['when','deadline']
     message = 'A job was/is going to be released.'
 
-#Not yet used by Sched Trace 
+#Not yet used by Sched Trace
 class StAssignedData:
     format =  'Qc'
     formatStr = struct.Struct(StHeader.format + format)
@@ -244,6 +270,8 @@ def _get_type(type_num):
     types = [None,StNameData,StParamData,StReleaseData,StAssignedData,
              StSwitchToData,StSwitchAwayData,StCompletionData,StBlockData,
              StResumeData,StSysReleaseData]
+    if type_num > len(types)-1 or type_num < 1:
+        raise Exception
     return types[type_num]
 
 # Return the type name, given the type_num (this is simply a convenience to
diff --git a/unit_trace/viz/draw.py b/unit_trace/viz/draw.py
new file mode 100644
index 0000000..dced27d
--- /dev/null
+++ b/unit_trace/viz/draw.py
@@ -0,0 +1,1377 @@
+#!/usr/bin/python
+
+import math
+import cairo
+import os
+import copy
+
+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
+
+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
+    MAX_FADE_WIDTH = 250
+
+    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):
+        fade_span = min(width, Pattern.MAX_FADE_WIDTH)
+
+        if len(self.color_list) == 1:
+            if fade:
+                canvas.fill_rect_fade(x, y, fade_span, height, (1.0, 1.0, 1.0), \
+                    self.color_list[0])
+            else:
+                canvas.fill_rect(x, y, width, height, self.color_list[0])
+
+            if width > Pattern.MAX_FADE_WIDTH:
+                    canvas.fill_rect(x + Pattern.MAX_FADE_WIDTH, y, width - Pattern.MAX_FADE_WIDTH,
+                                     height, self.color_list[0])
+        else:
+            n = 0
+            bottom = y + height
+            while y < bottom:
+                i = n % len(self.color_list)
+                if fade:
+                    canvas.fill_rect_fade(x, y, fade_span, \
+                        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])
+
+                if width > Pattern.MAX_FADE_WIDTH:
+                    canvas.fill_rect(x + Pattern.MAX_FADE_WIDTH, y, width - Pattern.MAX_FADE_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)
+
+    NULL_PATTERN = -1
+
+    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, snap=True):
+        """Draws a rectangle somewhere (border only)."""
+        raise NotImplementedError
+
+    def fill_rect(self, x, y, width, height, color, snap=True):
+        """Draws a filled rectangle somewhere. ``color'' is a 3-tuple."""
+        raise NotImplementedError
+
+    def fill_rect_fade(self, x, y, width, height, lcolor, rcolor, snap=True):
+        """Draws a rectangle somewhere, filled in with the fade."""
+        raise NotImplementedError
+
+    def draw_line(self, p0, p1, color, thickness, snap=True):
+        """Draws a line from p0 to p1 with a certain color and thickness."""
+        raise NotImplementedError
+
+    def draw_polyline(self, coor_list, color, thickness, snap=True):
+        """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, snap=True):
+        """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, snap=True):
+        """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, snap=True):
+        """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:
+            return
+
+        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_border_common(self, x, y, width, height, color, thickness, clip_side):
+        if clip_side is None:
+            self.draw_rect(x, y, width, height, color, thickness)
+        elif clip_side == AlignMode.LEFT:
+            self.draw_polyline([(x, y), (x + width, y), (x + width, y + height), (x, y + height)],
+                                color, thickness)
+        elif clip_side == AlignMode.RIGHT:
+            self.draw_polyline([(x + width, y), (x, y), (x, y + height), (x + width, y + height)],
+                                 color, thickness)
+
+    def draw_bar(self, x, y, width, height, n, clip_side, 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_bar_border_common(x, y, width, height, color, thickness, clip_side)
+
+    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, clip_side, 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_bar_border_common(x, y, width, height, color, thickness, clip_side)
+
+    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, real_x, real_y, width, height):
+        x = real_x + self.surface.virt_x
+        y = real_y + self.surface.virt_y
+        for event in self.selectable_regions.keys():
+            if self.selectable_regions[event].intersects(x, y, width, height):
+                del self.selectable_regions[event]
+
+    def add_sel_region(self, region):
+        self.selectable_regions[region.get_event()] = region
+
+    def get_sel_region(self, event):
+        return self.selectable_regions[event]
+
+    def get_selected_regions(self, real_x, real_y, width, height):
+        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.intersects(x, y, width, height):
+                selected[event] = region
+
+        return selected
+
+    def whiteout(self, real_x, real_y, width, height):
+        """Overwrites the surface completely white, but technically doesn't delete anything"""
+        self.fill_rect(self.surface.virt_x + real_x, self.surface.virt_y + real_y, width,
+                       height, (1.0, 1.0, 1.0), False)
+
+    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."""
+        if n < 0:
+            return self.bar_plist[-1]
+        return self.bar_plist[n % (len(self.bar_plist) - 1)]
+
+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, do_snap=True):
+        x, y, width, height = self.scaled(x, y, width, height)
+        x, y = self.surface.get_real_coor(x, y)
+        if do_snap:
+            self.surface.ctx.rectangle(snap(x), snap(y), width, height)
+        else:
+            self.surface.ctx.rectangle(x, 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, do_snap=True):
+        self._rect_common(x, y, width, height, color, thickness, do_snap)
+        self.surface.ctx.stroke()
+
+    def fill_rect(self, x, y, width, height, color, do_snap=True):
+        self._rect_common(x, y, width, height, color, 1, do_snap)
+        self.surface.ctx.fill()
+
+    def fill_rect_fade(self, x, y, width, height, lcolor, rcolor, do_snap=True):
+        """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)
+
+        if do_snap:
+            linear = cairo.LinearGradient(snap(x), snap(y), \
+                                      snap(x + width), snap(y + height))
+        else:
+            linear = cairo.LinearGradient(x, y, \
+                                      x + width, 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)
+        if do_snap:
+            self.surface.ctx.rectangle(snap(x), snap(y), width, height)
+        else:
+            self.surface.ctx.rectangle(snap(x), snap(y), width, height)
+        self.surface.ctx.fill()
+
+    def draw_line(self, p0, p1, color, thickness, do_snap=True):
+        """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])
+        if do_snap:
+            p0 = (snap(p0[0]), snap(p0[1]))
+            p1 = (snap(p1[0]), snap(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, do_snap=True):
+        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])
+        if do_snap:
+            for i in range(0, len(real_coor_list)):
+                real_coor_list[i] = (snap(real_coor_list[i][0]), snap(real_coor_list[i][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, do_snap=True):
+        self._polyline_common(coor_list, color, thickness, do_snap)
+        self.surface.ctx.stroke()
+
+    def fill_polyline(self, coor_list, color, thickness, do_snap=True):
+        self._polyline_common(coor_list, color, thickness, do_snap)
+        self.surface.ctx.fill()
+
+    def _draw_label_common(self, text, x, y, fopts, x_bearing_factor, \
+                           f_descent_factor, width_factor, f_height_factor, do_snap=True):
+        """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])
+
+        if do_snap:
+            self.surface.ctx.move_to(snap(actual_x), snap(actual_y))
+        else:
+            self.surface.ctx.move_to(actual_x, 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, do_snap=True):
+        """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, do_snap)
+
+    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, do_snap=True):
+        """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, do_snap)
+        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, do_snap)
+
+# 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 intersects(self, x, y, width, height):
+        return x <= self.x + self.width and x + width >= self.x and y <= self.y + self.height and y + height >= self.y
+
+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):
+        # deal with possibly blank schedules
+        if start_time is None:
+            start_time = 0
+        if end_time is None:
+            end_time = 0
+
+        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, width, height):
+        return self.canvas.get_selected_regions(real_x, real_y, width, height)
+
+    def get_width(self):
+        return self.width
+
+    def get_height(self):
+        return self.height
+
+    def get_origin(self):
+        return self.origin
+
+    def get_attrs(self):
+        return self.attrs
+
+    def add_sel_region(self, region):
+        self.canvas.add_sel_region(region)
+
+    def get_sel_region(self, event):
+        return self.canvas.get_sel_region(event)
+
+    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 _recomp_min_max(self, start_time, end_time, start_item, end_item):
+        if self.min_time is None or start_time < self.min_time:
+            self.min_time = start_time
+        if self.max_time is None or end_time > self.max_time:
+            self.max_time = end_time
+        if self.min_item is None or start_item < self.min_item:
+            self.min_item = start_item
+        if self.max_item is None or end_item > self.max_item:
+            self.max_item = end_item
+
+    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, real_x, real_y, width, height):
+        start_time = self.xcoor_to_time(self.canvas.surface.virt_x + real_x)
+        end_time = self.xcoor_to_time(self.canvas.surface.virt_x + real_x + width)
+
+        start_item = self.ycoor_to_item_no(self.canvas.surface.virt_y + real_y)
+        end_item = 2 + self.ycoor_to_item_no(self.canvas.surface.virt_y + real_y + 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, regions, selectable=False):
+        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, clip_side=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, clip_side=None, 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, regions, selectable=False):
+        events_to_render = {}
+        for layer in Canvas.LAYERS:
+            events_to_render[layer] = {}
+
+        for region in regions:
+            x, y, width, height = region
+            if not selectable:
+                self.canvas.whiteout(x, y, width, height)
+            else:
+                self.canvas.clear_selectable_regions(x, y, width, height)
+
+        self.min_time, self.max_time, self.min_item, self.max_item = None, None, None, None
+        for region in regions:
+            x, y, width, height = region
+            start_time, end_time, start_item, end_item = self.get_offset_params(x, y, width, height)
+            self._recomp_min_max(start_time, end_time, start_item, end_item)
+
+            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):
+                events_to_render[event.get_layer()][event] = None
+
+        if not selectable:
+            self.draw_skeleton(self.min_time, self.max_time,
+                               self.min_item, self.max_item)
+
+        #if not selectable:
+        #    for layer in events_to_render:
+        #        print 'task render on layer', layer, ':', [str(e) for e in events_to_render[layer].keys()]
+
+        for layer in Canvas.LAYERS:
+            prev_events = {}
+            for event in events_to_render[layer]:
+                event.render(self, layer, prev_events, selectable)
+
+    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, clip_side=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, clip_side, 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, clip_side=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, Canvas.NULL_PATTERN, clip_side, 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, regions, selectable=False):
+        BOTTOM_EVENTS = [schedule.ReleaseEvent, schedule.DeadlineEvent, schedule.InversionStartEvent,
+                     schedule.InversionEndEvent, schedule.InversionDummy]
+        TOP_EVENTS = [schedule.SuspendEvent, schedule.ResumeEvent, schedule.CompleteEvent,
+                  schedule.SwitchAwayEvent, schedule.SwitchToEvent, schedule.IsRunningDummy]
+
+        events_to_render = {}
+        for layer in Canvas.LAYERS:
+            events_to_render[layer] = {}
+
+        self.min_time, self.max_time, self.min_item, self.max_item = None, None, None, None
+        for region in regions:
+            x, y, width, height = region
+            if not selectable:
+                #self.canvas.whiteout(x, y, width, height)
+                self.canvas.whiteout(0, 0, self.canvas.surface.width, self.canvas.surface.height)
+            else:
+                self.canvas.clear_selectable_regions(x, y, width, height)
+
+        for region in regions:
+            x, y, width, height = region
+            start_time, end_time, start_item, end_item = self.get_offset_params(x, y, width, height)
+            self._recomp_min_max(start_time, end_time, start_item, end_item)
+
+            for event in sched.get_time_slot_array().iter_over_period(
+                        start_time, end_time, start_item, end_item,
+                        schedule.TimeSlotArray.CPU_LIST,
+                        TOP_EVENTS):
+                events_to_render[event.get_layer()][event] = None
+
+            if end_item >= len(self.y_item_list):
+                # we are far down enough that we should render the releases and deadlines and inversions,
+                # which appear near the x-axis
+                x, y, width, height = region
+                for event in sched.get_time_slot_array().iter_over_period(
+                        start_time, end_time, 0, sched.get_num_cpus(),
+                        schedule.TimeSlotArray.CPU_LIST,
+                        BOTTOM_EVENTS):
+                    events_to_render[event.get_layer()][event] = None
+
+        if not selectable:
+            self.draw_skeleton(self.min_time, self.max_time,
+                               self.min_item, self.max_item)
+
+        for layer in Canvas.LAYERS:
+            prev_events = {}
+            for event in events_to_render[layer]:
+                event.render(self, layer, prev_events, selectable)
+
+    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_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(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.COMPLETION_MARKER_FACTOR
+
+        x = self._get_time_xpos(time)
+        y = self._get_item_ypos(cpu_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):
+        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.SMALL_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.SMALL_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, clip_side=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, clip_side, 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_bar(x, y, width, height, event)
+
+    def draw_mini_bar_at_time(self, start_time, end_time, task_no, cpu_no, job_no=None, clip_side=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(len(self.y_item_list))
+        width = self._get_bar_width(start_time, end_time)
+        height = self._get_mini_bar_height()
+
+        self.canvas.draw_mini_bar(x, y, width, height, task_no, clip_side, 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(len(self.y_item_list))
+        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)