export const BREAK = Symbol("BREAK");
export const FOUND = BREAK;

/**
 * Generic graph/tree traversal supporting both DFS and BFS
 * @param root - Starting node(s)
 * @param mode - "d" for DFS (depth-first), "b" for BFS (breadth-first)
 * @param traverser - Function receiving (node, path) where path is ancestors from root (not including node).
 *                    Returns next nodes, or BREAK to stop and return current node.
 * @param cycle_breaker - Optional function or boolean for cycle detection
 * @returns The node that caused a BREAK, or null if traversal completed
 */
export function traverse<T>(
    root: T | T[],
    mode: "d" | "b",
    traverser: (node: T, path: T[]) => T[] | typeof BREAK | null,
    cycle_breaker?: boolean | ((node: T) => any) | null,
): T | null {
    const front: Array<[T, T[]]> = (Array.isArray(root) ? root : [root]).map((n) => [n, []]);
    const visited = new Set<any>();

    if (cycle_breaker === true) cycle_breaker = (x) => x;

    while (front.length > 0) {
        const [node, path] = mode === "b" ? front.shift()! : front.pop()!;

        if (cycle_breaker) {
            const key = cycle_breaker(node);
            if (visited.has(key)) continue;
            visited.add(key);
        }

        const result = traverser(node, path);
        if (result === BREAK) {
            return node;
        } else if (result != null) {
            const child_path = [...path, node];
            for (const child of result) front.push([child, child_path]);
        }
    }
    return null;
}

export function bft<T>(root: T | T[], traverser: (node: T, path: T[]) => T[] | typeof BREAK): T | null {
    return traverse(root, "b", traverser);
}

export function dft<T>(root: T | T[], traverser: (node: T, path: T[]) => T[] | typeof BREAK): T | null {
    return traverse(root, "d", traverser);
}