Javascript数据结构之集合

数据集合

集合是由一组无序且唯一的元素组成。

• add(element)：向集合中插入一个新元素
• delete(element)：从集合移除一个元素
• has(element)：判断元素是否存在集合中
• clear()：移除集合中所有元素
• size()：返回集合所包含的元素个数
• values()：返回集合中所有值

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;
  }

  // 判断元素是否存在集合中
  has(element) {
    return element in this.items;
    // return Object.prototype.hasOwnProperty.call(this.items, element);
  }
  
  // 移除集合中所有元素
  clear() {
    this.items = {};
  }

  // 返回集合所包含的元素个数
  size() {
    return Object.keys(this.items).length;
  }

  // 返回集合中所有值
  values() {
    return Object.values(this.items);
  }
}

const set = new Set();
set.add(1);
console.log(set.values()); // [1]
console.log(set.has(1)); // true
console.log(set.size()); // 1

set.delete(1);
console.log(set.values()); // []

集合运算

• 并集：返回两个集合中所有元素的新集合
• 交集：返回两个集合中共有元素的新集合
• 差集：返回存在于第一个集合且不存在第二个集合的元素的新集合
• 子集：验证一个给定集合是否是另一个集合的子集

并集

union(data) {
  const unionSet = new Set();
  this.values().forEach(value => unionSet.add(value));
  data.values().forEach(value => unionSet.add(value));
  return unionSet;
}

// 验证
const A = new Set();
A.add(1);
A.add(2);
A.add(3);
const B = new Set();
B.add(3);
B.add(4);
B.add(5);
const unionAB = A.union(B);
console.log(unionAB.values()); // [ 1, 2, 3, 4, 5 ]

交集

intersects(data) {
  const intersectSet = new Set();
  const values = this.values();
  for (let i = 0; i < values.length; i++) {
    if (data.has(values[i])) {
      intersectSet.add(values[i]);
    }
  }
  return intersectSet;
}

// 验证
const A = new Set();
A.add(1);
A.add(2);
A.add(3);
const B = new Set();
B.add(3);
B.add(4);
B.add(5);
const intersectAB = A.intersects(B);
console.log(intersectAB.values()); // [ 3 ]

差集

subtract(data) {
  const subtractSet = new Set();
  this.values().forEach(value => {
    if (!data.has(value)) {
      subtractSet.add(value);
    }
  });
  return subtractSet;
}

// 验证
const A = new Set();
A.add(1);
A.add(2);
A.add(3);
const B = new Set();
B.add(3);
B.add(4);
B.add(5);
const subtractAB = A.subtract(B);
console.log(subtractAB.values()); // [ 1, 2 ]

子集

isSubsetOf(data) {
  if (this.size() > data.size()) {
    return false;
  }
  let isSubset = true;
  this.values().every(value => {
    if (!data.has(value)) {
      isSubset = false;
      return false;
    } else {
      return true;
    }
  })
  return isSubset;
}

// 验证
const A = new Set();
A.add(1);
A.add(2);
A.add(3);
const B = new Set();
B.add(3);
console.log(A.isSubsetOf(B)); // false

ECMAScript 2015 – Set 类

var set1 = new Set([1,2,3]);
var set2 = new Set([2,3,4]);

并集
let union = new Set([…set1, …set2]);

交集
let intersects = new Set([…set1].filter( x => set2.has(x)));

差集
let subtract = new Set([…set1].filter(x => !set2.has(x)));