udiff.js

/**
 * computes the what elements were added to, and removed from, s1
 * to obtain s2, where s1 and s2 are assumed to be unordered Array
 * possibly with duplicates
 * uDiff([1,3], [2,3]) --> {added: [2], removed: [1]}
 * uDiff([1,2,3], [2,3,1]) --> {added: [], removed: []}
 * uDiff([1,2,1], [1,2,2]) --> {added: [2], removed: [1]}

 * @param s1 Array
 * @param s2 Array
 * @return object {added: [], removed: []} object of lists containing the elements that need to be
 *   added, resp. removed to/from s1 to obtain s2
 */
var uDiff = function(s1, s2) {
    if (!Array.isArray(s1) || !Array.isArray(s2)) {
        throw new Error("s1 and s2 params must be arrays");
    }
    var counts = {};
    var added = [];
    var removed = [];
    var i, item;

    for (i = 0; i < s2.length; i++) {
        counts[s2[i]] = (counts[s2[i]] === undefined) ? 1 : counts[s2[i]] + 1;
    }
    for (i = 0; i < s1.length; i++) {
        counts[s1[i]] = (counts[s1[i]] === undefined) ? -1 : counts[s1[i]] - 1;
    }
    for (item in counts) {
        if (counts[item] > 0) {
            for (i = 0; i < counts[item]; i++) {
                added.push(item);
            }
        } else if (counts[item] < 0) {
            for (i = counts[item]; i < 0; i++) {
                removed.push(item);
            }
        }
    }
    return {added: added, removed: removed};
};