Fast 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

// Set operations union, intersection, symmetric difference,
// relative complement, equals. Set operations are fast.
(function(so) {
'use strict';
  
  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) {
    // Create a histogram of 'a'.
    var hist = Object.create(null), out = [], ukey, k;
    a.forEach(function(value) {
      ukey = uid.call(value);
      if(!hist[ukey]) {
        hist[ukey] = { value: value, freq: 1 };
      }
    });
    // Merge 'b' into the histogram.
    b.forEach(function(value) {
      ukey = uid.call(value);
      if (hist[ukey]) {
        if (hist[ukey].freq === 1)
          hist[ukey].freq = 3;
      } else {
        hist[ukey] = { value: value, freq: 2 };
      }
    });
    // Call the given evaluator.
    if (evaluator) {
      for (k in hist) {
        if (evaluator(hist[k].freq)) out.push(hist[k].value);
      }
      return out;
    } else {
      return hist;
    }
  };

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

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

  // 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) {
    return process(a, b, function(freq) {
      return freq < 3;
    });
  };

  // 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) {
    return process(a, b, function(freq) {
      return freq === 1;
    });
  };

  // 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) {
    var max = 0, min = Math.pow(2, 53), key,
      hist = process(a, b);
    for (var key in hist) {
      max = Math.max(max, hist[key].freq);
      min = Math.min(min, hist[key].freq);
    }
    return min === 3 && max === 3;
  };
})(window.setOps = window.setOps || Object.create(null));

setOps.md

setOps.js

Set operations in setOps.js take two arrays and return the result of the operation as an array. 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.

Usage

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

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

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

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

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

// Set equality. A = B
so.equals(a, b); // => false
so.equals(a, [1, 2, 3]); // => 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); // => [{id:1}, {id:2}, {id:3}]

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

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

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

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

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

uidMethod = so.popUid();