## A324
## David Martin Alaminos

from math import log2, floor
import random


'''
1.
Define a funtion Y = RC(X,f) that implements residual coding of the
numerical list X using the function f (defined for non-negative
integers) as a model. Check it with the example on page T5.9. Define
also a function X = RD(Y,f) that implements the corresponding decoding.
'''

def RC(X,f):
    M = list(map(f, range(1,len(X)+1))) #model values
    return [(x-m) for (x,m) in zip(X,M)]

def RD(Y,f):
    M = list(map(f, range(1,len(Y)+1)))
    return [m+y for (y,m) in zip(Y,M)]

#T5.9 example
f = lambda n: n**2 - n + 41
X = [41,43,46,52,62,71,82,98,115,131]
Y = RC(X,f)

assert(X == RD(Y,f))


#A rough estimation of the compression ratio?
def nbits(n): return 1 + floor(log2(max(1,n)))
bitsX = sum([nbits(x) for x in X])
bitsY = sum([nbits(y) for y in Y])
print("Residual coding compression ratio:",bitsX/bitsY)



'''
2.
Define similar functions Y = PC(X) and X = PD(Y) (predictive coding and
decoding), where yj = xj-(xj-2+xj-1)/2, with the convention that x-2=x-1=0.
Test them with some suitable examples.
'''

def PC(X):
    return [X[i] - (X[i-2]+X[i-1])/2  for i in range(len(X)) if i > 1]

def PD(Y):
    X = [0,0]
    for i in range(len(Y)): X += [Y[i] + (X[i] + X[i+1])/2]
    return X


#Test 1: random integers
X = [0,0]+[random.randint(0,1000) for _ in range(1000)]
Y = PC(X)

assert(X == PD(Y))


#Test 2: T5.9 example revisited
X = [0,0,41,43,46,52,62,71,82,98,115,131]
Y = PC(X)

assert(X == PD(Y))

bitsX = sum([nbits(x) for x in X])
bitsY = sum([nbits(y) for y in Y])
print("Predictive coding compression ratio:",bitsX/bitsY) #probably not a fair comparison against RC