ordering.py

"""Deterministic ordering checks for replay sequences."""

from __future__ import annotations

from collections.abc import Iterable, Sequence


Edge = tuple[str, str]


def find_order_violations(
    sequence: Sequence[str],
    required_before: Iterable[Edge],
) -> tuple[Edge, ...]:
    """Return lexicographically sorted order violations."""
    positions = {node: index for index, node in enumerate(sequence)}
    violations: set[Edge] = set()

    for before, after in required_before:
        if before not in positions or after not in positions:
            continue
        if positions[before] > positions[after]:
            violations.add((before, after))

    return tuple(sorted(violations))