Sequential data structures such as arrays (lists), stacks, queues, and lists should be familiar to you. Now we’re going to learn about sets, which are sequential data structures that do not allow repeating values. We’ll learn how to create data structures like collections, how to add and remove values, and how to search for the presence of values. You will also learn how to perform mathematical operations such as union, intersection, and difference sets.

This chapter includes:

• Create a Set class from scratch
• Let’s do the math with Set

Building a data set

A collection is a set of unordered and unique (that is, non-repeating) items. This data structure uses the same mathematical concepts as finite sets, but applies to computer science data structures.

Before diving into the computer science implementation of sets, let’s look at the mathematical concepts. In mathematics, a set is a set of different objects.

For example, a set of natural numbers consisting of integers greater than or equal to 0: N = {0, 1, 2, 3, 4, 5, 6,… }. The list of objects in the collection is surrounded by curly braces ({}).

There is also a concept called an empty set. An empty set is a set that contains no elements. For example, the set of primes between 24 and 29, since there are no primes between 24 and 29 (natural numbers greater than 1 with no positive factors other than 1 and itself), the set is empty. The empty set is represented by {}.

You can also think of a set as an array with no repeating elements and no concept of order. In mathematics, sets also have such basic operations as union, intersection and difference set. These operations are also described in this article.

Creating a collection class

Creating a base class

Start with the following Set class and its constructor declaration.

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

One very important detail is that we use objects instead of arrays to represent collections (items). However, you can also do it with an array. The object implementation here is similar to the object implementation we learned in Chapters 4 and 5. Similarly, JavaScript objects do not allow a single key to point to two different attributes, and ensure that all elements in a collection are unique.

Next, you need to declare some of the methods available to the collection (we’ll try to emulate the same Set class implemented in ECMAScript 2015).

• Add (element) : Adds a new element to the collection.
• Delete (element) : Removes an element from the collection.
• Has (element) : True if the element is in the collection, false otherwise.
• Clear () : Removes all elements from the collection.
• Size () : returns the number of elements contained in the collection. It is similar to the length property of an array.
• Values () : returns an array containing all the values(elements) in the collection.

From the (item) method

The first thing to implement is the has(Element) method, because it gets called by add, DELETE, and other methods. It checks whether or not an element exists in the set, so let’s look at the implementation.

has(item) {
    return Object.prototype.hasOwnProperty.call(this.items, item);
}
Copy the code

In addition to using the Object. The prototype. The hasOwnProperty method, you can also use the item in this. The items and enclosing the items. The hasOwnProperty (item) to realize from the method.

Add (item) method

Next, implement the add(item) method.

add(item) {
    if (this.has(item)) {
        return false;
    }
    this.items[item] = item;
    return true;
}
Copy the code

Given an item, you can check whether it exists in the collection. If not, we add the item to the collection and return true to indicate that the element was added. If the element is already in the collection, return false to indicate that it was not added.

Delete (item) and clear() methods

Next, implement the delete(item) method.

delete(item) {
    if (this.has(item)) {
        delete this.items[item];
        return true
    }
    return false
}
Copy the code

In the delete method, we verify that the given item exists in the collection. If it exists, remove the item from the collection, returning true to indicate that the element was removed; Otherwise return false.

Since we are using objects to store the items of the collection, we can simply delete the elements from the Items using the delete operator of the object.

If you want to remove all values from a collection, use the clear method.

clear() {
    this.items = {}
}
Copy the code

The size () method

There are several ways to implement the size method:

1. Use a length variable that is controlled whenever the add or DELETE methods are used
2. Object.keys(this.items).length
3. usefor in(Remember to usehasOwnPropertyJudge)
4. .

Now we use the method in 2, the code is as follows

size() {
    return Object.keys(this.items).length;
}
Copy the code

Values () method

To implement the values() method, we can also use the built-in values method of the Object class.

values() {
    return Object.values(values); 
}
Copy the code

The object.values () method returns an array of all property values for a given Object. It was added in ECMAScript 2017 and is currently only available in modern browsers.

Using the Set class

Now that the data structure is complete, take a look at how to use it. Try executing some commands to test our Set class.

