'''
Created on June 27, 2011
Modifedi on Aug 2
@author: Dilum Bandara
@version: 0.21
@license: GNU
@copyright: Copyright(c) 2011, Dilum Bandara
'''

#Solve optimization problem for co-operative/global caching under fixed cache capacity

import math
import sys

N = 4000 #Number of nodes
K = 30000 #No of keys
h_ave = 6.82 #4800 - 6.88, 2400 - 6.46, 6.84 - 4000, 1200 - 5.94, 1000 - 5.85
c_n = 10 #Cache capacity per node
alpha = [0.5, 0.6, 0.7, 0.8, 0.9, 1.0, 1.1, 1.2, 1.3, 1.4, 1.5] #Range of Zipf's parameters
#alpha = [0.6, 0.8, 1.0, 1.2] #Range of Zipf's parameters
#alpha = [0.7, 0.8, 0.9, 1.0, 1.1, 1.2] #Range of Zipf's parameters
rMin = 0.5 # let r determine c_k = (f_k^r) * BUDGET
rInc = 0.05
rNum = 20
fOut = 'optimized_result.txt'

BUDGET = c_n * N #Total cache budget
 
def zipfs(alpha, k):
    '''
    Calcutae Zipf's distribution
    @param alpha: Zipf's parameter
    @param k: Number of keys
    @return: List of key frequencies 
    '''
    H = 0.0
    result = []
    for i in range(1, k + 1): 
        H += 1/math.pow(i, alpha)
    for i in range(1, k + 1):
        result.append((1/math.pow(i, alpha))/H)
    return result
 
def mixKeys(input):
    '''
    Mix keys from different communities
    @param input: list for each community that contains [alpha, numKeys, numQueries]
    '''
    results = []
    for i in range(len(input)): #Find contribution from each community & key
        tmp = zipfs(input[i][0], input[i][1])
        for j in range(len(tmp)):
            results.append(tmp[j] * input[i][2])
    total = sum(results)
    for i in range(len(results)):
        results[i] = results[i]/total
    return results

def funG(n, c_k):
    '''
    g() Cacluate number of queries served if c_k cache capacity is allocted to k-th key
    @param n: Number of nodes
    @param c_k: Cache capacity for node key k 
    @return: Function value which is sum (1 to c_k) (2^(log2(N) - 1 - floor(log2(i))))
    '''
    if c_k == 0: return 0.0
    result = 0.0
    for i in range(1, c_k + 1):
        power = math.log(n, 2) - 1 - math.floor(math.log(i, 2))
        result += math.pow(2, power)
    return result

def funGTmp(n, c_k):
    if c_k == 0: return 1/0.6054
    result = 0.0
    for i in range(1, c_k + 1):
        result += 1/(0.6054 * i + 38340) 
    return result

def obj(f_k, r, n, b):
    '''
    Function vale of objective function - this is the function to minimize
    @param f_k: List of frequencies
    @param r: r value to use
    @param n: Number of nodes
    @param b: Cache budget
    @return: Function value which is sum (1 to K) (f_k funG(c_k))
    '''
    result = 0.0
    total_c_k = 0.0
    for i in range(len(f_k)): #For each key
        c_k = int(round(pow(f_k[i], r) * b))
        if c_k > n - 1: c_k = n - 1 # Cap number of caching entries to (N - 1) 
        total_c_k += c_k
        if total_c_k > b: c_k = c_k - int(total_c_k - b) #Budget exceeded
        result += f_k[i] * funG(n, c_k)
        if total_c_k >= b: return result
    return result

