9537246397

Committed 16 Jun 2024 04:03PM UTC coverage: 100.0%. Remained the same

Build # 9537246397

Build Type

Pull #423

github

Committed by

web-flow

Commit Message

Merge 5966e4742 into f5754f82e

Pull Request Pull Request #423: chore(deps-dev): bump braces from 3.0.2 to 3.0.3

Run Details

143 of 147 branches covered (97.28%)

187 of 187 relevant lines covered (100.0%)

2074.11 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

100.0

/src/diff/lcs.ts

function lcs<T, U = T>(a: T[], b: U[], compareFunc: (a: T, b: U) => boolean): number {
  const M = a.length,
    N = b.length;
  const MAX = M + N;

  interface LongestPosition {
    [index: number]: number;
  }
  const v: LongestPosition = { 1: 0 };

  for (let d = 0; d <= MAX; ++d) {
    for (let k = -d; k <= d; k += 2) {
      let x: number;
      if (k === -d || (k !== d && v[k - 1] + 1 < v[k + 1])) {
        x = v[k + 1];
      } else {
        x = v[k - 1] + 1;
      }
      let y = x - k;
      while (x < M && y < N && compareFunc(a[x], b[y])) {
        x++;
        y++;
      }
      if (x === M && y === N) {
        return d;
      }
      v[k] = x;
    }
  }
  /* istanbul ignore next */
  return -1; // never reach
}

enum Direct {
  none = 0,
  horizontal = 1,
  vertical = 1 << 1,
  diagonal = 1 << 2,
  all = horizontal | vertical | diagonal,
}

