m.js

class Keep {
    constructor(line) {
        this.type = 'Keep';
        this.line = line;
    }
}

class Insert {
    constructor(line) {
        this.type = 'Insert';
        this.line = line;
    }
}

class Remove {
    constructor(line) {
        this.type = 'Remove';
        this.line = line;
    }
}

// Represents a point on the frontier with its history
class Frontier {
    constructor(x, history) {
        this.x = x;        // x-coordinate in edit graph
        this.history = history;  // sequence of operations to reach this point
    }
}

function myersDiff(old, current) {
    // Initialize the frontier with starting point
    // K=1 diagonal starts at (0,0) with empty history
    const frontier = { 1: new Frontier(0, []) };

    // Convert from 1-based to 0-based indexing
    // Algorithm uses 1-based indexing, but JavaScript uses 0-based
    function one(idx) {
        return idx - 1;
    }

    const aMax = old.length;  // horizontal size of edit graph
    const bMax = current.length;  // vertical size of edit graph

    // Main loop: try increasing numbers of edits
    for (let d = 0; d <= aMax + bMax + 1; d++) {
        // For each value of D, try all possible diagonals
        for (let k = -d; k <= d; k += 2) {
            // Determine whether to go down or right
            // This choice affects which diagonal we extend from
            const goDown = (k === -d ||  // at left edge, must go down
                (k !== d && frontier[k - 1].x < frontier[k + 1].x));  // compare positions

            // Find starting point for this iteration
            let oldX, history;
            if (goDown) {
                // Copy from k+1 diagonal (going down)
                ({ x: oldX, history } = frontier[k + 1]);
                var x = oldX;
            } else {
                // Copy from k-1 diagonal and move right
                ({ x: oldX, history } = frontier[k - 1]);
                var x = oldX + 1;
            }

            // Clone history to avoid modifying previous paths
            history = [...history];
            let y = x - k;  // Calculate y from x and k

            // Record the edit we made to get here
            if (y >= 1 && y <= bMax && goDown) {
                // Insert from new sequence when going down
                history.push(new Insert(current[one(y)]));
            } else if (x >= 1 && x <= aMax) {
                // Remove from old sequence when going right
                history.push(new Remove(old[one(x)]));
            }

            // Follow the snake: match diagonal moves as far as possible
            // This is key optimization - extend path along matches
            while (x < aMax && y < bMax &&
                old[one(x + 1)].hashVal === current[one(y + 1)].hashVal) {
                x += 1;
                y += 1;
                history.push(new Keep(current[one(y)]));
            }

            // Check if we've reached the end
            if (x >= aMax && y >= bMax) {
                return history;  // Found solution
            } else {
                // Save this point in the frontier
                frontier[k] = new Frontier(x, history);
            }
        }
    }

    throw new Error('Could not find edit script');
}

let text1 = "PQRSTUZ".split("").map(item => ({hashVal: item, content: item}));
let text2 = "PQTUARS".split("").map(item => ({hashVal: item, content: item}));

const editScript = myersDiff(text1, text2);
let diff2 = editScript.map(operation => {
    const element = operation.line;
    if (operation instanceof Keep) {
        element.status = 'unchanged';
    } else if (operation instanceof Insert) {
        element.status = 'inserted';
    } else if (operation instanceof Remove) {
        element.status = 'removed';
    }
    return element;
});

console.log(diff2);
console.log(diff2.length);