集合

集合由一组无序且唯一（不能重复）的项组成
使用了与 有限集合 相同的数学概念。

/**
 * @namespace abstract_Set
 * @description 抽象集合命名空间
 */
export namespace abstract_Set {
  /**
   * @class Set
   * @classdesc 数据结构 集合
   *
   * 集合由一组无序且唯一（不能重复）的项组成
   * 使用了与 有限集合 相同的数学概念
   *
   *
   * 集合之间的运算包括 并集、交集、差集\
   * set1 = [1, 2, 3, 4]\
   * set2 = [2, 3, 5, 6]
   *
   * - 并集 即 将两个集合相加，去除重复项
   *        [...set1, ...set2] === [1, 2, 3, 4, 5, 6]
   * - 交集 即 将两个集合相加，去除不重复项
   *        [...set1, ...set2] === [2, 3]
   * - 差集 即 将两个集合对比，去除 集合1相对于集合2 的重复项
   *        set1 - set2 === [1, 4]
   *    - 超集 即 set1 完全拥有 set2 的元素 但 set2 不包含 set1 源
   *    - 子集 即 set2 被 set1 完全拥有 所有元素 但 set2 不包含 set1 源
   *  - 对称差集 即 两个集合相加后，所有重复的项
   *        set1 + set2 = [2, 3]
   *
   * 一个集合中，应有以下方法
   * - add(element) 添加元素
   * - delete(element) 从 集合 删除元素
   * - has(element) 元素是否在集合中
   * - clear() 清空集合
   * - size() 集合大小
   * - values() 返回一个包含集合中所有元素的数组
   * - unions(otherSet) 返回与其它集合的并集
   * - intersection(otherSet) 返回与其它集合的交集
   * - difference(otherSet) 返回与其它集合的差集
   * - isSubsetOf(otherSet) 返回是否为其它集合的子集
   *
   * 在 ES2015 之后 已存在原生的 Set 数据结构
   * 但没有上述方法
   */
  export abstract class CustomSet<T> {
    /** 当前集合项 */
    protected items?: Set<T>
    /**
     * 添加元素到集合
     * @param element
     */
    abstract add (element: T): void
    /**
     * 移除集合元素
     * @param element
     */
    abstract delete (element: T): boolean
    /**
     * 元素是否存在于集合
     * @param element
     */
    abstract has (element: T): boolean
    /**
     * 清空集合
     */
    abstract clear (): void
    /**
     * 返回集合大小
     */
    abstract size (): number
    /**
     * 返回包含集合元素的数组
     */
    abstract values (): T[]
    /**
     * 并集
     * @param otherSet
     */
    abstract unions (otherSet: CustomSet<T>): CustomSet<T>
    /**
     * 交集
     * @param otherSet
     */
    abstract intersection (otherSet: CustomSet<T>): CustomSet<T>
    /**
     * 差集
     * @param otherSet
     */
    abstract difference (otherSet: CustomSet<T>): CustomSet<T>
    /**
     * 子集
     * @param otherSet
     */
    abstract isSubsetOf (otherSet: CustomSet<T>): boolean
  }
}

/**
 * @namespace example_Set
 * @description 实例集合命名空间
 */
export namespace example_Set {
  export class example_Set<T> extends abstract_Set.CustomSet<T> {
    constructor (array?: T[]) {
      super()
      this.items = new Set(array)
    }

    add (element: T): void {
      if (this.has(element)) return
      else this.items?.add(element)
    }

    delete (element: T): boolean {
      if (this.has(element)) {
        this.items?.delete(element)
        return true
      }
      else return false
    }

    has (element: T): boolean {
      return this.items!.has(element)
    }

    values (): T[] {
      const arr: Array<T> = []
      this.items?.forEach(value => arr.push(value))
      return arr
    }

    unions (otherSet: abstract_Set.CustomSet<T>): abstract_Set.CustomSet<T> {
      const unionSet = new example_Set<T>()
      // 先将自身集合的数据添加到创建的 unionSet 中
      this.values().forEach((value => unionSet.add(value)))
      // 在将传入的集合的元素添加到 unionSet 中
      otherSet.values().forEach(value => unionSet.add(value))
      // 直接返回，因为并集取两个集合的不同元素
      return unionSet
    }

