"""Build the unified document: move Camelot bodies into the docling spine.

The matcher classified every region; this pass acts on those records with
docling-core's native mutation API, so no custom serializer is needed:

- `replace` — rebuild each matched docling table's body from the Camelot cells,
  in place, and attach the SoM title/subtitle/units/footnotes. The spine element
  and its reading-order position are untouched.
- `docling_miss` — insert the Camelot table into the spine right after the
  nearest element above it on the page (before the page's first element when the
  table sits at the top), so reading order is preserved.
- `docling_undercount` — delete the docling table(s) in the region and insert the
  finer-grained Camelot tables in their place.
- `image_table` — no graft. docling already holds the OCR'd table. The region
  still takes part in the region-text dedup below, so docling text items inside
  it that the SoM table's text accounts for are deleted.
- `chart` — no graft. docling already holds the picture. The matched picture's
  meta records that Set-of-Mark read it, under `READ_BY_FIELD`.
- `som_miss` — no change, surfaced as an error. A table docling found but SoM did
  not is never synthesized from docling.

The source document is never mutated: `build_unified_document` deep-copies it
and mutates the copy.

Deleting and inserting tables renumbers every later table's `self_ref`, so after
all mutation the pass rewrites each match's `docling_table_refs` to the grafted
tables' final positions. The matches ship in the fusion report beside the
unified document, and a consumer resolving a ref against that document must land
on the table the match is about — a stale ref silently hands it a neighboring
table's identity (its section heading, its position in the flow).
"""

from __future__ import annotations

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

from docling_core.types.doc.base import BoundingBox, CoordOrigin
from docling_core.types.doc.document import (
    DocItem,
    DoclingDocument,
    FloatingMeta,
    NodeItem,
    PictureMeta,
    ProvenanceItem,
    TableCell,
    TableData,
    TableItem,
)
from docling_core.types.doc.labels import DocItemLabel
from loguru import logger

from quber.core.extractors.base import ExtractedTable
from quber.core.extractors.set_of_mark.merge_grounding import markdown_rows
from quber.core.fusion.models import RegionMatch
from quber.core.printed_text import printed_key

#: Where an element records which readers have read its region, and what each
#: produced. A later reader consults it rather than judging the region again.
READ_BY_FIELD = "quber__read_by"

#: The table engine that extracts from the PDF text layer.
SET_OF_MARK = "set-of-mark"

NormBox = Tuple[float, float, float, float]
Box = Tuple[float, float, float, float]


def build_unified_document(
    document: DoclingDocument,
    som_tables: List[ExtractedTable],
    matches: List[RegionMatch],
    page_dims: Dict[int, Tuple[float, float]],
) -> Tuple[DoclingDocument, List[str]]:
    """Graft the Camelot bodies into a clone of `document` per the matches.

    Returns the unified document and a list of error strings: one per `som_miss`
    region (a table docling found that SoM did not match), one per `som_merged`
    region the split pass left unresolved, and one per `docling_miss` or
    `docling_undercount` SoM table with no Camelot body, which stays out of the
    unified document. The input document is not mutated.
    """
    unified = document.model_copy(deep=True)
    tables_by_ref = {t.self_ref: t for t in unified.tables}
    errors: List[str] = []

    # Which TableItem(s) in the unified document realize each match. Deleting
    # and inserting tables renumbers every later table's self_ref, so refs
    # recorded against the pre-graft document go stale; the objects are
    # tracked here and each match's refs are rewritten to their final
    # positions once all mutation is done. Surviving tables map through
    # `tables_by_ref` (the graft mutates them in place, never re-creates
    # them); deleted-and-replaced regions map to the inserted tables.
    realized: List[Tuple[RegionMatch, List[Tuple[str, Optional[TableItem]]]]] = []

    for match in matches:
        surviving = [(r, tables_by_ref.get(r)) for r in match.docling_table_refs]
        if match.kind == "replace":
            _apply_replace(unified, tables_by_ref, match, som_tables, page_dims)
            realized.append((match, surviving))
        elif match.kind == "docling_miss":
            inserted, errs = _apply_insert(unified, match, som_tables, page_dims)
            errors.extend(errs)
            realized.append((match, [("", t) for t in inserted]))
        elif match.kind == "docling_undercount":
            inserted, errs = _apply_undercount(unified, tables_by_ref, match, som_tables, page_dims)
            errors.extend(errs)
            realized.append((match, [("", t) for t in inserted]))
        elif match.kind == "som_merged":
            # The split pass should have refined this region into a 1:1 replace
            # before grafting. If a residual som_merged reaches here the split was
            # declined or failed; docling's table count stands and its bodies are
            # left untouched rather than grafting a fused body over split tables.
            errors.append(
                f"page {match.page}: som_merged not resolved by split "
                f"({len(match.som_indices)} SoM vs {len(match.docling_table_refs)} docling); "
                "docling tables left untouched"
            )
            realized.append((match, surviving))
        elif match.kind == "som_miss":
            errors.append(
                f"page {match.page}: docling table {match.docling_table_refs} has no SoM match "
                "(SoM/Camelot missed a table docling found)"
            )
            realized.append((match, surviving))
        elif match.kind == "chart":
            _mark_vetted(unified, match, som_tables)
            realized.append((match, surviving))
        else:
            # image_table grafts nothing here, but its docling refs still
            # shift when another region's graft deletes a table.
            realized.append((match, surviving))

    _dedup_table_region_text(unified, matches, som_tables, page_dims)
    _rewrite_report_refs(unified, realized)
    return unified, errors


