What's a good mathematical sets implementation in JavaScript?

Question

Where is a good mathematical sets implementation for JavaScript? It should include efficient implementations of intersection, union, complement, and (for bonus points) the Cartesian product.

No, it's not homework. I got a yubikey, it is a USB keyboard that types a sequence chosen from 16 keycodes to type a 128-bit one time password (otp). To make it more useful, software should detect the keyboard layout based on the characters produced and map those characters back to what they would be in the "us" layout for compatibility with the existing backend.

So I've got 93 different sequences of 16 characters representing everything the yubikey can type in each of 430 keyboard layouts. (Many layouts are the same for this purpose.) The possible mappings for a particular otp is each 16-character sequence that contains every character in the otp.

To find this efficiently I use a reverse index mapping each possible character to a list of the keyboard layouts that use that character. The answer is the intersection of each entry of the reverse index for each unique character in the otp. This almost always winds up with exactly 1 element.

It would be easier to write this cross-browser with a good implementation of Set().

Code so far is at http://dingoskidneys.com/~dholth/yubikey/

Answer 1

Sylvester is a good library for doing vector and matrix Math in Javascript. It's the only Math library I can think of right now.

Answer 2

In the program that sparked this question, a set is an Array and intersect is

s = [1,2,3];
q = [3,4,5];
sq = s.filter(function(x) {
    return q.indexOf(x) >= 0;
});

Of course it doesn't work in ie.

Answer 3

I don't know of any existing implementations, but if your set elements are strings (or have a unique string representation) you can use JavaScript objects pretty easily. The elements would be the object properties, and the value could be anything.

// Make a set from an array of elements
function makeSet(items) {
    var set = {};
    for (var i = 0; i < items.length; i++) {
        set[items[i]] = true;
    }
    return set;
}

function copyInto(s, copy) {
    for (var item in s) {
        if (s[item] === true) {
            copy[item] = true;
        }
    }
}

function union(s1, s2) {
    var u = {};
    copyInto(s1, u);
    copyInto(s2, u);
    return u;
}

function intersection(s1, s2) {
    var i = {};
    for (var item in s1) {
        if (s1[item] === true && s2[item] === true) {
            i[item] = true;
        }
    }
    return i;
}

function difference(s1, s2) {
    var diff = {};
    copyInto(s1, diff);
    for (var item in s2) {
        if (s2[item] === true) {
            delete diff[item];
        }
    }
    return diff;
}

// etc.

You could also use item in set or set.hasOwnProperty(item) instead of set[item] === true, but checking by for true explicitly, you automatically ignore any functions that might be attached to the object (in case someone modified Object.prototype, or it's not a plain object).