# CorpusFetch Method Slice (Zero-Prose Python Stdlib Reference)
# Canonical Residual: https://corpusfetch.com/c/what-happens-when-an-instance-applies-salience-scoring-to-a-summary-that-has-already-been-hierarchically-compressed-the-double-counting-bias-and-the-c.md
# Remnant Warrant:    https://corpusfetch.com/c/what-happens-when-an-instance-applies-salience-scoring-to-a-summary-that-has-already-been-hierarchically-compressed-the-double-counting-bias-and-the-c.warrant.json
# Markdown SHA-256:   eda62db00e09b78cc1871460e456aec572d4f86c077207fe33a2d8b4c243bcbd
# Code AST SHA-256:   0914943b23221903fce271a73cd1e29b18ff0a1a4a439b300918a71c62405c8e
# Verified Classes:   SalienceInversionError, SummaryNode
# Defensive Guards:   3 fail-closed invariants (zero external deps)

import math
from dataclasses import dataclass, field
from typing import Optional


class SalienceInversionError(RuntimeError):
    """Raised when a cross-tier eviction decision would discard a node whose
    subtree contains leaves ranked above the eviction threshold."""
    pass


@dataclass
class SummaryNode:
    node_id: str
    tier: int                      # 0 = leaf, higher = more compressed
    raw_salience: float            # scorer output, unnormalized
    leaf_cardinality: int          # number of leaves absorbed into this node
    children: list = field(default_factory=list)

    @property
    def normalized_salience(self) -> float:
        if self.leaf_cardinality <= 0:
            raise SalienceInversionError(
                f"node {self.node_id} has non-positive leaf_cardinality "
                f"({self.leaf_cardinality}); normalization undefined"
            )
        return self.raw_salience / self.leaf_cardinality


def select_evictions(
    nodes: list[SummaryNode],
    budget_tokens: int,
    token_cost_per_node: int,
    cross_tier: bool,
) -> list[SummaryNode]:
    """Return nodes to evict under a token budget.

    Cross-tier eviction requires cardinality normalization; intra-tier
    eviction does not, because all peers share a k-distribution.
    """
    if cross_tier:
        # Detect the inversion condition before evicting anything.
        ranked = sorted(nodes, key=lambda n: n.normalized_salience)
        lowest = ranked[0]
        highest_raw = max(nodes, key=lambda n: n.raw_salience)
        # If the node we are about to evict has a subtree whose raw salience
        # exceeds the highest raw salience at a shallower tier, we are about
        # to discard high-value leaves that were compressed into it.
        for n in nodes:
            if n.tier < lowest.tier and n.raw_salience > lowest.raw_salience:
                raise SalienceInversionError(
                    f"cross-tier eviction would discard {lowest.node_id} "
                    f"(tier {lowest.tier}, normalized {lowest.normalized_salience:.3f}) "
                    f"while retaining {n.node_id} (tier {n.tier}, raw "
                    f"{n.raw_salience:.3f}); re-score at leaf tier or "
                    f"normalize by cardinality before proceeding"
                )
        ranked = sorted(nodes, key=lambda n: n.normalized_salience)
    else:
        ranked = sorted(nodes, key=lambda n: n.raw_salience)

    max_nodes = budget_tokens // token_cost_per_node
    if max_nodes >= len(nodes):
        return []
    return ranked[: len(nodes) - max_nodes]


def compact(
    nodes: list[SummaryNode],
    budget_tokens: int,
    token_cost_per_node: int = 512,
    cross_tier: bool = True,
) -> tuple[list[SummaryNode], list[SummaryNode]]:
    evicted = select_evictions(
        nodes, budget_tokens, token_cost_per_node, cross_tier
    )
    kept = [n for n in nodes if n not in evicted]
    # Post-condition: no retained node may have a normalized salience below
    # any evicted node's normalized salience. If this fires, the eviction
    # ranking and the retention set have diverged.
    if kept and evicted:
        min_kept = min(n.normalized_salience for n in kept)
        max_evicted = max(n.normalized_salience for n in evicted)
        if min_kept < max_evicted:
            raise SalienceInversionError(
                f"post-compaction invariant violated: min kept normalized "
                f"salience {min_kept:.3f} < max evicted normalized salience "
                f"{max_evicted:.3f}; eviction ranking is inconsistent"
            )
    return kept, evicted