def _rewrite_report_refs(
    unified: DoclingDocument,
    realized: List[Tuple[RegionMatch, List[Tuple[str, Optional[TableItem]]]]],
) -> None:
    """Point every match's `docling_table_refs` at the unified document.

    Final refs are read off each tracked object's position in the tables
    array — the same positions serialization writes — so the rewrite cannot
    disagree with the document on disk. A ref that never resolved to a table
    is kept verbatim rather than dropped: it still names what the matcher saw,
    and dropping it would hide the mismatch.
    """
    final_ref = {id(t): f"#/tables/{i}" for i, t in enumerate(unified.tables)}
    for match, items in realized:
        refs: List[str] = []
        for original, item in items:
            ref = final_ref.get(id(item)) if item is not None else None
            if ref is None and not original:
                continue  # an inserted table later deleted; nothing to name
            refs.append(ref if ref is not None else original)
        match.docling_table_refs = refs


#: docling labels that are loose body/attribution text, safe to drop when a fused
#: table already represents them. Section headers, titles, and page headers/footers
#: are deliberately excluded so the spine stays intact.
_REDUNDANT_LABELS = {
    DocItemLabel.TEXT,
    DocItemLabel.PARAGRAPH,
    DocItemLabel.CAPTION,
    DocItemLabel.FOOTNOTE,
}


def _mark_vetted(document: DoclingDocument, match: RegionMatch, som_tables: List[ExtractedTable]) -> None:
    """Record on a picture that the table engine has already read its region.

    A `chart` match is a table the engine extracted from the text layer whose
    region overlaps a picture the parse detected. That is routinely a real table
    printed beside a chart, both inside the one region the engine bounded: the
    engine read the table correctly and drew its box around the pair.

    Nothing about the document changes. What is recorded is which reader has read
    the region and what it produced, so a later reader leaves it alone instead of
    stating the same table twice. The alternative is for that later step to
    recompute the overlap against an artifact it is not handed, which is the same
    judgement made again from less.

    The tag names the reader rather than the outcome. A region already read is
    the general condition; which tool did the reading is what a caller needs to
    weigh it, and another tool added later says so the same way.
    """
    produced = [som_tables[i].table_id for i in match.som_indices if som_tables[i].table_id]
    by_ref = {p.self_ref: p for p in document.pictures}
    for ref in match.docling_picture_refs:
        picture = by_ref.get(ref)
        if picture is None:
            continue
        base = picture.meta or PictureMeta()
        read_by = list(getattr(base, READ_BY_FIELD, None) or [])
        read_by.append({"reader": SET_OF_MARK, "produced": produced})
        picture.meta = base.model_copy(update={READ_BY_FIELD: read_by})
        logger.info("Fusion: picture {} read by {} ({})", ref, SET_OF_MARK, ", ".join(produced))


