"""Convert between integers and canonical (subtractive) Roman numerals."""

# Ordered from largest to smallest, including the six subtractive forms.
_VALUES = (
    (1000, "M"),
    (900, "CM"),
    (500, "D"),
    (400, "CD"),
    (100, "C"),
    (90, "XC"),
    (50, "L"),
    (40, "XL"),
    (10, "X"),
    (9, "IX"),
    (5, "V"),
    (4, "IV"),
    (1, "I"),
)


def int_to_roman(n):
    """Convert an integer in 1..3999 to its canonical Roman numeral string.

    Raises ValueError for any integer outside 1..3999.
    """
    if not isinstance(n, int) or isinstance(n, bool):
        raise ValueError("n must be an integer")
    if n < 1 or n > 3999:
        raise ValueError("n must be in the range 1..3999")

    result = []
    for value, symbol in _VALUES:
        count, n = divmod(n, value)
        result.append(symbol * count)
    return "".join(result)


def roman_to_int(s):
    """Convert a canonical Roman numeral string to its integer value.

    Raises ValueError for an empty string, or a malformed or non-canonical
    numeral (for example "IIII", "VX", or "ABC").
    """
    if not isinstance(s, str):
        raise ValueError("s must be a string")
    if s == "":
        raise ValueError("empty string is not a valid Roman numeral")

    # Greedily consume the canonical symbols from largest to smallest. A
    # canonical numeral matches this greedy parse exactly; anything that does
    # not consume the whole string (or uses a forbidden run length) is invalid.
    value = 0
    pos = 0
    for amount, symbol in _VALUES:
        # The additive symbols (M, C, X, I) may repeat at most three times;
        # the others (D, L, V) and the subtractive pairs at most once. Cap the
        # match count so a run like "IIII" or "VV" fails canonicality.
        max_repeat = 3 if symbol in ("M", "C", "X", "I") else 1
        count = 0
        while s.startswith(symbol, pos) and count < max_repeat:
            pos += len(symbol)
            value += amount
            count += 1

    if pos != len(s):
        raise ValueError("malformed or non-canonical Roman numeral: %r" % s)

    return value