function getSolution<T, U = T>(
  a: T[],
  aStart: number,
  aEnd: number,
  b: U[],
  bStart: number,
  bEnd: number,
  d: number,
  startDirect: Direct,
  endDirect: Direct,
  compareFunc: (a: T, b: U) => boolean,
  elementsChanged: (
    type: 'add' | 'remove' | 'same',
    a: T[],
    aStart: number,
    aEnd: number,
    b: U[],
    bStart: number,
    bEnd: number,
  ) => void,
): void {
  if (d === 0) {
    elementsChanged('same', a, aStart, aEnd, b, bStart, bEnd);
    return;
  } else if (d === aEnd - aStart + (bEnd - bStart)) {
    const removeFirst =
      (startDirect & Direct.horizontal ? 1 : 0) + (endDirect & Direct.vertical ? 1 : 0);
    const addFirst =
      (startDirect & Direct.vertical ? 1 : 0) + (endDirect & Direct.horizontal ? 1 : 0);
    if (removeFirst >= addFirst) {
      aStart !== aEnd && elementsChanged('remove', a, aStart, aEnd, b, bStart, bStart);
      bStart !== bEnd && elementsChanged('add', a, aEnd, aEnd, b, bStart, bEnd);
    } else {
      bStart !== bEnd && elementsChanged('add', a, aStart, aStart, b, bStart, bEnd);
      aStart !== aEnd && elementsChanged('remove', a, aStart, aEnd, b, bEnd, bEnd);
    }
    return;
  }

  const M = aEnd - aStart;
  const N = bEnd - bStart;
  let HALF = Math.floor(N / 2);

  interface PointInfo {
    d: number;
    segments: number;
    direct: Direct;
  }

  interface PointInfoMap {
    [index: number]: PointInfo;
  }

  let now: PointInfoMap = {};
  for (let k = -d - 1; k <= d + 1; ++k) {
    now[k] = { d: Infinity, segments: 0, direct: Direct.none };
  }
  let preview: PointInfoMap = {
    [-d - 1]: { d: Infinity, segments: 0, direct: Direct.none },
    [d + 1]: { d: Infinity, segments: 0, direct: Direct.none },
  };

  for (let y = 0; y <= HALF; ++y) {
    [now, preview] = [preview, now];
    for (let k = -d; k <= d; ++k) {
      const x = y + k;

      if (y === 0 && x === 0) {
        now[k] = {
          d: 0,
          segments: 0,
          direct: startDirect,
        };
        continue;
      }

      const currentPoints: PointInfo[] = [
        {
          direct: Direct.horizontal,
          d: now[k - 1].d + 1,
          segments: now[k - 1].segments + (now[k - 1].direct & Direct.horizontal ? 0 : 1),
        },
        {
          direct: Direct.vertical,
          d: preview[k + 1].d + 1,
          segments: preview[k + 1].segments + (preview[k + 1].direct & Direct.vertical ? 0 : 1),
        },
      ];

      if (x > 0 && x <= M && y > 0 && y <= N && compareFunc(a[aStart + x - 1], b[bStart + y - 1])) {
        currentPoints.push({
          direct: Direct.diagonal,
          d: preview[k].d,
          segments: preview[k].segments + (preview[k].direct & Direct.diagonal ? 0 : 1),
        });
      }

      const bestValue = currentPoints.reduce((best, info) => {
        if (best.d > info.d) {
          return info;
        } else if (best.d === info.d && best.segments > info.segments) {
          return info;
        }
        return best;
      });

      currentPoints.forEach((info) => {
        if (bestValue.d === info.d && bestValue.segments === info.segments) {
          bestValue.direct |= info.direct;
        }
      });
      now[k] = bestValue;
    }
  }

  let now2: PointInfoMap = {};
  for (let k = -d - 1; k <= d + 1; ++k) {
    now2[k] = { d: Infinity, segments: 0, direct: Direct.none };
  }
  let preview2: PointInfoMap = {
    [-d - 1]: { d: Infinity, segments: 0, direct: Direct.none },
    [d + 1]: { d: Infinity, segments: 0, direct: Direct.none },
  };

  for (let y = N; y >= HALF; --y) {
    [now2, preview2] = [preview2, now2];
    for (let k = d; k >= -d; --k) {
      const x = y + k;

      if (y === N && x === M) {
        now2[k] = {
          d: 0,
          segments: 0,
          direct: endDirect,
        };
        continue;
      }

      const currentPoints: PointInfo[] = [
        {
          direct: Direct.horizontal,
          d: now2[k + 1].d + 1,
          segments: now2[k + 1].segments + (now2[k + 1].direct & Direct.horizontal ? 0 : 1),
        },
        {
          direct: Direct.vertical,
          d: preview2[k - 1].d + 1,
          segments: preview2[k - 1].segments + (preview2[k - 1].direct & Direct.vertical ? 0 : 1),
        },
      ];

      if (x >= 0 && x < M && y >= 0 && y < N && compareFunc(a[aStart + x], b[bStart + y])) {
        currentPoints.push({
          direct: Direct.diagonal,
          d: preview2[k].d,
          segments: preview2[k].segments + (preview2[k].direct & Direct.diagonal ? 0 : 1),
        });
      }

      const bestValue = currentPoints.reduce((best, info) => {
        if (best.d > info.d) {
          return info;
        } else if (best.d === info.d && best.segments > info.segments) {
          return info;
        }
        return best;
      });

      currentPoints.forEach((info) => {
        if (bestValue.d === info.d && bestValue.segments === info.segments) {
          bestValue.direct |= info.direct;
        }
      });
      now2[k] = bestValue;
    }
  }
  const best = {
    k: -1,
    d: Infinity,
    segments: 0,
    direct: Direct.none,
  };

  for (let k = -d; k <= d; ++k) {
    const dSum = now[k].d + now2[k].d;
    if (dSum < best.d) {
      best.k = k;
      best.d = dSum;
      best.segments =
        now[k].segments + now2[k].segments + (now[k].segments & now2[k].segments ? 0 : 1);
      best.direct = now2[k].direct;
    } else if (dSum === best.d) {
      const segments =
        now[k].segments + now2[k].segments + (now[k].segments & now2[k].segments ? 0 : 1);
      if (segments < best.segments) {
        best.k = k;
        best.d = dSum;
        best.segments = segments;
        best.direct = now2[k].direct;
      } else if (
        segments === best.segments &&
        !(best.direct & Direct.diagonal) &&
        now2[k].direct & Direct.diagonal
      ) {
        best.k = k;
        best.d = dSum;
        best.segments = segments;
        best.direct = now2[k].direct;
      }
    }
  }

  if (HALF + best.k === 0 && HALF === 0) {
    HALF++;
    now[best.k].direct = now2[best.k].direct;
    now2[best.k].direct = preview2[best.k].direct;
  }

  getSolution(
    a,
    aStart,
    aStart + HALF + best.k,
    b,
    bStart,
    bStart + HALF,
    now[best.k].d,
    startDirect,
    now2[best.k].direct,
    compareFunc,
    elementsChanged,
  );
  getSolution(
    a,
    aStart + HALF + best.k,
    aEnd,
    b,
    bStart + HALF,
    bEnd,
    now2[best.k].d,
    now[best.k].direct,
    endDirect,
    compareFunc,
    elementsChanged,
  );
}

