class Keep {
constructor(unit) {
this.type = 'Keep';
this.unit = unit;
}
}
class Insert {
constructor(unit) {
this.type = 'Insert';
this.unit = unit;
}
}
class Remove {
constructor(unit) {
this.type = 'Remove';
this.unit = unit;
}
}
class Frontier {
constructor(x, history, path = []) {
this.x = x;
this.history = history;
this.path = path;
}
}
function getNextUnit(sequence1, pos1, sequence2, pos2) {
console.log(`nChecking for unit at pos1=${pos1}, pos2=${pos2}`);
if (pos1 < 0 || pos2 < 0 || pos1 >= sequence1.length) {
console.log('Position out of bounds, returning null');
return null;
}
// Look for compound unit only if we're at matching positions
if (pos1 + 2 < sequence1.length && pos2 + 2 < sequence2.length &&
sequence1[pos1].hashVal === sequence2[pos2].hashVal) {
const firstMatch = sequence1[pos1].hashVal === sequence2[pos2].hashVal;
const secondMatch = sequence1[pos1 + 1].hashVal === sequence2[pos2 + 1].hashVal;
const thirdMismatch = sequence1[pos1 + 2].hashVal !== sequence2[pos2 + 2].hashVal;
console.log(`Pattern check at ${pos1}:
First: ${sequence1[pos1].hashVal} vs ${sequence2[pos2].hashVal} = ${firstMatch}
Second: ${sequence1[pos1 + 1].hashVal} vs ${sequence2[pos2 + 1].hashVal} = ${secondMatch}
Third mismatch: ${sequence1[pos1 + 2].hashVal} vs ${sequence2[pos2 + 2].hashVal} = ${thirdMismatch}`);
if (firstMatch && secondMatch && thirdMismatch) {
console.log('Found compound unit:', sequence1.slice(pos1, pos1 + 3).map(x => x.hashVal));
return {
elements: sequence1.slice(pos1, pos1 + 3),
size: 3,
isCompound: true
};
}
}
console.log('Returning single unit:', sequence1[pos1].hashVal);
return {
elements: [sequence1[pos1]],
size: 1,
isCompound: false
};
}
function unitsMatch(unit1, unit2) {
if (!unit1 || !unit2) return false;
if (unit1.elements.length !== unit2.elements.length) return false;
return unit1.elements.every((elem, i) =>
elem.hashVal === unit2.elements[i].hashVal
);
}
function visualizePath(old, current, finalPath) {
const matrix = [];
const headerRow = [' '];
for (let char of old) {
headerRow.push(char.hashVal);
}
matrix.push(headerRow);
for (let i = 0; i < current.length; i++) {
const row = [current[i].hashVal];
for (let j = 0; j < old.length; j++) {
row.push('·');
}
matrix.push(row);
}
let prevX = 0, prevY = 0;
for (const [x, y] of finalPath) {
if (y >= 0 && y < matrix.length && x >= 0 && x < matrix[0].length) {
if (x === prevX && y > prevY) {
matrix[y][x] = '↓';
} else if (x > prevX && y === prevY) {
matrix[y][x] = '→';
} else if (x > prevX && y > prevY) {
matrix[y][x] = '↘';
}
}
prevX = x;
prevY = y;
}
console.log('nPath Visualization:');
for (const row of matrix) {
console.log(row.join(' '));
}
}
function addPathPoints(path, startX, startY, endX, endY, isDiagonal = false) {
if (isDiagonal) {
for (let i = 0; i <= endX - startX; i++) {
path.push([startX + i, startY + i]);
}
} else {
const xStep = Math.sign(endX - startX);
const yStep = Math.sign(endY - startY);
for (let x = startX; x !== endX; x += xStep) {
path.push([x, startY]);
}
for (let y = startY; y !== endY; y += yStep) {
path.push([endX, y]);
}
}
}
function myersDiffCompoundUnits(old, current) {
let frontier = { 0: new Frontier(0, [], [[0, 0]]) };
const aMax = old.length;
const bMax = current.length;
// Calculate max D based on compound units
const COMPOUND_SIZE = 3;
const maxD = Math.ceil((aMax + bMax) / COMPOUND_SIZE) + 1;
console.log('nStarting diff with compound units:');
console.log('Old:', old.map(x => x.hashVal).join(''));
console.log('Current:', current.map(x => x.hashVal).join(''));
console.log('Max D:', maxD);
for (let d = 0; d <= maxD; d++) {
console.log(`n=== Edit distance D = ${d} ===`);
const newFrontier = {};
for (let k = -d; k <= d; k += 2) {
console.log(`n--- Diagonal k = ${k} ---`);
const goDown = (k === -d ||
(k !== d && frontier[k - 1]?.x < frontier[k + 1]?.x));
let oldX, history, path;
if (goDown) {
({ x: oldX, history, path } = frontier[k + 1] || { x: 0, history: [], path: [[0, 0]] });
var x = oldX;
} else {
({ x: oldX, history, path } = frontier[k - 1] || { x: 0, history: [], path: [[0, 0]] });
var x = oldX + 1;
}
history = [...history];
path = [...path];
let y = x - k;
console.log(`Current position: x=${x}, y=${y}`);
// Try snake movement first before any edits
let snakeMoved = false;
while (x < aMax && y < bMax) {
const oldUnit = getNextUnit(old, x, current, y);
const currentUnit = getNextUnit(current, y, old, x);
if (!oldUnit || !currentUnit || !unitsMatch(oldUnit, currentUnit)) {
break;
}
console.log('Matching unit:', oldUnit.elements.map(e => e.hashVal));
const startX = x;
const startY = y;
x += oldUnit.size;
y += oldUnit.size;
history.push(new Keep(currentUnit));
addPathPoints(path, startX, startY, x, y, true);
snakeMoved = true;
}
// Only try edit operations if snake couldn't move
if (!snakeMoved) {
if (y >= 1 && y <= bMax && goDown) {
const unit = getNextUnit(current, y - 1, old, x);
if (unit) {
console.log('Inserting unit:', unit.elements.map(e => e.hashVal));
history.push(new Insert(unit));
const startX = x;
const startY = y;
y += unit.size - 1;
addPathPoints(path, startX, startY, x, y);
}
} else if (x >= 1 && x <= aMax) {
const unit = getNextUnit(old, x - 1, current, y);
if (unit) {
console.log('Removing unit:', unit.elements.map(e => e.hashVal));
history.push(new Remove(unit));
const startX = x;
const startY = y;
x += unit.size - 1;
addPathPoints(path, startX, startY, x, y);
}
}
}
console.log(`Position after moves: x=${x}, y=${y}`);
if (x >= aMax && y >= bMax) {
console.log('nFound solution!');
visualizePath(old, current, path);
return { history, path };
}
newFrontier[k] = new Frontier(x, history, path);
}
frontier = newFrontier;
}
throw new Error('Could not find edit script');
}
// Test
let text1 = [
{ hashVal: 'P', content: 'P'},
{ hashVal: 'Q', content: 'Q'},
{ hashVal: 'R', content: 'R'},
{ hashVal: 'S', content: 'S'},
{ hashVal: 'X', content: 'X'},
{ hashVal: 'R', content: 'R'},
{ hashVal: 'S', content: 'S'},
{ hashVal: 'Y', content: 'Y'},
{ hashVal: 'R', content: 'R'},
{ hashVal: 'S', content: 'S'},
{ hashVal: 'Z', content: 'Z'},
];
let text2 = [
{ hashVal: 'P', content: 'P'},
{ hashVal: 'Q', content: 'Q'},
{ hashVal: 'R', content: 'R'},
{ hashVal: 'S', content: 'S'},
{ hashVal: 'A', content: 'A'},
{ hashVal: 'R', content: 'R'},
{ hashVal: 'S', content: 'S'},
{ hashVal: 'X', content: 'X'},
{ hashVal: 'R', content: 'R'},
{ hashVal: 'S', content: 'S'},
{ hashVal: 'Y', content: 'Y'},
];
const result = myersDiffCompoundUnits(text1, text2);
const diff = result.history.flatMap(op => {
return op.unit.elements.map(element => {
if (op instanceof Keep) {
element.status = 'unchanged';
} else if (op instanceof Insert) {
element.status = 'inserted';
} else if (op instanceof Remove) {
element.status = 'removed';
}
return element;
});
});
console.log("nFinal diff:");
console.log(diff.map(item => ({status: item.status, hashVal: item.hashVal})));
