"""
Field Matching Module

Matches normalized field values to tokens extracted from documents.
"""

from dataclasses import dataclass, field
from typing import Protocol
import re
from functools import cached_property


# Pre-compiled regex patterns (module-level for efficiency)
_DATE_PATTERN = re.compile(r'(\d{4})-(\d{2})-(\d{2})')
_WHITESPACE_PATTERN = re.compile(r'\s+')
_NON_DIGIT_PATTERN = re.compile(r'\D')
_DASH_PATTERN = re.compile(r'[\u2013\u2014\u2212\u00b7]')  # en-dash, em-dash, minus sign, middle dot


def _normalize_dashes(text: str) -> str:
    """Normalize different dash types and middle dots to standard hyphen-minus (ASCII 45)."""
    return _DASH_PATTERN.sub('-', text)


class TokenLike(Protocol):
    """Protocol for token objects."""
    text: str
    bbox: tuple[float, float, float, float]
    page_no: int


class TokenIndex:
    """
    Spatial index for tokens to enable fast nearby token lookup.

    Uses grid-based spatial hashing for O(1) average lookup instead of O(n).
    """

    def __init__(self, tokens: list[TokenLike], grid_size: float = 100.0):
        """
        Build spatial index from tokens.

        Args:
            tokens: List of tokens to index
            grid_size: Size of grid cells in pixels
        """
        self.tokens = tokens
        self.grid_size = grid_size
        self._grid: dict[tuple[int, int], list[TokenLike]] = {}
        self._token_centers: dict[int, tuple[float, float]] = {}
        self._token_text_lower: dict[int, str] = {}

        # Build index
        for i, token in enumerate(tokens):
            # Cache center coordinates
            center_x = (token.bbox[0] + token.bbox[2]) / 2
            center_y = (token.bbox[1] + token.bbox[3]) / 2
            self._token_centers[id(token)] = (center_x, center_y)

            # Cache lowercased text
            self._token_text_lower[id(token)] = token.text.lower()

            # Add to grid cell
            grid_x = int(center_x / grid_size)
            grid_y = int(center_y / grid_size)
            key = (grid_x, grid_y)
            if key not in self._grid:
                self._grid[key] = []
            self._grid[key].append(token)

    def get_center(self, token: TokenLike) -> tuple[float, float]:
        """Get cached center coordinates for token."""
        return self._token_centers.get(id(token), (
            (token.bbox[0] + token.bbox[2]) / 2,
            (token.bbox[1] + token.bbox[3]) / 2
        ))

    def get_text_lower(self, token: TokenLike) -> str:
        """Get cached lowercased text for token."""
        return self._token_text_lower.get(id(token), token.text.lower())

    def find_nearby(self, token: TokenLike, radius: float) -> list[TokenLike]:
        """
        Find all tokens within radius of the given token.

        Uses grid-based lookup for O(1) average case instead of O(n).
        """
        center = self.get_center(token)
        center_x, center_y = center

        # Determine which grid cells to search
        cells_to_check = int(radius / self.grid_size) + 1
        grid_x = int(center_x / self.grid_size)
        grid_y = int(center_y / self.grid_size)

        nearby = []
        radius_sq = radius * radius

        # Check all nearby grid cells
        for dx in range(-cells_to_check, cells_to_check + 1):
            for dy in range(-cells_to_check, cells_to_check + 1):
                key = (grid_x + dx, grid_y + dy)
                if key not in self._grid:
                    continue

                for other in self._grid[key]:
                    if other is token:
                        continue

                    other_center = self.get_center(other)
                    dist_sq = (center_x - other_center[0]) ** 2 + (center_y - other_center[1]) ** 2

                    if dist_sq <= radius_sq:
                        nearby.append(other)

        return nearby


@dataclass
class Match:
    """Represents a matched field in the document."""
    field: str
    value: str
    bbox: tuple[float, float, float, float]  # (x0, y0, x1, y1)
    page_no: int
    score: float  # 0-1 confidence score
    matched_text: str  # Actual text that matched
    context_keywords: list[str]  # Nearby keywords that boosted confidence

    def to_yolo_format(self, image_width: float, image_height: float, class_id: int) -> str:
        """Convert to YOLO annotation format."""
        x0, y0, x1, y1 = self.bbox

        x_center = (x0 + x1) / 2 / image_width
        y_center = (y0 + y1) / 2 / image_height
        width = (x1 - x0) / image_width
        height = (y1 - y0) / image_height

        return f"{class_id} {x_center:.6f} {y_center:.6f} {width:.6f} {height:.6f}"