#: A docling item inside a table's region is a duplicate of the grafted table
#: only when the table's own text accounts for its words. The two extractors
#: render the same printed line with small differences (a curly against a
#: straight apostrophe, a hyphen dropped at a line break), so a duplicate can
#: miss a token or two; prose never comes close.
_COVERAGE_MIN = 0.98
_UNMATCHED_TOLERANCE = 1

_TOKEN_RE = re.compile(r"[a-z0-9]+")


def _dedup_table_region_text(
    unified: DoclingDocument,
    matches: List[RegionMatch],
    som_tables: List[ExtractedTable],
    page_dims: Dict[int, Tuple[float, float]],
) -> None:
    """Drop docling body text the grafted tables now represent.

    docling emits a table's cell text — and its title/units/footnote lines — both
    inside the TableItem and as loose TextItems in the reading-order flow, so the
    unified output would show each fused table once as a clean table and again as
    scattered fragments. For every `replace`, `docling_miss`, `docling_undercount`
    and `image_table` region, consider the docling TextItems
    (text/paragraph/caption/footnote) whose center falls inside the SoM region,
    and delete each one whose words the SoM table's own text accounts for (its
    cells, title, subtitle, units, and footnotes); the grafted body plus the
    structured caption/footnotes is then the single representation.

    An `image_table` region grafts no Camelot body and attaches no SoM caption or
    footnotes, so a docling text item there that the SoM text accounts for is
    deleted with nothing written in its place. `chart` and `som_merged` regions
    are not deduplicated.

    Position alone is never grounds for deletion. The locator's region is the
    vision model's box, and it reaches past the table body: it is drawn to
    enclose the footnote lines below the grid, and it can take in what is printed
    under those too. Text inside the box that the table does not carry is not
    table text; it is the box being too big. A paragraph stating what share of a
    loan book floats, a sentence introducing the next table, a footnote whose
    text continues on the next page and so exceeds what the table carries: each
    stays in the document as the text it is. The separation is logged.

    Section headers and page headers/footers are never removed, so the spine
    survives. The attribution captions/footnotes added during the graft carry no
    provenance box, so they are never matched here.
    """
    regions_by_page: Dict[int, List[Tuple[Box, ExtractedTable]]] = {}
    for match in matches:
        if match.kind not in ("replace", "docling_miss", "docling_undercount", "image_table"):
            continue
        for i in match.som_indices:
            som = som_tables[i]
            if som.som_region is None:
                continue
            width, height = page_dims.get(som.page, (612.0, 792.0))
            x1, y1, x2, y2 = som.som_region
            region = (min(x1, x2) * width, min(y1, y2) * height, max(x1, x2) * width, max(y1, y2) * height)
            regions_by_page.setdefault(som.page, []).append((region, som))

    if not regions_by_page:
        return

    bags: Dict[int, Counter[str]] = {}
    victims: List[NodeItem] = []
    for item in unified.texts:
        if item.label not in _REDUNDANT_LABELS or not item.prov:
            continue
        page_no = item.prov[0].page_no
        regions = regions_by_page.get(page_no)
        if not regions:
            continue
        _, height = page_dims.get(page_no, (612.0, 792.0))
        bbox = item.prov[0].bbox
        if bbox.coord_origin == CoordOrigin.TOPLEFT:
            box = (bbox.l, bbox.t, bbox.r, bbox.b)
        else:
            box = (bbox.l, height - bbox.t, bbox.r, height - bbox.b)
        enclosing = [som for region, som in regions if _center_in(box, region)]
        if not enclosing:
            continue
        covered = False
        for som in enclosing:
            bag = bags.get(id(som))
            if bag is None:
                bag = bags[id(som)] = _table_text_bag(som)
            if _covered_by(item.text, bag):
                covered = True
                break
        if covered:
            victims.append(item)
        else:
            logger.info(
                "Fusion: page {}: {} {} lies in the region of table {} but is not table text; kept: {!r}",
                page_no,
                item.label.value,
                item.self_ref,
                enclosing[0].table_id or enclosing[0].title,
                " ".join(item.text.split()[:12]),
            )

    if victims:
        unified.delete_items(node_items=victims)


