集合的javascript实现

集合是由一组无序且唯一（即不能重复）的项组成的。这个数据结构使用了与有限集合相同的数学概念，但应用在计算机科学的数据结构中。ES6也有原生Set类的实现。集合李包含下面这些方法：has、add、remove、clear、size、values。同时两个集合之间还会有这些操作：并集(union)、交集(interaction)、差集(difference)、子集(subset)。

Set类的实现

function MySet(){
  let items={}

  this.has=function(value){
    return items.hasOwnProperty(value)
  }

  this.add=function(value){
    if(this.has(value)){
      items[value]=value
      return true
    }
    return false
  }

  this.remove=function(value){
    if(this.has(value)){
      delete items[value]
      return true
    }
    return false
  }

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

  this.size=function(){
    let keys=Object.keys(items)
    return keys.length
  }

  this.values=function(){
    let keys=Object.keys(items)
    return keys.map(key=>items[key])
  }

  this.union=function(otherSet){ // 并集
    let unionSet=new MySet()

    let values=this.values()
    for(let i=0;i<values.length;i++){
      unionSet.add(values[i])
    }

    values=otherSet.values()
    for(let i=0;i<values.length;i++){
      unionSet.add(values[i])
    }

    return unionSet
  }

  this.intersection=function(otherSet){ // 交集
    let intersectionSet=new MySet()

    let values=this.values()
    for(let value of values){
      if(otherSet.has(value)){
        intersectionSet.add(value)
      }
    }

    return intersectionSet
  }

  this.difference=function(otherSet){ // 差集
    let differenceSet=new MySet()
    
    let values=this.values()
    for(let value of values){
      if(!otherSet.has(value)){
        differenceSet.add(value)
      }
    }

    return differenceSet
  }

  this.subset=function(otherSet){ // 子集
    if(this.size()>otherSet.size()){
      return false
    }else{
      let values=this.values()
      for(let i=0;i<values.length;i++){
        if(!otherSet.has(values[i])){
          return false
        }
      }
      return true
    }
  }
}

ES6 Set类的扩展

ES6实现了原生的Set类，不过它是基于数组的。因此创建一个实例是这样：new Set(arr)。Set类里基本也包含了上面的一些方法，但是没有类之间的操作。下面在原生的Set类基础上实现扩展。

Set.prototype.union=function(otherSet){
  let unionSet=new Set()
  for(let x of this){
    unionSet.add(x)
  }
  for(let x of otherSet){
    unionSet.add(x)
  }

  return unionSet
}

Set.prototype.intersection=function(otherSet){
  let intersectionSet=new Set()
  for (let x of this){
    if(otherSet.has(x)){
      intersectionSet.add(x)
    }
  }
  return intersectionSet
}

Set.prototype.difference=function(otherSet){
  let differenceSet=new Set()
  for(let x of this){
    if(!otherSet.has(x)){
      differenceSet.add(x)
    }
  }
  return differenceSet
}

Set.prototype.subset=function(otherSet){
  if(this.size<otherSet.size){
    return false
  }
  for(let x of this){
    if(!otherSet.has(x)){
      return false
    }
  }
  return true
}