Happy holiday come to an end, continue our learning ~

Set (Set)

As we learned in mathematics, a Set is composed of a group of disordered but interrelated members. Each member can only appear once in a Set. Different from dictionaries and linked lists, it is a data structure containing different elements (elements in a Set are called members). From its definition, we can see that it has two very important characteristics: first, the members of the set are unordered; second, the members of the set are not identical, that is, there are no identical members in the set.

In fact, collections are not a data type in many programming languages, but they can be useful if you need to create a data structure to hold unique elements. Let’s take a look at how to implement a collection in JS.

Definition of set

To implement a set, we first need to understand some of its definitions

  • A set containing no members is called an empty set, and a set containing all possible members is called a complete set.
  • Two sets are said to be equal if their members are identical.
  • If all members of a set are contained in another set, the former set is called a subset of the latter.

Operation of set

Generally speaking, there are three basic operations for collections:

  • Union: To combine the members of two sets to create a new set
  • Intersection: A new set formed by the common members of two sets
  • Complement: A new set of members belonging to one set but not to another

Implementation of collections

We use arrays to store data. According to the methods we learned and mentioned above, we can define the constructor of a Set as follows (in order to distinguish the Set type of ES6, we choose to name it MySet) :

// Constructor function MySet () {this.datastore = []; // Data store this.add = add; // Add member this.remove = remove; // Delete member this.size = size; // This. Union = union; // this. Intersect = union; // Set this. Subset = subset; // Check whether one set is a subset of another set this.difference = difference; // set complement this. Contains = contains; This. show = show; // display current collection}Copy the code

The first method we implement is to add a member to the collection, the Add method

Add: Adds a member to the collection

If (this.datastore.indexof (data) < 0){this.datastore.push (data); if(this.datastore.push (data); return true; }else{ console.warn( 'Can not add ' + data + ', must already be in set'); return false; }}Copy the code

As mentioned earlier, the element in a set is unique. Therefore, before we store data in an array, we need to ensure that the data does not exist in the set. Therefore, we use the indexOf method to check whether the newly added element exists and return the position of the member in the array if found. Otherwise, it returns -1, and the corresponding add method can be defined to return a Boolean value, true on success, false on otherwise, which tells us explicitly whether or not we inserted an element correctly.

Remove: deletes a member from the collection

Function remove (data) {var pos = this.datastore.indexof (data); var pos = this.datastore.indexof (data); if( pos > -1 ){ this.dataStore.splice(pos,1); return true; }else{ console.warn( data + ' is not in set'); return false; }}Copy the code

In this case, we implement the delete method, which is similar to the add method. We first check to see if the element to be deleted exists in the array. If it does, we call the array splice() method to delete the element and return true.

Now we can add and remove collections. To test these methods, we first need to define the show method, which displays the members of the collection. The implementation of this method is very simple, just return the array we defined:

Show: Displays the members of the collection