def _table_text_bag(table: ExtractedTable) -> Counter[str]:
    """Every word the grafted table carries, with multiplicity: its cells, title,
    subtitle, units, and footnote markers and bodies."""
    parts = [table.title, table.subtitle, table.units]
    for fn in table.footnotes:
        parts.extend([fn.marker, fn.text])
    for row in markdown_rows(table.markdown):
        parts.extend(row)
    return Counter(_TOKEN_RE.findall(" ".join(p for p in parts if p).lower()))


def _covered_by(text: str, bag: Counter[str]) -> bool:
    """Whether the table's words account for `text`: at most one token of it is
    missing from the bag, or all but a rendering-noise fraction are present."""
    tokens = _TOKEN_RE.findall(text.lower())
    if not tokens:
        return True
    remaining = bag.copy()
    matched = 0
    for tok in tokens:
        if remaining[tok] > 0:
            remaining[tok] -= 1
            matched += 1
    unmatched = len(tokens) - matched
    return unmatched <= _UNMATCHED_TOLERANCE or matched / len(tokens) >= _COVERAGE_MIN


def _center_in(box: Box, region: Box) -> bool:
    cx, cy = (box[0] + box[2]) / 2, (box[1] + box[3]) / 2
    x0, y0 = min(region[0], region[2]), min(region[1], region[3])
    x1, y1 = max(region[0], region[2]), max(region[1], region[3])
    return x0 <= cx <= x1 and y0 <= cy <= y1


def _apply_replace(
    unified: DoclingDocument,
    tables_by_ref: Dict[str, TableItem],
    match: RegionMatch,
    som_tables: List[ExtractedTable],
    page_dims: Dict[int, Tuple[float, float]],
) -> None:
    """Rebuild each matched docling table's body from its paired Camelot table."""
    for som_idx, ref in _pair_by_vertical_order(match, som_tables, tables_by_ref):
        table_item = tables_by_ref.get(ref)
        if table_item is None:
            continue
        som = som_tables[som_idx]
        markdown = (som.markdown or "").strip()
        if not markdown:
            # A matched-but-empty Camelot body would blank a docling table that has
            # OCR'd content; keep docling's body in that case.
            continue
        table_item.data = markdown_to_table_data(markdown)
        attach_attribution(unified, table_item, som, page_dims)


def _apply_insert(
    unified: DoclingDocument,
    match: RegionMatch,
    som_tables: List[ExtractedTable],
    page_dims: Dict[int, Tuple[float, float]],
) -> Tuple[List[TableItem], List[str]]:
    """Insert a Camelot table docling missed, at its reading-order position.

    Returns the inserted tables and an error for any table that has no Camelot
    body: a table SoM located but neither docling nor Camelot could read (a
    scanned table on a page docling did not detect). It is surfaced, never
    silently dropped.
    """
    tables: List[TableItem] = []
    errors: List[str] = []
    for som_idx in match.som_indices:
        som = som_tables[som_idx]
        markdown = (som.markdown or "").strip()
        if not markdown:
            errors.append(
                f"page {som.page}: SoM located a table docling missed but Camelot read no "
                f"body (title={som.title!r}); table not in the unified document"
            )
            continue
        data = markdown_to_table_data(markdown)
        prov = _som_prov(som, page_dims)
        sibling, after = reading_order_anchor(unified, som, page_dims)
        if sibling is None:
            inserted = unified.add_table(data=data, prov=prov)
        else:
            inserted = unified.insert_table(sibling=sibling, data=data, prov=prov, after=after)
        attach_attribution(unified, inserted, som, page_dims)
        tables.append(inserted)
    return tables, errors


