Adding missing features to Set
Published
ES2015 bought a Set
constructor to JavaScript. It's pretty barebones,
consisting of a constructor which creates objects with a few methods for adding,
removing, checking if something is a member, and iterating over the set.
Instances have the essential quality of a set; an item is a member of the set or
not a member. Unlike an array, an item cannot be an element more than once. In
other words you can avoid using arrays and doing a lot of indexOf
checking.
For example, abusing an array to act like a set is very common:
var myCollection = [];
// Check if element is in the collection.
function has(collection, element) {
return collection.indexOf(element) !== -1;
}
// Add an element to the collection.
function add(collection, element) {
if (!has(collection, element)) {
collection.push(element);
}
}
add(myCollection, 123);
has(myCollection, 123); // returns true
has(myCollection, 456); // returns false
Using a set is more straight forward:
var myCollection = new Set();
myCollection.add(123); // add an element
myCollection.has(123); // returns true
myCollection.has(456); // returns false
That's all grand, but a colleague of mine, a programmer dipping a toe into
modern JS, noted that Set
lacks some functions that you might expect it to
have out of the box, such as union, intersection and (relative)
complement.
I'd implement these as static methods of Set
, and shim them in. Hopefully
these methods will be added to the standard in the future. Until then, here are
some possible implementations.
Union
The union of two sets is defined as the set of elements found in either or both sets.
Set.union = function (a, b) {
const unionSet = new Set();
for (const element of a) {
unionSet.add(element);
}
for (const element of b) {
unionSet.add(element)
}
return union;
};
This function iterates over both sets, adding their elements to a new set, which is then returned.
As a one liner:
Set.union = (a, b) => new Set([...a, ...b]);
Sets are iterable, so the spread operator can be used to expand them as arrays. Set can also take an array as an argument, filling the constructed set object with elements from the array. This means that both sets can be spread into an array literal and fed back into the set constructor. Since repeated elements are ignored, the resultant set is the union of the two input sets.
Intersection
The intersection of two sets is defined as the set of elements they have in common.
Set.intersection = function (a, b) {
const [small, big] = a.size < b.size ? [a, b] : [b, a];
const intersectionSet = new Set();
for (const element of small) {
if (big.has(element)) {
intersectionSet.add(element);
}
}
return intersectionSet;
};
The first line of this one is an optimisation. The largest an intersection can
be is the size of the smaller set. The first line uses destructuring assignment
and a ternary to assign the smaller set to small
and the larger set to big
.
The intersectionSet
is then constructed, and small
looped over to fill it
with elements which are also in the big
.
If you want a one liner for this (and don't care about the size optimisation):
Set.intersection = (a, b) => new Set([...a].filter(element => b.has(element)));
This uses similar tricks to Set.union
. One set is expanded as an array, and
then filtered to an array of elements which are in the other. The filtered array
is then fed to Set
to get the intersection set.
Relative complement
The relative complement of A in B is the set of those elements in B which are not in A.
Set.complement = function (a, b) {
const complementSet = new Set();
for (const element of b) {
if (!a.has(element)) {
complementSet.add(element);
}
}
return complementSet;
};
This function makes a new set and iterates over the second set, filling the new set with elements of the second set which are not in the first.
As a one liner:
Set.complement = (a, b) => new Set([...b].filter(element => !a.has(element)));
This uses similar tricks to the Set.intersection
one liner. It expands the
second set as an array, filters it down to elements not in the first, and then
instantiates a new Set
with the filtered array.