const set = new Set(a); set.add(1); 
console.log(set.values()); / / output [1]
console.log(set.has(1)); / / output true
console.log(set.size()); / / output 1
set.add(2); 
console.log(set.values()); // Output [1, 2]
console.log(set.has(2)); / / output true
console.log(set.size()); 2 / / output
set.delete(1); 
console.log(set.values()); / / output [2]
set.delete(2); 
console.log(set.values()); / / output []
Copy the code

Set operations

Set is a fundamental concept in mathematics and is also very important in the field of computer science. One of its main applications in computer science is databases, which are the foundation of most applications. Collections are used for query design and processing. Set operations are used when we create a query that retrieves a set of data from a relational database (Oracle, Microsoft SQL Server, MySQL, etc.) and the database returns a set of data. When we create an SQL query command, we can specify whether to retrieve all or a subset of the data from the table; You can also get data that is shared by two tables, data that exists only in one table (not in the other), or data that exists in both tables (through other operations). These SQL domain operations are called joins, and the foundation of SQL joins is set operations.

We can perform the following operations on the set.

• Union: For a given set of two sets, returns a new set containing all elements of both sets.
• Intersection: For two given sets, returns a new set containing elements from both sets.
• Difference set: For two given sets, return a new set containing all elements that exist in the first set and do not exist in the second set.
• Subset: Verifies that a given set is a subset of another set.

It is important to note that the union, intersection, and Difference methods implemented in this article do not modify the current instance of the Set class or the otherSet passed in as a parameter. Methods and functions that have no side effects are called pure functions. A pure function does not modify the current instance or argument, but generates a new result. This is a very important concept in functional programming.

And set

The mathematical concept of union. The union of set A and set B is represented as A union BA∪ BA∪B, as defined below.

It means that x (element) exists in A, or x exists in B. The figure below shows the union operation.

Code implementation

union(otherSet) {
    let unionSet = new Set(a);let values = this.values();
    values.forEach((value) = > {
        unionSet.add(value);
    });
    values = otherSet.values();
    values.forEach((value) = > {
        unionSet.add(value);
    });
    return unionSet;
}
Copy the code

intersection

The mathematical concept of intersection. The intersection of set A and set B is expressed as A∩BA ∩BA ∩B, defined as follows.

That means x exists in A, and x exists in B. The graph below shows the intersection operation.

Code implementation

intersection(otherSet) {
    let intersectionSet = new Set(a);const values = this.values();
    const otherValues = otherSet.values();
    let smallerValues = values;
    let biggerValues = otherValues;
    if (otherValues.length < values.length) {
        smallerValues = otherValues;
        biggerValues = values;
    }
    smallerValues.forEach((value) = > {
        if(biggerValues.includes(value)) { intersectionSet.add(value); }});return intersectionSet;
}
Copy the code

In order to reduce the number of loops, which set has the smallest length is determined in the code, and then the set with smaller length is loops to reduce the number of loops.

Difference set

The mathematical concept of difference sets. The difference set of sets A and B is expressed as A− BA-BA −B, defined as follows.

That means x exists in A, and x does not exist in B. The figure below shows the difference set operation of set A and set B.

Code implementation

difference(otherSet) {
    let differenceSet = new Set(a);this.values().forEach((value) = > {
        if (!otherSet.has(value)) {
            differenceSet.add(value);
        }
    });
    return differenceSet;
}
Copy the code

A subset of

The last set operation I want to introduce is subset. An example of its mathematical concept is that the set A is A subset of the set B (or that the set B contains the set A), expressed as A∈BA ∈BA ∈B, defined as follows.

That means that every x in set A has to be in set B. The figure below shows that set A is A subset of set B.

Code implementation

isSubsetOf(otherSet) {
    if (this.size() > otherSet.size()) {
        return false;
    }
    let isSubset = true;
    const values = this.values();
    const size = this.size();
    for (let i = 0; i < size; i++) {
        if(! otherSet.has(values[i])) { isSubset =false;
            break; }}return isSubset;
}
Copy the code

The resources

• Learn JavaScript data structures and algorithms 3rd edition

Articles on other data structures

• The List of data structure | let’s learn a piece of data structure
• Data structure of Stack | let’s learn a piece of data structure
• Data structure of the Queue | let’s learn a piece of data structure
• Data structure of the LinkedList | let’s learn a piece of data structure