def objOpt(f_k, n, b, a):
    '''
    Optimum value of objective function
    @param f_k: List of frequencies/popularities
    @param n: Number of nodes
    @param b: Cache Budget
    @param a: Determine whether discrete funG() or continuous version is used. -1 - use
    discrete function g(c_k), else addpt based on a  
    @return: Function value
    '''
    result = 0.0
    total_c_k = 0.0
    limit_f_k = 0.0
    limit_c_k = 0.0

    for i in range(len(f_k)): #For each key
        #Use either integer version or natural number
        #c_k = int(round((f_k[i] * (b - limit_c_k))/(1 - limit_f_k)))
        #if a == -1: c_k = int(math.ceil((f_k[i] * (b - limit_c_k))/(1 - limit_f_k)))
        if a == -1: c_k = int(round((f_k[i] * (b - limit_c_k))/(1 - limit_f_k)))
        else : c_k = f_k[i] * (b - limit_c_k)/(1 - limit_f_k)
        if c_k >= n - 1: 
            c_k = n - 1 # Cap number of caching entries to (N - 1)
            limit_f_k += f_k[i] #Sum popularity
            limit_c_k += c_k #Sum popularity
        if c_k <= 0: break
        total_c_k += c_k
        if total_c_k > b: 
            if a == -1: c_k = c_k - int(total_c_k - b)
            else : c_k = c_k - total_c_k - b
            if c_k < 0: break
        if a == -1: result += f_k[i] * funG(n, c_k)
        #else: result += f_k[i] * math.log(c_k)
        else:
           if c_k >= 1: result += f_k[i] * math.log(c_k)
        #else: result += f_k[i] * funGTmp(n, c_k)
            #if a == 0 and c_k > 0: result += f_k[i] * math.log(c_k)
            #elif a > 0 and c_k > 1: result += f_k[i] * math.log(c_k)
        if total_c_k >= b: break
    if a == -1: return result
    #else: return 0.5 * result
    #else: return 0.75 * (0.5772156649 + result)
    else: return math.pow(2, a - 1) * (0.5772156649 + result)

def PopCache(f_k, n, b, k):
    '''
    Optimum value from PopCache algorithm
    @param f_k: List of frequencies/popularities
    @param n: Number of nodes
    @param b: Cache budget
    @param k: branching factor 
    @return: Function value
    '''
    total = 0.0
    for i in f_k: total += i * math.log(i, k)
    return h_ave - total - math.log(b, k)
    #return math.log(n, 2) - total - math.log(b, k)

#------------- Test code -----------------
'''
result = zipfs(1.0, 10)
print result[0], 0.3414, result[1], 0.1707
result = zipfs(0.8, 5)
print result[0], 0.3852, result[1], 0.2212
print funG(32, 1), 16
print funG(32, 2), 24
print funG(32, 3), 32
print funG(32, 4), 36
print funG(32, 8), 50
print obj([0.3414, 0.1707], 1.0, 32, 32), 25.2648 
print obj([0.3852, 0.2212], 1.0, 32, 32), 32.0744
'''
'''
result = [0.25, 0.2, 0.15, 0.1, 0.1, 0.05, 0.05, 0.05, 0.05]
print objOpt(result, 7, 20)
print '5, 4, 3, 2, 2, 1, 1, 1, 1'
result = [0.3, 0.2, 0.15, 0.1, 0.05, 0.05, 0.05, 0.05, 0.05]
print objOpt(result, 7, 20)
print '6, 4, 3, 2, 1, 1, 1, 1, 1'
result = [0.3, 0.25, 0.10, 0.1, 0.05, 0.05, 0.05, 0.05, 0.05]
print objOpt(result, 5, 20)
print '4, 4, 3, 3, 1, 1, 1, 1, 1'
'''
pValue = []
for i in range(len(alpha)): #For each Zipf's parameter
    f_k = zipfs(alpha[i], K)
    pValue.append([alpha[i], h_ave - objOpt(f_k, N, BUDGET, -1)/N])
    pValue.append([alpha[i], h_ave - objOpt(f_k, N, BUDGET, 0)])
    #pValue.append([alpha[i], h_ave - objOpt(f_k, N, BUDGET, 0.5)])
    pValue.append([alpha[i], h_ave - objOpt(f_k, N, BUDGET, 1.0)])    
    pValue.append([alpha[i], h_ave - objOpt(f_k, N, BUDGET, 0.5849625)])
    #pValue.append([alpha[i], h_ave - objOpt(f_k, N, BUDGET, 0.23458)])
