"""Emulation of the Perl values used by the original explorer.

The original program was written in Perl with the CPAN module
Math::Fraction (v.53b).  Its printed output depends on details of how
Perl and Math::Fraction represent numbers: a fraction prints as "0/1" or
"3/1" unless the program strips the "/1", decimals typed by the user
are kept as strings (".75"), a decimal such as .33 is read by
Math::Fraction as the repeating decimal 1/3, and mixing a fraction
with a decimal can give an unreduced fraction such as "25/100".

To reproduce the output faithfully this module models a Perl scalar
as one of

  * ``None``               -- undef
  * ``int`` / ``float``    -- a Perl number (IV / NV)
  * ``str``                -- a Perl string
  * :class:`PFrac`         -- a Math::Fraction object

and ports the parts of Math::Fraction the explorer uses (construction,
arithmetic, comparison, stringification, the decimal -> fraction
conversion).  All arithmetic on fractions is exact (Python integers).

One deliberate difference: Math::Fraction's ``<=>`` ignores Perl's
"swapped operands" flag, so ``1 <=> frac(1,2)`` has the wrong sign.
That made some sorts in the Perl program depend on the order of
comparisons (and on Perl's random hash order).  Here comparisons are
always mathematically correct.
"""

import math
import re

__all__ = [
    "PFrac", "frac", "pstr", "pnum", "padd", "psub", "pmul", "pdiv",
    "pneg", "pabs", "pcmp", "peq", "plt", "ple", "pgt", "pge", "pint",
    "fix_str", "is_frac",
]

# ----------------------------------------------------------------------
# Plain Perl numbers and strings
# ----------------------------------------------------------------------

_NUM_PREFIX = re.compile(
    r"^\s*([+-]?)((?:\d+\.?\d*|\.\d+)(?:[eE][+-]?\d+)?)")


def is_frac(x):
    return isinstance(x, PFrac)


def fmt_nv(f):
    """Perl's stringification of a floating point number (%.15g)."""
    if f != f:
        return "NaN"
    if f in (math.inf, -math.inf):
        return "Inf" if f > 0 else "-Inf"
    if f == 0:
        return "0"
    s = "%.15g" % f
    return s


def pstr(x):
    """Perl stringification of a scalar."""
    if x is None:
        return ""
    if isinstance(x, bool):
        return "1" if x else ""
    if isinstance(x, int):
        return str(x)
    if isinstance(x, float):
        return fmt_nv(x)
    if isinstance(x, PFrac):
        return x.string()
    return x


def str_to_num(s):
    """Perl numification of a string: the longest numeric prefix."""
    m = _NUM_PREFIX.match(s)
    if not m:
        t = s.strip().lower()
        for word, val in (("inf", math.inf), ("nan", math.nan)):
            if t.lstrip("+-").startswith(word):
                return -val if t.startswith("-") else val
        return 0
    sign, body = m.group(1), m.group(2)
    if "." not in body and "e" not in body and "E" not in body:
        v = int(body)
        return -v if sign == "-" else v
    v = float(body)
    return -v if sign == "-" else v


def pnum(x):
    """Perl numification (a Math::Fraction numifies to num/den)."""
    if x is None:
        return 0
    if isinstance(x, bool):
        return 1 if x else 0
    if isinstance(x, (int, float)):
        return x
    if isinstance(x, PFrac):
        return x.decimal()
    return str_to_num(x)


def _norm(v):
    """Keep a Perl number an IV when it is an exact integer."""
    return v


def n_add(a, b):
    if isinstance(a, int) and isinstance(b, int):
        return a + b
    return float(a) + float(b)


def n_sub(a, b):
    if isinstance(a, int) and isinstance(b, int):
        return a - b
    return float(a) - float(b)


def n_mul(a, b):
    if isinstance(a, int) and isinstance(b, int):
        return a * b
    return float(a) * float(b)


def n_div(a, b):
    if b == 0:
        raise ZeroDivisionError("Illegal division by zero")
    if isinstance(a, int) and isinstance(b, int) and a % b == 0:
        return a // b
    return float(a) / float(b)


def n_mod(a, b):
    """Perl's integer modulus (operands truncated to integers)."""
    a, b = int(a), int(b)
    if b == 0:
        raise ZeroDivisionError("Illegal modulus zero")
    return a % b


def n_pow(a, b):
    if isinstance(a, int) and isinstance(b, int) and b >= 0:
        return a ** b
    return float(a) ** float(b)