# Context keywords for each field type (Swedish invoice terms)
CONTEXT_KEYWORDS = {
    'InvoiceNumber': ['fakturanr', 'fakturanummer', 'invoice', 'inv.nr', 'inv nr', 'nr'],
    'InvoiceDate': ['fakturadatum', 'datum', 'date', 'utfärdad', 'utskriftsdatum', 'dokumentdatum'],
    'InvoiceDueDate': ['förfallodatum', 'förfaller', 'due date', 'betalas senast', 'att betala senast',
                       'förfallodag', 'oss tillhanda senast', 'senast'],
    'OCR': ['ocr', 'referens', 'betalningsreferens', 'ref'],
    'Bankgiro': ['bankgiro', 'bg', 'bg-nr', 'bg nr'],
    'Plusgiro': ['plusgiro', 'pg', 'pg-nr', 'pg nr'],
    'Amount': ['att betala', 'summa', 'total', 'belopp', 'amount', 'totalt', 'att erlägga', 'sek', 'kr'],
    'supplier_organisation_number': ['organisationsnummer', 'org.nr', 'org nr', 'orgnr', 'org.nummer',
                                      'momsreg', 'momsnr', 'moms nr', 'vat', 'corporate id'],
    'supplier_accounts': ['konto', 'kontonr', 'konto nr', 'account', 'klientnr', 'kundnr'],
}


