export class PlaceHierarchyModel {
    static buildRows(nodes = []) {
        const byKey = new Map(nodes.map(node => [node.key, node]));
        const childrenByParent = new Map();
        const roots = [];

        for (const node of nodes) {
            const requestedParentKey = String(node.parentKey || "").trim() || null;
            const parentKey = requestedParentKey && requestedParentKey !== node.key && byKey.has(requestedParentKey)
                ? requestedParentKey
                : null;
            if (!parentKey) {
                roots.push(node.key);
                continue;
            }
            const children = childrenByParent.get(parentKey) || [];
            children.push(node.key);
            childrenByParent.set(parentKey, children);
        }

        const sortKeys = keys => keys.sort((leftKey, rightKey) => this.#sortNodes(byKey.get(leftKey), byKey.get(rightKey)));
        sortKeys(roots);
        for (const children of childrenByParent.values()) sortKeys(children);

        const rows = [];
        const visited = new Set();
        const visit = (key, depth = 0, parentNodeId = null, hierarchyIssue = false) => {
            if (!key || visited.has(key)) return;
            const node = byKey.get(key);
            if (!node) return;
            visited.add(key);
            const childKeys = (childrenByParent.get(key) || []).filter(childKey => !visited.has(childKey));
            rows.push({
                ...node,
                id: key,
                parentNodeId,
                depth,
                hasChildren: childKeys.length > 0,
                hierarchyIssue
            });
            for (const childKey of childKeys) visit(childKey, depth + 1, key, hierarchyIssue);
        };

        for (const rootKey of roots) visit(rootKey);
        for (const node of [...nodes].sort(this.#sortNodes)) {
            if (!visited.has(node.key)) visit(node.key, 0, null, true);
        }
        return rows;
    }

    static getBranch(nodes = [], rootKey = "") {
        const rows = this.buildRows(nodes);
        const root = rows.find(row => row.key === rootKey);
        if (!root) return [];
        return rows.filter(row => row.key === root.key || this.#hasAncestor(row, root.key, rows));
    }

    static #hasAncestor(row, ancestorKey, rows) {
        const byKey = new Map(rows.map(candidate => [candidate.key, candidate]));
        const visited = new Set();
        let parentKey = row.parentNodeId;
        while (parentKey && !visited.has(parentKey)) {
            if (parentKey === ancestorKey) return true;
            visited.add(parentKey);
            parentKey = byKey.get(parentKey)?.parentNodeId || null;
        }
        return false;
    }

    static #sortNodes(left = {}, right = {}) {
        const nameOrder = String(left.name || "Place").localeCompare(String(right.name || "Place"), game.i18n.lang);
        return nameOrder || String(left.type || "").localeCompare(String(right.type || ""));
    }
}
