What is a set

A collection of

A collection is a collection of unordered and unique (that is, unrepeatable) items.

In mathematics, a set is a collection of different objects. 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 {}.

An empty set

An empty set is a set that does not contain any elements. The empty set is represented by {}.

Implement collection

Defining a collection class

We use ES6’s class syntax to create an object-based Set class:

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

Next, we declare some available methods for collections:

  • Add (Element) Adds a new element to the collection
  • Delete (Element) Removes an element from the collection
  • Has (Element) Determines whether an element is in the collection
  • Clear () removes all elements from the collection
  • Size () returns the number of elements contained in the collection
  • Values () returns an array containing all the elements of the collection
  • IsEmpty () determines whether the collection isEmpty
  • Size () returns the number of elements in the collection
  • Clear () clears the collection
  • ToString () prints the elements of the collection as strings

Let’s implement these methods one by one:

Add adds a new element to the collection

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

When you add an element to a collection, first check to see if it exists in the collection. If it does not, add it to the collection and return true to indicate that the element was added. If the collection already has the element, return false to indicate that the element was not added.

Delete Removes an element from the collection

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

  return false;
}
Copy the code

Similarly, when an element is removed from the set, it first checks whether the element exists in the set. If so, it is removed from the set and returns true, indicating that the element was removed. If it does not exist, return false.

Has determines whether an element is in a set

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

We use the Object prototype method hasOwnProperty to determine if an element is in a collection. The hasOwnProperty method returns a Boolean value indicating whether the object has a particular property.

Clear removes all elements from the collection

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

Size returns the number of elements contained in the collection

Keys ()

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

In the size method, we use the Keys method of the Object class to get the number of elements contained in the collection. The keys method returns an array containing all the attributes of a given object, and we can then use the array’s Length attribute to return the number of elements in the collection.

Method 2: Use for… In circulation

size() {
  let count = 0;
  for (let key in this.items) {
    if (this.items.hasOwnProperty(key)) {
        count++
    }
  }
  return count;
}
Copy the code

We define a count variable to store the number of elements in the collection, and then use for… The in loop iterates through all the properties of the Items object, checks if they are properties of the object itself, increments the value of the count variable if they are, and finally returns the count variable at the end of the method.

Values returns an array containing all the elements of the collection

Method 1: Use object.values ()

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

We can easily retrieve all the elements of the collection using the values method built into the Object class, but the Object.values method is currently only available in modern browsers.

Method 2: Use for… In circulation

values() { let values = []; For (let the key in this. The items) {if (this. Items. HasOwnProperty (key)) {/ / note that the key is the same as the value we save a collection of elements, So you can push key directly into values. Value.push (key)}}}Copy the code

IsEmpty determines whether the collection isEmpty

isEmpty() {
    return this.size() === 0;
}
Copy the code

ToString outputs the elements of the collection as strings

toString() {
  if (this.isEmpty()) {
    return '';
  }

  const values = this.values();
  let objString = `${values[0]}`;
  for (let i = 1; i < values.length; i++) {
    objString = `${objString}, ${values[i].toString()}`;
  }

  return objString;
}
Copy the code

Set operations

In mathematics, sets have union, intersection, difference, subset and so on, and we can also use our defined set classes to perform these operations.

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

And set

In mathematical concepts, the union of sets A and B is expressed as follows:

A ∪ B

The set is defined as follows:

A ∪ B = {x | x ∈ ∨ x ∈ B}

That means x is present in A, or x is present in B. The following figure shows the union operation:

Here, we implement the union method of the Set class:

Union (otherSet) {const unionSet = new Set(); This.values ().foreach (value => unionSet. Add (value)); Otherset.values ().foreach (value => unionSet. Add (value)); return unionSet; }Copy the code

First, the data structure Set provided by ES6 was used to create a new collection, unionSet, representing the union of the two collections. We then get all the values of the first Set (the current instance of the Set class), iterate over and add them all to the Set representing the union. Then do the same for the second set, and finally return the set that represents the union.

intersection

In mathematical concepts, the intersection of sets A and B is expressed as follows:

A studying B

The set is defined as follows:

A studying B = {x | x ∈ A Sunday afternoon x ∈ B}

It means that x (element) exists in A and x exists in B. The following figure shows the intersection operation:

We implement the intersection method of the Set class:

