preface

Hello, I’m Tutu. The last article talked about the data structure of linked lists. Linked lists include: one-way linked lists, two-way linked lists, circular lists and ordered lists. And in the process of operation, it is also more complicated. Because it has a pointer to the next node, you need to be careful. So in this chapter we’re going to talk about sets. Let’s not talk any more, it’s all in the code.

A collection of

A set is made up of an unordered set of elements that cannot be repeated. You can think of a set as an array with no repeating elements and no order.

Create a collection

For those of you who have studied ES6, a new data structure, Set, has been added. It is also the set of this chapter. The following will implement a Set class of its own based on ES6’s Set data structure.

Let’s declare a Set class.

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

The collection is represented by an object items, the main reason for using objects is that objects do not allow the same key to point to two different properties. This also ensures that the elements in the collection are unique, but can also be represented as arrays.

Here’s the collection method.

  • add(ele): Adds an element to the collection.
  • delete(ele): Removes an element from the collection.
  • has(ele): checks to see if the element exists in the collection and returns if it doestrueOtherwise returnfalse.
  • clear(): Deletes all elements in the collection.
  • size(): Returns the number of elements in the collection.
  • values(): returns an array containing all the elements of the collection.

From the way

Implement the HAS method first, because it will be called by the Add and DELETE methods.

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

Here we use the hasOwnProperty method on the Object prototype. This method returns a Boolean value to see if the specified property is present on the object. Of course you can also use the in operator. The difference between these two methods is that hasOwnProperty checks whether the instance has the specified property. The in operator returns true regardless of whether the specified property is in the stereotype or in the instance.

The add method

Here’s how to add elements.

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

The Add method is relatively simple. First, check if the element to be added exists in the collection and return true if it does not, or false if it does.

When you add an element, it’s best to store it as a key and value, which makes it easier to find the element.

Delete and clear methods

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

The delete method first checks if the element exists in the collection, deletes it if it does and returns true, and returns false if it does not.

The clear method is the same as the clear method for other data structures.

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

Simply initialize items. Another approach is to iterate through the collection, using the DELETE operator to delete the elements one by one, but this is cumbersome.

The size method

There are three methods to implement size:

  1. Like stacks and queuesaddanddeleteThe way to do that is to use onecountVariables control it.
  2. useObject.keysMethod that returns an array of enumerable properties from an object. And then take the length of this arraylengthreturnitemsNumber of attributes in an object.
  3. withfor-inIterate over properties in an object with onecountVariable records the number of attributes and returnscountThe variable.
size() {
    return Object.keys(this.items).length;
}

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

Iterate over all properties of the Items object and check if they are its own properties using the HAS method. If so, increment the count variable.

The reason for using the HAS step is that assuming additional attributes on the object’s prototype also causes count to increment.

Values method

For the values method, both object. values and for-in iteration work.

values() {
    return Object.values(this.items);
}

theOtherOneValues() {
    const arr = [];

    for (const key in this.items) {
      if (this.has(key)) { arr.push(key); }}return arr;
}
Copy the code

The for-in iteration is the same as the size method above, except instead of counting the number of attributes.

The test Set class

const set = new Set(a);console.log(set.size()); / / 0

console.log(set.add(1)); // true
console.log(set.add(2)); // true
console.log(set.add(3)); // true

console.log(set.size()); / / 3

console.log(set.has(1)); // true

console.log(set.values()); / / [1, 2, 3]

console.log(set.delete(3)); // true
Copy the code

The overall code

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

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

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

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

  clear() {
    this.items = {};
  }

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

  theOtherOneSize() {
    let count = 0;
    for (const key in this.items) {
      if (this.has(key)) { count++; }}return count;
  }

  values() {
    return Object.values(this.items);
  }

  theOtherOneValues() {
    const arr = [];

    for (const key in this.items) {
      if (this.has(key)) { arr.push(key); }}returnarr; }}Copy the code

Set operations

And set

Given two sets, return a set containing all the elements of both sets.

// Add methods to the Set class
union(otherSet) {
    const unionSet = new Set(a);this.values().forEach((item) = > unionSet.add(item));
    otherSet.values().forEach((item) = > unionSet.add(item));
    return unionSet;
}
Copy the code

The test code

const setA = new Set(a);const setB = new Set(a); setA.add(1);
setA.add(3);
setA.add(5);
setA.add(6);

setB.add(2);
setB.add(4);
setB.add(6);

const otherSetB = setA.union(setB);

console.log(otherSetB.values());
// [1, 2, 3, 4, 5, 6]
Copy the code

Note that the element 6 is added to both setA and setB, but only one 6 appears in the printed data below.

intersection

Given two collections, returns a collection containing elements that are common in both collections.

intersectionFn(otherSet) {
    const intersection = new Set(a);const values = this.values();
    for (let i = 0; i < values.length; i++) {
      if(otherSet.has(values[i])) { intersection.add(values[i]); }}return intersection.values();
}
Copy the code

First create a Set instance, then iterate over all values in the current Set instance. The has method is used to verify whether there is otherSet. If so, it is added to Interseciton set. Finally, return it as an array.

The test code

const setA = new Set(a);const setB = new Set(a); setA.add(1);
setA.add(3);
setA.add(5);
setA.add(6);