    intersection (otherSet: abstract_Set.CustomSet<T>): abstract_Set.CustomSet<T> {
      const intersectionSet = new example_Set<T>()

      // 当前集合过滤 otherSet 中 不存在元素
      // 先将自身元素以数组形式取出
      this.values()
        // 在过滤 掉 传入的 otherSet 中 存在 当前遍历的元素的 项
        .filter(v => otherSet.has(v))
        // 再遍历已经过滤的数组 添加数据到 intersectionSet 中
        .forEach(v => intersectionSet.add(v))
      // 返回
      return intersectionSet
    }

    difference (otherSet: abstract_Set.CustomSet<T>): abstract_Set.CustomSet<T> {
      const differenceSet = new example_Set<T>()

      // 在 当前集合中过滤 otherSet 中存在元素
      this.values()
        .filter(v => !otherSet.has(v))
        .forEach(v => differenceSet.add(v))

      return differenceSet
    }
    isSubsetOf (otherSet: abstract_Set.CustomSet<T>): boolean {
      // 如果 当前集合的大小 大于 传入的集合大小 则 不是 传入集合的子集
      if (this.size() > otherSet.size()) return false
      // 当前集合的元素在 otherSet 中 都有
      this.values().forEach(v => {
        // 如果 传入集合中不存在 当前遍历的 元素 则 不是
        if (!otherSet.has(v)) return false
      })
      // 通过 是子集
      return true
    }

    isEmpty (): boolean {
      return this.size() === 0
    }

    size (): number {
      return this.items!.size
    }

    clear (): void {
      this.items = new Set()
    }

    toString (): string {
      return this.values().toString()
    }
  }
}

多重集合

/**
 * @namespace abstract_multiSet
 * @description 抽象 多重集 命名空间
 */
export namespace abstract_multiSet {

    /**
     * @class MultiSet
     * @description 数据结构 多重集
     *
     * 集合结构不允许存在重复的元素，但是在数学中存在 多重集 的概念
     * 允许向集合插入重复元素
     * 在计算集合中元素出现次数很有用
     *
     * 多重集和普通集合的区别
     * - count(element) 返回集合中指定元素的数量
     * - set(element, count) 将 集合中 指定 element 设置为 count 个
     * - add(element, count) 向集合添加 count 个 element
     * - remove(element, count) 在 集合 删除 count 个 element
     * - delete(element) 移除所有 element
     * - dimension() 返回集合所包含元素的种类数，与数组 length 类似
     */
    export abstract class MultiSet<T> {
        protected items: Map<T, number> = new Map()

        /**
         * 当前集合是否包含 element
         * @param element
         */
        abstract has(element: T): boolean
        /**
         * 当前集合包含多少 element
         * @param element
         */
        abstract count(element: T): number
        /**
         * 设置当前集合中 element 为 count 个
         * @param element
         * @param count
         */
        abstract set(element: T, count: number): boolean
        /**
         * 添加 count 个 element 到当前集合中
         * @param element
         * @param count
         */
        abstract add(element: T, count: number): boolean
        /**
         * 在当前集合中 删除 count 个 element
         * @param element
         * @param count
         */
        abstract remove(element: T, count: number): boolean
        /**
         * 删除所有当前集合中的 element
         * @param element
         */
        abstract delete(element: T): boolean
        /**
         * 返回当前集合所包含的元素种类数
         */
        abstract dimension(): number
        /**
         * 返回 当前集合与 otherSet 的并集\
         * this = [1,2,3]\
         * otherSet = [2,3,4]\
         * 返回 [1,2,3,4]
         * @param otherSet
         */
        abstract union(otherSet: MultiSet<T>): MultiSet<T>
        /**
         * 返回 当前集合与 otherSet 的交集\
         * this = [1,2,3]\
         * otherSet = [2,3,4]\
         * 返回 [2,3]
         * @param otherSet
         */
        abstract intersection(otherSet: MultiSet<T>): MultiSet<T>
        /**
         * 返回当前集合与 otherSet 的差集\
         * this = [1,2,3]\
         * otherSet = [2,3,4]\
         * 返回 [1]
         * @param otherSet
         */
        abstract difference(otherSet: MultiSet<T>): MultiSet<T>
        /**
         * 返回当前集合是否是 otherSet 的子集\
         * this = [1,2,3]\
         * otherSet1 = [0,1,2,3,4,5]\
         * otherSet2 = [1,2,4,5,6]\
         * otherSet1 是 this 的超集, this 是 otherSet1 的子集\
         * otherSet2 不是 this 的超集, this 不是 otherSet2 的子集
         * @param otherSet
         */
        abstract isSubsetOf(otherSet: MultiSet<T>): boolean
        /**
         * 返回一个包含了当前集合所有元素的数组
         */
        abstract values():Array<T>
        /**
         * 返回集合大小
         */
        abstract size(): number
    }
}