Function show(){console.log(this.datastore); function show(){console.log(this.datastore); return this.dataStore; }Copy the code

Next, let’s test this out:

var fruits = new MySet(); // Add member fruits. Add ('Apple'); fruits.add('Banana'); fruits.add('Pear'); fruits.show(); / / / "Apple", "Banana", "Pear"] / / add repeat members fruits. Add (" Apple "); // Can not add Apple, must already be in set // remove member fruits. Remove ('Banana'); fruits.show(); // ["Apple", "Pear"] // Remove non-existent member fruits.remove('Banana'); // Banana is not in setCopy the code

Okay, so we’re ready to implement some advanced operations on sets, so let’s look at the implementation of unions.

Union: Find the union of sets

For collection and collection, is to get the two merged into one set, and removing repetitive elements, our implementation approach is to put the first member of the collection in a temporary collection, judge whether the members of the second set also belong to the first set, if it is true, representative for repeated elements, we just skip the members, will be the members to join the temporary collection, Finally return the collection can be;

So, the question is, how do we know if a member is in the set? Therefore, we need a helper method contains(), which is also very simple to implement using indexOf

Function contains (data) {if(this.datastore.indexof (data) > -1){return true; }else{ return false; }}Copy the code

Now we can define the union method

Function union (set) {var tempSet = new MySet(); for( var i = 0 ; i < this.dataStore.length ; i++ ){ tempSet.add(this.dataStore[i]); } for( var i = 0 ; i< set.dataStore.length ; i++ ){ if( ! tempSet.contains(set.dataStore[i])){ tempSet.dataStore.push(set.dataStore[i]); } } return tempSet; }Copy the code

And then we can have the union of sets,

var fruits1 = new MySet();
fruits1.add('Apple');
fruits1.add('Banana');
fruits1.add('Pear');

var fruits2 = new MySet();
fruits2.add('Grape');
fruits2.add('Banana');
fruits2.add('Pear');
fruits2.add('Orange');

var union = fruits1.union( fruits2 );
union.show();                           // ["Apple", "Banana", "Pear", "Grape", "Orange"]
Copy the code

Success! So now we can look at finding the intersection of sets.

Intersect: Finds the intersection of sets

With the idea of union set above, the definition of intersection is relatively simple. The idea is to find that the member of the first set also belongs to the second set, add the member to the new set, and finally return the new set.

Function intersect (set) {var tempSet = new MySet(); for(var i = 0 ; i < this.dataStore.length ; i++ ){ if( set.contains(this.dataStore[i])){ tempSet.add(this.dataStore[i]); } } return tempSet; }Copy the code

We still use the above two sets and then find their intersection:

var intersect = fruits1.intersect( fruits2 );
intersect.show();                               // ["Banana", "Pear"]
Copy the code

The next defined operation is subset;

Subset: Determines whether a set is a subset of another set

The method first determines whether the length of the set is less than the set to be compared. If the set is larger than the set to be compared, it must not be a subset of the set to be compared. When, to compare the collection is large, to determine whether a member of the collection classes are set to compare, if one is not, the direct returns false, only when all elements are set to compare, we can say that set is a subset of the set to compare, this method will return true, in order to convenient view, I added console printing;

Function subset (set) {if(this.size() > set.size()){console.log('not a subset'); return false; }else{ for ( var i = 0 ; i < this.dataStore.length ; i++ ){ if( ! set.contains(this.dataStore[i])){ console.log('not a subset'); return false; } } } console.log(' a subset'); return true; }Copy the code

We see the size method used above, which is defined as follows:

Function size () {return this.datastore.length; }Copy the code

Fruits1 and fruits2 are retained and a new fruits3 is created to demonstrate the subset method

var fruits3 = new MySet(); fruits3.add('Apple'); fruits3.add('Banana'); fruits3.add('Pear'); fruits3.add('Grape'); fruits3.add('Orange'); Fruits1. Subset (fruits2); // not a subset fruits2.subset( fruits2 ); // a subset fruits1.subset( fruits3 ); // a subsetCopy the code

Everything seems to be going well, and we’re left with the final difference method, which returns a new set of members that belong to the first set but not the second.

Difference: the complement

With the idea of intersection, the realization of complement appears very natural.

Function difference (set) {var tempSet = new MySet(); for( var i = 0 ; i < this.dataStore.length ; i ++ ){ if( ! set.contains(this.dataStore[i])){ tempSet.dataStore.push( this.dataStore[i] ); } } return tempSet; }Copy the code

Let’s test it out:

fruits1.difference(fruits2).show();     // ['Apple']
fruits1.difference(fruits3).show();     // []
fruits2.difference(fruits1).show();     // ["Grape", "Orange"]
Copy the code

Ok, so far we have a complete set, isn’t that great!

ES6 provides a Set of data structure, there are many readymade methods can be directly called, very method, is not very familiar friends can refer to my previous blog, about ES6 Symbol, Set and Map article, I believe there will be a good gain ~