/**
 * Random Tree Generator
 *
 * Generates a random tree with 1–MAX_CHILDREN children per node.
 * Exports a function that returns the tree data in memory.
 */

// ══════════════════════════════════════════════════════════
// Configuration
// ══════════════════════════════════════════════════════════

const TARGET_NODES = 100000;      // Approximate number of nodes to generate
const MAX_CHILDREN = 3;        // Each node gets 1..MAX_CHILDREN children

// ══════════════════════════════════════════════════════════
// Tree data types
// ══════════════════════════════════════════════════════════

export interface TreeData {
    root: number;
    nodeCount: number;
    childrenOf: Map<number, number[]>;
    parentOf: Map<number, number>;
}

// ══════════════════════════════════════════════════════════
// Generator
// ══════════════════════════════════════════════════════════

export function generateTree(): TreeData {
    const childrenOf = new Map<number, number[]>();
    const parentOf = new Map<number, number>();

    const root = 0;
    let nextId = 1;
    const queue: number[] = [root];
    let head = 0;

    while (head < queue.length && nextId < TARGET_NODES) {
        const parent = queue[head++];
        const nKids = 1 + Math.floor(Math.random() * MAX_CHILDREN); // 1..MAX_CHILDREN

        const kids: number[] = [];
        for (let c = 0; c < nKids && nextId < TARGET_NODES; c++) {
            const child = nextId++;
            kids.push(child);
            parentOf.set(child, parent);
            queue.push(child);
        }
        childrenOf.set(parent, kids);
    }

    console.log(`Generated tree: ${nextId} nodes, ${parentOf.size} edges, root=${root}`);

    return {
        root,
        nodeCount: nextId,
        childrenOf,
        parentOf,
    };
}