/**
 * @namespace example_multiSet
 * @description 实例 多重集 命名空间
 */
export namespace example_multiSet {
    class MultiSet<T> extends abstract_multiSet.MultiSet<T> {

        has(element: T): boolean {
            return this.items.has(element)
        }

        dimension(): number {
            return this.items.size
        }

        count(element: T): number {
            // 双问号 在 前值为 null 或 undefined 时 取后值
            // 否则为前值
            return this.items.get(element) ?? 0
        }

        delete(element: T): boolean {
            return this.items.delete(element)
        }

        set(element: T, count: number): boolean {
            if (count <= 0) return this.delete(element)
            this.items.set(element, count)
            return true
        }

        add(element: T, count: number = 1): boolean {
            let newCount = this.count(element) + count
            return this.set(element, newCount)
        }

        remove(element: T, count: number = 1): boolean {
            return this.add(element, -count)
        }

        isEmpty(): boolean {
            return this.dimension() === 0
        }

        values(): T[] {
            // reduce 方法
            // 接受四个参数
            // Accumulator (acc 累计器)
            // Current Value (cur 当前值)
            // Current Index (idx 当前索引)
            // Source Array (src 源数组)
            return Array.from(this.items.entries())
                .reduce((acc, cur) => {
                    // Array.from 可以将 Map 转换为了数组
                    // map 的 数组形式为 [[k, v], [k, v]]
                    // 解构赋值 分别取出 k 和 v
                    const [key, value] = cur
                    // 循环遍历， 多重集 允许元素重复
                    // 遍历次数为 元素重复次数， 并在 acc 累计器中重复添加元素
                    for(let i = 0; i < value; i++){
                        (acc as T[]).push(key)
                    }
                    // 返回
                    return acc
                // [] 的作用为 在 充当 reduce 第一次调用时的 callback 的 acc 参数
                // 如果没有提供 []， 则 会以 数组第一个元素作为 acc
                }, [])
        }

        size(): number {
            return this.values().length
        }

        clear(): void {
            this.items = new Map()
        }

        union(otherSet: abstract_multiSet.MultiSet<T>): abstract_multiSet.MultiSet<T> {
            const unionSet = new MultiSet<T>()

            this.values().forEach(v => unionSet.add(v))
            otherSet.values().forEach(v => unionSet.add(v))

            return unionSet
        }

        intersection(otherSet: abstract_multiSet.MultiSet<T>): abstract_multiSet.MultiSet<T> {
            const intersectionSet = new MultiSet<T>()

            this.values()
                .filter(v => otherSet.has(v))
                .forEach(v => intersectionSet.add(v))

            return intersectionSet
        }

        difference(otherSet: abstract_multiSet.MultiSet<T>): abstract_multiSet.MultiSet<T> {
            const differenceSet = new MultiSet<T>()

            this.values()
                .filter(v => !otherSet.has(v))
                .forEach(v => differenceSet.add(v))

            return differenceSet
        }

        isSubsetOf(otherSet: abstract_multiSet.MultiSet<T>): boolean {
            if (this.size() > otherSet.size()) return false

            this.values().forEach(v => {
                if (!otherSet.has(v)) return false
            })
            return true
        }

        toString(): string {
            return `${this.values()}`
        }
    }
}