/*
 * rat.c -- exact rational arithmetic.
 *
 * Normalization: gcd(num, den) = 1, den > 0, zero represented as 0/1.
 * Every arithmetic op normalizes its result.
 */
#include "rat.h"

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

static int64_t i64_abs(int64_t x) { return x < 0 ? -x : x; }

static int64_t gcd64(int64_t a, int64_t b) {
    a = i64_abs(a); b = i64_abs(b);
    while (b) { int64_t r = a % b; a = b; b = r; }
    return a ? a : 1;
}

static void normalize(int64_t *n, int64_t *d) {
    assert(*d != 0);
    if (*d < 0) { *n = -*n; *d = -*d; }
    if (*n == 0) { *d = 1; return; }
    int64_t g = gcd64(*n, *d);
    *n /= g;
    *d /= g;
}

Rat rat_int(int64_t k) { Rat r = {k, 1}; return r; }

Rat rat_make(int64_t n, int64_t d) {
    normalize(&n, &d);
    Rat r = {n, d};
    return r;
}

Rat rat_neg(Rat a) {
    Rat r = { -a.n, a.d };
    return r;
}

Rat rat_add(Rat a, Rat b) {
    /* a.n/a.d + b.n/b.d = (a.n*b.d + b.n*a.d) / (a.d*b.d) */
    int64_t g = gcd64(a.d, b.d);
    int64_t ad = a.d / g, bd = b.d / g;
    int64_t n  = a.n * bd + b.n * ad;
    int64_t d  = ad * b.d;   /* = (a.d / g) * b.d = a.d * b.d / g */
    return rat_make(n, d);
}

Rat rat_sub(Rat a, Rat b) { return rat_add(a, rat_neg(b)); }

Rat rat_mul(Rat a, Rat b) {
    /* Cross-reduce before multiplying. */
    int64_t g1 = gcd64(a.n, b.d);
    int64_t g2 = gcd64(b.n, a.d);
    int64_t n  = (a.n / g1) * (b.n / g2);
    int64_t d  = (a.d / g2) * (b.d / g1);
    return rat_make(n, d);
}

Rat rat_div(Rat a, Rat b) {
    assert(b.n != 0);
    /* a.n/a.d  /  b.n/b.d = (a.n*b.d) / (a.d*b.n) */
    int64_t bn = b.n, bd = b.d;
    if (bn < 0) { bn = -bn; bd = -bd; }
    Rat inv = { bd, bn };
    return rat_mul(a, inv);
}

int rat_cmp(Rat a, Rat b) {
    /* sign(a.n*b.d - b.n*a.d), watch overflow.
     * For the tutorial scale we accept the i64*i64 risk. */
    int64_t lhs = a.n * b.d;
    int64_t rhs = b.n * a.d;
    if (lhs < rhs) return -1;
    if (lhs > rhs) return  1;
    return 0;
}

int rat_sgn(Rat a) {
    if (a.n < 0) return -1;
    if (a.n > 0) return  1;
    return 0;
}

int rat_is_zero(Rat a) { return a.n == 0; }
int rat_eq     (Rat a, Rat b) { return a.n == b.n && a.d == b.d; }

int rat_print(char *buf, int sz, Rat a) {
    if (a.d == 1) return snprintf(buf, (size_t)sz, "%lld",
                                  (long long)a.n);
    return snprintf(buf, (size_t)sz, "%lld/%lld",
                    (long long)a.n, (long long)a.d);
}

/* --- Drat --- */

const Drat DRAT_ZERO = { {0,1}, {0,1} };

Drat drat_rat (Rat q)            { Drat r = { q, rat_int(0) }; return r; }
Drat drat_int (int64_t k)        { Drat r = { rat_int(k), rat_int(0) }; return r; }
Drat drat_make(Rat q, Rat d)     { Drat r = { q, d }; return r; }
Drat drat_neg (Drat a)           { Drat r = { rat_neg(a.q), rat_neg(a.d) }; return r; }

Drat drat_add(Drat a, Drat b) {
    Drat r = { rat_add(a.q, b.q), rat_add(a.d, b.d) };
    return r;
}
Drat drat_sub(Drat a, Drat b) {
    Drat r = { rat_sub(a.q, b.q), rat_sub(a.d, b.d) };
    return r;
}
Drat drat_mul_rat(Drat a, Rat k) {
    Drat r = { rat_mul(a.q, k), rat_mul(a.d, k) };
    return r;
}

int drat_cmp(Drat a, Drat b) {
    int c = rat_cmp(a.q, b.q);
    if (c) return c;
    return rat_cmp(a.d, b.d);
}

int drat_is_zero(Drat a) { return rat_is_zero(a.q) && rat_is_zero(a.d); }

int drat_print(char *buf, int sz, Drat a) {
    int w = rat_print(buf, sz, a.q);
    if (!rat_is_zero(a.d)) {
        if (w < sz) {
            int s = rat_sgn(a.d);
            w += snprintf(buf + w, (size_t)(sz - w), " %s ",
                          s > 0 ? "+" : "-");
        }
        if (w < sz) {
            Rat ad = a.d;
            if (ad.n < 0) ad.n = -ad.n;
            if (!(ad.n == 1 && ad.d == 1)) {
                w += rat_print(buf + w, sz - w, ad);
                if (w < sz) w += snprintf(buf + w, (size_t)(sz - w), "*");
            }
            w += snprintf(buf + w, (size_t)(sz - w), "d");
        }
    }
    return w;
}
