import sys
import re
from fractions import Fraction
import functools
import heapq
import sys
import copy

@functools.total_ordering
class Interval:
  def __init__(self, ar, dl):
    self.ar = ar
    self.dl = dl

  def isWithin(self, other):
    return (self.ar >= other.ar and self.dl <= other.dl)

  def __str__(self):
    return ('[' + ', '.join((
      str(self.ar),
      str(self.dl))) + ']')

  def __lt__(self, other):
    if not isinstance(other, self.__class__):
      return NotImplemented
    isLessThan = False
    if (self.ar < other.ar):
      isLessThan = True
    elif (self.ar == other.ar):
      isLessThan = (self.dl < other.dl)
    else:
      isLessThan = False
    return isLessThan


@functools.total_ordering
class Task(Interval):
  def __init__(self, name, arrival, comp, dline):
    super(Task, self).__init__(arrival, dline)
    self.name = name
    self.comp = comp

  def __str__(self):
    s = ','.join((
      str(self.ar),
      str(self.comp),
      str(self.dl)))
    return (self.name + '[' + s + ']')

  def __eq__(self, other):
    return (
      self.name == other.name and
      self.ar == other.ar and
      self.dl == other.dl and
      self.comp == other.comp)

  def __hash__(self):
    return hash(self.__str__())


class CriticalInterval(Interval):
  def __init__(self, ar, dl):
    super(CriticalInterval, self).__init__(ar, dl)
    self.critTaskSet = []
    self.intensity = Fraction(0, 1)

  def addTask(self, task):
    self.critTaskSet.append(task)

  def calculateIntensity(self):
    totalComp = 0
    for task in self.critTaskSet:
      totalComp += task.comp
    self.intensity = Fraction(totalComp, (self.dl - self.ar))

  def __str__(self):
    return ('[' + ','.join((
      str(self.ar),
      str(self.dl))) + '] : ' + str(self.intensity))


class CpuSchedule(Interval):
  def __init__(self, ar, dl, taskName, cpurate):
    super(CpuSchedule, self).__init__(ar, dl)
    self.taskName = taskName
    self.cpurate = cpurate

  def __copy__(self):
    return CpuSchedule(self.ar, self.dl, self.taskName, self.cpurate)

  def __str__(self):
    s = super(CpuSchedule, self).__str__() + ' '
    s += ((self.taskName if self.taskName is not None else '')
         + ' cpurate=' + str(self.cpurate))
    return s

class TaskSchedule(CpuSchedule):
  @classmethod
  def cloneFromCpuSchedule(cls, cpuSched):
    ts = cls(cpuSched.ar, cpuSched.dl, cpuSched.cpurate)
    return ts

  def __init__(self, ar, dl, cpurate):
    super(TaskSchedule, self).__init__(ar, dl, None, cpurate)


def findCriticalInterval(taskSet):
  taskSet.sort()
  critInterval = CriticalInterval(0, 0)
  for t in taskSet:
    for tt in taskSet:
      ci = CriticalInterval(t.ar, tt.dl)
      for job in taskSet:
        if job.isWithin(ci):
          ci.addTask(job)
      ci.calculateIntensity()
      if ci.intensity > critInterval.intensity:
        critInterval = ci
  return critInterval


def edfPeekNextTask(curTask, eventQueue):
  temp = []
  nextFound = False
  taskNext = None
  while (len(eventQueue) > 0 and taskNext is None):
    job = heapq.heappop(eventQueue)
    temp.append(job)
    if (job.ar > curTask.ar):
      taskNext = job
  for t in temp:
    heapq.heappush(eventQueue, t)
  return taskNext


def edfUpdateReoccurTask(curTask, cpurate, nextTask, eventQueue):
  elapsed = Fraction(curTask.comp, cpurate)
  endTime = curTask.ar + elapsed
  if (nextTask is None or (endTime <= nextTask.ar)): pass
  else:
    endTime = nextTask.ar
    remainingComp = curTask.comp - cpurate * (endTime - curTask.ar)
    newTask = Task(curTask.name, endTime, remainingComp, curTask.dl)
    heapq.heappush(eventQueue, newTask)
  return (endTime, eventQueue)


def edfUpdateRemainingTasks(newArrivalTime, eventQueue):
  temp = []
  done = False
  while (len(eventQueue) > 0 and not done):
    job = heapq.heappop(eventQueue)
    if (job.ar <= newArrivalTime):
      job.ar = newArrivalTime
    else:
      done = True
    temp.append(job)
  for job in temp:
    heapq.heappush(eventQueue, job)
  return eventQueue


def shouldMerge(sched1, sched2):
  if sched1 is None:
    return False
  return (sched1.taskName == sched2.taskName and
          sched1.cpurate == sched2.cpurate and
          sched1.dl == sched2.ar)

