# Principled Programming / Tim Teitelbaum / Chapter 18.
from rational import Rational
import time
class EnumerateRationals:
    """Unbounded enumeration of positive rationals."""
    @classmethod
    def main(cls) -> None:
        """Output reduced fractions, i.e., positive rationals, without repetitions."""
        d = 0
        startTime = time.time()
        count = 0  # number of rationals so far.
        while count < 100000:
            r = d
            for c in range(0, d + 1):
                if gcd(r + 1, c + 1)==1:
                    z: Rational = Rational(r + 1, c + 1)
                    # print(z)
                    count += 1
                    if (count % 10000) == 0:
                        print(time.time() - startTime)
                r -= 1
            d += 1

def gcd(x:int, y:int) -> int:
    """Given x>0 and y>0, return the greatest common divisor of x and y."""
    while x != y:
        if x > y:
            x = x - y
        else:
            y = y - x
    return x

EnumerateRationals.main()