"""
Invoke as, e.g.,
    best_fraction(Fraction("0.001"), Fraction("0.0005"), Fraction("0.0015"))
to get Fraction(1, 1000) as output.
"""

from fractions import Fraction
import math


def best_fraction(target, left, right, left_open=False, right_open=True):
    # Check types of inputs
    if not isinstance(target, Fraction):
        raise ValueError(f"target value ({target}) must be a Fraction")
    if not isinstance(left, Fraction):
        raise ValueError(f"left value ({left}) must be a Fraction")
    if not isinstance(right, Fraction):
        raise ValueError(f"right value ({right}) must be a Fraction")
    if not target > left:
        raise ValueError(
            f"target value ({target}) must be greater than left value ({left})"
        )
    if not target < right:
        raise ValueError(
            f"target value ({target}) must be less than right value ({right})"
        )
    if not isinstance(left_open, bool):
        raise ValueError(f"left_open ({left_open}) must be True or False")
    if not isinstance(right_open, bool):
        raise ValueError(f"right_open ({right_open}) must be True or False")

    # Define useful helper function
    def update_fraction(endpoint, endpoint_plus, endpoint_floor):
        endpoint = (
            1 / (endpoint - endpoint_floor) if endpoint != endpoint_floor else math.inf
        )
        endpoint_plus = not endpoint_plus
        endpoint_floor = (
            math.inf
            if endpoint == math.inf
            else math.floor(endpoint)
            if endpoint_plus
            else math.ceil(endpoint) - 1
        )
        return (endpoint, endpoint_plus, endpoint_floor)

    # Is each endpoint effectively plus epsilon (as opposed to minus epsilon)?
    left_plus = left_open
    right_plus = not right_open

    # To get to the next iteration of the continued fraction expansion, we need to know
    # the floor of each endpoint.  Note that an exact integer has a "floor" that depends
    # upon whether our value is implicitly +epsilon or -epsilon.
    left_floor = math.floor(left) if left_plus else math.ceil(left) - 1
    right_floor = math.floor(right) if right_plus else math.ceil(right) - 1

    # The start up convergents for a continued fraction expansion
    (prev_numer, prev_denom) = (0, 1)
    (curr_numer, curr_denom) = (1, 0)

    while left_floor == right_floor:
        # For each endpoint, compute one more convergent and retain one previous
        # convergent
        (curr_numer, prev_numer) = (left_floor * curr_numer + prev_numer, curr_numer)
        (curr_denom, prev_denom) = (left_floor * curr_denom + prev_denom, curr_denom)

        # Update the values so that we can compute the next convergents
        (left, left_plus, left_floor) = update_fraction(left, left_plus, left_floor)
        (right, right_plus, right_floor) = update_fraction(
            right, right_plus, right_floor
        )

    # Tentatively, the best fraction is based upon a next "floor" of min(left_floor,
    # right_floor) + 1.
    best_floor = test_floor = min(left_floor, right_floor) + 1
    best_numer = test_numer = best_floor * curr_numer + prev_numer
    best_denom = test_denom = best_floor * curr_denom + prev_denom
    best_difference = test_difference = abs(target - Fraction(best_numer, best_denom))

    # Check whether incrementing the "test_floor" will help, but don't go so far as to
    # leave the initially supplied interval, (right, left).
    while test_floor < max(left_floor, right_floor):
        test_floor += 1
        test_numer += curr_numer
        test_denom += curr_denom
        test_difference = abs(target - Fraction(test_numer, test_denom))
        if test_difference >= best_difference:
            # We've passed the target; it only gets worse from here.
            break
        # This "test_floor" proved better.  Remember it as best.
        (best_floor, best_numer, best_denom, best_difference) = (
            test_floor,
            test_numer,
            test_denom,
            test_difference,
        )

    return Fraction(best_numer, best_denom)