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

Last change on this file since ceaed42 was 6a3a178, checked in by Ema <ema_spirova@…>, 3 years ago

initial commit

  • Property mode set to 100644
File size: 3.5 KB
Line 
1/*
2 MIT License http://www.opensource.org/licenses/mit-license.php
3 Author Tobias Koppers @sokra
4*/
5"use strict";
6
7const path = require("path");
8
9/**
10 * @template T
11 * @typedef {Object} TreeNode
12 * @property {string} filePath
13 * @property {TreeNode} parent
14 * @property {TreeNode[]} children
15 * @property {number} entries
16 * @property {boolean} active
17 * @property {T[] | T | undefined} value
18 */
19
20/**
21 * @template T
22 * @param {Map<string, T[] | T} plan
23 * @param {number} limit
24 * @returns {Map<string, Map<T, string>>} the new plan
25 */
26module.exports = (plan, limit) => {
27 const treeMap = new Map();
28 // Convert to tree
29 for (const [filePath, value] of plan) {
30 treeMap.set(filePath, {
31 filePath,
32 parent: undefined,
33 children: undefined,
34 entries: 1,
35 active: true,
36 value
37 });
38 }
39 let currentCount = treeMap.size;
40 // Create parents and calculate sum of entries
41 for (const node of treeMap.values()) {
42 const parentPath = path.dirname(node.filePath);
43 if (parentPath !== node.filePath) {
44 let parent = treeMap.get(parentPath);
45 if (parent === undefined) {
46 parent = {
47 filePath: parentPath,
48 parent: undefined,
49 children: [node],
50 entries: node.entries,
51 active: false,
52 value: undefined
53 };
54 treeMap.set(parentPath, parent);
55 node.parent = parent;
56 } else {
57 node.parent = parent;
58 if (parent.children === undefined) {
59 parent.children = [node];
60 } else {
61 parent.children.push(node);
62 }
63 do {
64 parent.entries += node.entries;
65 parent = parent.parent;
66 } while (parent);
67 }
68 }
69 }
70 // Reduce until limit reached
71 while (currentCount > limit) {
72 // Select node that helps reaching the limit most effectively without overmerging
73 const overLimit = currentCount - limit;
74 let bestNode = undefined;
75 let bestCost = Infinity;
76 for (const node of treeMap.values()) {
77 if (node.entries <= 1 || !node.children || !node.parent) continue;
78 if (node.children.length === 0) continue;
79 if (node.children.length === 1 && !node.value) continue;
80 // Try to select the node with has just a bit more entries than we need to reduce
81 // When just a bit more is over 30% over the limit,
82 // also consider just a bit less entries then we need to reduce
83 const cost =
84 node.entries - 1 >= overLimit
85 ? node.entries - 1 - overLimit
86 : overLimit - node.entries + 1 + limit * 0.3;
87 if (cost < bestCost) {
88 bestNode = node;
89 bestCost = cost;
90 }
91 }
92 if (!bestNode) break;
93 // Merge all children
94 const reduction = bestNode.entries - 1;
95 bestNode.active = true;
96 bestNode.entries = 1;
97 currentCount -= reduction;
98 let parent = bestNode.parent;
99 while (parent) {
100 parent.entries -= reduction;
101 parent = parent.parent;
102 }
103 const queue = new Set(bestNode.children);
104 for (const node of queue) {
105 node.active = false;
106 node.entries = 0;
107 if (node.children) {
108 for (const child of node.children) queue.add(child);
109 }
110 }
111 }
112 // Write down new plan
113 const newPlan = new Map();
114 for (const rootNode of treeMap.values()) {
115 if (!rootNode.active) continue;
116 const map = new Map();
117 const queue = new Set([rootNode]);
118 for (const node of queue) {
119 if (node.active && node !== rootNode) continue;
120 if (node.value) {
121 if (Array.isArray(node.value)) {
122 for (const item of node.value) {
123 map.set(item, node.filePath);
124 }
125 } else {
126 map.set(node.value, node.filePath);
127 }
128 }
129 if (node.children) {
130 for (const child of node.children) {
131 queue.add(child);
132 }
133 }
134 }
135 newPlan.set(rootNode.filePath, map);
136 }
137 return newPlan;
138};
Note: See TracBrowser for help on using the repository browser.