def pint(x):
    """Perl int(): truncate towards zero."""
    v = pnum(x)
    if isinstance(v, int):
        return v
    if v != v or v in (math.inf, -math.inf):
        return v
    return int(v)


# ----------------------------------------------------------------------
# Math::Fraction
# ----------------------------------------------------------------------

OUTFORMAT, REDUCE, SIZE, AUTO, INTERNAL, RED_STATE = range(6)

_TAGS = {
    "NORMAL": (OUTFORMAT, "NORMAL"), "MIXED": (OUTFORMAT, "MIXED"),
    "MIXED_RAW": (OUTFORMAT, "MIXED_RAW"), "RAW": (OUTFORMAT, "RAW"),
    "DEF_MIXED": (OUTFORMAT, None),
    "REDUCE": (REDUCE, "REDUCE"), "NO_REDUCE": (REDUCE, "NO_REDUCE"),
    "DEF_REDUCE": (REDUCE, None),
    "SMALL": (SIZE, "SMALL"), "BIG": (SIZE, "BIG"), "DEF_BIG": (SIZE, None),
    "AUTO": (AUTO, "AUTO"), "NO_AUTO": (AUTO, "NO_AUTO"),
    "DEF_AUTO": (AUTO, None),
    "CONVERTED": (INTERNAL, "CONVERTED"),
    "IS_REDUCED": (RED_STATE, "IS_REDUCED"),
}
_DEFAULT_TAGS = ["NORMAL", "REDUCE", "SMALL", "AUTO"]


def _tags(names):
    ret = [None, None]
    for t in names:
        if t is None or t not in _TAGS:
            continue
        num, value = _TAGS[t]
        while len(ret) <= num:
            ret.append(None)
        ret[num] = value
    return ret


def _tag(item, *reflists):
    for ref in list(reflists) + [_DEFAULT_TAGS]:
        v = ref[item] if item < len(ref) else None
        if v:
            return v
    return None


def _is_decimal(x):
    return re.match(r"^\s*[\+\-0-9eE\.]+\s*$", pstr(x)) is not None


def _fix_num(tags, *vals):
    """Port of Math::Fraction::_fix_num (SMALL/AUTO mode)."""
    while len(tags) <= SIZE:
        tags.append(None)
    auto = _tag(AUTO, tags) == "AUTO"
    tags[SIZE] = _tag(SIZE, tags)
    if auto:
        tags[SIZE] = "SMALL"
    decimal = 0
    out = list(vals)
    for v in out:
        if isinstance(v, PFrac):
            continue
        if "." in pstr(v):          # Perl: /[\.\e\E]/ (the \e is ESC)
            decimal = 1
    if auto:
        out = [pnum(pstr(v)) for v in out]
    return decimal, out


def _de_decimal(f0, f1):
    parts = []
    for v in (f0, f1):
        m = re.search(r"(\d+)\.(\d+)", pstr(v))
        parts.append(len(m.group(2)) if m else 0)
    parts.sort()
    factor = n_pow(10, parts[1])
    return [n_mul(pnum(f0), factor), n_mul(pnum(f1), factor)]


def _gcd(a, b):
    x, y = abs(pnum(a)), abs(pnum(b))
    if y > 1e17:
        return 1
    while y != 0:
        x0 = x
        x, y = y, n_mod(x, y)
        if (x0 > 99999999 or x > 999999999) and \
                n_add(n_mul(pint(n_div(x0, x)), x), y) != x0:
            x = 1
            break
    return x


def _reduce(f0, f1):
    g = _gcd(f0, f1)
    if g == 1:
        return 0, [f0, f1]
    return 1, [n_div(f0, g), n_div(f1, g)]


def _simplify_sign(f0, f1):
    sign = 1
    if pnum(f0):
        sign = n_mul(n_div(f0, abs(f0)), n_div(f1, abs(f1)))
    return [n_mul(sign, abs(f0)), abs(f1)]


