from typing import Dict, List, Sequence, Tuple

from .manufacturing_bom_explode_types import BomLine, BomRequirement
from .math_rational import Rational, add_rational, multiply_rational, rational, rational_to_integer

MAX_SAFE = 2**53 - 1


def explode_bom(lines: Sequence[BomLine], item: str, build_quantity: int) -> List[BomRequirement]:
    """Total quantity of every item under ``item``, summed over every place it
    is used, in exact fractions. Walks the BOM depth first, carrying the path
    so a loop is reported by name instead of recursing for ever.
    """
    if isinstance(build_quantity, bool) or not isinstance(build_quantity, int) or build_quantity < 0 or build_quantity > MAX_SAFE:
        raise ValueError("buildQuantity must be a whole number, not negative, received %r" % (build_quantity,))
    children: Dict[str, List[Tuple[BomLine, Rational]]] = {}
    for line in lines:
        q = rational(line.quantity.numerator, line.quantity.denominator)
        if q.numerator <= 0:
            raise ValueError('quantity of "%s" in "%s" must be greater than zero' % (line.component, line.parent))
        scrap = line.scrap_basis_points
        if isinstance(scrap, bool) or not isinstance(scrap, int) or scrap < 0 or scrap > MAX_SAFE:
            raise ValueError(
                'scrapBasisPoints of "%s" in "%s" must be a whole number, not negative, received %r'
                % (line.component, line.parent, scrap)
            )
        factor = multiply_rational(q, rational(10000 + scrap, 10000))
        children.setdefault(line.parent, []).append((line, factor))
    if item not in children:
        raise ValueError('"%s" has no bill of materials' % (item,))
    # name -> [first-seen index, level, quantity]; dicts keep insertion order.
    entries: Dict[str, list] = {}

    def walk(parent: str, need: Rational, depth: int, path: List[str]) -> None:
        for line, factor in children.get(parent, []):
            if line.component in path:
                raise ValueError("bill of materials has a cycle: %s" % " -> ".join(path + [line.component]))
            quantity = multiply_rational(need, factor)
            entry = entries.get(line.component)
            if entry is None:
                entries[line.component] = [len(entries), depth, quantity]
            else:
                entry[1] = max(entry[1], depth)
                entry[2] = add_rational(entry[2], quantity)
            if line.component in children:
                walk(line.component, quantity, depth + 1, path + [line.component])

    walk(item, rational(build_quantity, 1), 1, [item])
    ordered = sorted(entries.items(), key=lambda kv: (kv[1][1], kv[1][0]))
    return [
        BomRequirement(
            item=name,
            level=e[1],
            quantity=e[2],
            whole_units=rational_to_integer(e[2], "up"),
            leaf=name not in children,
        )
        for name, e in ordered
    ]