"""Routing tree builder for contextweaver.

Converts a flat list of :class:`~contextweaver.types.SelectableItem` objects
into a :class:`~contextweaver.routing.graph.ChoiceGraph` by grouping items
under intermediate nodes.  Three grouping strategies are tried in priority
order:

1. **Namespace grouping** — group by first unused namespace dot-segment.
2. **Clustering** — farthest-first Jaccard seeding + nearest assignment.
3. **Alphabetical fallback** — sort by name and split into labelled chunks.

The builder guarantees that every node in the resulting graph has at most
*max_children* children.  Empty input raises
:class:`~contextweaver.exceptions.GraphBuildError`.
"""

from __future__ import annotations

import logging
import math
from collections import defaultdict

from contextweaver.exceptions import GraphBuildError
from contextweaver.profiles import RoutingConfig
from contextweaver.protocols import ClusteringEngine
from contextweaver.routing.graph import ChoiceGraph
from contextweaver.routing.labeler import KeywordLabeler
from contextweaver.routing.manifest import GraphManifest
from contextweaver.routing.registry import EngineRegistry, default_registry
from contextweaver.types import SelectableItem

logger = logging.getLogger("contextweaver.routing")


class TreeBuilder:
    """Build a bounded :class:`ChoiceGraph` from a list of items.

    The tree guarantees every node has at most *max_children* children.
    The builder is deterministic: identical inputs always produce identical
    graphs.

    Args:
        max_children: Maximum children per node (default 20).
        labeler: Optional :class:`KeywordLabeler` instance.
        target_group_size: Hint for cluster sizes; defaults to *max_children*.
        routing_config: Keyword-only.  Optional :class:`~contextweaver.config.RoutingConfig`
            that sets *max_children*.  When provided, *max_children* is
            replaced by the value from this config object.  In every
            build, the effective *max_children* is recorded under
            ``manifest.extra["max_children"]``.
        clustering: Keyword-only.  Optional
            :class:`~contextweaver.protocols.ClusteringEngine` instance.
            Used by the clustering grouping strategy.  Takes precedence
            over *engine_registry*.
        engine_registry: Keyword-only.  Optional
            :class:`~contextweaver.routing.registry.EngineRegistry`
            used to resolve the clustering engine when *clustering* is
            ``None``.  Defaults to
            :data:`~contextweaver.routing.registry.default_registry`.

    Raises:
        GraphBuildError: If *max_children* < 1 or *target_group_size* < 1.
    """

    def __init__(
        self,
        max_children: int = 20,
        labeler: KeywordLabeler | None = None,
        target_group_size: int | None = None,
        *,
        routing_config: RoutingConfig | None = None,
        clustering: ClusteringEngine | None = None,
        engine_registry: EngineRegistry | None = None,
    ) -> None:
        if routing_config is not None:
            max_children = routing_config.max_children
        if max_children < 1:
            raise GraphBuildError(f"max_children must be >= 1, got {max_children!r}")
        if target_group_size is not None and target_group_size < 1:
            raise GraphBuildError(f"target_group_size must be >= 1, got {target_group_size!r}")
        self._max_children = max_children
        self._labeler = labeler or KeywordLabeler()
        self._target_group_size = target_group_size or max_children
        self._routing_config = routing_config
        self._engine_registry = engine_registry or default_registry
        self._clustering: ClusteringEngine = (
            clustering if clustering is not None else self._engine_registry.resolve("clustering")
        )
        # Cache: (catalog_hash) -> ChoiceGraph (issue #15).
        self._cache: dict[str, ChoiceGraph] = {}

    def build(
        self,
        items: list[SelectableItem],
        *,
        use_cache: bool = True,
    ) -> ChoiceGraph:
        """Build a :class:`ChoiceGraph` from *items*.

        Strategies are tried in priority order:
        1. Namespace grouping (if items have namespaces and >= 2 groups form).
        2. Clustering (Jaccard-based k-means variant).
        3. Alphabetical fallback.

        Caching (issue #15): when *use_cache* is ``True`` (default), a
        SHA-256 hash of the input catalog is computed via
        :func:`~contextweaver.routing.manifest.compute_catalog_hash` and
        used to look up a previously built graph.  Cached graphs are
        returned unchanged.  Use *use_cache=False* to force a rebuild
        without consulting or polluting the cache.

        Args:
            items: The items to organise.
            use_cache: When ``True``, consult and update the per-builder
                build cache keyed by catalog hash.  Default ``True``.

        Returns:
            A bounded DAG rooted at ``"root"``.

        Raises:
            GraphBuildError: If *items* is empty.
        """
        if not items:
            raise GraphBuildError("Cannot build tree from empty item list.")

        catalog_hash = ""
        if use_cache:
            from contextweaver.routing.manifest import compute_catalog_hash

            catalog_hash = compute_catalog_hash(items)
            cached = self._cache.get(catalog_hash)
            if cached is not None:
                return cached

        graph = ChoiceGraph(max_children=self._max_children)
        graph.add_node("root", label="root", routing_hint="All available tools")

        # Register all items in the graph
        for item in items:
            graph.add_item(item.id)

        # Sort items by id for determinism
        sorted_items = sorted(items, key=lambda it: it.id)

        self._build_subtree(graph, "root", sorted_items, depth=0)

        max_depth = graph.stats()["max_depth"]
        # Use timestamp=0.0 for determinism: AGENTS.md requires that
        # TreeBuilder.build() produce identical output for identical
        # input.  Callers wanting a wall-clock timestamp can replace the
        # manifest after build via ``graph.manifest = GraphManifest.for_build(items)``.
        manifest = GraphManifest.for_build(
            items,
            strategy="auto",
            max_depth=max_depth,
            seed=None,
            engine_versions={"tree_builder": "1.0", "labeler": "keyword-1.0"},
            extra={"max_children": self._max_children},
            timestamp=0.0,
        )
        graph.build_meta = {
            "version": "1.0",
            "strategy": "auto",
            "item_count": len(items),
            "max_depth": max_depth,
            "manifest": manifest.to_dict(),
        }

        if use_cache and catalog_hash:
            self._cache[catalog_hash] = graph

        return graph

    def clear_cache(self) -> None:
        """Drop all cached graphs.

        Subsequent :meth:`build` calls will rebuild from scratch.  Useful
        when item metadata has changed in ways the catalog hash does not
        reflect (e.g. tweaking labeler configuration between builds).
        """
        self._cache.clear()

    def _build_subtree(
        self,
        graph: ChoiceGraph,
        parent_id: str,
        items: list[SelectableItem],
        depth: int,
    ) -> None:
        """Recursively build a subtree under *parent_id*."""
        if len(items) <= self._max_children:
            # Leaf group — attach items directly
            for item in sorted(items, key=lambda it: it.id):
                graph.add_node(item.id)
                graph.add_edge(parent_id, item.id)
            return

        # Try strategies in priority order
        strategy = "namespace"
        groups = self._try_namespace_grouping(items)
        if groups is None:
            strategy = "clustering"
            groups = self._try_clustering(items)
        if groups is None:
            strategy = "alphabetical"
            groups = self._alphabetical_fallback(items)

        # The primary strategy is namespace grouping; clustering and the
        # alphabetical split are fallbacks that frequently surprise users,
        # so surface those at INFO while the chosen strategy stays at DEBUG.
        logger.debug(
            "tree_builder.subtree: parent=%s, depth=%d, items=%d, strategy=%s, groups=%d",
            parent_id,
            depth,
            len(items),
            strategy,
            len(groups),
        )
        if strategy != "namespace":
            logger.info(
                "tree_builder.subtree: parent=%s used fallback strategy=%s (items=%d, groups=%d)",
                parent_id,
                strategy,
                len(items),
                len(groups),
            )

        # If strategy produced more groups than max_children, merge
        # adjacent groups (sorted by key) until within bounds.
        if len(groups) > self._max_children:
            groups = self._coalesce_groups(groups)

        # Create intermediate nodes and recurse
        for group_label, group_items in sorted(groups.items()):
            node_id = f"{parent_id}/{group_label}"
            label, routing_hint = self._labeler.label_group(group_items)
            graph.add_node(node_id, label=label, routing_hint=routing_hint)
            graph.add_edge(parent_id, node_id)
            self._build_subtree(graph, node_id, group_items, depth + 1)

    # ------------------------------------------------------------------
    # Strategy 1: Namespace grouping
    # ------------------------------------------------------------------

    def _try_namespace_grouping(
        self, items: list[SelectableItem]
    ) -> dict[str, list[SelectableItem]] | None:
        """Group by first unused namespace dot-segment.

        Returns None (fallback) if fewer than 2 groups form or most items
        lack namespaces.
        """
        with_ns = [it for it in items if it.namespace]
        if len(with_ns) < len(items) * 0.5:
            return None

        groups: dict[str, list[SelectableItem]] = defaultdict(list)
        for item in sorted(items, key=lambda it: it.id):
            if item.namespace:
                # Use first dot-segment as the group key
                segment = item.namespace.split(".")[0]
                groups[segment].append(item)
            else:
                groups["_other"].append(item)

        if len(groups) < 2:
            return None

        # Re-split any oversized groups
        result: dict[str, list[SelectableItem]] = {}
        for key, group in sorted(groups.items()):
            if len(group) > self._max_children:
                sub = self._split_by_next_segment(group, key)
                for sub_key, sub_items in sub.items():
                    result[sub_key] = sub_items
            else:
                result[key] = group

        if len(result) > self._max_children:
            return None

        return result

    def _split_by_next_segment(
        self, items: list[SelectableItem], prefix: str
    ) -> dict[str, list[SelectableItem]]:
        """Split a group by the next namespace dot-segment after *prefix*."""
        sub_groups: dict[str, list[SelectableItem]] = defaultdict(list)
        for item in sorted(items, key=lambda it: it.id):
            ns = item.namespace
            rest = ns[len(prefix) :].lstrip(".")
            segment = rest.split(".")[0] if rest else "_leaf"
            sub_groups[f"{prefix}.{segment}"].append(item)

        # If still oversized or only 1 group, just chunk alphabetically
        if len(sub_groups) < 2:
            return self._alphabetical_fallback(items)
        return dict(sub_groups)

    # ------------------------------------------------------------------
    # Strategy 2: Clustering (farthest-first Jaccard seeding)
    # ------------------------------------------------------------------

    def _try_clustering(
        self, items: list[SelectableItem]
    ) -> dict[str, list[SelectableItem]] | None:
        """Cluster items via the configured :class:`ClusteringEngine`.

        Delegates the seeding + assignment to ``self._clustering``
        (default: farthest-first Jaccard from :data:`default_registry`)
        and then re-splits any oversized clusters via alphabetical
        chunking so every returned group fits within
        ``self._max_children``.

        Returns None if clustering produces degenerate results (fewer
        than two non-empty groups after rebalancing).
        """
        k = max(2, math.ceil(len(items) / self._target_group_size))
        k = min(k, self._max_children)

        raw_clusters = self._clustering.cluster(items, k=k)
        if not raw_clusters:
            return None

        # Rebalance: re-split oversized clusters and renumber labels.
        groups: dict[str, list[SelectableItem]] = {}
        cluster_idx = 0
        for label in sorted(raw_clusters):
            members = raw_clusters[label]
            if not members:
                continue
            cluster_items = list(members)
            if len(cluster_items) > self._max_children:
                # Sub-split using alphabetical chunking.
                chunks = self._chunk_list(cluster_items, self._max_children)
                for chunk in chunks:
                    groups[f"cluster_{cluster_idx:03d}"] = chunk
                    cluster_idx += 1
            else:
                groups[f"cluster_{cluster_idx:03d}"] = cluster_items
                cluster_idx += 1

        if len(groups) < 2:
            return None

        return groups

    # ------------------------------------------------------------------
    # Strategy 3: Alphabetical fallback
    # ------------------------------------------------------------------

    def _alphabetical_fallback(
        self, items: list[SelectableItem]
    ) -> dict[str, list[SelectableItem]]:
        """Sort by name and split into labelled alphabetical chunks."""
        sorted_items = sorted(items, key=lambda it: it.name.lower())
        chunks = self._chunk_list(sorted_items, self._max_children)

        groups: dict[str, list[SelectableItem]] = {}
        for chunk in chunks:
            first = chunk[0].name[0].upper() if chunk[0].name else "?"
            last = chunk[-1].name[0].upper() if chunk[-1].name else "?"
            label = f"{first}-{last}" if first != last else first
            # Ensure unique labels
            base = label
            counter = 1
            while label in groups:
                label = f"{base}_{counter}"
                counter += 1
            groups[label] = chunk

        return groups

    # ------------------------------------------------------------------
    # Utilities
    # ------------------------------------------------------------------

    def _coalesce_groups(
        self,
        groups: dict[str, list[SelectableItem]],
    ) -> dict[str, list[SelectableItem]]:
        """Merge adjacent groups until the count is <= max_children."""
        entries = sorted(groups.items())
        target = self._max_children
        while len(entries) > target:
            # Merge last two entries into one
            k1, v1 = entries.pop()
            k2, v2 = entries.pop()
            merged_label = f"{k2}+{k1}"
            entries.append((merged_label, v2 + v1))
        return dict(entries)

    @staticmethod
    def _chunk_list(items: list[SelectableItem], chunk_size: int) -> list[list[SelectableItem]]:
        """Split *items* into chunks of at most *chunk_size*."""
        k = max(1, math.ceil(len(items) / chunk_size))
        # Distribute as evenly as possible
        base_size = len(items) // k
        remainder = len(items) % k
        chunks: list[list[SelectableItem]] = []
        start = 0
        for i in range(k):
            size = base_size + (1 if i < remainder else 0)
            chunks.append(items[start : start + size])
            start += size
        return chunks
