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

Two functions, inverse on 1..3999:

    int_to_roman(n)  -> canonical Roman numeral string
    roman_to_int(s)  -> integer value

Standard library only.
"""

# Value table in descending order, including the six subtractive forms.
# Greedy encoding over this table yields exactly the canonical representation.
_INT_TO_ROMAN_TABLE = (
    (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"),
)

_ROMAN_VALUES = {
    "I": 1,
    "V": 5,
    "X": 10,
    "L": 50,
    "C": 100,
    "D": 500,
    "M": 1000,
}


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

    Uses subtractive forms (IV, IX, XL, XC, CD, CM). Raises ValueError for
    any integer outside the range 1..3999, or for a non-integer argument.
    """
    # Reject bool explicitly (bool is a subclass of int) and any non-int type.
    if isinstance(n, bool) or not isinstance(n, int):
        raise ValueError("n must be an integer in the range 1..3999")
    if n < 1 or n > 3999:
        raise ValueError("n must be in the range 1..3999")

    parts = []
    remainder = n
    for value, symbol in _INT_TO_ROMAN_TABLE:
        if remainder == 0:
            break
        count, remainder = divmod(remainder, value)
        if count:
            parts.append(symbol * count)
    return "".join(parts)


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

    Accepts only canonical subtractive numerals for 1..3999. Raises
    ValueError for an empty string, a non-string argument, or any 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")

    # Every character must be a valid Roman symbol.
    total = 0
    prev_value = 0
    for ch in s:
        value = _ROMAN_VALUES.get(ch)
        if value is None:
            raise ValueError("invalid Roman numeral character: {!r}".format(ch))
        # Standard left-to-right accumulation: subtract when a smaller
        # symbol precedes a larger one.
        if value > prev_value and prev_value != 0:
            total += value - 2 * prev_value
        else:
            total += value
        prev_value = value

    # Canonicity gate: a value is canonical if and only if re-encoding it
    # reproduces the original string exactly. This rejects non-canonical
    # spellings such as "IIII", "VIIII", "XXXX", "VX", "IM", "MMMM", etc.,
    # and also catches any value that fell outside 1..3999.
    if total < 1 or total > 3999 or int_to_roman(total) != s:
        raise ValueError("not a canonical Roman numeral: {!r}".format(s))

    return total