| 1709 | }; |
| 1710 | |
| 1711 | function myersDiff(a: string[], b: string[]): Edit[] { |
| 1712 | const n = a.length; |
| 1713 | const m = b.length; |
| 1714 | const max = n + m; |
| 1715 | const vSize = 2 * max + 1; |
| 1716 | const v = new Int32Array(vSize); |
| 1717 | v.fill(-1); |
| 1718 | const offset = max; |
| 1719 | v[offset + 1] = 0; |
| 1720 | |
| 1721 | const trace: Int32Array[] = []; |
| 1722 | |
| 1723 | outer: for (let d = 0; d <= max; d++) { |
| 1724 | trace.push(v.slice()); |
| 1725 | for (let k = -d; k <= d; k += 2) { |
| 1726 | let x: number; |
| 1727 | if (k === -d || (k !== d && v[offset + k - 1] < v[offset + k + 1])) { |
| 1728 | x = v[offset + k + 1]; |
| 1729 | } else { |
| 1730 | x = v[offset + k - 1] + 1; |
| 1731 | } |
| 1732 | let y = x - k; |
| 1733 | while (x < n && y < m && a[x] === b[y]) { |
| 1734 | x++; |
| 1735 | y++; |
| 1736 | } |
| 1737 | v[offset + k] = x; |
| 1738 | if (x >= n && y >= m) break outer; |
| 1739 | } |
| 1740 | } |
| 1741 | |
| 1742 | const edits: Edit[] = []; |
| 1743 | let x = n; |
| 1744 | let y = m; |
| 1745 | |
| 1746 | for (let d = trace.length - 1; d >= 0; d--) { |
| 1747 | const vPrev = trace[d]; |
| 1748 | const k = x - y; |
| 1749 | let prevK: number; |
| 1750 | if ( |
| 1751 | k === -d || |
| 1752 | (k !== d && vPrev[offset + k - 1] < vPrev[offset + k + 1]) |
| 1753 | ) { |
| 1754 | prevK = k + 1; |
| 1755 | } else { |
| 1756 | prevK = k - 1; |
| 1757 | } |
| 1758 | const prevX = vPrev[offset + prevK]; |
| 1759 | const prevY = prevX - prevK; |
| 1760 | |
| 1761 | while (x > prevX && y > prevY) { |
| 1762 | x--; |
| 1763 | y--; |
| 1764 | edits.push({ type: "keep", lineA: x, lineB: y }); |
| 1765 | } |
| 1766 | if (d > 0) { |
| 1767 | if (x === prevX) { |
| 1768 | edits.push({ type: "insert", lineA: x, lineB: y - 1 }); |