数据结构 集合

集合的实现

集合的实现需要用到哈希表，由于 JS 中的对象就是一个哈希表，这里我们直接使用对象多为哈希表

function MySet() {
  const items = {};
  this.has = function (value) {
    return items.hasOwnProperty(value);
  };
  this.add = function (value) {
    if (!items.hasOwnProperty(value)) {
      // 利用键名的不可重复的性质
      items[value] = value;
      return true;
    } else {
      return false;
    }
  };
  this.remove = function (value) {
    if (items.hasOwnProperty(value)) {
      delete items[value];
      return true;
    } else {
      return false;
    }
  };
  this.clear = function () {
    items = {};
  };
  this.size = function () {
    return Object.keys(items).length;
  };
  this.values = function () {
    return Object.keys(items);
  };
  this.union = function (otherSet) {
    const union = new MySet();
    this.values().forEach((item) => {
      union.add(item);
    });
    otherSet.values().forEach((item) => {
      union.add(item);
    });
    return union;
  };
  this.intersection = function (otherSet) {
    const intersection = new MySet();
    this.values().forEach((item) => {
      if (otherSet.has(item)) {
        intersection.add(item);
      }
    });
    return intersection;
  };
  this.difference = function (otherSet) {
    const difference = new MySet();
    this.values().forEach((item) => {
      if (!otherSet.has(item)) {
        difference.add(item);
      }
    });
    return difference;
  };
  this.subset = function (otherSet) {
    let flag = true;
    otherSet.values().forEach((item) => {
      if (!this.has(item)) {
        flag = false;
      }
    });
    return flag;
  };
}

module.exports = MySet;

// MySet.test.js
const MySet = require("./MySet.js");

const set = new MySet();
set.add(1);
set.add(2);
console.log(set.size()); // 2
console.log(set.values()); // [ '1', '2' ]

const set1 = new MySet();
set1.add(1);
set1.add(2);
const set2 = new MySet();
set2.add(2);
set2.add(3);

console.log(set1.union(set2).values()); // [ '1', '2', '3' ]
console.log(set1.intersection(set2).values()); //  [ '2' ]
console.log(set1.difference(set2).values()); //  [ '1' ]
console.log(set1.subset(set2)); // false