from random import random

# Residual coding function
def RC(X, f):
	return [X[i] - f(i+1) for i in range(0, len(X))];

# Residual encoding function
def RD(X, f):
	return [X[i] + f(i+1) for i in range(0, len(X))];

# Random polynomial function generator with small coefficients.
# Returns a polynomial function with the degree specified as parameter.
def generate_poly_func(degree):
	coef_list = [int(random()*7 + 1) for _ in range(0, degree+1)]
	def ret_func(x):
		return sum([coef_list[i]*(x**i) for i in range(len(coef_list))])
	return (ret_func, coef_list)

# Prints a coefficient list as a polynomial function (assuming coef_list[0] = coef_0, ... coef_list[i] = coef_i)
def print_poly_func(coef_list):
	poly_print = reversed([str(coef_list[i])+'x^'+str(i) for i in range(len(coef_list))])
	return ((' + ').join(list(poly_print)))

# Predictive coding
def PC(X):
	return [X[i] - (X[i-2]+X[i-1])/2 for i in range(len(X))]

# Predictive decoding
def PD(Y):
	ret = Y
	ret[-1] = 0
	ret[-2] = 0
	for i in range(1, len(Y)-2):
		ret[i] += (ret[i-2]+ret[i-1])/2
	return ret

# Epsilon checking (simple equality test can give wrong results due to floating point precision)
def eps_ok(x, y, epsilon):
	return not [x[i] for i in range(len(x)) if (x[i]-y[i]) > epsilon]

def main():
	def sample_f(x): return x*x - x + 41
	sample_list = [41, 43, 46, 52, 62, 71, 82, 98, 115, 131]
	encoded_list = RC(sample_list, sample_f)
	print ('Residual coding for', sample_list,':',encoded_list)
	print ('Is the decoding of the encoded list equal to the original one ?', RD(encoded_list, sample_f) == sample_list)
	print('-'*20)
	print
	# Random tests. While the functions computed may not be useful to
	# compress the numbers, they can be used to check if coding and decoding
	# works properly. 
	print ('Testing RC and RD with random lists and functions...')
	print ('-'*20)
	for i in range(0, 6):
		print ('Testing with degree',i,'...')
		for j in range(5, 200):
			random_list = [int(random()*133.7) for _ in range(0, j)]
			random_func, coef_list = generate_poly_func(i)
			encoded_random_list = RC(random_list, random_func)
			# Only the first list is displayed and only for some degrees
			# in order to avoid to print too much output.
			if j == 5 and i>0 and i<3:
				print('List of random elements:', random_list)
				print('Random polynomial function:',print_poly_func(coef_list))
				print('p(1..|X|) = ', [random_func(x+1) for x in range(len(random_list))])
				print('RC(X) =', encoded_random_list)
			if RD(encoded_random_list, random_func) != random_list:
				print ('ERROR: RD(RC(X,f)) != X, where:')
				print ('X = ', random_list)
				print ('f(x) = '), print_poly_func(coef_list)
				raise
			if j == 5 and i>0 and i<3:
				print('RD(RC(X,f), f) =', RD(RC(random_list, random_func),random_func))
		print ('-'*20)
	print ('Random tests for RC and RD passed')
	print ('-'*20)
	print ('-'*20)
	print ('Predictive coding example:')
	pc_example_list = [1.0,2.0,3.0,4.0,5.0,0.0,0.0]
	print ('List L:', pc_example_list)
	print ('PC(L):', PC(pc_example_list))
	print ('Is PD(PC(L)) = L?', eps_ok(PD(PC(pc_example_list)), pc_example_list, 1e-6))
	print ('-'*20)
	print ('Testing predictive coding functions with random lists...')
	# Random tests
	for i in range(0, 1000):
		random_list = []
		for j in range(0, i): random_list.append(random())
		random_list += [0.0, 0.0]
		encoded_list = PC(random_list)
		if not eps_ok(PD(PC(random_list)), random_list, 1e-9):
			print ('ERROR: PD(PC(X)) != X, with X =', random_list)
			print ('PD(PC(X)):0', PD(PC(random_list))) 
			raise
	print ('Random tests for PD and PC passed')


if __name__ == "__main__":
	main()