class PFrac(object):
    """A Math::Fraction object: numerator, denominator and tags."""

    __slots__ = ("f", "tags")

    def __init__(self, f, tags):
        self.f = f
        self.tags = tags

    # -- construction (Math::Fraction->new) ---------------------------
    @classmethod
    def new(cls, *args):
        vals = []
        tagnames = []
        # Split positional numbers from trailing tag names, as Perl does
        # by position: the caller always passes numbers first.
        nums = list(args)
        a0 = nums[0] if nums else None
        a1 = nums[1] if len(nums) > 1 else None
        if len(nums) >= 2 and _is_decimal(a0) and _is_decimal(a1) \
                and not isinstance(a0, PFrac) and not isinstance(a1, PFrac):
            tags = _tags(nums[2:])
            decimal, fr = _fix_num(tags, a0, a1)
            if decimal:
                fr = _de_decimal(*fr)
            fr = _simplify_sign(*fr)
        elif _is_decimal(a0) and not isinstance(a0, PFrac):
            tags = _tags(nums[1:])
            decimal, (p1,) = _fix_num(tags, a0)
            if not decimal:
                fr = [p1, 1]
            else:
                r = _from_decimal(p1)
                fr = [r[0], r[1]]
                extra = r[2] if len(r) > 2 else None
                tags = _tags_merge(tags, [extra])
                decimal, fr = _fix_num(tags, *fr)
                if decimal:
                    fr = _de_decimal(*fr)
        else:
            s = pstr(a0)
            m = re.search(r"\s*([\+\-]?)\s*([0-9e\.\+\-]+)\s+([0-9e\.\+\-]+)"
                          r"\s*\/\s*([0-9e\.\+\-]+)", s)
            m2 = re.search(r"\s*([0-9e\.\+\-]+)\s*\/\s*([0-9e\.\+\-]+)", s)
            if m:
                sign = pnum(m.group(1) + "1")
                tags = _tags(nums[1:])
                decimal, (p1, p2, p3) = _fix_num(tags, m.group(2),
                                                 m.group(3), m.group(4))
                p1, p2, p3 = abs(p1), abs(p2), abs(p3)
                fr = [n_add(n_mul(p1, p3), p2), n_mul(sign, p3)]
                if decimal:
                    fr = _de_decimal(*fr)
            elif m2:
                tags = _tags(nums[1:])
                decimal, fr = _fix_num(tags, m2.group(1), m2.group(2))
                if decimal:
                    fr = _de_decimal(*fr)
                fr = _simplify_sign(*fr)
            else:
                raise ValueError('"%s" is of unknown format' % s)
        if pnum(fr[1]) == 0:
            raise ZeroDivisionError("Can not have 0 as the denominator")
        while len(tags) <= RED_STATE:
            tags.append(None)
        if _tag(REDUCE, tags) != "NO_REDUCE" and \
                _tag(RED_STATE, tags) != "IS_REDUCED":
            not_reduced, fr = _reduce(*fr)
            if not_reduced and _tag(AUTO, tags) == "AUTO":
                fr = [pnum(pstr(v)) for v in fr]
        if _tag(RED_STATE, tags) == "IS_REDUCED":
            tags[RED_STATE] = None
        return cls(fr, tags)

    # -- output --------------------------------------------------------
    def plist(self, mixed=False):
        f0, f1 = self.f
        if mixed:
            whole = pint(n_div(f0, f1))
            f0 = abs(n_sub(f0, n_mul(f1, whole)))
            out = [whole, f0, f1]
        else:
            out = [f0, f1]
        return [re.sub(r"^\+", "", pstr(v)) for v in out]

    def string(self):
        a, b = self.plist()
        return "%s/%s" % (a, b)

    def __str__(self):
        return self.string()

    def __repr__(self):
        return "PFrac(%s)" % self.string()

    def decimal(self):
        return n_div(self.f[0], self.f[1])

    # -- arithmetic ----------------------------------------------------
    def _other(self, other):
        if isinstance(other, PFrac):
            return list(other.f), list(other.tags)
        r = _from_decimal(other)
        t = [None] * 6
        t[INTERNAL] = "CONVERTED"
        return [r[0], r[1]], t

    def add(self, other):
        f1, t1 = list(self.f), list(self.tags)
        f2, t2 = self._other(other)
        tags = _tags_preserve(t1, t2)
        while len(tags) <= RED_STATE:
            tags.append(None)
        if _tag(REDUCE, tags) == "NO_REDUCE":
            fr = [n_add(n_mul(f1[0], f2[1]), n_mul(f2[0], f1[1])),
                  n_mul(f1[1], f2[1])]
        else:
            g1 = _gcd(f1[1], f2[1])
            tmp = n_add(n_mul(f1[0], n_div(f2[1], g1)),
                        n_mul(f2[0], n_div(f1[1], g1)))
            g2 = _gcd(tmp, g1)
            fr = [n_div(tmp, g2), n_mul(n_div(f1[1], g1), n_div(f2[1], g2))]
            tags[RED_STATE] = "IS_REDUCED"
        return PFrac.new(fr[0], fr[1], *_tagnames(tags))

    def mul(self, other):
        f1, t1 = list(self.f), list(self.tags)
        f2, t2 = self._other(other)
        tags = _tags_preserve(t1, t2)
        while len(tags) <= RED_STATE:
            tags.append(None)
        if _tag(REDUCE, tags) == "NO_REDUCE":
            fr = [n_mul(f1[0], f2[0]), n_mul(f1[1], f2[1])]
        else:
            g1, g2 = _gcd(f1[0], f2[1]), _gcd(f2[0], f1[1])
            fr = [n_mul(n_div(f1[0], g1), n_div(f2[0], g2)),
                  n_mul(n_div(f1[1], g2), n_div(f2[1], g1))]
            tags[RED_STATE] = "IS_REDUCED"
        return PFrac.new(fr[0], fr[1], *_tagnames(tags))

    @staticmethod
    def sub(a, b):
        """a - b where at least one of a, b is a PFrac."""
        if not isinstance(a, PFrac):
            a = PFrac.new(a, "CONVERTED")
        if not isinstance(b, PFrac):
            b = PFrac.new(b, "CONVERTED")
        nb = PFrac.new(b.f[0], _neg_num(b.f[1]), *_tagnames(b.tags))
        return a.add(nb)

    @staticmethod
    def div(a, b):
        if not isinstance(a, PFrac):
            a = PFrac.new(a, "CONVERTED")
        if not isinstance(b, PFrac):
            b = PFrac.new(b, "CONVERTED")
        rb = PFrac.new(b.f[1], b.f[0], *_tagnames(b.tags))
        return a.mul(rb)

    def pabs(self):
        return PFrac.new(abs(pnum(self.f[0])), abs(pnum(self.f[1])),
                         *(_tagnames(self.tags) + ["IS_REDUCED"]))

    def cmp(self, other):
        f1 = self.f
        if isinstance(other, PFrac):
            f2 = other.f
        else:
            f2 = _from_decimal(other)
        x = n_mul(f1[0], f2[1])
        y = n_mul(f2[0], f1[1])
        return (x > y) - (x < y)


