Data Structures & Algorithms in JavaScript(Sets)

Hello Everyone, this is part 9 in the series of blogs about data structures and algorithms in JavaScript, In this blog, I will cover Set.

What is Set?

Sets are a type of associative containers in which each element has to be unique because the value of the element identifies it. The value of the element cannot be modified once it is added to the set, though it is possible to remove and add the modified value of that element - geeksforgeeks

List Of Operations Available

• Add: Insert an element in the set if present not.
• Delete: Remove an element from the set.
• Has : Return true if the an element is present or else return false.
• Size: Return Size of the Set.
• isEmpty : Check if the set is empty if empty return true else false.
• Union: Return new Set which contains all the elements from two sets.
• Intersection: Return new Set which contains the intersecting element from two sets.
• Difference: Return new Set only containing the elements which are not present in other sets.
• isSubset: Return true if all elements are present in the given otherSet.

Set Only Contains Unique Elements in it.

Implementation of Set in Javascript

Let start by defining an ES6 class class name Set that has one property, items which will hold the elements in the set.we are using objects to store elements in the set instead, you can also use an array.

 class Set {
    constructor() {
        this.items = {};
    }
 }

Add

While inserting an element into the Set, we first need to check if it already exists or not. By using has a method.

1. if the element is already present
   • Return false
2. Else insert an element into the Set.
   • Set items property key and value as an element.

 add(element) {
    if (!this.has(element)) {
        this.items[element] = element;
        return true;
    }
    return false;
    }

Has

Check if the element already exists in the set or not.
You can loop until the entire the items and compare the given element with the set elements. If a match is found then return true or else false.
Or you can javascript built-in method of Object.prototype.hasOwnProperty()

 has(element) {
        return Object.prototype.hasOwnProperty.call(this.items, 
 element);
    }

Delete

Remove an element from the set.

• Check if the element is already present
  • If not present return false.
  • Else delete the element from the items property.

 delete(element) {
        if (this.has(element)) {
            delete this.items[element];
            return true;
        }
        return false;
    }

Elements

Return all elements present in the Set

 elements(){
        let elements = [];
        for (const key in this.items) {
            if (this.items.hasOwnProperty(key)) {
                elements.push(key);
            }
        }
        return elements;
    }

Set Data Structure was also introduced in the ES6, javascript all the methods defined until know is present in Standard ES6 Set.

Set Operations

In mathematics, a set also has some basic operations such as union, intersection, and difference.

Union

The union of the sets A and B, denoted by A ∪ B. It is set only contains distinct elements from set A or set B or both.

Eg :- 

Set A = {1,2,3,4,5,6}
Set B = {3,4,5,10}

A ∪ B = { 1,2,3,4,5,6,10 }

• otherSet Must be an Instance of Set if not throw an error.
• Define a new Union Set.
• Loop both the Sets and add elements into the Union Set if not present.

union(otherSet){
        if (!(otherSet instanceof Set)) {
            throw new Error("Must be Instance Of Set");
        }
        const unionSet = new Set();
        this.elements().forEach(element => {
            unionSet.add(element);
        });
        otherSet.elements().forEach(element => {
            unionSet.add(element);
        });

        return unionSet;

    }

Intersection

The intersection of the sets A and B, denoted by A ∩ B, is the Set of elements belongs to both A and B, only common elements.

Eg :- 

Set A = {1,2,3,4,5,6}
Set B = {3,4,5,10}

A ∩ B = {3,4,5 }

• otherSet Must be an Instance of Set if not throw an error.
• Define a new Intersection Set.
• Loop the Set and add elements into the Intersection Set if and only if, the elements are present in both the Sets.

  intersection(otherSet){
        if (!(otherSet instanceof Set)) {
            throw new Error("Must be Instance Of Set");
        }
        const intersectionSet = new Set();
        this.elements().forEach(element => {
            if (otherSet.has(element)) {
                intersectionSet.add(element);
            }
        });

        return intersectionSet;
    }

Difference

The difference between sets A and B is denoted by A – B. Only containing elements of set A but not in B.

Eg :- 

Set A = {1,2,3,4,5,6}
Set B = {3,4,5,10}

A – B = {1,2,6}

• otherSet Must be an Instance of Set if not throw an error.
• Define a new Difference Set.
• Loop the Set and add elements into the Difference Set which are not common in otherSet

difference(otherSet){
        if (!(otherSet instanceof Set)) {
            throw new Error("Must be Instance Of Set");
        }
        const differenceSet = new Set();
        this.elements().forEach(element => {
            if (!otherSet.has(element)) {
                differenceSet.add(element);
            }
        });
        return differenceSet;
    }

isSubset

B is a subset of A, denoted by B ⊆ A or equivalently.if only if all the elements of B are present in A.

• otherSet Must be an Instance of Set if not throw an error.
• Loop the otherSet check if all the elements are present or not or use every method.

isSubset(otherSet){
        if (!(otherSet instanceof Set)) {
            throw new Error("Must be Instance Of Set");
        }
        if (!(otherSet.size() > this.size())) {
            return false;
        }
        let isSubset  = true;
        this.elements().every(element => {
            if (!otherSet.has(element)) {
                isSubset = false;
                return;
            }
        });

        return isSubset;

    }

you get the full source here

Conclusion :

Methods	Complexity
Add	O(n)
Delete	O(1)
Has	O(n)

So, stay tuned for the next blog, in which I will cover another DS Dictionary