def _apply_undercount(
    unified: DoclingDocument,
    tables_by_ref: Dict[str, TableItem],
    match: RegionMatch,
    som_tables: List[ExtractedTable],
    page_dims: Dict[int, Tuple[float, float]],
) -> Tuple[List[TableItem], List[str]]:
    """Delete the docling table(s) in the region and insert the finer Camelot tables.

    docling under-counted (dropped or merged a complex table); Camelot's finer
    count is trusted. The Camelot tables are inserted after the spine element
    above the region, in vertical order. Returns the inserted tables and an
    error for any Camelot table with no body, so a dropped sub-table is
    surfaced rather than lost.
    """
    tables: List[TableItem] = []
    errors: List[str] = []
    doomed: List[NodeItem] = [tables_by_ref[r] for r in match.docling_table_refs if r in tables_by_ref]
    anchor_som = min(
        (som_tables[i] for i in match.som_indices),
        key=lambda t: _vertical_key(t),
        default=None,
    )
    sibling: Optional[NodeItem] = None
    after = True
    if anchor_som is not None:
        sibling, after = reading_order_anchor(unified, anchor_som, page_dims, exclude=doomed)

    if doomed:
        unified.delete_items(node_items=doomed)

    last: Optional[TableItem] = None
    for som_idx in sorted(match.som_indices, key=lambda i: _vertical_key(som_tables[i])):
        som = som_tables[som_idx]
        markdown = (som.markdown or "").strip()
        if not markdown:
            errors.append(
                f"page {som.page}: a sub-table of a docling-merged region had no Camelot body "
                f"(title={som.title!r}); not in the unified document"
            )
            continue
        data = markdown_to_table_data(markdown)
        prov = _som_prov(som, page_dims)
        if last is not None:
            last = unified.insert_table(sibling=last, data=data, prov=prov, after=True)
        elif sibling is not None:
            last = unified.insert_table(sibling=sibling, data=data, prov=prov, after=after)
        else:
            last = unified.add_table(data=data, prov=prov)
        attach_attribution(unified, last, som, page_dims)
        tables.append(last)
    return tables, errors


def attach_attribution(
    unified: DoclingDocument,
    table_item: TableItem,
    som: ExtractedTable,
    page_dims: Dict[int, Tuple[float, float]],
) -> None:
    """Carry the SoM identity, cell geometry, title, subtitle, units (captions)
    and footnotes onto a table.

    The SoM table's `table_id` and `content_fingerprint` bind onto the docling
    item through `meta` (docling's sanctioned extension point — the meta
    model allows extra fields, so they serialize with the document), and every
    grafted cell carries its measured box where the provenance record can pin
    one. SoM is the vetted, vision-grounded side, so its attribution takes
    precedence over whatever docling attached:

    - the sentence that introduces the table, its printed name and its units
      become CAPTION nodes referenced from the table (top-to-bottom order; see
      `caption_lines`). The table serializer emits captions inline, so they
      render above the table in markdown/HTML.
    - each footnote is inserted as a FOOTNOTE node in the body right after the
      table, in order. docling's markdown serializer does NOT emit a table's
      `footnotes` refs, so a referenced footnote would round-trip in JSON but
      vanish from the rendered markdown; a body node after the table renders as a
      paragraph below it and keeps the reading order.

    Both kinds carry no provenance box, so the region-text dedup that strips
    docling's loose copies never matches them.
    """
    if som.table_id:
        base = table_item.meta or FloatingMeta()
        table_item.meta = base.model_copy(
            update={
                "quber__table_id": som.table_id,
                "quber__content_fingerprint": som.content_fingerprint,
            }
        )
    _graft_cell_geometry(table_item, som, page_dims)

    caption_refs = []
    for text in caption_lines(unified, som):
        caption = unified.add_text(label=DocItemLabel.CAPTION, text=text)
        caption_refs.append(caption.get_ref())
    if caption_refs:
        table_item.captions = caption_refs

    anchor: NodeItem = table_item
    for note in som.footnotes:
        # Render the footnote the way the page prints it: its own marker,
        # then its text. An unmarked general note has no marker to lead with.
        text = f"{note.marker} {note.text}".strip() if note.marker else note.text
        if not text.strip():
            continue
        anchor = unified.insert_text(label=DocItemLabel.FOOTNOTE, text=text, sibling=anchor, after=True)


#: docling text items that can hold the sentence introducing a table.
_CAPTION_SOURCE_LABELS = {
    DocItemLabel.TEXT,
    DocItemLabel.PARAGRAPH,
    DocItemLabel.CAPTION,
    DocItemLabel.SECTION_HEADER,
}


