Implemented correct ordering for trace reader and a test suite

- Trace reader reads in records from all files "in parallel", so
      they come in ordered correctly
- runtests.py has unit tests in it for testing the program
- Added sample_traces as part of test suite

10 files changed, 127 insertions, 28 deletions

diff --git a/TODO b/TODO
index 41dc878..e69de29 100644
--- a/TODO
+++ b/TODO
@@ -1,3 +0,0 @@
-- Currently, trace.py reads all records from the first trace file, then all
-    records from the second, etc. Instead it should progress through all
-    files simultaneously, producing records in order based on timestamp.
diff --git a/run.py b/run.py
index 42def18..ca13708 100755
--- a/run.py
+++ b/run.py
@@ -20,10 +20,10 @@ import text_print
 ###############################################################################
 
 g4 = [
-'/home/mollison/old/sta/traces/st-g4-0.bin',
-'/home/mollison/old/sta/traces/st-g4-1.bin',
-'/home/mollison/old/sta/traces/st-g4-2.bin',
-'/home/mollison/old/sta/traces/st-g4-3.bin'
+'./sample_traces/st-g4-0.bin',
+'./sample_traces/st-g4-1.bin',
+'./sample_traces/st-g4-2.bin',
+'./sample_traces/st-g4-3.bin',
 ]
 
 ###############################################################################
diff --git a/runtests.py b/runtests.py
new file mode 100755
index 0000000..dbbc9a9
--- /dev/null
+++ b/runtests.py
@@ -0,0 +1,42 @@
+#!/usr/bin/env python3
+
+###############################################################################
+# Description
+###############################################################################
+
+# Unit Tests
+
+
+###############################################################################
+# Imports
+###############################################################################
+
+import trace
+import os
+
+###############################################################################
+# Trace files
+###############################################################################
+
+files = [
+'./sample_traces/st-g4-0.bin',
+'./sample_traces/st-g4-1.bin',
+'./sample_traces/st-g4-2.bin',
+'./sample_traces/st-g4-3.bin',
+]
+
+###############################################################################
+# Tests
+###############################################################################
+
+# Does the trace reader sort files by time correctly?
+def test1():
+    stream = trace.get_trace_record_stream(files)
+    last_time = 0
+    for item in stream:
+        if last_time > item.when:
+            return "[FAIL]"
+        last_time = item.when
+    return "[SUCCESS]"
+
+print("Test 1: {}".format(test1()))
diff --git a/sample_traces/.runtests.py.swp b/sample_traces/.runtests.py.swp
new file mode 100644
index 0000000..d9a9acd
--- /dev/null
+++ b/sample_traces/.runtests.py.swp
diff --git a/sample_traces/st-g4-0.bin b/sample_traces/st-g4-0.bin
new file mode 100644
index 0000000..c52ed7b
--- /dev/null
+++ b/sample_traces/st-g4-0.bin
diff --git a/sample_traces/st-g4-1.bin b/sample_traces/st-g4-1.bin
new file mode 100644
index 0000000..77fea28
--- /dev/null
+++ b/sample_traces/st-g4-1.bin
diff --git a/sample_traces/st-g4-2.bin b/sample_traces/st-g4-2.bin
new file mode 100644
index 0000000..4d5d3cd
--- /dev/null
+++ b/sample_traces/st-g4-2.bin
diff --git a/sample_traces/st-g4-3.bin b/sample_traces/st-g4-3.bin
new file mode 100644
index 0000000..1cd7ee4
--- /dev/null
+++ b/sample_traces/st-g4-3.bin
diff --git a/text_print.py b/text_print.py
index 7254b51..98e91fa 100644
--- a/text_print.py
+++ b/text_print.py
@@ -21,3 +21,4 @@ def print_stream(stream):
 def _print_event(record):
     print("Job: {}.{}".format(record.pid,record.job))
     print("Type: {}".format(record.type_name))
+    print("Time: {}".format(record.when))
diff --git a/trace.py b/trace.py
index 1ceccae..a0a32ce 100644
--- a/trace.py
+++ b/trace.py
@@ -19,32 +19,89 @@ import struct
 
 # Generator function returning an iterable over records in a trace file.
 def get_trace_record_stream(files):
+
+    # Create iterators for each file and a buffer to store records in
+    file_iters = [] # file iterators
+    file_iter_buff = [] # file iterator buffers
     for file in files:
-        with open(file,'rb') as f:
-            while True:
-                data = f.read(24)
-                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()
-                Record = _dict2obj(record_dict)
-                Record.type_name = _get_type_name(type_num)
-                Record.record_type = "event"
-                yield Record
+        file_iter = _get_file_iter(file)
+        file_iters.append(_get_file_iter(file))
+        file_iter_buff.append([next(file_iter)])
+
+    # We keep 100 records in each buffer and then keep the buffer sorted
+    # This is because records may be recorded slightly out of order
+    for x in range(0,len(file_iter_buff)):
+        for y in range(0,100):
+            file_iter_buff[x].append(next(file_iters[x])) 
+    for x in range(0,len(file_iter_buff)):
+        file_iter_buff[x] = sorted(file_iter_buff[x],key=lambda rec: rec.when)
+
+    # Keep pulling records as long as we have a buffer
+    while len(file_iter_buff) > 0:
+
+        # Select the earliest record from those at the heads of the buffers
+        earliest = -1
+        buff_to_refill = -1
+        for x in range(0,len(file_iter_buff)):
+            if earliest==-1 or file_iter_buff[x][0].when < earliest.when:
+                earliest = file_iter_buff[x][0]
+                buff_to_refill = x
+
+        # Take it out of the buffer
+        del file_iter_buff[buff_to_refill][0]
+
+        # Try to append a new record to the buffer (if there is another) and
+        #     then keep the buffer sorted
+        try:
+            file_iter_buff[buff_to_refill].append(next(file_iters[buff_to_refill]))
+            file_iter_buff[buff_to_refill] = sorted(file_iter_buff[buff_to_refill],
+                key=lambda rec: rec.when)
+
+        # If there aren't any more records, fine. Unless the buffer is also empty.
+        # If that is the case, delete the buffer.
+        except StopIteration:
+            if len(file_iter_buff[buff_to_refill]) < 1:
+                del file_iter_buff[buff_to_refill]
+                del file_iters[buff_to_refill]
+
+        # Yield the record
+        yield earliest 
 
 ###############################################################################
 # Private functions
 ###############################################################################
 
+# Returns an iterator to pull records from a file
+def _get_file_iter(file):
+    with open(file,'rb') as f:
+        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()
+            record = _dict2obj(record_dict)
+            record.type_name = _get_type_name(type_num)
+
+            # All records should have a 'record type' field.
+            # e.g. these are 'event's as opposed to 'error's
+            record.record_type = "event"
+
+            # If there is no timestamp, set the time to 0
+            if 'when' not in record.__dict__.keys():
+                record.when = 0
+
+            yield record
+
 # Convert a dict into an object
 def _dict2obj(d):
     class Obj: pass
@@ -57,6 +114,8 @@ def _dict2obj(d):
 # Trace record data types and accessor functions
 ###############################################################################
 
+RECORD_HEAD_SIZE = 24
+
 class StHeader:
     format =  '<bbhi'
     formatStr = struct.Struct(format)
@@ -78,7 +137,7 @@ class StParamData:
 class StReleaseData:
     format =  'QQ'
     formatStr = struct.Struct(StHeader.format + format)
-    keys = StHeader.keys + ['release_time','deadline']
+    keys = StHeader.keys + ['when','deadline']
     message = 'A job was/is going to be released.'
 
 #Not yet used by Sched Trace