"""This module provides functionality for dealing with continued fractions."""

from math import sqrt
from fractions import gcd, Fraction


def cont_frac_sqrt(n):
    """Calculate the continued fraction representation of the square root of n.
    Returns a 2-tuple containing a tuple of the non-repeating parts and a tuple
    of the repeating parts. Assumes that n is not square.
    """
    def r(a, b, c, d, reps):
        i = (a * sqrt(b) + c) / d
        i = int(i) #i holds the integer part of the value
        newRep = (i, a, c, d)
        if newRep in reps:
            index = reps.index(newRep)
            return [[x[0] for x in reps[:index]], [x[0] for x in reps[index:]]]
        else:
            reps.append(newRep)
            a, b, c, d = a*d, b, d*d*i - c*d, a*a*b - c*c + 2*c*d*i - d*d*i*i
            g = gcd(gcd(a, c), d)
            a, c, d = a // g, c // g, d // g
            return r(a, b, c, d, reps)
    return r(1, n, 0, 1, [])


def evaluate(quotients):
    """Evaluates a continued fraction given a list of integer quotients. The
    result returned is an instance of the Fraction class.
    """
    f = Fraction(0)
    for a in reversed(quotients):
        f = 1 / (a + f)
    return 1 / f
    