def mergeSeqOfSameSchedules(scheds):
  merged = []
  for sched in scheds:
    try:
      tail = merged[-1]
    except:
      tail = None
    if shouldMerge(tail, sched):
      tail.dl = sched.dl
      merged[-1] = tail
    else:
      merged.append(sched)
  return merged


def edfSchedule(taskSet, cpurate):
  eventQueue = []
  scheduleIntervals = []
  for task in taskSet:
    heapq.heappush(eventQueue, task)
  while (len(eventQueue) > 0):
    taskExec = heapq.heappop(eventQueue)
    taskNext = edfPeekNextTask(taskExec, eventQueue)
    endTime, eventQueue = edfUpdateReoccurTask(taskExec, cpurate, taskNext, eventQueue)
    scheduleIntervals.append(
        CpuSchedule(taskExec.ar, endTime, taskExec.name, cpurate))
    eventQueue = edfUpdateRemainingTasks(endTime, eventQueue)
  scheduleIntervals = mergeSeqOfSameSchedules(scheduleIntervals)
  return scheduleIntervals


def findLowHighRateForTasks(critTaskSet, cpurate, cpuModes):
  taskRateMap = {}
  for i in range(1, len(cpuModes)):
    if cpurate <= cpuModes[i] and cpurate > cpuModes[i-1]:
      break
  lrate = cpuModes[i-1]
  hrate = cpuModes[i]
  for task in critTaskSet:
    requiredTime = task.comp / cpurate
    switchTime = (requiredTime * hrate - task.comp) / (hrate - lrate)
    taskRateMap[task.name] = (lrate, hrate, switchTime)
  return taskRateMap


def adjustScheduleWith2Rates(scheduleIntervals, taskRateMap):
  adjusted = []
  trackingTimeLeftBeforeSwitch = {}
  for cpuSched in scheduleIntervals:
    lrate, hrate, switchTime = taskRateMap[cpuSched.taskName]
    if hrate == cpuSched.cpurate:
      adjusted.append(cpuSched)
    else:
      info = trackingTimeLeftBeforeSwitch.get(cpuSched.taskName)
      if info is None:
        if cpuSched.ar + switchTime < cpuSched.dl:
          adjusted.append(
              CpuSchedule(cpuSched.ar, cpuSched.ar + switchTime,
                          cpuSched.taskName, lrate))
          adjusted.append(
              CpuSchedule(cpuSched.ar + switchTime, cpuSched.dl,
                          cpuSched.taskName, hrate))
          trackingTimeLeftBeforeSwitch[cpuSched.taskName] = 0
        else:
          adjusted.append(
              CpuSchedule(cpuSched.ar, cpuSched.dl, cpuSched.taskName, lrate))
          trackingTimeLeftBeforeSwitch[cpuSched.taskName] = (
              switchTime - (cpuSched.dl - cpuSched.ar))
      else:
        if info == 0:
          adjusted.append(
              CpuSchedule(cpuSched.ar, cpuSched.dl, cpuSched.taskName, hrate))
        else:
          if cpuSched.ar + info < cpuSched.dl:
            adjusted.append(
                CpuSchedule(cpuSched.ar, cpuSched.ar + info,
                            cpuSched.taskName, lrate))
            adjusted.append(
                CpuSchedule(cpuSched.ar + info, cpuSched.dl,
                            cpuSched.taskName, hrate))
            trackingTimeLeftBeforeSwitch[cpuSched.taskName] = 0
          else:
            adjusted.append(
                CpuSchedule(cpuSched.ar, cpuSched.dl, cpuSched.taskName, lrate))
            trackingTimeLeftBeforeSwitch[cpuSched.taskName] = (
                info - (cpuSched.dl - cpuSched.ar))
  return adjusted


def schedule(critInterval, cpuModes):
  cpurate = critInterval.intensity
  scheduleIntervals = edfSchedule(critInterval.critTaskSet, cpurate)
  taskRateMap = findLowHighRateForTasks(
      critInterval.critTaskSet, cpurate, cpuModes)
  adjusted = adjustScheduleWith2Rates(scheduleIntervals, taskRateMap)
  return (scheduleIntervals, adjusted)


def updateTimeByRemovingInterval(t, x, y):
  if t <= x: return t
  elif t <= y: return x
  else: return t - (y - x)


def generateNewTaskSet(taskSet, critInterval):
  remaining = [e for e in taskSet if e not in critInterval.critTaskSet]
  iStart = critInterval.ar
  iEnd = critInterval.dl
  for task in remaining:
    task.ar = updateTimeByRemovingInterval(task.ar, iStart, iEnd)
    task.dl = updateTimeByRemovingInterval(task.dl, iStart, iEnd)
  while (len(taskSet) > 0):
    taskSet.pop()
  for t in remaining:
    taskSet.append(t)