def _neg_num(v):
    v = pnum(v)
    if isinstance(v, int):
        return -v
    return -float(v)


def _tagnames(tags):
    """Turn a positional tag list back into the tag names new() takes."""
    return [t for t in tags if t]


def _tags_merge(tags, names):
    t = list(tags)
    for n in names:
        if n and n in _TAGS:
            num, val = _TAGS[n]
            while len(t) <= num:
                t.append(None)
            t[num] = val
    return t


def _tags_preserve(t1, t2):
    t1 = t1 + [None] * (6 - len(t1))
    t2 = t2 + [None] * (6 - len(t2))
    if t1[INTERNAL] == "CONVERTED":
        return list(t2)
    if t2[INTERNAL] == "CONVERTED":
        return list(t1)
    return [(t1[i] if (t1[i] or "") == (t2[i] or "") and t1[i] else "")
            for i in range(len(t1))]


def _from_decimal(decimal):
    """Port of Math::Fraction::_from_decimal (SMALL mode).

    Converts a decimal to (numerator, denominator), recognising
    repeating decimals: "0.33" -> 1/3, "0.666666666666667" -> 2/3.
    """
    decimal = re.sub(r"\s", "", pstr(decimal))
    m = re.search(r"([\+\-]?)\s*(\d*)\.(\d+)$", decimal)
    if not m:
        return [n_mul(pnum(decimal), 1), 1]
    sign, int_part, dec = m.group(1), m.group(2), m.group(3)
    sign = sign + "1"
    dec_len = len(dec)
    if not int_part or int_part == "0":
        int_part = ""
    factor = "1" + "0" * dec_len
    repeat = False
    beg_part = pat = ""
    pat_len = 0
    beg_len = 0
    while beg_len < dec_len and not repeat:
        beg_part = dec[:beg_len]
        other = dec[beg_len:]
        olen = len(other)
        i = 1
        while i < olen / 2 + 1 and not repeat:
            pat = other[:i]
            pat_len = i
            cur = other
            while True:
                if cur is not None and cur.startswith(pat):
                    cur = cur[len(pat):]
                else:
                    cur = None
                length = len(cur) if cur is not None else 0
                if length <= pat_len:
                    if not length:
                        break
                    pat_lastb = pat[:length]
                    if pat_lastb == cur:
                        repeat = True
                        break
                    if pat_lastb == pstr(n_sub(str_to_num(cur), 1)):
                        dp2 = dec[:dec_len - len(pat_lastb)]
                        factor2 = "1" + "0" * len(dp2)
                        fr1 = PFrac.new("0" + beg_part, "1" + "0" * beg_len,
                                        "NO_REDUCE")
                        fr2 = PFrac.new("0" + pat,
                                        "9" * pat_len + "0" * beg_len,
                                        "NO_REDUCE")
                        fr3 = fr1.add(fr2)
                        got = fr3.decimal()
                        places = len(pstr(got))
                        should = pstr(n_div(str_to_num(dp2),
                                            str_to_num(factor2))) \
                            + pat * places
                        if got == str_to_num(should):
                            repeat = True
                            break
            i += 1
        if not repeat:
            beg_len += 1
    if repeat:
        fr1 = PFrac.new("0" + beg_part, "1" + "0" * beg_len)
        fr2 = PFrac.new("0" + pat, "9" * pat_len + "0" * beg_len)
        s = padd(padd(int_part, fr1), fr2)
        fr3 = pmul(sign, s)
        return [fr3.f[0], fr3.f[1]]
    return [n_mul(pnum(decimal), str_to_num(factor)), str_to_num(factor)]


