| | |
| | | |
| | | /** |
| | | * @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 |
| | | * @typedef {object} TreeNode |
| | | * @property {string} target target |
| | | * @property {TreeNode<T>} parent parent |
| | | * @property {TreeNode<T>[]} children children |
| | | * @property {number} entries number of entries |
| | | * @property {boolean} active true when active, otherwise false |
| | | * @property {T[] | T | undefined} value value |
| | | */ |
| | | |
| | | /** |
| | | * @template T |
| | | * @param {Map<string, T[] | T} plan |
| | | * @param {number} limit |
| | | * @param {Map<string, T[] | T>} plan plan |
| | | * @param {number} limit 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, |
| | | for (const [target, value] of plan) { |
| | | treeMap.set(target, { |
| | | target, |
| | | parent: undefined, |
| | | children: undefined, |
| | | entries: 1, |
| | | active: true, |
| | | value |
| | | 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) { |
| | | const parentPath = path.dirname(node.target); |
| | | if (parentPath !== node.target) { |
| | | let parent = treeMap.get(parentPath); |
| | | if (parent === undefined) { |
| | | parent = { |
| | | filePath: parentPath, |
| | | target: parentPath, |
| | | parent: undefined, |
| | | children: [node], |
| | | entries: node.entries, |
| | | active: false, |
| | | value: undefined |
| | | value: undefined, |
| | | }; |
| | | treeMap.set(parentPath, parent); |
| | | node.parent = parent; |
| | |
| | | while (currentCount > limit) { |
| | | // Select node that helps reaching the limit most effectively without overmerging |
| | | const overLimit = currentCount - limit; |
| | | let bestNode = undefined; |
| | | let bestNode; |
| | | let bestCost = Infinity; |
| | | for (const node of treeMap.values()) { |
| | | if (node.entries <= 1 || !node.children || !node.parent) continue; |
| | |
| | | bestNode.active = true; |
| | | bestNode.entries = 1; |
| | | currentCount -= reduction; |
| | | let parent = bestNode.parent; |
| | | let { parent } = bestNode; |
| | | while (parent) { |
| | | parent.entries -= reduction; |
| | | parent = parent.parent; |
| | |
| | | if (node.value) { |
| | | if (Array.isArray(node.value)) { |
| | | for (const item of node.value) { |
| | | map.set(item, node.filePath); |
| | | map.set(item, node.target); |
| | | } |
| | | } else { |
| | | map.set(node.value, node.filePath); |
| | | map.set(node.value, node.target); |
| | | } |
| | | } |
| | | if (node.children) { |
| | |
| | | } |
| | | } |
| | | } |
| | | newPlan.set(rootNode.filePath, map); |
| | | newPlan.set(rootNode.target, map); |
| | | } |
| | | return newPlan; |
| | | }; |