export const flatten = <Node>(tree: Node[], childrenKey: string) => {
    const stack = tree && tree.length ? [{ pointer: tree, offset: 0 }] : [];
    const flat: Node[] = [];
    let current: { pointer: Node[]; offset: number; node?: Node };

    while (stack.length) {
        current = stack.pop();
        while (current.offset < current.pointer.length) {
            const node = current.pointer[current.offset];
            const children = node[childrenKey];

            flat.push({ ...node });

            current.offset += 1;

            if (children) {
                stack.push(current);
                current = {
                    pointer: children,
                    offset: 0,
                    node,
                };
            }
        }
    }
    return flat;
};

export const unFlatten = <T>(
    list: T[],
    pIdKey: string,
    idKey: string,
    childrenKey: string,
    convert?: (node: T) => T,
) => {
    if (!convert) {
        return list.reduce((tree: T[], node: T) => {
            const parentNode = list.find((parent) => node[pIdKey] === parent[idKey]);

            if (parentNode === undefined) {
                tree.push(node);
            } else {
                if (!Array.isArray(parentNode[childrenKey])) {
                    parentNode[childrenKey] = [];
                }
                parentNode[childrenKey].push(node);
            }
            return tree;
        }, []);
    } else {
        const mappedList: { in: T; out: T }[] = list.map((node: T) => ({
            in: node,
            out: convert(node),
        }));

        return mappedList.reduce((tree: T[], node: { in: T; out: T }) => {
            const parentNode = mappedList.find((parent) => node.in[pIdKey] === parent.in[idKey]);

            if (parentNode === undefined) {
                tree.push(node.out);
            } else {
                node.out[childrenKey].push(
                    mappedList.find((treeNode) => treeNode.in === parentNode.in).out,
                );
            }

            return tree;
        }, []);
    }
};

export const dfsTree = <T, O>(
    tree: T[],
    idKey: string,
    childrenKey: string,
    cb: (node: T, parent: T, parentResult: O, path: string[]) => O,
) => {
    const dtsTreeFn = (nodes: T[], parent: T, parentResult: O, path: string[]) => {
        nodes.forEach((node) => {
            const currentPath = parent ? [...path, parent?.[idKey]] : [...path];
            // 额外回掉
            const result = cb(node, parent, parentResult, currentPath);
            // 收集子数据提供给父
            if (Array.isArray(node[childrenKey])) {
                dtsTreeFn(node[childrenKey], node, result, currentPath);
            }
        });
    };

    dtsTreeFn(tree, null, null, []);
};