def caption_lines(unified: DoclingDocument, som: ExtractedTable) -> List[str]:
    """The header lines a table carries, top to bottom: the sentence that
    introduces it, its printed name, its units.

    The introducing sentence is the docling paragraph on the table's page that
    contains the caption the vetting agent copied. Two tables printed side by
    side under one sentence then carry the same whole sentence, whichever words
    each copy kept, and a bold lead-in the copy left out comes back with the
    paragraph. When no such paragraph exists, the copied caption stands. The
    fusion graft calls this before its region dedup runs, so docling's copy of
    the sentence is still in the document at that point. A name that repeats the
    sentence is not written twice.

    Page furniture is never a header line. A running header or footer the
    parse labeled as such ("Table of Contents", the statement banner) is
    printed on the page, so the printed-text check upstream lets it through
    when the agent copies it; the parse's own label is what rules it out.
    """
    furniture = _furniture_keys(unified, som.page)
    lines: List[str] = []
    caption = (som.caption or "").strip()
    if caption and printed_key(caption) not in furniture:
        lines.append(_paragraph_containing(unified, som.page, caption) or caption)
    title = (som.title or "").strip()
    if title and printed_key(title) in furniture:
        title = ""
    if title and not (lines and printed_key(title) in printed_key(lines[0])):
        lines.append(title)
    # Artifacts from earlier runs still carry a subtitle; new runs leave it empty.
    if som.subtitle and som.subtitle.strip():
        lines.append(som.subtitle.strip())
    if som.units and som.units.strip():
        lines.append(som.units.strip())
    return lines


def _furniture_keys(unified: DoclingDocument, page: int) -> set[str]:
    """The printed keys of the page's running headers and footers, as the parse labeled them."""
    keys: set[str] = set()
    for item in unified.texts:
        if (
            item.label in (DocItemLabel.PAGE_HEADER, DocItemLabel.PAGE_FOOTER)
            and item.prov
            and item.prov[0].page_no == page
        ):
            key = printed_key(item.text)
            if key:
                keys.add(key)
    return keys


def _paragraph_containing(unified: DoclingDocument, page: int, caption: str) -> Optional[str]:
    """The text of the first docling item on `page` whose printed words contain
    `caption`, whitespace collapsed; None when no item does. Items without a
    page box are skipped, which excludes the caption nodes the graft adds."""
    key = printed_key(caption)
    for item in unified.texts:
        if item.label not in _CAPTION_SOURCE_LABELS or not item.prov or item.prov[0].page_no != page:
            continue
        if key in printed_key(item.text):
            return " ".join(item.text.split())
    return None


def markdown_to_table_data(markdown: str) -> TableData:
    """Parse a pipe-delimited markdown table into a docling `TableData` grid.

    The first content row is treated as the column header. The markdown separator
    row (`| --- | --- |`) is dropped. Ragged rows are padded to the widest row so
    the grid stays rectangular.
    """
    rows = markdown_rows(markdown)
    if not rows:
        return TableData(table_cells=[], num_rows=0, num_cols=0)

    num_cols = max(len(r) for r in rows)
    num_rows = len(rows)
    table_cells: List[TableCell] = []
    for r, row in enumerate(rows):
        padded = row + [""] * (num_cols - len(row))
        for c, text in enumerate(padded):
            table_cells.append(
                TableCell(
                    text=text,
                    start_row_offset_idx=r,
                    end_row_offset_idx=r + 1,
                    start_col_offset_idx=c,
                    end_col_offset_idx=c + 1,
                    row_span=1,
                    col_span=1,
                    column_header=(r == 0),
                )
            )
    return TableData(table_cells=table_cells, num_rows=num_rows, num_cols=num_cols)


def _graft_cell_geometry(
    table_item: TableItem, som: ExtractedTable, page_dims: Dict[int, Tuple[float, float]]
) -> None:
    """Carry the already-resolved cell geometry onto the grafted TableCells.

    `corrected_grid` is the complete cell-level view the grounding stage
    produced — same markdown, same row/col addressing — so this is pure
    carriage: read each cell's box and convert it from the normalized top-left
    frame to docling's bottom-left points, the same convention `_som_prov`
    uses for the table-level box. No matching or reconciliation happens here;
    a cell the grounding stage could not pin arrives with box=None and stays
    without one.
    """
    grid = som.corrected_grid
    if not grid:
        return
    width, height = page_dims.get(som.page, (612.0, 792.0))
    for cell in table_item.data.table_cells:
        r, c = cell.start_row_offset_idx, cell.start_col_offset_idx
        box = grid[r][c].box if r < len(grid) and c < len(grid[r]) else None
        if box is None:
            continue
        x1, y1, x2, y2 = box
        cell.bbox = BoundingBox(
            l=min(x1, x2) * width,
            r=max(x1, x2) * width,
            t=(1.0 - min(y1, y2)) * height,
            b=(1.0 - max(y1, y2)) * height,
            coord_origin=CoordOrigin.BOTTOMLEFT,
        )