def rebuildWithHidenInterval(partialSchedule, iHiden):
  rebuilt = []
  while (len(partialSchedule) > 0):
    cpuSched = partialSchedule.pop()
    shrinkingPoint = iHiden.ar
    if cpuSched.dl <= shrinkingPoint:
      rebuilt.append(cpuSched)
    elif cpuSched.ar >= shrinkingPoint:
      cpuSched.ar += iHiden.dl - iHiden.ar
      cpuSched.dl += iHiden.dl - iHiden.ar
      rebuilt.append(cpuSched)
    else:
      left = copy.copy(cpuSched)
      right = copy.copy(cpuSched)
      left.dl = shrinkingPoint
      right.ar = iHiden.dl
      right.dl += iHiden.dl - iHiden.ar
      rebuilt.append(left)
      rebuilt.append(right)
  return rebuilt


def minPowerSchedule(taskSet, cpuModes):
  globalSched = []
  while (len(taskSet) > 0):
    critInterval = findCriticalInterval(taskSet)
    if (critInterval.intensity > 1):
      print('!!!Unable to schedule with a critical interval with intesity > 1.')
    scheduleIntervals, adjusted = schedule(critInterval, cpuModes)
    iHiden = Interval(critInterval.ar, critInterval.dl)
    globalSched.append((scheduleIntervals, adjusted, iHiden))
    generateNewTaskSet(taskSet, critInterval)

  reconSched = []
  reconAdjustedSched = []
  for tup in reversed(globalSched):
    curSchedIntervals = tup[0]
    curAdjustedSchedIntervals = tup[1]
    iHiden = tup[2]
    reconSched = rebuildWithHidenInterval(reconSched, iHiden)
    reconAdjustedSched = rebuildWithHidenInterval(reconAdjustedSched, iHiden)
    for sched in curSchedIntervals:
      reconSched.append(sched)
    for sched in curAdjustedSchedIntervals:
      reconAdjustedSched.append(sched)

  reconSched.sort()
  reconAdjustedSched.sort()
  return (reconSched, reconAdjustedSched)


def getSchedByTasks(theSched):
  schedByTasks = {}
  for s in theSched:
    intervals = schedByTasks.get(s.taskName)
    if intervals is None:
      intervals = []
    intervals.append(TaskSchedule.cloneFromCpuSchedule(s))
    schedByTasks[s.taskName] = intervals
  return schedByTasks


def calTotalEnergy(theSched):
  energy = 0
  for cpuSched in theSched:
    energy += ((cpuSched.cpurate * cpuSched.cpurate) *
               (cpuSched.dl - cpuSched.ar))
  return energy


def main():
  fname = 'input.txt'
  if len(sys.argv) == 2:
    fname = sys.argv[1]

  taskSet = []
  taskNameSet = []
  delims = r'[\W]+'
  with open(fname) as f:
    for line in f:
      taskName, taskInfo = line.split(':')
      tokens = re.split(delims, taskInfo)
      taskName = taskName.strip()
      if taskName:
        taskSet.append(Task(
          taskName,
          int(tokens[1]),
          int(tokens[2]),
          int(tokens[1]) + int(tokens[3])))
        taskNameSet.append(taskName)

  theSched, theAdjustedSched = minPowerSchedule(taskSet, cpuModes)
  print('===Global Optimal Schedule:')
  for s in theSched:
    print(s)

  energy = calTotalEnergy(theSched)
  print('===Total energy: ' + str(energy) + ' = '
        + '{:.2f}'.format(round(float(energy),2)))

  schedByTasks = getSchedByTasks(theSched)
  print('===Optimal Schedule by tasks:')
  for taskName in taskNameSet:
    s = taskName + ': '
    for i in schedByTasks[taskName]:
      s += str(i) + ', '

    energy = calTotalEnergy(schedByTasks[taskName])
    s += 'energy: ' + '{:.2f}'.format(round(float(energy),2))
    print(s)

  print()
  print('*** CPU with discrete power modes ***')
  print()
  print('===Global Optimal Schedule with discrete-power-mode CPU:')
  for s in theAdjustedSched:
    print(s)

  discreteEnergy = calTotalEnergy(theAdjustedSched)
  print('===Total energy with discrete-power-mode CPU: ' + str(discreteEnergy) + ' = '
        + '{:.2f}'.format(round(float(discreteEnergy),2)))

  adjustedSchedByTasks = getSchedByTasks(theAdjustedSched)
  print('===Optimal Schedule by tasks with discrete-power-mode CPU:')
  for taskName in taskNameSet:
    s = taskName + ': '
    for i in adjustedSchedByTasks[taskName]:
      s += str(i) + ', '

    energy = calTotalEnergy(adjustedSchedByTasks[taskName])
    s += 'energy: ' + '{:.2f}'.format(round(float(energy),2))
    print(s)

if __name__ == '__main__':
  cpuModes = [
      Fraction(0),
      Fraction(10, 100),
      Fraction(25, 100),
      Fraction(40, 100),
      Fraction(55, 100),
      Fraction(70, 100),
      Fraction(85, 100),
      Fraction(1)]
  main()
