# Copyright (c) 2012 Guillermo Romero (Gato) <gato@felimage.com>
# Permission to use this source code in any way and for any purpose is
# hereby granted, provided that the above copyright notice and this
# permission notice appear in all copies.
# This source code is distributed without any warranty whatsoever.

import math

def cfract(n):
	den = 1

	# use euclid's algorithm to get the continued fraction
	while den:
		m = math.floor(n / den)

		yield m

		den, n = n - m * den, den

# get successive rational approximations to n (convergents)
def rationalApprox(n):
	h1,h2 = 1,0
	k1,k2 = 0,1

	for cf in cfract(n):
		h = cf * h1 + h2
		k = cf * k1 + k2

		if h != 0:
			yield h,k
	
		h1,h2 = h,h1
		k1,k2 = k,k1


def GetScaling(F, X, q):
	if F <= 0:
		raise Exception("Invalid value for scaling factor: %s"%F)

	n = 1
	E = 0

	B = X * q

	for num,den in rationalApprox(F):
		d = math.ceil(float(X) / float(den))

		scaled_den = den * d

		if scaled_den <= B or scaled_den < E or E == 0:
			S, E = num*d, scaled_den

		if den > B:
			break

	return int(S),int(E)

def GetCropping(X, F):
	return int(math.ceil( X * F ))


if __name__ == "__main__":
	test = ["0.01", "5.12135", "math.pi", "math.e", "1/10.0", "1/11.0","2/7.0", "4/3.0", "math.sqrt(2)"]

	x = 123

	print "Image width or height: %s"%x
	print
	print "Resize to:"
	
	print "       value    embed size  resize to    crop to  relative error"
	for t in test:
		f = eval(t)

		s,e = GetScaling(f, x, 2.0)

		c = GetCropping(x, f)

		f_prime = float(s)/float(e)

		rel_error = 100.0 * (f_prime - f) / f

		print "%12s %13s %10s %10s  %g%%"%(t, e,s,c, rel_error)