class FieldMatcher:
    """Matches field values to document tokens."""

    def __init__(
        self,
        context_radius: float = 200.0,  # pixels - increased to handle label-value spacing in scanned PDFs
        min_score_threshold: float = 0.5
    ):
        """
        Initialize the matcher.

        Args:
            context_radius: Distance to search for context keywords (default 200px to handle
                           typical label-value spacing in scanned invoices at 150 DPI)
            min_score_threshold: Minimum score to consider a match valid
        """
        self.context_radius = context_radius
        self.min_score_threshold = min_score_threshold
        self._token_index: TokenIndex | None = None

    def find_matches(
        self,
        tokens: list[TokenLike],
        field_name: str,
        normalized_values: list[str],
        page_no: int = 0
    ) -> list[Match]:
        """
        Find all matches for a field in the token list.

        Args:
            tokens: List of tokens from the document
            field_name: Name of the field to match
            normalized_values: List of normalized value variants to search for
            page_no: Page number to filter tokens

        Returns:
            List of Match objects sorted by score (descending)
        """
        matches = []
        # Filter tokens by page and exclude hidden metadata tokens
        # Hidden tokens often have bbox with y < 0 or y > page_height
        # These are typically PDF metadata stored as invisible text
        page_tokens = [
            t for t in tokens
            if t.page_no == page_no and t.bbox[1] >= 0 and t.bbox[3] > t.bbox[1]
        ]

        # Build spatial index for efficient nearby token lookup (O(n) -> O(1))
        self._token_index = TokenIndex(page_tokens, grid_size=self.context_radius)

        for value in normalized_values:
            # Strategy 1: Exact token match
            exact_matches = self._find_exact_matches(page_tokens, value, field_name)
            matches.extend(exact_matches)

            # Strategy 2: Multi-token concatenation
            concat_matches = self._find_concatenated_matches(page_tokens, value, field_name)
            matches.extend(concat_matches)

            # Strategy 3: Fuzzy match (for amounts and dates only)
            if field_name in ('Amount', 'InvoiceDate', 'InvoiceDueDate'):
                fuzzy_matches = self._find_fuzzy_matches(page_tokens, value, field_name)
                matches.extend(fuzzy_matches)

            # Strategy 4: Substring match (for values embedded in longer text)
            # e.g., "Fakturanummer: 2465027205" should match OCR value "2465027205"
            # Note: Amount is excluded because short numbers like "451" can incorrectly match
            # in OCR payment lines or other unrelated text
            if field_name in ('InvoiceDate', 'InvoiceDueDate', 'InvoiceNumber', 'OCR', 'Bankgiro', 'Plusgiro',
                              'supplier_organisation_number', 'supplier_accounts', 'customer_number'):
                substring_matches = self._find_substring_matches(page_tokens, value, field_name)
                matches.extend(substring_matches)

        # Strategy 5: Flexible date matching (year-month match, nearby dates, heuristic selection)
        # Only if no exact matches found for date fields
        if field_name in ('InvoiceDate', 'InvoiceDueDate') and not matches:
            flexible_matches = self._find_flexible_date_matches(
                page_tokens, normalized_values, field_name
            )
            matches.extend(flexible_matches)

        # Deduplicate and sort by score
        matches = self._deduplicate_matches(matches)
        matches.sort(key=lambda m: m.score, reverse=True)

        # Clear token index to free memory
        self._token_index = None

        return [m for m in matches if m.score >= self.min_score_threshold]

    def _find_exact_matches(
        self,
        tokens: list[TokenLike],
        value: str,
        field_name: str
    ) -> list[Match]:
        """Find tokens that exactly match the value."""
        matches = []
        value_lower = value.lower()
        value_digits = _NON_DIGIT_PATTERN.sub('', value) if field_name in ('InvoiceNumber', 'OCR', 'Bankgiro', 'Plusgiro',
                                                                            'supplier_organisation_number', 'supplier_accounts') else None

        for token in tokens:
            token_text = token.text.strip()

            # Exact match
            if token_text == value:
                score = 1.0
            # Case-insensitive match (use cached lowercase from index)
            elif self._token_index and self._token_index.get_text_lower(token).strip() == value_lower:
                score = 0.95
            # Digits-only match for numeric fields
            elif value_digits is not None:
                token_digits = _NON_DIGIT_PATTERN.sub('', token_text)
                if token_digits and token_digits == value_digits:
                    score = 0.9
                else:
                    continue
            else:
                continue

            # Boost score if context keywords are nearby
            context_keywords, context_boost = self._find_context_keywords(
                tokens, token, field_name
            )
            score = min(1.0, score + context_boost)

            matches.append(Match(
                field=field_name,
                value=value,
                bbox=token.bbox,
                page_no=token.page_no,
                score=score,
                matched_text=token_text,
                context_keywords=context_keywords
            ))

        return matches

    def _find_concatenated_matches(
        self,
        tokens: list[TokenLike],
        value: str,
        field_name: str
    ) -> list[Match]:
        """Find value by concatenating adjacent tokens."""
        matches = []
        value_clean = _WHITESPACE_PATTERN.sub('', value)

        # Sort tokens by position (top-to-bottom, left-to-right)
        sorted_tokens = sorted(tokens, key=lambda t: (t.bbox[1], t.bbox[0]))

        for i, start_token in enumerate(sorted_tokens):
            # Try to build the value by concatenating nearby tokens
            concat_text = start_token.text.strip()
            concat_bbox = list(start_token.bbox)
            used_tokens = [start_token]

            for j in range(i + 1, min(i + 5, len(sorted_tokens))):  # Max 5 tokens
                next_token = sorted_tokens[j]

                # Check if tokens are on the same line (y overlap)
                if not self._tokens_on_same_line(start_token, next_token):
                    break

                # Check horizontal proximity
                if next_token.bbox[0] - concat_bbox[2] > 50:  # Max 50px gap
                    break

                concat_text += next_token.text.strip()
                used_tokens.append(next_token)

                # Update bounding box
                concat_bbox[0] = min(concat_bbox[0], next_token.bbox[0])
                concat_bbox[1] = min(concat_bbox[1], next_token.bbox[1])
                concat_bbox[2] = max(concat_bbox[2], next_token.bbox[2])
                concat_bbox[3] = max(concat_bbox[3], next_token.bbox[3])

                # Check for match
                concat_clean = _WHITESPACE_PATTERN.sub('', concat_text)
                if concat_clean == value_clean:
                    context_keywords, context_boost = self._find_context_keywords(
                        tokens, start_token, field_name
                    )

                    matches.append(Match(
                        field=field_name,
                        value=value,
                        bbox=tuple(concat_bbox),
                        page_no=start_token.page_no,
                        score=min(1.0, 0.85 + context_boost),  # Slightly lower base score
                        matched_text=concat_text,
                        context_keywords=context_keywords
                    ))
                    break

        return matches

    def _find_substring_matches(
        self,
        tokens: list[TokenLike],
        value: str,
        field_name: str
    ) -> list[Match]:
        """
        Find value as a substring within longer tokens.

        Handles cases like:
        - 'Fakturadatum: 2026-01-09' where the date is embedded
        - 'Fakturanummer: 2465027205' where OCR/invoice number is embedded
        - 'OCR: 1234567890' where reference number is embedded

        Uses lower score (0.75-0.85) than exact match to prefer exact matches.
        Only matches if the value appears as a distinct segment (not part of a larger number).
        """
        matches = []

        # Supported fields for substring matching
        supported_fields = ('InvoiceDate', 'InvoiceDueDate', 'InvoiceNumber', 'OCR', 'Bankgiro', 'Plusgiro', 'Amount',
                            'supplier_organisation_number', 'supplier_accounts', 'customer_number')
        if field_name not in supported_fields:
            return matches

        # Fields where spaces/dashes should be ignored during matching
        # (e.g., org number "55 65 74-6624" should match "5565746624")
        ignore_spaces_fields = ('supplier_organisation_number', 'Bankgiro', 'Plusgiro', 'supplier_accounts')

        for token in tokens:
            token_text = token.text.strip()
            # Normalize different dash types to hyphen-minus for matching
            token_text_normalized = _normalize_dashes(token_text)

            # For certain fields, also try matching with spaces/dashes removed
            if field_name in ignore_spaces_fields:
                token_text_compact = token_text_normalized.replace(' ', '').replace('-', '')
                value_compact = value.replace(' ', '').replace('-', '')
            else:
                token_text_compact = None
                value_compact = None

            # Skip if token is the same length as value (would be exact match)
            if len(token_text_normalized) <= len(value):
                continue

            # Check if value appears as substring (using normalized text)
            # Try case-sensitive first, then case-insensitive
            idx = None
            case_sensitive_match = True
            used_compact = False

            if value in token_text_normalized:
                idx = token_text_normalized.find(value)
            elif value.lower() in token_text_normalized.lower():
                idx = token_text_normalized.lower().find(value.lower())
                case_sensitive_match = False
            elif token_text_compact and value_compact in token_text_compact:
                # Try compact matching (spaces/dashes removed)
                idx = token_text_compact.find(value_compact)
                used_compact = True
            elif token_text_compact and value_compact.lower() in token_text_compact.lower():
                idx = token_text_compact.lower().find(value_compact.lower())
                case_sensitive_match = False
                used_compact = True

            if idx is None:
                continue

            # For compact matching, boundary check is simpler (just check it's 10 consecutive digits)
            if used_compact:
                # Verify proper boundary in compact text
                if idx > 0 and token_text_compact[idx - 1].isdigit():
                    continue
                end_idx = idx + len(value_compact)
                if end_idx < len(token_text_compact) and token_text_compact[end_idx].isdigit():
                    continue
            else:
                # Verify it's a proper boundary match (not part of a larger number)
                # Check character before (if exists)
                if idx > 0:
                    char_before = token_text_normalized[idx - 1]
                    # Must be non-digit (allow : space - etc)
                    if char_before.isdigit():
                        continue

                # Check character after (if exists)
                end_idx = idx + len(value)
                if end_idx < len(token_text_normalized):
                    char_after = token_text_normalized[end_idx]
                    # Must be non-digit
                    if char_after.isdigit():
                        continue

            # Found valid substring match
            context_keywords, context_boost = self._find_context_keywords(
                tokens, token, field_name
            )

            # Check if context keyword is in the same token (like "Fakturadatum:")
            token_lower = token_text.lower()
            inline_context = []
            for keyword in CONTEXT_KEYWORDS.get(field_name, []):
                if keyword in token_lower:
                    inline_context.append(keyword)

            # Boost score if keyword is inline
            inline_boost = 0.1 if inline_context else 0

            # Lower score for case-insensitive match
            base_score = 0.75 if case_sensitive_match else 0.70

            matches.append(Match(
                field=field_name,
                value=value,
                bbox=token.bbox,  # Use full token bbox
                page_no=token.page_no,
                score=min(1.0, base_score + context_boost + inline_boost),
                matched_text=token_text,
                context_keywords=context_keywords + inline_context
            ))

        return matches

    def _find_fuzzy_matches(
        self,
        tokens: list[TokenLike],
        value: str,
        field_name: str
    ) -> list[Match]:
        """Find approximate matches for amounts and dates."""
        matches = []

        for token in tokens:
            token_text = token.text.strip()

            if field_name == 'Amount':
                # Try to parse both as numbers
                try:
                    token_num = self._parse_amount(token_text)
                    value_num = self._parse_amount(value)

                    if token_num is not None and value_num is not None:
                        if abs(token_num - value_num) < 0.01:  # Within 1 cent
                            context_keywords, context_boost = self._find_context_keywords(
                                tokens, token, field_name
                            )

                            matches.append(Match(
                                field=field_name,
                                value=value,
                                bbox=token.bbox,
                                page_no=token.page_no,
                                score=min(1.0, 0.8 + context_boost),
                                matched_text=token_text,
                                context_keywords=context_keywords
                            ))
                except:
                    pass

        return matches

    def _find_flexible_date_matches(
        self,
        tokens: list[TokenLike],
        normalized_values: list[str],
        field_name: str
    ) -> list[Match]:
        """
        Flexible date matching when exact match fails.

        Strategies:
        1. Year-month match: If CSV has 2026-01-15, match any 2026-01-XX date
        2. Nearby date match: Match dates within 7 days of CSV value
        3. Heuristic selection: Use context keywords to select the best date

        This handles cases where CSV InvoiceDate doesn't exactly match PDF,
        but we can still find a reasonable date to label.
        """
        from datetime import datetime, timedelta

        matches = []

        # Parse the target date from normalized values
        target_date = None
        for value in normalized_values:
            # Try to parse YYYY-MM-DD format
            date_match = re.match(r'^(\d{4})-(\d{2})-(\d{2})$', value)
            if date_match:
                try:
                    target_date = datetime(
                        int(date_match.group(1)),
                        int(date_match.group(2)),
                        int(date_match.group(3))
                    )
                    break
                except ValueError:
                    continue

        if not target_date:
            return matches

        # Find all date-like tokens in the document
        date_candidates = []

        for token in tokens:
            token_text = token.text.strip()

            # Search for date pattern in token (use pre-compiled pattern)
            for match in _DATE_PATTERN.finditer(token_text):
                try:
                    found_date = datetime(
                        int(match.group(1)),
                        int(match.group(2)),
                        int(match.group(3))
                    )
                    date_str = match.group(0)

                    # Calculate date difference
                    days_diff = abs((found_date - target_date).days)

                    # Check for context keywords
                    context_keywords, context_boost = self._find_context_keywords(
                        tokens, token, field_name
                    )

                    # Check if keyword is in the same token
                    token_lower = token_text.lower()
                    inline_keywords = []
                    for keyword in CONTEXT_KEYWORDS.get(field_name, []):
                        if keyword in token_lower:
                            inline_keywords.append(keyword)

                    date_candidates.append({
                        'token': token,
                        'date': found_date,
                        'date_str': date_str,
                        'matched_text': token_text,
                        'days_diff': days_diff,
                        'context_keywords': context_keywords + inline_keywords,
                        'context_boost': context_boost + (0.1 if inline_keywords else 0),
                        'same_year_month': (found_date.year == target_date.year and
                                           found_date.month == target_date.month),
                    })
                except ValueError:
                    continue

        if not date_candidates:
            return matches

        # Score and rank candidates
        for candidate in date_candidates:
            score = 0.0

            # Strategy 1: Same year-month gets higher score
            if candidate['same_year_month']:
                score = 0.7
                # Bonus if day is close
                if candidate['days_diff'] <= 7:
                    score = 0.75
                if candidate['days_diff'] <= 3:
                    score = 0.8
            # Strategy 2: Nearby dates (within 14 days)
            elif candidate['days_diff'] <= 14:
                score = 0.6
            elif candidate['days_diff'] <= 30:
                score = 0.55
            else:
                # Too far apart, skip unless has strong context
                if not candidate['context_keywords']:
                    continue
                score = 0.5

            # Strategy 3: Boost with context keywords
            score = min(1.0, score + candidate['context_boost'])

            # For InvoiceDate, prefer dates that appear near invoice-related keywords
            # For InvoiceDueDate, prefer dates near due-date keywords
            if candidate['context_keywords']:
                score = min(1.0, score + 0.05)

            if score >= self.min_score_threshold:
                matches.append(Match(
                    field=field_name,
                    value=candidate['date_str'],
                    bbox=candidate['token'].bbox,
                    page_no=candidate['token'].page_no,
                    score=score,
                    matched_text=candidate['matched_text'],
                    context_keywords=candidate['context_keywords']
                ))

        # Sort by score and return best matches
        matches.sort(key=lambda m: m.score, reverse=True)

        # Only return the best match to avoid multiple labels for same field
        return matches[:1] if matches else []

    def _find_context_keywords(
        self,
        tokens: list[TokenLike],
        target_token: TokenLike,
        field_name: str
    ) -> tuple[list[str], float]:
        """
        Find context keywords near the target token.

        Uses spatial index for O(1) average lookup instead of O(n) scan.
        """
        keywords = CONTEXT_KEYWORDS.get(field_name, [])
        if not keywords:
            return [], 0.0

        found_keywords = []

        # Use spatial index for efficient nearby token lookup
        if self._token_index:
            nearby_tokens = self._token_index.find_nearby(target_token, self.context_radius)
            for token in nearby_tokens:
                # Use cached lowercase text
                token_lower = self._token_index.get_text_lower(token)
                for keyword in keywords:
                    if keyword in token_lower:
                        found_keywords.append(keyword)
        else:
            # Fallback to O(n) scan if no index available
            target_center = (
                (target_token.bbox[0] + target_token.bbox[2]) / 2,
                (target_token.bbox[1] + target_token.bbox[3]) / 2
            )

            for token in tokens:
                if token is target_token:
                    continue

                token_center = (
                    (token.bbox[0] + token.bbox[2]) / 2,
                    (token.bbox[1] + token.bbox[3]) / 2
                )

                distance = (
                    (target_center[0] - token_center[0]) ** 2 +
                    (target_center[1] - token_center[1]) ** 2
                ) ** 0.5

                if distance <= self.context_radius:
                    token_lower = token.text.lower()
                    for keyword in keywords:
                        if keyword in token_lower:
                            found_keywords.append(keyword)

        # Calculate boost based on keywords found
        # Increased boost to better differentiate matches with/without context
        boost = min(0.25, len(found_keywords) * 0.10)
        return found_keywords, boost

    def _tokens_on_same_line(self, token1: TokenLike, token2: TokenLike) -> bool:
        """Check if two tokens are on the same line."""
        # Check vertical overlap
        y_overlap = min(token1.bbox[3], token2.bbox[3]) - max(token1.bbox[1], token2.bbox[1])
        min_height = min(token1.bbox[3] - token1.bbox[1], token2.bbox[3] - token2.bbox[1])
        return y_overlap > min_height * 0.5

    def _parse_amount(self, text: str | int | float) -> float | None:
        """Try to parse text as a monetary amount."""
        # Convert to string first
        text = str(text)

        # First, handle Swedish öre format: "239 00" means 239.00 (239 kr 00 öre)
        # Pattern: digits + space + exactly 2 digits at end
        ore_match = re.match(r'^(\d+)\s+(\d{2})$', text.strip())
        if ore_match:
            kronor = ore_match.group(1)
            ore = ore_match.group(2)
            try:
                return float(f"{kronor}.{ore}")
            except ValueError:
                pass

        # Remove everything after and including parentheses (e.g., "(inkl. moms)")
        text = re.sub(r'\s*\(.*\)', '', text)

        # Remove currency symbols and common suffixes (including trailing dots from "kr.")
        text = re.sub(r'\b(SEK|kr|kronor|öre)\b\.?', '', text, flags=re.IGNORECASE)
        text = re.sub(r'[:-]', '', text)

        # Remove spaces (thousand separators) but be careful with öre format
        text = text.replace(' ', '').replace('\xa0', '')

        # Handle comma as decimal separator
        # Swedish format: "500,00" means 500.00
        # Need to handle cases like "500,00." (after removing "kr.")
        if ',' in text:
            # Remove any trailing dots first (from "kr." removal)
            text = text.rstrip('.')
            # Now replace comma with dot
            if '.' not in text:
                text = text.replace(',', '.')

        # Remove any remaining non-numeric characters except dot
        text = re.sub(r'[^\d.]', '', text)

        try:
            return float(text)
        except ValueError:
            return None

    def _deduplicate_matches(self, matches: list[Match]) -> list[Match]:
        """
        Remove duplicate matches based on bbox overlap.

        Uses grid-based spatial hashing to reduce O(n²) to O(n) average case.
        """
        if not matches:
            return []

        # Sort by: 1) score descending, 2) prefer matches with context keywords,
        # 3) prefer upper positions (smaller y) for same-score matches
        # This helps select the "main" occurrence in invoice body rather than footer
        matches.sort(key=lambda m: (
            -m.score,
            -len(m.context_keywords),  # More keywords = better
            m.bbox[1]  # Smaller y (upper position) = better
        ))

        # Use spatial grid for efficient overlap checking
        # Grid cell size based on typical bbox size
        grid_size = 50.0  # pixels
        grid: dict[tuple[int, int], list[Match]] = {}
        unique = []

        for match in matches:
            bbox = match.bbox
            # Calculate grid cells this bbox touches
            min_gx = int(bbox[0] / grid_size)
            min_gy = int(bbox[1] / grid_size)
            max_gx = int(bbox[2] / grid_size)
            max_gy = int(bbox[3] / grid_size)

            # Check for overlap only with matches in nearby grid cells
            is_duplicate = False
            cells_to_check = set()
            for gx in range(min_gx - 1, max_gx + 2):
                for gy in range(min_gy - 1, max_gy + 2):
                    cells_to_check.add((gx, gy))

            for cell in cells_to_check:
                if cell in grid:
                    for existing in grid[cell]:
                        if self._bbox_overlap(bbox, existing.bbox) > 0.7:
                            is_duplicate = True
                            break
                    if is_duplicate:
                        break

            if not is_duplicate:
                unique.append(match)
                # Add to all grid cells this bbox touches
                for gx in range(min_gx, max_gx + 1):
                    for gy in range(min_gy, max_gy + 1):
                        key = (gx, gy)
                        if key not in grid:
                            grid[key] = []
                        grid[key].append(match)

        return unique

    def _bbox_overlap(
        self,
        bbox1: tuple[float, float, float, float],
        bbox2: tuple[float, float, float, float]
    ) -> float:
        """Calculate IoU (Intersection over Union) of two bounding boxes."""
        x1 = max(bbox1[0], bbox2[0])
        y1 = max(bbox1[1], bbox2[1])
        x2 = min(bbox1[2], bbox2[2])
        y2 = min(bbox1[3], bbox2[3])

        if x2 <= x1 or y2 <= y1:
            return 0.0

        intersection = float(x2 - x1) * float(y2 - y1)
        area1 = float(bbox1[2] - bbox1[0]) * float(bbox1[3] - bbox1[1])
        area2 = float(bbox2[2] - bbox2[0]) * float(bbox2[3] - bbox2[1])
        union = area1 + area2 - intersection

        return intersection / union if union > 0 else 0.0


def find_field_matches(
    tokens: list[TokenLike],
    field_values: dict[str, str],
    page_no: int = 0
) -> dict[str, list[Match]]:
    """
    Convenience function to find matches for multiple fields.

    Args:
        tokens: List of tokens from the document
        field_values: Dict of field_name -> value to search for
        page_no: Page number

    Returns:
        Dict of field_name -> list of matches
    """
    from ..normalize import normalize_field

    matcher = FieldMatcher()
    results = {}

    for field_name, value in field_values.items():
        if value is None or str(value).strip() == '':
            continue

        normalized_values = normalize_field(field_name, str(value))
        matches = matcher.find_matches(tokens, field_name, normalized_values, page_no)
        results[field_name] = matches

    return results
