from support.expr_types import *
from functools import cache
from support.canonicalize import *
from src.differentiation import evaluate_diff 
from fractions import Fraction

EPSILON = 10**(-5)
MAX_ITER = 1000

INFINITY = 10**(1000)
ZERO = 10**(-1000)

@cache
def newton(f, x0, var):
    """
    The goal of Newton's method is to find a zero of the provided function f w.r.t. the variable var.
    It works by iteratively making guesses (with an initial guess of x0) until it's close enough to
    a correct answer.

    Some useful functions:
        - abs(x): Takes the absolute value of x
        - coerce_float(x): Converts any number (int, Fraction, Decimal, float) to a float for
                           comparison with other floats.
        - evaluate_diff(expr, var): This is the function you wrote in the previous part!
        - eval_expr(expr, {v1: val1, v2:, val2, ...}): Plugs in val1 for v1, val2 for v2, etc. into expr
                                                       and simplifies as much of expr as possible.

    Algorithm:
        Until we've tried MAX_ITER times...
            Our current estimate is x_0.
            Calculate f(x_0) and f'(x_0).
            If both are at least INFINITY, assume we've failed.
            If f'(x_0) is at most ZERO, assume we've failed.
            Calculate a new estimate, x_1, where x_1 = x_0 - (f(x_0)/f'(x_0))
            If we've converged on a value (x_0 and x_1 are close enough with tolerance EPSILON)...
                If f(x_1) is close enough to 0 with tolerance EPSILON, we've found a zero! Return it!
                Otherwise, assume we've failed.
                
        
    """
    return None