""" usage
from algs import *
print vef((13,7),((0,1),(1,0)), '', 10)
path_7_13 = cwp([0,1,1,6])[::-1]
print path_7_13
sbr(path_7_13)
print sbp([0,1,1,6])
"""

def slope(basis):
	dx = (basis[0][0] - basis[1][0])
	dy = (basis[0][1] - basis[1][1])
	return 1.*dy/dx

def quotient(alpha):
	return 1.*alpha[0]/alpha[1]

""" add two vectors componentwise
this could be generalized, but no need at the moment
"""
def add_vec(alpha, beta):
	return (alpha[0] + beta[0], alpha[1] + beta[1])

""" compute a mediant of two rationals represented as tuples
This definition is redundant, but is useful semantically.
"""
def mediant_tuple(alpha, beta):
	return add_vec(alpha, beta)

""" reverse a string
This shouldn't even be a definition,
I should remember to use the slice notation in place,
but I constantly forget so I'm writing it here.
"""
def str_rev(string):
	return string[::-1]

""" stern-brocot path associated to cf
computes the path to the rational represented by the continued fraction cf
in the stern-brocot tree where cf = [a_0, ... a_m], a_m > 1
"""
def sbp(cf):
	parity = len(cf) % 2 == 0
	steps = ['L', 'R']
	path = ''
	for i in cf:
		multiple = i
		path = path + multiple*steps[(int)(parity)]
		parity = not parity
	return path[0:-1]

""" calkin-wilf path associated to cf
computes the path to the rational represented by the continued fraction cf
in the calkin-wilf tree where cf = [a_0, ... a_m], a_m > 1
as it turns out, it is the reverse of the stern-brocot path
"""
def cwp(cf):
	path = sbp(cf)[::-1]
	return path

""" compute the rational in the stern-brocot tree associated to path
returns a tuple representing the fraction at the corresponding node
currently the paths should have R for 'right' and something else for 'left'
"""
def sbr(path):
	ancestors = [(0,1),(1,1),(1,0)]
	for i in path:
		direction = (int)(i == 'R')
		ancestor_low = ancestors[direction]
		ancestor_high = ancestors[direction+1]
		tng = mediant_tuple(ancestor_low, ancestor_high)
		ancestors = [ancestor_low, tng, ancestor_high]
	return tng

""" a form of the euclidean algorithm in a vector space
alpha is a tuple representing a fraction
"""
def vef(alpha, basis=((0,1),(1,0)), path='', depth=None):
	if(depth is not None):
		depth = depth - 1
		if(depth <= 0):
			return "depth exceeded"
	steps = ['L', 'R']
	basis_sum = add_vec(basis[0],basis[1])
	qa = quotient(alpha)
	try:
		qb = quotient(basis_sum)
	except ZeroDivisionError:
		qb = 0
	if(qa == qb):
		return path
	step = qb > qa
	path = path + steps[step]
	if(step):
		return vef(alpha, (basis[0], basis_sum), path, depth)
	return vef(alpha, (basis_sum, basis[1]), path, depth)