setB.add(2);
setB.add(4);
setB.add(6);

const otherSetB = setA.intersectionFn(setB);

console.log(otherSetB);
/ / [6]
Copy the code

Improved version

Suppose we now have two sets like this:

  • setAThe value is[1, 2, 3, 4, 5, 6];
  • setBThe value is[2, 6];

By using the intersectionFn method, setA values need to be iterated for six times and then compared with two setB values. On the other hand, as long as setB is used to compare with setA, the performance cost is reduced. Because you only need to iterate setB twice. Next, modify the previous intersectionFn method.

otherIntersection(otherSet) {
    const intersection = new Set(a);const values = this.values();
    const otherVal = otherSet.values();
    // A collection of large arrays
    let biggerSet = values;
    // A collection of small arrays
    let smallerSet = otherVal;

    /* If the number of elements in the Set passed is greater than the number of elements in the current Set, this step is not taken */
    if (otherVal.length - values.length > 0) {
      biggerSet = otherVal;
      smallerSet = values;
    }

    // Iterate over smaller collections
    smallerSet.forEach((item) = > {
      if(biggerSet.includes(item)) { intersection.add(item); }});return intersection;
}
Copy the code

Difference set

Given two sets, return a set containing all elements that are in the first set but not in the second set.

difference(otherSet) {
    const differenceSet = new Set(a);this.values().forEach((item) = > {
      if (!otherSet.has(item)) {
        differenceSet.add(item);
      }
    });

    return differenceSet.values();
}
Copy the code

The difference method returns an array of elements that are in the set setA but not in the set setB. You first create the result set, and then iterate over all the values in the set. Checks if the current value exists in the given set, and if so, adds the value to the result set.

The test code

const setA = new Set(a);const setB = new Set(a); setA.add(1);
setA.add(3);
setA.add(5);
setA.add(6);

setB.add(2);
setB.add(4);
setB.add(6);

const otherSetB = setA.difference(setB);

console.log(otherSetB);
/ / [1, 3, 5]
Copy the code

Here [1, 3, 5] is printed because [1, 3, 5] only exists in setA. If setb.difference (setA) is executed, [2, 4] is printed because [2, 4] only exists in setB.

The difference method cannot be optimized as the Intersecton method can be optimized, because the difference set between setA and setB may be different from that between setB and setA.

A subset of

Verify that a set is a subset of another set.

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

First, verify the size of the current Set instance. If the current instance has more elements than otherSet, it is not a subset. Return false. Remember that the number of elements in a subset is always less than or equal to that of the set being compared.

In the code above, suppose the current instance is a subset of a given set (isSubset = true). Iterate over all the elements in the current collection and verify that they exist in otherSet. If none exists, it is not a subset and returns false. If they’re all in otherSet, then isSubset doesn’t change. Returns true.

The reason for using the every method is that if a value does not exist in otherSet, you can stop iterating, indicating that it is not a subset. As long as the callback returns true, it continues. If false is returned, the loop stops.

The test code

const setA = new Set(a);const setB = new Set(a);const setC = new Set(a); setA.add(1);
setA.add(2);
setA.add(3);

setB.add(1);
setB.add(2);
setB.add(3);
setB.add(4);

setC.add(2);
setC.add(3);
setC.add(4);
setC.add(5);

console.log(setA.isSubsetOf(setB)); // true
console.log(setA.isSubsetOf(setC)); // false
Copy the code

There are three sets: setA is a subset of setB, so it prints true. SetA is not a subset of setC because setC contains only the 2 in setA, so false is printed.

Set class in ES6

Next we use ES6’s Set class to simulate union, intersection, difference and subset.

Let’s first define two sets, because we’ll use them later.

const setA = new Set(a);const setB = new Set(a); setA.add(10);
setA.add(20);
setA.add(30);

setB.add(20);
setB.add(30);
setB.add(40);
setB.add(50);
Copy the code

Simulation and set

const union = (setA, setB) = > {
  let values = new Set(a); setA.forEach((item) = > values.add(item));
  setB.forEach((item) = > values.add(item));
  return values.values();
};

console.log(union(setA, setB));
// {10, 20, 30, 40, 50}
Copy the code

Simulation of overlap

const intersection = (setA, setB) = > {
  let values = new Set(a); setA.forEach((item) = > {
    if(setB.has(item)) { values.add(item); }});return values.values();
};
console.log(intersection(setA, setB));
/ / {20, 30}
Copy the code

Simulation difference set

const difference = (setA, setB) = > {
  const values = new Set(a); setA.forEach((item) = > {
    if (!setB.has(item)) {
      values.add(item);
    }
  });

  return values.values();
};

console.log(difference(setA, setB));
/ / {10}
Copy the code

To simulate the subset

const isSubsetOf = (setA, setB) = > {
  if (setA.size > setB.size) {
    return false;
  }

  let isSubset = true;
  let arr = [...setA];
  arr.every((value) = > {
    if(! setB.has(value)) { isSubset =false;
      return false;
    }

    return true;
  });
  return isSubset;
};

console.log(isSubsetOf(setA, setB)); // false
Copy the code

At the end

If the text appears error, welcome everybody big guy to give directions. If the content of this chapter for you harvest, welcome to like and pay attention to oh!