Async JavaScript set operations: union, intersection, difference, complement, and equals. Includes support for objects.

setOps.js

// setOps.js MIT License © 2014 James Abney http://github.com/jabney
// async.js modification © 2015 Tobias Rittig http://github.com/diiigle

// Set operations union, intersection, symmetric difference,
// relative complement, equals. Set operations are fast.
(function() {
'use strict';
    var so = {};
    
    // global on the server, window in the browser
    var previous_setOps;

    // Establish the root object, `window` (`self`) in the browser, `global`
    // on the server, or `this` in some virtual machines. We use `self`
    // instead of `window` for `WebWorker` support.
    var root = typeof self === 'object' && self.self === self && self ||
            typeof global === 'object' && global.global === global && global ||
            this;

    if (root != null) {
        previous_setOps = root.setOps;
    }

    so.noConflict = function () {
        root.setOps = previous_setOps;
        return so;
    };
    
    //get async.js, window.async in the browser, via require on the server
    var async = root != null && root.async || typeof require == 'function' && require('async');
    
    var uidList = [], uid;

    // Create and push the uid identity method.
    uidList.push(uid = function() {
        return this;
    });

    // Push a new uid method onto the stack. Call this and
    // supply a unique key generator for sets of objects.
    so.pushUid = function(method) {
        uidList.push(method);
        uid = method;
        return method;
    };

    // Pop the previously pushed uid method off the stack and
    // assign top of stack to uid. Return the previous method.
    so.popUid = function() {
        var prev;
        uidList.length > 1 && (prev = uidList.pop());
        uid = uidList[uidList.length-1];
        return prev || null;
    };

    // Processes a histogram consructed from two arrays, 'a' and 'b'.
    // This function is used generically by the below set operation 
    // methods, a.k.a, 'evaluators', to return some subset of
    // a set union, based on frequencies in the histogram. 
    function process(a, b, evaluator, processCallback) {
        async.waterfall([
            function aHistogram(callback){
                // Create a histogram of 'a'.
                var hist = Object.create(null), ukey;
                async.each(a,
                    function(value,cb) {
                        ukey = uid.call(value);
                        if(!hist[ukey]) {
                            hist[ukey] = { value: value, freq: 1 };
                        }
                        cb();},
                    function(err){
                        if(err) return callback(err);
                        callback(null,hist);
                    });
            }, function bHistogram(hist,callback) {
                // Merge 'b' into the histogram.
                var ukey;
                async.each(b,
                    function(value,cb) {
                        ukey = uid.call(value);
                        if (hist[ukey]) {
                            if (hist[ukey].freq === 1)
                                hist[ukey].freq = 3;
                        } else {
                            hist[ukey] = { value: value, freq: 2 };
                        }
                        cb();},
                    function(err) {
                        if(err) return callback(err);
                        callback(null,hist);
                    });
            }, function evaluate(hist, callback){
                // Call the given evaluator.
                if (typeof evaluator == 'function') {
                    var out = [];
                    async.forEachOf(hist,function(item,k,cb) {
                        if (evaluator(item.freq)) out.push(item.value);
                        cb();
                    },function(err){
                        if(err) return callback(err);
                        callback(out);
                    });
                } else {
                    return callback(hist);
                }
            }
            ],processCallback);
    };

    // Join two sets together.
    // Set.union([1, 2, 2], [2, 3]) => [1, 2, 3]
    so.union = function(a, b, cb) {
        process(a, b, function(freq) {
            return true;
        }, cb);
    };

    // Return items common to both sets. 
    // Set.intersection([1, 1, 2], [2, 2, 3]) => [2]
    so.intersection = function(a, b, cb) {
        return process(a, b, function(freq) {
            return freq === 3;
        }, cb);
    };

    // Symmetric difference. Items from either set that
    // are not in both sets.
    // Set.difference([1, 1, 2], [2, 3, 3]) => [1, 3]
    so.difference = function(a, b, cb) {
        return process(a, b, function(freq) {
            return freq < 3;
        }, cb);
    };

    // Relative complement. Items from 'a' which are
    // not also in 'b'.
    // Set.complement([1, 2, 2], [2, 2, 3]) => [3]
    so.complement = function(a, b, cb) {
        return process(a, b, function(freq) {
            return freq === 1;
        }, cb);
    };

    // Returns true if both sets are equivalent, false otherwise.
    // Set.equals([1, 1, 2], [1, 2, 2]) => true
    // Set.equals([1, 1, 2], [1, 2, 3]) => false
    so.equals = function(a, b, cb) {
        process(a, b,null, function(err, hist){
            if(err) return cb(err);
            async.detect(Object.keys(hist),function(key, cb){
               cb(hist[key].freq != 3);
            },function(result){
                cb(typeof result == 'undefined');
            });
        });
    };
    
    //export mechanism taken from async.js

    // Node.js
    if (typeof module === 'object' && module.exports) {
        module.exports = so;
    }
    // AMD / RequireJS
    else if (typeof define === 'function' && define.amd) {
        define([], function () {
                return so;
        });
    }
    // included directly via <script> tag
    else {
        root.setOps = so;
    }

})();

setOps.md

async setOps.js

Set operations in setOps.js take two arrays and return the result of the operation as an array to the callback. Supported operations are union, intersection, difference, complement, and equals. difference is the symmetric difference and complement is the relative complement. The set operations are fast, even for large arrays. A test on JSPerf validates its slow behaviour compared to the synchronous version.

Usage

Requires async.js from https://github.com/caolan/async

var so = setOps,
a = [1, 1, 2, 3, 3], // [1, 2, 3]
b = [3, 4, 4, 5, 5]; // [3, 4, 5]

function plotResult(err,result){
    console.log(result;
}

// Join two sets together. A ∪ B
so.union(a, b, plotResult); // => [1, 2, 3, 4, 5]

// The intersection of two sets. A ∩ B
so.intersection(a, b, plotResult); // => [3]

// The symmetric difference of two sets. A Δ B
so.difference(a, b, plotResult); // => [1, 2, 4, 5]

// The relative complement, or a minus b. A\B
so.complement(a, b, plotResult); // => [1]

// Set equality. A = B
so.equals(a, b, plotResult); // => false
so.equals(a, [1, 2, 3], plotResult); // => true

Using Objects

Arrays of objects can be used in set operations as long as they have some type of unique identifier. If objects have a toString method which returns the unique identifier, they can be used as is. If not, a custom uid method can be specified. The methods pushUid and popUid work together to set and remove a context for returning an object's identifier.

var so = setOps,
a = [{id:1}, {id:2}],
b = [{id:2}, {id:3}],

// Push a method to retrieve object ids onto the uid stack.
uidMethod = so.pushUid(function() {
  return this.id;
});

// Peform set operations.

so.union(a, b, plotResult); // => [{id:1}, {id:2}, {id:3}]

so.intersection(a, b, plotResult); // => [{id:2}]

so.difference(a, b, plotResult); // => [{id:1}, {id:3}]

so.complement(a, b, plotResult); // => [{id:1}]

so.equals(a, b, plotResult); // => false
so.equals(a, [{id:1}, {id:2}], plotResult); // => true

// Now that we're done, restore the previous uid method
// (by default an identity method).

uidMethod = so.popUid();