#------ Use f_k^r * budget ------
'''
for i in range(len(alpha)): #For each Zipf's parameter
    f_k = zipfs(alpha[i], K)
    for j in range(rNum): #For each r
        r = rMin + j * rInc
        p = obj(f_k, r, N, BUDGET)
        pValue.append([alpha[i], r, p, h_ave - p/N])
'''

#----------- Multiple communities -------
'''
input = []
input.append([0.85, 40000, 137197])
input.append([0.95, 30000, 133297])
input.append([1.1, 30000, 144547])
input.append([0.5, 40000, 262050])
input.append([0.8, 40000, 259306])
input.append([0.8, 40000, 265739])
input.append([1.0, 50000, 283201])
input.append([0.9, 50000, 262511])
input.append([0.9, 50000, 527697])
input.append([0.75, 50000, 989840])
'''
'''
f_k = mixKeys(input) 
f_k.sort(reverse=True)
print f_k[0], f_k[1], f_k[2]
'''

#print h_ave - P(f_k, 1.0, N, BUDGET)/N
#print h_ave - objOpt(f_k, N, BUDGET, -1)/N, h_ave - objOpt(f_k, N, budget, 0)/N, h_ave - objOpt(f_k, N, budget, 1)/N
'''
total_queries = 0
for i in range(len(input)): total_queries += input[i][2]
for i in range(len(input)):
    f_k = zipfs(input[i][0], input[i][1])
    #pValue.append([input[i][0], h_ave - P(f_k, 1.0, N, BUDGET)/N])
    #print  5.94 - objOpt(f_k, 1200, 1200 * 20, -1)/1200
    #print  5.94 - objOpt(f_k, 1200, 1200 * 20, 0)/1200
    #print  5.94 - objOpt(f_k, 1200, 1200 * 20, 0.5)/1200
    #print  5.94 - objOpt(f_k, 1200, 1200 * 20, 1.0)/1200
'''
'''
    if i == 8:
        pValue.append([input[i][0], 6.46 - objOpt(f_k, 2400, 2400 * 20, 0.5)/2400])
    elif i == 9:
        pValue.append([input[i][0], 6.88 - objOpt(f_k, 4800, 4800 * 20, 0.5)/4800])
    else:
        pValue.append([input[i][0], h_ave - objOpt(f_k, N, BUDGET, 0.5)/N])
'''
'''
    pValue.append([input[i][0], h_ave - objOpt(f_k, N, BUDGET, 0.5)/N])
    #print h_ave - objOpt(f_k, N, BUDGET, -1)/N
    #pValue.append([input[i][0], h_ave - objOpt(f_k, N, BUDGET, -1)/N])
    #pValue.append([input[i][0], h_ave - objOpt(f_k, N, BUDGET, -1)/N])
    #pValue.append([input[i][0], h_ave - objOpt(f_k, N, BUDGET, 1.0)/N])    
for i in range(len(pValue)): print pValue[i][1]

tmp_h = 0.0
for i in range(len(pValue)):
    tmp_h += pValue[i][1] * input[i][2] 
print tmp_h/total_queries
'''


fdOut = open(fOut, 'w')
for i in range(len(pValue)/4):
    fdOut.write(str(pValue[i * 4][0]) + '\t' + str(pValue[i * 4][1])  + '\t' + str(pValue[i * 4 + 1][1])\
    + '\t' + str(pValue[i*4 + 2][1])  + '\t' + str(pValue[i* 4 + 3][1]) + '\n')
#for i in range(len(pValue)):
#    fdOut.write(str(pValue[i][0]) + '\t' + str(pValue[i][1]) + '\n')
'''
for i in range(len(pValue)):
    fdOut.write(str(pValue[i][0]) + '\t' + str(pValue[i][1]) + '\t' + str(pValue[i][2]) \
                   + '\t' + str(pValue[i][3]) + '\n')
'''
fdOut.close()
