"""
Roman numeral conversion: int_to_roman and roman_to_int.
Both use canonical (subtractive) notation for the range 1..3999.
"""

import re

# Mapping from integer value to Roman numeral symbol, in descending order.
# Subtractive pairs are included (e.g. 900=CM, 400=CD, 90=XC, 40=XL, 9=IX, 4=IV).
_INT_TO_ROMAN = [
    (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_TO_INT = {symbol: value for value, symbol in _INT_TO_ROMAN}

# A regex that matches exactly the canonical form of a Roman numeral in 1..3999.
# Structure: M{0,3} then hundreds then tens then ones, each using subtractive forms.
_CANONICAL_RE = re.compile(
    r"^"
    r"M{0,3}"                           # thousands: 0-3 M's
    r"(CM|CD|D?C{0,3})"                # hundreds
    r"(XC|XL|L?X{0,3})"                # tens
    r"(IX|IV|V?I{0,3})"                # ones
    r"$"
)


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

    Raises ValueError for integers outside that range.
    """
    if not isinstance(n, int) or isinstance(n, bool):
        raise ValueError(f"Expected an integer, got {type(n).__name__}")
    if n < 1 or n > 3999:
        raise ValueError(f"Integer must be in range 1..3999, got {n}")

    result = []
    remaining = n
    for value, symbol in _INT_TO_ROMAN:
        while remaining >= value:
            result.append(symbol)
            remaining -= value
    return "".join(result)


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

    Raises ValueError for an empty string or a malformed/non-canonical numeral.
    """
    if not s:
        raise ValueError("Roman numeral string must not be empty")

    # Reject any string that is not a valid canonical Roman numeral.
    # The regex enforces canonical form including subtractive rules and
    # maximum repetition counts, and rejects non-Roman characters.
    if not _CANONICAL_RE.match(s):
        raise ValueError(f"Invalid or non-canonical Roman numeral: {s!r}")

    # Parse left-to-right: if the current symbol has a smaller value than the
    # next one, subtract it; otherwise add it.  Because we have already
    # validated the string, this always yields the correct result.
    total = 0
    prev = 0
    for ch in reversed(s):
        value = _ROMAN_TO_INT.get(ch)
        if value is None:
            raise ValueError(f"Unknown Roman numeral character: {ch!r}")
        if value < prev:
            total -= value
        else:
            total += value
        prev = value
    return total