Set

Set is a data structure that does not contain duplicate items, and the items are ordered by insertion.

Example Use Cases#

Eliminating duplicates, checking the presence of an item in a collection, comparison of two or more lists.

Set Methods#

1. has(item) - checks for the presence of an element.
2. add(item) - inserts a new element if the specified value isn't already in the set. Returns the set object with the added value.
3. delete(item) - removes the specified element. Returns a boolean that asserts whether it was successfully removed or not.
4. values() - an iteration method that returns all elements in the set, ordered by insertion.
5. size - returns the number of values in the set.

JavaScript ES6 (ES2015) has a built-in Set object, which contains all of the methods above, and more (set.size in ES6 is a number property and not a method).

However, it does not have all of the common methods that are expected from a set data structure, such as union, intersection, difference, symmetricDifference, isSuperSet.

Set Data Structure Implementation in TypeScript#

Not needed irl because JavaScript has a built-in Set object, but it's useful to see how the methods are implemented at a basic level to understand under the hood.

interface ISet<T> {
    size: number;
    has(item: T): boolean;
    add(item: T): this;
    delete(item: T): boolean;
}
class SetExt<T> implements ISet<T> {
    private items: T[] = [];
    size: number = 0;
    constructor(params?: T[]) {
        if (!!params) {
            this.items = [...params];
            this.size = params.length;
        }
    }
    has(item: T): boolean {
        return this.items.indexOf(item) !== -1;
    }
    
    add(item: T): this {
        if (!this.has(item)) {
            this.items.push(item);
            this.size++;
        }
        return this;
    }
    delete(item: T): boolean {
        if (this.has(item)) {
            this.items.splice(this.items.indexOf(item), 1);
            this.size--;
            return true;
        } else {
            return false;
        }
    }
}

The implementation above uses array methods such as indexOf() for lookup, which has a linear time complexity O(n). Thus, the above implementation can be improved for performance by using hash tables instead of regular arrays to store the collection.

You can refer to hash table to get an idea of how a hash table works.

Extending the JavaScript Set Object#

We mentioned earlier that the built-in JavaScript Set object does not have support for the common methods that you'd expect from a set data structure, such as:

1. union - returns the combined values of two sets.
2. intersection - returns a new set that contains the common elements in two sets.
3. difference - returns a new set that contains elements from the first set which are not in the second set.
4. symmetricDifference - returns a new set that contains elements from the first set which are not present in the second set, and elements of the second set which are not present in the first set.
5. isSuperSet - checks if all elements of subset are present in the set.

This time, we'll extend the Set interface and implement these missing methods. Take not that extending the Set interface allows us to use the built-in Set object methods this time.

interface ISet<T> extends Set<T> {
    size: number;
    has(item: T): boolean;
    add(item: T): this;
    delete(item: T): boolean;
    union(otherSet: ISet<T>): SetExt<T>;
    intersection(otherSet: ISet<T>): SetExt<T>;
    difference(otherSet: ISet<T>): SetExt<T>;
    symmetricDifference(otherSet: ISet<T>): SetExt<T>;
    isSuperSet(subset: ISet<T>): boolean;
}
class SetExt<T> implements ISet<T> {
    private items: Set<T> = new Set();
    size: number = 0;
    constructor(params?: T[]) {
        if (!!params) {
            for (let i = 0; i < params.length; i++) {
                if (!this.items.has((params[i]))) {
                    this.items.add(params[i]);
                    this.size++;
                }
            }
        }
    }
    has(item: T): boolean {
        return this.items.has(item);
    }
    
    add(item: T): this {
        this.items.add(item);
        this.size++;
        return this;
    }
    delete(item: T): boolean {
        if (this.has(item)) {
            this.size--;
        }
        return this.items.delete(item);
    }
    union(otherSet: ISet<T>): SetExt<T> {
        const union = new SetExt<T>();
        this.items.forEach(item => union.add(item));
        otherSet.forEach(item => union.add(item));
        return union;
    }
    intersection(otherSet: ISet<T>): SetExt<T> {
        const intersection = new SetExt<T>();
        this.items.forEach(item => {
            if (otherSet.has(item)) {
                intersection.add(item);
            }
        });
        return intersection;
    }
    difference(otherSet: ISet<T>): SetExt<T> {
        const difference = new SetExt<T>();
        this.items.forEach(item => {
            if (!otherSet.has(item)) {
                difference.add(item);
            }
        });
        return difference;
    }
    symmetricDifference(otherSet: ISet<T>): SetExt<T> {
        const difference = new SetExt<T>([...this.items.values()]);
        otherSet.forEach(item => {
            if (difference.has(item)) {
                difference.delete(item);
            } else {
                difference.add(item);
            }
        });
        return difference;
    }
    isSuperSet(subset: ISet<T>): boolean {
        subset.forEach(item => {
            if (!this.items.has(item)) {
                return false;
            }
        });
        return true;
    }
    /* because we're extending the Set object, we must define the other Set methods to satisfy the Set interface */
    [Symbol.iterator]() {
        return this.items.values();
    }
    [Symbol.toStringTag] = this.items.toString();
    values(): IterableIterator<T> {
        return this.items.values();
    }
    forEach(callbackfn: (value: T, value2: T, set: Set<T>) => void, thisArg?: any): void {
        return this.items.forEach(callbackfn, thisArg);
    }
    keys(): IterableIterator<T> {
        return this.items.keys();
    }
    entries(): IterableIterator<[T, T]> {
        return this.items.entries();
    }
    clear(): void {
        return this.items.clear();
    }
}