<?php

declare(strict_types=1);

namespace App\Business\DataImport\Support;

/**
 * 商品分类导入 parent_code 引用校验与拓扑排序。
 */
final class ProductCategoryImportGraph
{
    /**
     * @param  array<string, string|null>  $codeToParentCode  文件内 code => parent_code
     * @param  list<string>  $existingCodes  数据库已有分类编码
     * @return list<string> 按先父后子排序的 code 列表
     */
    public function topologicalOrder(array $codeToParentCode, array $existingCodes): array
    {
        $existingLookup = array_fill_keys($existingCodes, true);
        $codes = array_keys($codeToParentCode);

        $inDegree = array_fill_keys($codes, 0);
        /** @var array<string, list<string>> $children */
        $children = array_fill_keys($codes, []);

        foreach ($codeToParentCode as $code => $parentCode) {
            if ($parentCode === null || $parentCode === '') {
                continue;
            }

            if (isset($existingLookup[$parentCode])) {
                continue;
            }

            if (! array_key_exists($parentCode, $codeToParentCode)) {
                continue;
            }

            $children[$parentCode][] = $code;
            $inDegree[$code]++;
        }

        $queue = [];

        foreach ($codes as $code) {
            if ($inDegree[$code] === 0) {
                $queue[] = $code;
            }
        }

        $ordered = [];

        while ($queue !== []) {
            $current = array_shift($queue);
            $ordered[] = $current;

            foreach ($children[$current] as $childCode) {
                $inDegree[$childCode]--;

                if ($inDegree[$childCode] === 0) {
                    $queue[] = $childCode;
                }
            }
        }

        if (count($ordered) !== count($codes)) {
            throw new \RuntimeException((string) __('dberp.data_import.validation.circular_parent_reference'));
        }

        return $ordered;
    }

    /**
     * @param  array<string, string|null>  $codeToParentCode
     * @param  list<string>  $existingCodes
     * @return list<string> 存在环的 code 列表（用于行级错误定位）
     */
    public function detectCycleCodes(array $codeToParentCode, array $existingCodes): array
    {
        $existingLookup = array_fill_keys($existingCodes, true);
        $visiting = [];
        $visited = [];
        $cycleNodes = [];

        foreach (array_keys($codeToParentCode) as $code) {
            if (isset($visited[$code])) {
                continue;
            }

            $this->visitForCycle($code, $codeToParentCode, $existingLookup, $visiting, $visited, $cycleNodes);
        }

        return array_values(array_unique($cycleNodes));
    }

    /**
     * @param  array<string, string|null>  $codeToParentCode
     * @param  array<string, true>  $existingLookup
     * @param  array<string, true>  $visiting
     * @param  array<string, true>  $visited
     * @param  list<string>  $cycleNodes
     */
    private function visitForCycle(
        string $code,
        array $codeToParentCode,
        array $existingLookup,
        array &$visiting,
        array &$visited,
        array &$cycleNodes,
    ): void {
        if (isset($visiting[$code])) {
            $cycleNodes[] = $code;

            return;
        }

        if (isset($visited[$code])) {
            return;
        }

        $visiting[$code] = true;
        $parentCode = $codeToParentCode[$code] ?? null;

        if ($parentCode !== null && $parentCode !== '' && ! isset($existingLookup[$parentCode]) && array_key_exists($parentCode, $codeToParentCode)) {
            $this->visitForCycle($parentCode, $codeToParentCode, $existingLookup, $visiting, $visited, $cycleNodes);
        }

        unset($visiting[$code]);
        $visited[$code] = true;
    }
}
