from collections import Counter
from typing import List, Dict, Tuple

class RougeScorer:
    """
    ROUGE (Recall-Oriented Understudy for Gisting Evaluation) Scorer
    implemented from scratch supporting ROUGE-1, ROUGE-2, and ROUGE-L.
    Computes Precision, Recall, and F1 scores.
    """

    @staticmethod
    def _get_ngrams(tokens: List[str], n: int) -> Counter:
        """Extracts n-grams from a token list."""
        if len(tokens) < n:
            return Counter()
        return Counter(tuple(tokens[i:i+n]) for i in range(len(tokens) - n + 1))

    @staticmethod
    def _lcs_length(seq1: List[str], seq2: List[str]) -> int:
        """
        Computes the length of the Longest Common Subsequence (LCS)
        between two token sequences using dynamic programming.
        """
        m, n = len(seq1), len(seq2)
        if m == 0 or n == 0:
            return 0

        # Space-optimized DP table
        prev = [0] * (n + 1)
        curr = [0] * (n + 1)

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if seq1[i - 1] == seq2[j - 1]:
                    curr[j] = prev[j - 1] + 1
                else:
                    curr[j] = max(prev[j], curr[j - 1])
            prev = list(curr)

        return curr[n]

    def score_rouge_n(self, candidate_tokens: List[str], reference_tokens: List[str], n: int) -> Dict[str, float]:
        """
        Calculates ROUGE-N Precision, Recall, and F1.
        """
        cand_ngrams = self._get_ngrams(candidate_tokens, n)
        ref_ngrams = self._get_ngrams(reference_tokens, n)

        total_ref = sum(ref_ngrams.values())
        total_cand = sum(cand_ngrams.values())

        if total_ref == 0 or total_cand == 0:
            return {"precision": 0.0, "recall": 0.0, "f1": 0.0}

        # Overlapping n-grams
        overlap = 0
        for ngram, count in cand_ngrams.items():
            if ngram in ref_ngrams:
                overlap += min(count, ref_ngrams[ngram])

        precision = overlap / total_cand if total_cand > 0 else 0.0
        recall = overlap / total_ref if total_ref > 0 else 0.0
        f1 = (2 * precision * recall / (precision + recall)) if (precision + recall) > 0 else 0.0

        return {
            "precision": round(precision, 4),
            "recall": round(recall, 4),
            "f1": round(f1, 4)
        }

    def score_rouge_l(self, candidate_tokens: List[str], reference_tokens: List[str]) -> Dict[str, float]:
        """
        Calculates ROUGE-L (Longest Common Subsequence) Precision, Recall, and F1.
        """
        m = len(candidate_tokens)
        n = len(reference_tokens)

        if m == 0 or n == 0:
            return {"precision": 0.0, "recall": 0.0, "f1": 0.0}

        lcs = self._lcs_length(candidate_tokens, reference_tokens)

        precision = lcs / m if m > 0 else 0.0
        recall = lcs / n if n > 0 else 0.0
        f1 = (2 * precision * recall / (precision + recall)) if (precision + recall) > 0 else 0.0

        return {
            "precision": round(precision, 4),
            "recall": round(recall, 4),
            "f1": round(f1, 4)
        }

    def evaluate(self, candidate_text: str, reference_text: str) -> Dict[str, Dict[str, float]]:
        """
        Full ROUGE evaluation suite returning ROUGE-1, ROUGE-2, and ROUGE-L.
        """
        cand_tokens = candidate_text.strip().split()
        ref_tokens = reference_text.strip().split()

        return {
            "rouge-1": self.score_rouge_n(cand_tokens, ref_tokens, n=1),
            "rouge-2": self.score_rouge_n(cand_tokens, ref_tokens, n=2),
            "rouge-l": self.score_rouge_l(cand_tokens, ref_tokens)
        }