Qubyte Codes

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.