export default function bestSubSequence<T, U = T>(
  a: T[],
  b: U[],
  compareFunc: (a: T, b: U) => boolean,
  elementsChanged: (
    type: 'add' | 'remove' | 'same',
    a: T[],
    aStart: number,
    aEnd: number,
    b: U[],
    bStart: number,
    bEnd: number,
  ) => void,
): void {
  const d = lcs(a, b, compareFunc);
  getSolution(
    a,
    0,
    a.length,
    b,
    0,
    b.length,
    d,
    Direct.diagonal,
    Direct.all,
    compareFunc,
    elementsChanged,
  );
}

1	function lcs<T, U = T>(a: T[], b: U[], compareFunc: (a: T, b: U) => boolean): number {	1✔
2	const M = a.length,	70✔
3	N = b.length;
4	const MAX = M + N;	70✔
5
6	interface LongestPosition {
7	[index: number]: number;
8	}
9	const v: LongestPosition = { 1: 0 };	70✔
10
11	for (let d = 0; d <= MAX; ++d) {	70✔
12	for (let k = -d; k <= d; k += 2) {	354✔
13	let x: number;	1,822✔
14	if (k === -d \|\| (k !== d && v[k - 1] + 1 < v[k + 1])) {	1,822✔
15	x = v[k + 1];	530✔
16	} else {
17	x = v[k - 1] + 1;	1,292✔
18	}
19	let y = x - k;	1,822✔
20	while (x < M && y < N && compareFunc(a[x], b[y])) {	1,822✔
21	x++;	441✔
22	y++;	441✔
23	}
24	if (x === M && y === N) {	1,822✔
25	return d;	70✔
26	}
27	v[k] = x;	1,752✔
28	}
29	}
30	/* istanbul ignore next */
31	return -1; // never reach	1✔
32	}
33
34	enum Direct {	2✔
35	none = 0,	1✔
36	horizontal = 1,	1✔
37	vertical = 1 << 1,	1✔
38	diagonal = 1 << 2,	1✔
39	all = horizontal \| vertical \| diagonal,	1✔
40	}
41
42	function getSolution<T, U = T>(	1✔
43	a: T[],
44	aStart: number,
45	aEnd: number,
46	b: U[],
47	bStart: number,
48	bEnd: number,
49	d: number,
50	startDirect: Direct,
51	endDirect: Direct,
52	compareFunc: (a: T, b: U) => boolean,
53	elementsChanged: (
54	type: 'add' \| 'remove' \| 'same',
55	a: T[],
56	aStart: number,
57	aEnd: number,
58	b: U[],
59	bStart: number,
60	bEnd: number,
61	) => void,
62	): void {
63	if (d === 0) {	590✔
64	elementsChanged('same', a, aStart, aEnd, b, bStart, bEnd);	171✔
65	return;	171✔
66	} else if (d === aEnd - aStart + (bEnd - bStart)) {	419✔
67	const removeFirst =	159✔
68	(startDirect & Direct.horizontal ? 1 : 0) + (endDirect & Direct.vertical ? 1 : 0);	318✔
69	const addFirst =	159✔
70	(startDirect & Direct.vertical ? 1 : 0) + (endDirect & Direct.horizontal ? 1 : 0);	318✔
71	if (removeFirst >= addFirst) {	159✔
72	aStart !== aEnd && elementsChanged('remove', a, aStart, aEnd, b, bStart, bStart);	130✔
73	bStart !== bEnd && elementsChanged('add', a, aEnd, aEnd, b, bStart, bEnd);	130✔
74	} else {
75	bStart !== bEnd && elementsChanged('add', a, aStart, aStart, b, bStart, bEnd);	29✔
76	aStart !== aEnd && elementsChanged('remove', a, aStart, aEnd, b, bEnd, bEnd);	29✔
77	}
78	return;	159✔
79	}
80
81	const M = aEnd - aStart;	260✔
82	const N = bEnd - bStart;	260✔
83	let HALF = Math.floor(N / 2);	260✔
84
85	interface PointInfo {
86	d: number;
87	segments: number;
88	direct: Direct;
89	}
90
91	interface PointInfoMap {
92	[index: number]: PointInfo;
93	}
94
95	let now: PointInfoMap = {};	260✔
96	for (let k = -d - 1; k <= d + 1; ++k) {	260✔
97	now[k] = { d: Infinity, segments: 0, direct: Direct.none };	2,462✔
98	}
99	let preview: PointInfoMap = {	260✔
100	[-d - 1]: { d: Infinity, segments: 0, direct: Direct.none },
101	[d + 1]: { d: Infinity, segments: 0, direct: Direct.none },
102	};
103
104	for (let y = 0; y <= HALF; ++y) {	260✔
105	[now, preview] = [preview, now];	831✔
106	for (let k = -d; k <= d; ++k) {	831✔
107	const x = y + k;	11,933✔
108
109	if (y === 0 && x === 0) {	11,933✔
110	now[k] = {	260✔
111	d: 0,
112	segments: 0,
113	direct: startDirect,
114	};
115	continue;
116	}
117
118	const currentPoints: PointInfo[] = [	11,673✔
119	{
120	direct: Direct.horizontal,
121	d: now[k - 1].d + 1,
122	segments: now[k - 1].segments + (now[k - 1].direct & Direct.horizontal ? 0 : 1),	11,673✔
123	},
124	{
125	direct: Direct.vertical,
126	d: preview[k + 1].d + 1,
127	segments: preview[k + 1].segments + (preview[k + 1].direct & Direct.vertical ? 0 : 1),	11,673✔
128	},
129	];
130
131	if (x > 0 && x <= M && y > 0 && y <= N && compareFunc(a[aStart + x - 1], b[bStart + y - 1])) {	11,673✔
132	currentPoints.push({	802✔
133	direct: Direct.diagonal,
134	d: preview[k].d,
135	segments: preview[k].segments + (preview[k].direct & Direct.diagonal ? 0 : 1),	802✔
136	});
137	}
138
139	const bestValue = currentPoints.reduce((best, info) => {	11,673✔
140	if (best.d > info.d) {	12,475✔
141	return info;	2,258✔
142	} else if (best.d === info.d && best.segments > info.segments) {	10,217✔
143	return info;	210✔
144	}
145	return best;	10,007✔
146	});
147
148	currentPoints.forEach((info) => {	11,673✔
149	if (bestValue.d === info.d && bestValue.segments === info.segments) {	24,148✔
150	bestValue.direct \|= info.direct;	16,468✔
151	}
152	});
153	now[k] = bestValue;	11,673✔
154	}
155	}
156
157	let now2: PointInfoMap = {};	260✔
158	for (let k = -d - 1; k <= d + 1; ++k) {	260✔
159	now2[k] = { d: Infinity, segments: 0, direct: Direct.none };	2,462✔
160	}
161	let preview2: PointInfoMap = {	260✔
162	[-d - 1]: { d: Infinity, segments: 0, direct: Direct.none },
163	[d + 1]: { d: Infinity, segments: 0, direct: Direct.none },
164	};
165
166	for (let y = N; y >= HALF; --y) {	260✔
167	[now2, preview2] = [preview2, now2];	963✔
168	for (let k = d; k >= -d; --k) {	963✔
169	const x = y + k;	12,957✔
170
171	if (y === N && x === M) {	12,957✔
172	now2[k] = {	260✔
173	d: 0,
174	segments: 0,
175	direct: endDirect,
176	};
177	continue;
178	}
179
180	const currentPoints: PointInfo[] = [	12,697✔
181	{
182	direct: Direct.horizontal,
183	d: now2[k + 1].d + 1,
184	segments: now2[k + 1].segments + (now2[k + 1].direct & Direct.horizontal ? 0 : 1),	12,697✔
185	},
186	{
187	direct: Direct.vertical,
188	d: preview2[k - 1].d + 1,
189	segments: preview2[k - 1].segments + (preview2[k - 1].direct & Direct.vertical ? 0 : 1),	12,697✔
190	},
191	];
192
193	if (x >= 0 && x < M && y >= 0 && y < N && compareFunc(a[aStart + x], b[bStart + y])) {	12,697✔
194	currentPoints.push({	1,131✔
195	direct: Direct.diagonal,
196	d: preview2[k].d,
197	segments: preview2[k].segments + (preview2[k].direct & Direct.diagonal ? 0 : 1),	1,131✔
198	});
199	}
200
201	const bestValue = currentPoints.reduce((best, info) => {	12,697✔
202	if (best.d > info.d) {	13,828✔
203	return info;	2,822✔
204	} else if (best.d === info.d && best.segments > info.segments) {	11,006✔
205	return info;	224✔
206	}
207	return best;	10,782✔
208	});
209
210	currentPoints.forEach((info) => {	12,697✔
211	if (bestValue.d === info.d && bestValue.segments === info.segments) {	26,525✔
212	bestValue.direct \|= info.direct;	19,410✔
213	}
214	});
215	now2[k] = bestValue;	12,697✔
216	}
217	}
218	const best = {	260✔
219	k: -1,
220	d: Infinity,
221	segments: 0,
222	direct: Direct.none,
223	};
224
225	for (let k = -d; k <= d; ++k) {	260✔
226	const dSum = now[k].d + now2[k].d;	1,942✔
227	if (dSum < best.d) {	1,942✔
228	best.k = k;	523✔
229	best.d = dSum;	523✔
230	best.segments =	523✔
231	now[k].segments + now2[k].segments + (now[k].segments & now2[k].segments ? 0 : 1);	523✔
232	best.direct = now2[k].direct;	523✔
233	} else if (dSum === best.d) {	1,419✔
234	const segments =	568✔
235	now[k].segments + now2[k].segments + (now[k].segments & now2[k].segments ? 0 : 1);	568✔
236	if (segments < best.segments) {	568✔
237	best.k = k;	17✔
238	best.d = dSum;	17✔
239	best.segments = segments;	17✔
240	best.direct = now2[k].direct;	17✔
241	} else if (	551✔
242	segments === best.segments &&	825✔
243	!(best.direct & Direct.diagonal) &&
244	now2[k].direct & Direct.diagonal
245	) {
246	best.k = k;	55✔
247	best.d = dSum;	55✔
248	best.segments = segments;	55✔
249	best.direct = now2[k].direct;	55✔
250	}
251	}
252	}
253
254	if (HALF + best.k === 0 && HALF === 0) {	260✔
255	HALF++;	30✔
256	now[best.k].direct = now2[best.k].direct;	30✔
257	now2[best.k].direct = preview2[best.k].direct;	30✔
258	}
259
260	getSolution(	260✔
261	a,
262	aStart,
263	aStart + HALF + best.k,
264	b,
265	bStart,
266	bStart + HALF,
267	now[best.k].d,
268	startDirect,
269	now2[best.k].direct,
270	compareFunc,
271	elementsChanged,
272	);
273	getSolution(	260✔
274	a,
275	aStart + HALF + best.k,
276	aEnd,
277	b,
278	bStart + HALF,
279	bEnd,
280	now2[best.k].d,
281	now[best.k].direct,
282	endDirect,
283	compareFunc,
284	elementsChanged,
285	);
286	}
287
288	export default function bestSubSequence<T, U = T>(	2✔
289	a: T[],
290	b: U[],
291	compareFunc: (a: T, b: U) => boolean,
292	elementsChanged: (
293	type: 'add' \| 'remove' \| 'same',
294	a: T[],
295	aStart: number,
296	aEnd: number,
297	b: U[],
298	bStart: number,
299	bEnd: number,
300	) => void,
301	): void {
302	const d = lcs(a, b, compareFunc);	70✔
303	getSolution(	70✔
304	a,
305	0,
306	a.length,
307	b,
308	0,
309	b.length,
310	d,
311	Direct.diagonal,
312	Direct.all,
313	compareFunc,
314	elementsChanged,
315	);
316	}

YuJianrong / fast-array-diff / 9537246397

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous