"""퍼지 매칭 유틸리티.

파일명, 함수명, 스킬명 등의 유사 매칭을 제공한다.
Levenshtein distance 기반으로, 순수 Python으로 구현 (외부 의존성 없음).

주요 함수:
    levenshtein_distance(s1, s2) -> int
    similarity_ratio(s1, s2) -> float
    fuzzy_match(query, candidates, threshold, max_results) -> list[tuple[str, float]]
"""

from __future__ import annotations


def levenshtein_distance(s1: str, s2: str) -> int:
    """두 문자열 사이의 Levenshtein(편집) 거리를 계산한다.

    삽입(insert), 삭제(delete), 치환(substitute) 1회를 각각 비용 1로 계산.
    공간 최적화를 위해 2-row DP를 사용한다.

    Args:
        s1: 첫 번째 문자열.
        s2: 두 번째 문자열.

    Returns:
        0 이상의 정수. 0이면 동일 문자열.
    """
    # 짧은 쪽이 s1이 되도록 교환 → 내부 배열 크기 최소화
    if len(s1) < len(s2):
        s1, s2 = s2, s1

    len1, len2 = len(s1), len(s2)

    # 빈 문자열 처리
    if len2 == 0:
        return len1

    # prev[j] = dp[i-1][j], 이전 행
    prev = list(range(len2 + 1))
    curr = [0] * (len2 + 1)

    for i in range(1, len1 + 1):
        curr[0] = i
        for j in range(1, len2 + 1):
            if s1[i - 1] == s2[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(
                    prev[j],  # 삭제
                    curr[j - 1],  # 삽입
                    prev[j - 1],  # 치환
                )
        prev, curr = curr, prev

    return prev[len2]


def similarity_ratio(s1: str, s2: str) -> float:
    """두 문자열의 유사도를 0.0~1.0으로 반환한다.

    1.0 = 동일, 0.0 = 완전히 다름 (또는 한쪽이 빈 문자열).

    공식: 1 - dist / max(len(s1), len(s2))

    Args:
        s1: 첫 번째 문자열.
        s2: 두 번째 문자열.

    Returns:
        0.0~1.0 범위의 float.
    """
    if not s1 and not s2:
        return 1.0
    if not s1 or not s2:
        return 0.0

    max_len = max(len(s1), len(s2))
    dist = levenshtein_distance(s1, s2)
    return 1.0 - dist / max_len


def fuzzy_match(
    query: str,
    candidates: list[str],
    threshold: float = 0.6,
    max_results: int = 5,
) -> list[tuple[str, float]]:
    """쿼리 문자열과 가장 유사한 후보들을 반환한다.

    각 후보의 유사도(similarity_ratio)를 계산해 threshold 이상인 것을
    점수 내림차순으로 최대 max_results 개 반환한다.

    Args:
        query: 검색할 문자열.
        candidates: 비교 대상 문자열 목록.
        threshold: 최소 유사도 (0.0~1.0, 기본 0.6).
        max_results: 반환할 최대 결과 수 (기본 5).

    Returns:
        [(candidate, score), ...] 형태의 리스트. 점수 내림차순 정렬.
        threshold 미만 결과는 제외. 빈 후보 목록이면 빈 리스트 반환.
    """
    if not candidates:
        return []

    scored: list[tuple[str, float]] = []
    for candidate in candidates:
        score = similarity_ratio(query, candidate)
        if score >= threshold:
            scored.append((candidate, score))

    # 점수 내림차순, 동점이면 문자열 알파벳 순
    scored.sort(key=lambda x: (-x[1], x[0]))

    return scored[:max_results]