def _pair_by_vertical_order(
    match: RegionMatch,
    som_tables: List[ExtractedTable],
    tables_by_ref: Dict[str, TableItem],
) -> List[Tuple[int, str]]:
    """Pair SoM tables to docling tables in a region by top-to-bottom order."""
    soms = sorted(match.som_indices, key=lambda i: _vertical_key(som_tables[i]))
    refs = sorted(
        (r for r in match.docling_table_refs if r in tables_by_ref),
        key=lambda r: _table_top(tables_by_ref[r]),
    )
    return list(zip(soms, refs, strict=False))


def _vertical_key(table: ExtractedTable) -> float:
    region = table.som_region
    if region is not None:
        return min(region[1], region[3])
    if table.bbox is not None:
        return -max(table.bbox[1], table.bbox[3])  # bottom-left points: larger y is higher
    return 0.0


def _table_top(table: TableItem) -> float:
    if not table.prov:
        return 0.0
    bbox = table.prov[0].bbox
    if bbox.coord_origin == CoordOrigin.TOPLEFT:
        return bbox.t
    return -max(bbox.t, bbox.b)  # bottom-left: larger y is higher on the page


def _som_prov(som: ExtractedTable, page_dims: Dict[int, Tuple[float, float]]) -> Optional[ProvenanceItem]:
    """A ProvenanceItem for an inserted Camelot table, box in bottom-left points."""
    width, height = page_dims.get(som.page, (612.0, 792.0))
    region = som.som_region
    if region is None:
        return None
    x1, y1, x2, y2 = region
    bbox = BoundingBox(
        l=min(x1, x2) * width,
        r=max(x1, x2) * width,
        t=(1.0 - min(y1, y2)) * height,
        b=(1.0 - max(y1, y2)) * height,
        coord_origin=CoordOrigin.BOTTOMLEFT,
    )
    return ProvenanceItem(page_no=som.page, bbox=bbox, charspan=(0, 0))


def reading_order_anchor(
    document: DoclingDocument,
    som: ExtractedTable,
    page_dims: Dict[int, Tuple[float, float]],
    exclude: Optional[List[NodeItem]] = None,
) -> Tuple[Optional[NodeItem], bool]:
    """Find the spine element to anchor an inserted table to.

    Returns (sibling, after). The sibling is the last element above the table on
    its page, with after=True. When the table sits above every element on the
    page, returns that page's first element with after=False. Returns (None, True)
    when the page has no other anchorable element (caller falls back to add_table).
    """
    _width, height = page_dims.get(som.page, (612.0, 792.0))
    region = som.som_region
    if region is None:
        return None, True
    table_top = min(region[1], region[3]) * height  # top-left points

    excluded = {id(e) for e in (exclude or [])}
    on_page: List[Tuple[float, NodeItem]] = []
    for item, _level in document.iterate_items():
        if not isinstance(item, DocItem) or id(item) in excluded:
            continue
        prov = item.prov[0] if item.prov else None
        if prov is None or prov.page_no != som.page:
            continue
        top = _item_top_left_top(prov, height)
        on_page.append((top, item))

    if not on_page:
        return None, True

    on_page.sort(key=lambda x: x[0])
    above = [item for top, item in on_page if top < table_top]
    if above:
        return above[-1], True
    return on_page[0][1], False


def _item_top_left_top(prov: ProvenanceItem, page_height: float) -> float:
    bbox = prov.bbox
    if bbox.coord_origin == CoordOrigin.TOPLEFT:
        return bbox.t
    return page_height - max(bbox.t, bbox.b)