def frac(*args):
    """Math::Fraction::frac."""
    return PFrac.new(*args)


# ----------------------------------------------------------------------
# Generic Perl operators (dispatching to Math::Fraction overloads)
# ----------------------------------------------------------------------

def padd(a, b):
    if isinstance(a, PFrac):
        return a.add(b)
    if isinstance(b, PFrac):
        return b.add(a)
    return n_add(pnum(a), pnum(b))


def psub(a, b):
    if isinstance(a, PFrac) or isinstance(b, PFrac):
        return PFrac.sub(a, b)
    return n_sub(pnum(a), pnum(b))


def pmul(a, b):
    if isinstance(a, PFrac):
        return a.mul(b)
    if isinstance(b, PFrac):
        return b.mul(a)
    return n_mul(pnum(a), pnum(b))


def pdiv(a, b):
    if isinstance(a, PFrac) or isinstance(b, PFrac):
        return PFrac.div(a, b)
    return n_div(pnum(a), pnum(b))


def pneg(a):
    """Perl unary minus (Math::Fraction falls back to 0 - a)."""
    if isinstance(a, PFrac):
        return PFrac.sub(0, a)
    if isinstance(a, str):
        s = a
        if s and (s[0].isalpha() or s[0] == "_"):
            return "-" + s
        if s[:1] == "+" or (s[:1] == "-" and not _looks_like_number(s)):
            return ("+" if s[0] == "-" else "-") + s[1:]
    v = pnum(a)
    if isinstance(v, int):
        return -v
    return -v if v != 0 else 0.0


def _looks_like_number(s):
    return re.match(r"^\s*[+-]?(\d+\.?\d*([eE][+-]?\d+)?|\.\d+([eE][+-]?\d+)?)"
                    r"\s*$", s) is not None


def pabs(a):
    if isinstance(a, PFrac):
        return a.pabs()
    v = pnum(a)
    return abs(v)


def pcmp(a, b):
    """Perl <=> (mathematically correct also for swapped operands)."""
    if isinstance(a, PFrac):
        return a.cmp(b)
    if isinstance(b, PFrac):
        return -b.cmp(a)
    x, y = pnum(a), pnum(b)
    return (x > y) - (x < y)


def peq(a, b):
    return pcmp(a, b) == 0


def plt(a, b):
    return pcmp(a, b) < 0


def ple(a, b):
    return pcmp(a, b) <= 0


def pgt(a, b):
    return pcmp(a, b) > 0


def pge(a, b):
    return pcmp(a, b) >= 0


def fix_str(x):
    """Perl ``$x =~ s/\\/1$//``: strip a trailing "/1".

    Like Perl, a value that does not match is returned unchanged (a
    fraction object stays a fraction object); one that matches becomes
    a string.
    """
    s = pstr(x)
    if re.search(r"/1$", s) or re.search(r"/1\n$", s):
        return re.sub(r"/1(\n?)$", r"\1", s, count=1)
    return x