import numpy as np
from scipy.optimize import minimize 
import scipy 

m = 10 #m parameter from paper
comp_ratio = 0.883 #The competitive ratio we claim.

def lamb(j, cs):
    return 1/m * sum(cs[i] for i in range(1, j))

    
def fj(j, cs, l):
    part1 = 1-np.exp(-lamb(j, cs))
    part2 = 0
    for k in range(j, m+1):
        term = np.exp(- lamb(k, cs))
        term *= np.exp(-1*(m+1)/m*cs[k])
        inner = (m*np.exp(cs[k])*l*(np.exp(cs[k]/m)-1)*(2*cs[k]-l) 
                    + cs[k]*l*np.exp(k*cs[k]/m)*(l-cs[k]))
        term *= inner 
        term /= (m*cs[k]**2)
        part2 += term
    return part1+part2


def verify_competitive_ratio(cs):
    for i in range(1, len(cs)):
        if cs[i]<cs[i-1]:
            raise Exception("cs should be sorted in ascending order")
    
    defeciency = 1 # This is the min value of f_j(c1, ..., cm, \ell') - comp_ratio*(1-e^(-\ell'))
                    #This needs to be >=0 by the end of execution so that the bound we claim
                    #Is truthful.
    
    defeciency = min(defeciency, 1-np.exp(-1/m * float(sum(cs))) - comp_ratio)
    for j in range(1, m+1): 
        ell_bounds = [(cs[j-1],cs[j])]
        
        res = scipy.optimize.shgo(lambda l: fj(j, cs, l[0]) - comp_ratio*(1-np.exp(-l[0])), 
                                  iters=10,
                       bounds=ell_bounds, options={'disp':False, 'f_tol':1e-9})
        
        """As a sanity check, make sure res.fun <= some values in the middle to make sure minimization worked"""
        for xx in np.linspace(ell_bounds[0][0], ell_bounds[0][1], 10000):
            assert res.fun <= fj(j, cs, xx) - comp_ratio*(1-np.exp(-xx)), (j, ell_bounds, xx, res)
        """End of sanity check"""
        defeciency = min(defeciency, res.fun)
    
    if defeciency>=0:
        print(f"Claimed bound of {comp_ratio} is True")
    else:
        print(f"Claimed bound of {comp_ratio} is False")
    
    
cs = [0., 0.35598315, 0.56202538, 0.86407969, 1.22558122, 1.65459166,
       2.14361195, 2.5868228 , 3.07922161, 4.0722262 , 5.21637928]

verify_competitive_ratio(cs)