epsilonize_plan.py
Go to the documentation of this file.
00001 #! /usr/bin/env python
00002 # -*- coding: utf-8 -*-
00003 
00004 from decimal import Decimal
00005 import itertools
00006 import re
00007 import sys
00008 
00009 
00010 class TimedAction(object):
00011     def __init__(self, timestamp, name, duration):
00012         if timestamp < 0:
00013             raise ValueError("bad timestamp: %r" % timestamp)
00014         if duration < 0:
00015             raise ValueError("bad duration: %r" % duration)
00016         self.timestamp = timestamp
00017         self.name = name
00018         self.duration = duration
00019 
00020     def end(self):
00021         return self.timestamp + self.duration
00022 
00023     def copy(self):
00024         return self.__class__(self.timestamp, self.name, self.duration)
00025 
00026     def dump(self, out=None):
00027         print >> out, "%.10f: (%s) [%.10f]" % (
00028             self.timestamp, self.name, self.duration)
00029 
00030     @classmethod
00031     def parse(cls, line, default_timestamp):
00032         def bad():
00033             raise ValueError("cannot parse line: %r" % line)
00034         # regex = re.compile(
00035         #   r"\s*(.*?)\s*:\s*\(\s*(.*?)\s*\)\s*(?:\[\s*(.*?)\s*\])?$")
00036         ## Changed regex to work around TLP-GP issue.
00037         regex = re.compile(
00038             r"\s*(?:(.*?)\s*:)?\s*\(\s*(.*?)\s*\)\s*(?:\[\s*(.*?)\s*\])?$")
00039         match = regex.match(line)
00040         if not match:
00041             bad()
00042         try:
00043             # The following lines used to be:
00044             #    timestamp = Decimal(match.group(1))
00045             timestamp_opt = match.group(1)
00046             if timestamp_opt is None:
00047                 timestamp = default_timestamp
00048                 assert timestamp is not None
00049             else:
00050                 timestamp = Decimal(timestamp_opt)
00051             name = match.group(2)
00052             if match.group(3) is not None:
00053                 duration = Decimal(match.group(3))
00054             else:
00055                 duration = Decimal("0")
00056         except ValueError:
00057             bad()
00058         return cls(timestamp, name, duration)
00059 
00060 
00061 class Plan(object):
00062     def __init__(self, actions):
00063         self.actions = actions
00064 
00065     def copy(self):
00066         return self.__class__([action.copy() for action in self.actions])
00067 
00068     @classmethod
00069     def parse(cls, lines):
00070         actions = []
00071         for line in lines:
00072             line = line.partition(";")[0].strip()
00073             if line:
00074                 # default_timestamp: workaround for TLP-GP bug
00075                 if actions:
00076                     default_timestamp = actions[-1].timestamp
00077                 else:
00078                     default_timestamp=None
00079                 action = TimedAction.parse(line, default_timestamp)
00080                 actions.append(action)
00081         return cls(actions)
00082 
00083     def dump(self, out=None):
00084         for action in self.actions:
00085             action.dump(out)
00086 
00087     def sort(self):
00088         self.actions.sort(key=lambda action: action.timestamp)
00089 
00090     def required_separation(self):
00091         duration_granularity = granularity(a.duration for a in self.actions)
00092         rounded_num_actions = next_power_of_ten(len(self.actions))
00093         return duration_granularity / rounded_num_actions / 100
00094 
00095     def add_separation(self):
00096         separation = self.required_separation()
00097         for index, action in enumerate(self.actions):
00098             action.timestamp += (index + 1) * separation
00099 
00100     def makespan(self):
00101         if not self.actions:
00102             return Decimal("0")
00103         else:
00104             return max(action.end() for action in self.actions)
00105 
00106     def remove_wasted_time(self):
00107         # Using last_happening_before() only works properly when all
00108         # happenings only concern a single action, so we add separation
00109         # first.
00110         self.add_separation()
00111         for action in sorted(self.actions, key=lambda a: a.timestamp):
00112             action.timestamp = self.last_happening_before(
00113                 action.timestamp, action)
00114 
00115     def last_happening_before(self, time, excluded_action):
00116         last_happening = Decimal("0")
00117         for action in self.actions:
00118             if action is not excluded_action:
00119                 if action.timestamp <= time:
00120                     last_happening = max(last_happening, action.timestamp)
00121                 if action.end() <= time:
00122                     last_happening = max(last_happening, action.end())
00123         return last_happening
00124 
00125     def wasted_time(self):
00126         return self.makespan() - self.adjusted_makespan()
00127 
00128     def adjusted_makespan(self):
00129         plan = self.copy()
00130         plan.remove_wasted_time()
00131         return plan.makespan()
00132 
00133 
00134 def granularity(numbers):
00135     numbers = list(numbers)
00136     for power in itertools.count():
00137         if all((number * 10 ** power) % 1 == 0
00138                for number in numbers):
00139             return Decimal("0.1") ** power
00140 
00141 
00142 def next_power_of_ten(num):
00143     for power in itertools.count():
00144         if num <= 10 ** power:
00145             return 10 ** power
00146 
00147 
00148 def epsilonize(infile, outfile):
00149     properties = {}
00150 
00151     plan = Plan.parse(infile)
00152     orig_makespan = plan.makespan()
00153     properties["eps_orig_makespan"] = orig_makespan
00154     plan.remove_wasted_time()
00155     plan.add_separation()
00156     adjusted_makespan = plan.adjusted_makespan()
00157     properties["eps_adjusted_makespan"] = adjusted_makespan
00158     properties["eps_makespan"] = plan.makespan()
00159     properties["eps_wasted_time"] = plan.wasted_time()
00160     properties["eps_val_param"] = plan.required_separation() / 2
00161 
00162     for item in sorted(properties.items()):
00163         print >> outfile, "; %s: %.10f" % item
00164     plan.dump(outfile)
00165 
00166     if orig_makespan < adjusted_makespan:
00167         raise SystemExit("ERROR: Original makespan should not "
00168                          "be smaller than adjusted!")
00169     return properties
00170 
00171 
00172 if __name__ == "__main__":
00173     import sys
00174     args = sys.argv[1:]
00175     if len(args) >= 3:
00176         raise SystemExit("usage: %s [infile [outfile]]" % sys.argv[0])
00177     infile = open(args[0]) if args else sys.stdin
00178     outfile = open(args[1], "w") if len(args) >= 2 else sys.stdout
00179     epsilonize(infile, outfile)


tfd_modules
Author(s): Maintained by Christian Dornhege (see AUTHORS file).
autogenerated on Mon Oct 6 2014 07:52:06