Matching windows with EMD (Earth Mover Distance)

[64z3r]

Current implementation seems to employ a greedy strategy when it comes to matching windows to saved windows (previous/saved session) when opening multiple windows at once (e.g., when Firefox opens all previous windows). A better strategy could be to use something like the EMD (Earth Mover Distance - Kantorovich Rubinstein Distance) to match all unmatched windows to saved windows.

Example (generated with ChatGPT):

'use strict';

import { SETTINGS_KEY_MATCH_THRESHOLD } from './settings'; // Assume this is your constants file
import { levensteinDistance } from './distance'; // Assume this is your Levenshtein function
import { Munkres } from 'munkres-js'; // Hungarian Algorithm implementation

/**
 * Compute the cost matrix for window matching.
 * @param {Array<Object>} savedWindows - List of saved windows from the old session.
 * @param {Array<Object>} currentWindows - List of currently open windows.
 * @returns {Array<Array<number>>} - Cost matrix.
 */
function computeCostMatrix(savedWindows, currentWindows) {
    return savedWindows.map(savedWindow => {
        return currentWindows.map(currentWindow => {
            let titleDist = levensteinDistance(savedWindow.title, currentWindow.title);
            let titleScore = (savedWindow.title.length - titleDist) / savedWindow.title.length;
            let positionCost = savedWindow.position !== currentWindow.position ? 1 : 0; // Example: binary penalty
            let workspaceCost = savedWindow.workspace !== currentWindow.workspace ? 1 : 0;

            // Combine costs: Adjust weights as necessary
            return 1 - titleScore + positionCost + workspaceCost;
        });
    });
}

/**
 * Match saved windows to current windows using the Hungarian algorithm.
 * @param {Array<Object>} savedWindows - List of saved windows.
 * @param {Array<Object>} currentWindows - List of current windows.
 * @returns {Array<Object>} - List of matched window pairs.
 */
function matchWindows(savedWindows, currentWindows) {
    let costMatrix = computeCostMatrix(savedWindows, currentWindows);
    let munkres = new Munkres();
    let assignments = munkres.compute(costMatrix);

    let matches = assignments.map(([savedIndex, currentIndex]) => {
        let cost = costMatrix[savedIndex][currentIndex];
        if (cost <= 1 - SETTINGS_KEY_MATCH_THRESHOLD) { // Respect the match threshold
            return {
                savedWindow: savedWindows[savedIndex],
                currentWindow: currentWindows[currentIndex],
                cost: cost
            };
        }
        return null; // No valid match
    });

    // Filter out invalid matches
    return matches.filter(match => match !== null);
}

// Example usage
let savedWindows = [
    { title: 'Document 1', position: '0,0', workspace: 1 },
    { title: 'Document 2', position: '1,1', workspace: 2 }
];

let currentWindows = [
    { title: 'Document 1', position: '0,0', workspace: 1 },
    { title: 'Document 2 (Edited)', position: '1,1', workspace: 2 }
];

let matchedWindows = matchWindows(savedWindows, currentWindows);
console.log(matchedWindows);

[sojusnik]

I'm curious if this approach could solve this issue.

[khimaros]

this is an interesting idea. would you be willing to test the code you've described and submit a PR?

[khimaros]

@64z3r i'm still interested in this!