source: trip-planner-front/node_modules/watchpack/lib/reducePlan.js@ 1ad8e64

/*
        MIT License http://www.opensource.org/licenses/mit-license.php
        Author Tobias Koppers @sokra
*/
"use strict";

const path = require("path");

/**
 * @template T
 * @typedef {Object} TreeNode
 * @property {string} filePath
 * @property {TreeNode} parent
 * @property {TreeNode[]} children
 * @property {number} entries
 * @property {boolean} active
 * @property {T[] | T | undefined} value
 */

/**
 * @template T
 * @param {Map<string, T[] | T} plan
 * @param {number} limit
 * @returns {Map<string, Map<T, string>>} the new plan
 */
module.exports = (plan, limit) => {
        const treeMap = new Map();
        // Convert to tree
        for (const [filePath, value] of plan) {
                treeMap.set(filePath, {
                        filePath,
                        parent: undefined,
                        children: undefined,
                        entries: 1,
                        active: true,
                        value
                });
        }
        let currentCount = treeMap.size;
        // Create parents and calculate sum of entries
        for (const node of treeMap.values()) {
                const parentPath = path.dirname(node.filePath);
                if (parentPath !== node.filePath) {
                        let parent = treeMap.get(parentPath);
                        if (parent === undefined) {
                                parent = {
                                        filePath: parentPath,
                                        parent: undefined,
                                        children: [node],
                                        entries: node.entries,
                                        active: false,
                                        value: undefined
                                };
                                treeMap.set(parentPath, parent);
                                node.parent = parent;
                        } else {
                                node.parent = parent;
                                if (parent.children === undefined) {
                                        parent.children = [node];
                                } else {
                                        parent.children.push(node);
                                }
                                do {
                                        parent.entries += node.entries;
                                        parent = parent.parent;
                                } while (parent);
                        }
                }
        }
        // Reduce until limit reached
        while (currentCount > limit) {
                // Select node that helps reaching the limit most effectively without overmerging
                const overLimit = currentCount - limit;
                let bestNode = undefined;
                let bestCost = Infinity;
                for (const node of treeMap.values()) {
                        if (node.entries <= 1 || !node.children || !node.parent) continue;
                        if (node.children.length === 0) continue;
                        if (node.children.length === 1 && !node.value) continue;
                        // Try to select the node with has just a bit more entries than we need to reduce
                        // When just a bit more is over 30% over the limit,
                        // also consider just a bit less entries then we need to reduce
                        const cost =
                                node.entries - 1 >= overLimit
                                        ? node.entries - 1 - overLimit
                                        : overLimit - node.entries + 1 + limit * 0.3;
                        if (cost < bestCost) {
                                bestNode = node;
                                bestCost = cost;
                        }
                }
                if (!bestNode) break;
                // Merge all children
                const reduction = bestNode.entries - 1;
                bestNode.active = true;
                bestNode.entries = 1;
                currentCount -= reduction;
                let parent = bestNode.parent;
                while (parent) {
                        parent.entries -= reduction;
                        parent = parent.parent;
                }
                const queue = new Set(bestNode.children);
                for (const node of queue) {
                        node.active = false;
                        node.entries = 0;
                        if (node.children) {
                                for (const child of node.children) queue.add(child);
                        }
                }
        }
        // Write down new plan
        const newPlan = new Map();
        for (const rootNode of treeMap.values()) {
                if (!rootNode.active) continue;
                const map = new Map();
                const queue = new Set([rootNode]);
                for (const node of queue) {
                        if (node.active && node !== rootNode) continue;
                        if (node.value) {
                                if (Array.isArray(node.value)) {
                                        for (const item of node.value) {
                                                map.set(item, node.filePath);
                                        }
                                } else {
                                        map.set(node.value, node.filePath);
                                }
                        }
                        if (node.children) {
                                for (const child of node.children) {
                                        queue.add(child);
                                }
                        }
                }
                newPlan.set(rootNode.filePath, map);
        }
        return newPlan;
};