学习JavaScript数据结构与算法：集合

[roojay]

简介

集合是由一组无序且唯一（即不能重复）的项组成的。这个数据结构使用了与有限集合相同的数学概念，但应用在计算机科学的数据结构中。

代码实现(TS)

interface IItem<T> {
  [index: string]: T;
}

/**
 * 集合是由一组无序且唯一（即不能重复）的项组成的。
 * @method add(value): 向集合添加一个新的项。
 * @method delete(value): 从集合移除一个值。
 * @method has(value): 如果值在集合中，返回 true，否则返回 false。
 * @method clear(): 移除集合中的所有项。
 * @method size(): 返回集合所包含元素的数量。
 * @method values(): 返回一个包含集合中所有值的数组。
 * @method union(otherSet) 并集：对于给定的两个集合，返回一个包含两个集合中所有元素的新集合。
 * @method intersection(otherSet) 交集：对于给定的两个集合，返回一个包含两个集合中共有元素的新集合。
 * @method difference(otherSet) 差集：对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合。
 * @method subset(otherSet) 子集：验证一个给定集合是否是另一集合的子集。
 */
export class Set<T> {
  private items: IItem<T> = {};
  constructor(items?: T[]) {
    if (items) [...items].forEach(i => this.add(i));
  }
  has = (value: T) => this.items.hasOwnProperty(value.toString());
  add = (value: T) => !this.has(value)
    ? !!(this.items[value.toString()] = value)
    : false
  delete = (value: T) => this.has(value)
    ? delete this.items[value.toString()]
    : false
  keys = () => [...Object.keys(this.items)];
  values = () => [...this.keys().map(k => this.items[k])];
  size = () => this.keys().length;
  clear = () => this.items = {};
  union = (otherSet: Set<T>) => {
    const unionSet = new Set();
    [...this.values(), ...otherSet.values()].forEach(v => unionSet.add(v));
    return unionSet;
  }
  intersection = (otherSet: Set<T>) => {
    const intersectionSet = new Set();
    this.values()
      .filter(v => otherSet.has(v))
      .forEach(v => intersectionSet.add(v));
    return intersectionSet;
  }
  difference = (otherSet: Set<T>) => {
    const differenceSet = new Set();
    this.values()
      .filter(v => !otherSet.has(v))
      .forEach(v => differenceSet.add(v));
    return differenceSet;
  }
  subset = (otherSet: Set<T>) => {
    return this.size() > otherSet.size()
      ? false
      : this.values().every(v => otherSet.has(v));
  }
}

单元测试

import { expect } from 'chai';
import { Set } from '../src/set';

describe('集合', () => {
  describe('Set', () => {
    const s = new Set();
    it('#add()', () => {
      s.add(1);
      expect(s.has(1)).to.be.ok;
    });
    it('#delete()', () => {
      s.delete(1);
      expect(s.has(1)).to.be.not.ok;
      expect(s.delete(2)).to.be.not.ok;
    });
    it('#has()', () => {
      expect(s.has(2)).to.be.not.ok;
    });
    it('#keys()', () => {
      s.add(2);
      s.add(3);
      s.add(4);
      expect(s.keys()).to.eql(['2', '3', '4']);
    });
    it('#values()', () => {
      expect(s.values()).to.eql([2, 3, 4]);
    });
    it('#size()', () => {
      expect(s.size()).to.equal(3);
    });
    it('#clear()', () => {
      s.clear();
      expect(s.keys()).to.be.empty;
    });
    it('#union()', () => {
      const setA = new Set([1, 2, 3]);
      const setB = new Set([3, 4, 5]);
      const unionSet = setA.union(setB);
      expect(unionSet.values()).to.eql([1, 2, 3, 4, 5]);
    });
    it('#intersection()', () => {
      const setA = new Set([1, 2, 3]);
      const setB = new Set([3, 4, 5]);
      const intersectionSet = setA.intersection(setB);
      expect(intersectionSet.values()).to.eql([3]);
    });
    it('#difference()', () => {
      const setA = new Set([1, 2, 3]);
      const setB = new Set([3, 4, 5]);
      const differenceSet = setA.difference(setB);
      expect(differenceSet.values()).to.eql([1, 2]);
    });
    it('#subset()', () => {
      const setA = new Set([1, 2]);
      const setB = new Set([3, 4, 5]);
      const setC = new Set([1, 2, 3]);
      const setD = new Set([1]);
      expect(setA.subset(setB)).to.be.not.ok;
      expect(setA.subset(setC)).to.be.ok;
      expect(setA.subset(setD)).to.be.not.ok;
    });
  });
});