Intersection (otherSet) {// intersectionSet const intersectionSet = new Set(); // All values of the current collection (instance of the current Set class) const values = this.values(); // All values of the second set const otherValues = otherset.values (); // Let biggerSet = values; // Let smallerSet = otherValues; // Compare two sets of elements, if the other set has more elements than the current set, If (othervalues.length-values. length > 0) {biggerSet = otherValues; smallerSet = values; } // Iterate over smaller sets, ForEach (value => {if (biggerset.includes (value)) {intersectionset.add (value); }}) // Return return intersectionSet; }Copy the code

The intersection method retrieves all elements in both collections. We first create a new set intersectionSet to store the intersection results. It then retrieves all elements in the current Set instance and all elements in another Set. We assume that the current set has more elements and the other set has fewer. We compare the number of elements in the two sets. If the other set has more elements than the current set, we swap the values of biggerSet and smallerSet. Finally, the smallerSet smallerSet is iterated to calculate the common elements of the two sets.

Difference set

In mathematical concepts, the difference set of sets A and B is expressed as:

A﹣B

The set is defined as follows:

A - B = {x | x ∈ A Sunday afternoon x ∉ B}

It means that x exists in A and x does not exist in B. The following figure shows the difference set operation of sets A and B:

Subtract method we implement the Set class subtract method

Const subtractionSet = new Set(); // Subtract (otherSet) {const subtractionSet = new Set(); This.values ().foreach (value => {// Current value does not exist in otherSet, add it to difference set if (! Otherset.has (value)) {// Add the element to the collection subtractionSet.add(value); } }) return subtractionSet; }Copy the code

Subtract method results in all elements that are in set A but not in set B. We start by creating a new set variable subtractionSet to hold the difference set results. Get all the values in set A with this.values() and iterate over all the values in set A. Place the elements in set A but not in set B into the subtractionSet. After iterating over all the elements in set A, The element in the subtractionSet is the difference between sets A and B.

A subset of

In mathematical concepts, set A is A subset of set B (or B contains A), expressed as follows:

⊆ B

The set is defined as follows:

{x | ∀ x ∈ ⇒ x ∈ B}

It means that every x in set A also needs to be in set B. The following figure shows that set A is A subset of set B:

Let’s implement the isSubsetOf method of the Set class:

IsSubsetOf (otherSet) {// Verify the size of the current Set instance // The current Set instance has more elements than otherSet, If (this.size() > otherset.size ()) {return false; } // let isSubset = true; This.values ().every(value => {// If any element does not exist in otherSet, then the current Set is not a subset of otherSet. If (! otherSet.has(value)) { isSubset = false; return false; } return true; }) return isSubset; }Copy the code

The isSubsetOf method verifies whether set A is A subset of set B. We first need to verify the size of the current Set instance (Set A). If the current instance has more elements than the otherSet instance (Set B), the current Set instance is not A subset of otherSet. (The subset needs to have less than or equal to the set being compared).

Next, we assume that the current collection is a subset of the given collection, and then iterate over all the elements of the current collection and verify that they exist in otherSet. If any element does not exist in otherSet, then the current collection is not a subset of the given collection, and we return false. If all elements exist in otherSet, the current collection is a subset of the given collection.

The complete code

class Set { constructor() { this.items = {}; } // Add (element) {if (! this.has(element)) { this.items[element] = element; return true; } return false; } // Delete (element) {if (this.has(element)) {delete this.items[element]; return true; } return false; } / / judge whether an element is present in the collection from the element () {return Object. The prototype. The hasOwnProperty. Call (enclosing the items, element); Clear () {this.items = {}; clear() {this.items = {}; } // Return the number of elements in the set size() {let count = 0; for(let key in this.items) { if (this.items.hasOwnProperty(key)) { count++; } } return count; } // Return an array containing all elements of the set values() {let values = []; for (let key in this.items) { if (this.items.hasOwnProperty(key)) { values.push(key); } } return values; } // union(otherSet) {const unionSet = new Set(); this.values().forEach(value => unionSet.add(value)); otherSet.values().forEach(value => unionSet.add(value)); return unionSet; } // Intersection intersection(otherSet) {const intersectionSet = new Set(); const values = this.values(); const otherValues = otherSet.values(); let biggerSet = values; let smallerSet = otherValues; if (otherValues.length - values.length > 0) { biggerSet = otherValues; smallerSet = values; } smallerSet.forEach(value => { if (biggerSet.includes(value)) { intersectionSet.add(value); } }) return intersectionSet; } // Subtract (otherSet) {const subtractionSet = new Set(); this.values().forEach(value => { if (! otherSet.has(value)) { subtractionSet.add(value) } }) return subtractionSet; } // subset isSubsetOf(otherSet) {if (this.size() > otherset.size ()) {return false; } let isSubset = true; this.values().every(value => { if (! otherSet.has(value)) { isSubset = false; return false; } return true; }) return isSubset; }}Copy the code

Set operation of ES6 Set class

And set

// function union(setA, setB) {const unionSet = new Set([...setA,...setB]); return unionSet; }Copy the code

intersection

// function intersection(setA, setB) {const intersect = new Set([... A].filter(x => b.hash (x))); return intersect }Copy the code

Difference set

Function subTract(setA, setB) {const subTractSet = new Set([... A].filter(x =>! b.has(x))); return subTractSet; }Copy the code

References:

Book: JavaScript Data Structures and Algorithms