15644705543

Committed 13 Jun 2025 09:58PM UTC coverage: 100.0%. Remained the same

Build # 15644705543

Build Type

push

github

Committed by

YuJianrong

Commit Message

chore: update Node.js version to 22.16.0 in GitHub Actions workflow

Run Details

143 of 147 branches covered (97.28%)

193 of 193 relevant lines covered (100.0%)

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

YuJianrong / fast-array-diff / 15644705543

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