#!/usr/bin/env python

# 2011 Christoph Durr + Fadi Kacem

# Speed Scaling with Power Down states
# minimum Energy scheduling
# single machine, agreable deadlines

from sys       import *
from copy      import *
from fractions import *

#constants
wakeupEnergy =  10
groundEnergy =   1
alpha        =   2
perfectSpeed =   1
INFINITE     = 1e6

# ------------------------------------------------ instance

class Job:
    def __init__(self,r,d,w,j):
        self.r = r # release time
        self.d = d # deadline
        self.w = w # workload
        self.j = j # index in original instance (before sorting)

    def __repr__(self):
        return "(r=%d,d=%d,w=%d,j=%d)"%(self.r, self.d, self.w, self.j)


def readInstance(jobs):
    ''' J = all jobs, N = all job indices from 0 to n-1 '''
    global J, N, n
    J = []
    l = jobs.split()
    n = len(l)
    N = range(n)
    # decode jobs
    for j in N:
        try:
            r,d,w = map(int,l[j].split("/"))
        except ValueError:
            fatalError('Illformed job description "%s", '    \
                           'try removing unecessary spaces'%l[j])            
        if not (0<=r and r<d and w>0):
            fatalError('Illformed job description "%s", '    \
                           'release time must be before deadline, and weight positive'%l[j])
        J.append(Job(r,d,w,j))
    # check if instance is agreeable
    J.sort(key = lambda j: (j.r, j.d))
    for j in range(len(l)-1):
        if J[j].d > J[j+1].d:
            fatalError('instance does not have agreeable deadlines')
    # add dummy jobs, useful for computing Y[-1,n]=all jobs
    if not J:
        fatalError('Instance is empty')
    J.append(Job(J[n-1].d,0,0,n-1))
    J.append(Job(0,J[0].r,0,-1))

# ------------------------------------------------ YDS schedule


class Block:
    ''' a block is a sequence of jobs scheduled in a time interval at
    constant speed. Its total workload is the workload of its jobs '''
    def __init__(self, jstart,jend, w, tstart, tend):
        self.jstart  = jstart
        self.jend    = jend
        self.w       = w
        self.tstart  = tstart
        self.tend    = tend

    def len(self):
        return self.tend-self.tstart

    def __repr__(self):
        return "(J=%d..%d,w=%d,t=%d..%d)"%                              \
                (self.jstart, self.jend, self.w, self.tstart, self.tend)

def newPrefixSeq(i,j, jend):
    tend = min(J[jend].r,J[j].d)
    w = sum(J[k].w for k in range(i,j+1))
    tstart = tend - w/perfectSpeed
    return block2schedule(Block(i,j,w,tstart,tend))

def newSuffixSeq(i,j,jstart):
    tstart = max(J[jstart].d,J[i].r)
    w = sum(J[k].w for k in range(i,j+1))
    tend = tstart + w/perfectSpeed
    return block2schedule(Block(i,j,w,tstart,tend))

# A schedule is a sequence executions described by tuples
# (start,end,speed,job) with speed=0,job=-1 for shutdown

def block2schedule(b):
    if not b:
        return []
    R = []
    t = b.tstart
    if b.len():
        s = Fraction(b.w, b.len())
    else:
        s = 1000
    for j in range(b.jstart, b.jend+1):
        t1 = t+J[j].w/s
        R.append((t,t1,s,j))
        t = t1
    return R

def list2schedule(L):
    R = []
    for b in L:
        R += block2schedule(b)
    return R

# ------------------------------------------------ Yao, Demers, Shenker


# Y[i,j] optimal YDS schedule over all jobs from i+1 to j-1
# restricted to the interval [di,rj]. Is defined only if di<=rj and if
# either j=i+1 or j>i+1 and d_{i+1}>d_i and r_{j-1}<r_j. (Otherwise
# some jobs would have to be scheduled at infinite speed.)

memY   = {}

def Ycost(i,j):
   if (i,j) in memY:
       return memY[i,j][0]
   
   if i+1>=j:
       memY[i,j] = (0,[])
       return 0

   def r(q):
       return max(J[q].r,J[i].d)

   def d(q):
       return min(J[q].d,J[j].r)

   L = [(d(l)-r(k), k,l, sum(J[q].w for q in range(k,l+1)))
        for k in range(i+1,j) for l in range(k,j)]
   len,k,l,w = min(L)
   if len<=0:
       cost  = INFINITE
       sched = []
   else:
       len,k,l,w = max(L, key=lambda (len,k,l,w): Fraction(w,len))
       s     = Fraction(w,len)
       cost  = len*(s**alpha)
       sched = block2schedule(Block(k,l,w,r(k),d(l)))
       if (k,l)!=(i+1,j-1):
           cost  = Ycost(i,k)  + cost  + Ycost(l,j)
           sched = Ysched(i,k) + sched + Ysched(l,j)

   memY[i,j] = (cost,sched)
   return cost

def YfullCost(i,j):
    r = Ycost(i,j) + max(0,(J[j].r-J[i].d))*groundEnergy
    return r

def Ysched(i,j):
    Ycost(i,j)
    return memY[i,j][1]


# ------------------------------------------------ prefix, suffix

def compute_pre_suffixes(i,j):
    # prefixes for the subinstance for jobs from i+1 to j-1 included
    t = min(J[j].r, J[j-1].d)
    prefix = [0 for _ in N]
    jend = j-1
    for k in range(j-1,i,-1):
        if J[k].d < t:
            jend = k
            t = J[k].d
        t -= Fraction(J[k].w, perfectSpeed)
        prefix[k] = jend
    # suffixes for the subinstance for jobs from i+1 to j-1 included
    t = max(J[i].d, J[i+1].r)
    suffixes = []
    jstart = i+1
    for k in range(i+1,j):
        if t<J[k].r:
            suffixes.append((jstart, k-1))
            jstart = k
            t = J[k].r
        t += Fraction(J[k].w, perfectSpeed)
    if jstart<j:
        suffixes.append((jstart, j-1))
    return (prefix, suffixes)
    

# ------------------------------------------------ fast jobs 

# solve initial subinstance over jobs 0..jend-1
def solveInitial(jend):
    #stderr.write("solveInitial(%d)\n"%jend)
    if jend==0:
        return []
    prefix, suffixes = compute_pre_suffixes(-1,jend)
    c  = prefix[0]
    S  = newPrefixSeq(0,c, jend)
    S += optSched(c,jend)
    #stderr.write(str(locals()))
    return S
    
def solve():
    cost = 0
    jstart = -1
    S = []
    # the YDS schedule of all jobs
    for b in Ysched(-1,n):
        (start,tend,speed,job) = b
        if speed >= perfectSpeed:
            if not S:
                # initial subinstance
                S = solveInitial(job)
            elif jstart+1 < job:
                # inner subinstance
                S += optSched(jstart, job)
            # block of fast jobs
            S.append(b)
            jstart = job
    # is there a final subinstance ?
    if jstart<n-1:
        prefix, suffixes = compute_pre_suffixes(jstart,n)
        (job,b) = suffixes[-1]
        assert b==n-1
        if not S:
            # initial subinstance
            S = solveInitial(job)
        elif jstart+1 < job:
            # inner subinstance
            S += optSched(jstart, job)
        S += newSuffixSeq(job,n-1, jstart)
    return S

# ------------------------------------------------ dynamical programming


memOptCost   = {}
memOptChoice = {}

def optCost(i,j):
    if (i,j) in memOptCost:
        return memOptCost[i,j]

    # first option: no shutdown
    memOptChoice[i,j]=None
    best = YfullCost(i,j)

    # prepare other options
    prefix, _suffixes = compute_pre_suffixes(i,j)
    # two sided shutdown
    options = [(a,b,prefix[b+1]) for (a,b) in _suffixes if b+1<j and prefix[b+1]<j]
    # shutdown, not followed by jobs
    for (a,k) in _suffixes:
        if k==j-1:
            options.append((a,k,-1))
    # shutdown, not preceded by jobs
    if i+1<j and prefix[i+1]<j:
        options.append((-1, i, prefix[i+1]))
    # shutdown, not surrounded by jobs
    if i+1==j:
        options.append((-1,-1,-1))

    # minimize over options
    for (a,b,c) in options:
        # shutdown
        alt = wakeupEnergy
        # suffixe ?
        perfectCost  = Fraction(perfectSpeed**alpha + groundEnergy, perfectSpeed)
        if a!=-1:
            alt += YfullCost(i,a)
            wsuf = sum(J[k].w for k in range(a,b+1))
            alt += wsuf * perfectCost
        # prefix ?
        if c!=-1:
            wpre = sum(J[k].w for k in range(b+1,c+1))
            alt += wpre * perfectCost
            alt += optCost(c,j)
        # found better option?            
        if alt<best:
            best = alt
            memOptChoice[i,j] = (a,b,c)

    memOptCost[i,j] = best
    return best



def optSched(i,j):
    #stderr.write("optSched(%d,%d)"%(i,j))
    optCost(i,j)
    if not memOptChoice[i,j]:
        return Ysched(i,j)

    a,b,c = memOptChoice[i,j]

    if a!=-1:
        # has suffix
        o    = newSuffixSeq(a,b,i)
        t1   = o[-1][1]
        suf  = Ysched(i,a) + o
    else:
        suf  = []
        t1   = J[i].d
        
    if c!=-1:
        # has prefix
        o    = newPrefixSeq(b+1,c, j)
        t2   = o[0][0]
        pre  = o + optSched(c,j)
    else:
        pre = []
        t2  = J[j].r

    # shutdown
    return suf + [(t1, t2, 0, -1)] + pre

# ------------------------------------------------ visual schedule


svgHeader = '<?xml version="1.0" standalone="no"?>\n'                     \
          '<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN" '               \
          '"http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd">\n' \
          '<svg xmlns="http://www.w3.org/2000/svg"'                       \
          ' font-family="sans-serif" font-size="10pt"'                    \
          ' xmlns:xlink="http://www.w3.org/1999/xlink" '                  \
          ' width="%d" height="%d" viewBox="0 0 %d %d">\n'                \
          '<text x="%d" y="%d" text-anchor="start">%s'                    \
          '</text>\n'

def schedule2svg(msg, S):
    # constants
    w = 18
    d =  3
    width  = w * max(30,(J[n-1].d + 2))
    base   = w * max(2,max(speed for (_,_,speed,_) in S))
    height = base+(n+3)*w+d
    
    print svgHeader % (width,height,width,height,d, height-2*d, msg)
    
    down = []

    # job release time deadline span with processing time
    for j in N:
        y1 = base+(J[j].j+2)*w
        x1 = J[j].r*w
        x2 = J[j].d*w
        y2 = y1-d
        L = [(x1,y2),(x1,y1),(x2,y1),(x2,y2)]
        for i in range(len(L)-1):
            print '<line x1="%d" y1="%d" x2="%d" y2="%d" '                    \
                'style="stroke:grey"/>\n'%(L[i][0],L[i][1], L[i+1][0],L[i+1][1])
        print '<text x="%d" y="%d" text-anchor="start">w%d=%d</text>'         \
               %(x1+d, y2, j+1,J[j].w)

    # compute each job execution 
    for (tstart,tend,speed,job) in S:
        if job==-1:
            #shutdown interval
            down.append((tstart,tend))
        else:
            # job execution            
            if speed==1:
                color="orange"
            elif speed>1:
                color="red"
            else:
                color="yellow"
            s = int(speed*w)
            y = base  - s
            x = tstart*w
            l = (tend-tstart)*w
            h = s
            print '<rect x="%d" y="%d" width="%d" height="%d" '       \
              ' style="fill:%s;stroke-width:1;stroke:rgb(0,0,0)" />'  \
              %(x,y,l,h,color)
            if speed<1:
                y = base - s -d
            else:
                y = y+h-d
            print '<text x="%d" y="%d" text-anchor="start">%d</text>'     \
                %(x+d,y,job+1)

    # show grey lines, for activity
    if S:
        tstart = S[0][0]
        tend   = S[-1][1]
        if down:
            activities  = [(tstart, down[0][0])] 
            activities += [(down[i-1][1],down[i][0]) 
                           for i in range(1,len(down))]
            activities += [(down[-1][1], tend)]
        else:
            activities = [(tstart, tend)]
        for x1,x2 in activities:
            print '<rect x="%d" y="%d" width="%d" height="%d" ' \
                ' style="fill:gray" />' %(x1*w,base+d,(x2-x1)*w,d)

    print '</svg>'

def fatalError(msg):
    print svgHeader % (1000,50,1000,50,3, 45, "Fatal error: "+msg)
    print '</svg>'
    sys.exit(1)

def cost(S):
    tstart = S[0][0]
    tend   = S[-1][1]
    L = {}
    L[0]  = tend-tstart
    L[-1] = 0
    for (tstart,tend,speed,job) in S:
        len = tend-tstart
        if job==-1:
            L[0]  -= len
            L[-1] += 1
        elif speed in L:
            L[speed] += len
        else:
            L[speed] = len
    total = wakeupEnergy * L[-1] + groundEnergy * L[0]
    for s in L:
        if s>0:
            total += L[s] * s**alpha
    res =  "Energy cost = %g [%dL + %gg" \
        %(total,L[-1],L[0])
    for s in L:
        if s>0:
            res += "+ %g(%s)&#170;"%(L[s],s)
    return res+"]"
    
# ------------------------------------------------ main program

if (len(argv)!=2):
    print 'Usage: minEnergyAgreeable.py "<list of release time/deadline/workload>"'
    exit(0)

readInstance(argv[1])
S = solve()
schedule2svg(cost(S), S)