Golang Set 数据结构

七秒钟回忆待续 · · 595 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

package intset

type Set map[int]struct{}

func New(v ...int) Set {
    s := Set{}
    s.Add(v...)
    return s
}

func (s Set) Add(v ...int) {
    for _, i := range v {
        s[i] = struct{}{}
    }
}

func (s Set) Cardinality() int {
    return len(s)
}

func (s Set) Contains(v int) bool {
    _, ok := s[v]
    return ok
}

func (s Set) Remove(v int) {
    delete(s, v)
}

func (s Set) ToSlice() []int {
    var rs []int
    for v := range s {
        rs = append(rs, v)
    }
    return rs
}

// 子1
func (s Set) IsSubset(o Set) bool {
    if s.Cardinality() > o.Cardinality() {
        return false
    }
    for v := range s {
        if !o.Contains(v) {
            return false
        }
    }
    return true
}

// 子2
func (s Set) Equal(o Set) bool {
    if s.Cardinality() != o.Cardinality() {
        return false
    }
    for v := range s {
        if !o.Contains(v) {
            return false
        }
    }
    return true
}

// 子3
func (s Set) IsProperSubset(o Set) bool {
    if s.Cardinality() >= o.Cardinality() {
        return false
    }
    return s.IsSubset(o)
}

// 子4
func (s Set) IsSuperSet(o Set) bool {
    return o.IsSubset(s)
}

// 交
func (s Set) InterSec(o Set) Set {
    r := New()
    //loop smaller set
    if s.Cardinality() < o.Cardinality() {
        for v := range s {
            if o.Contains(v) {
                r.Add(v)
            }
        }
    } else {
        for v := range o {
            if s.Contains(v) {
                r.Add(v)
            }
        }
    }
    return r
}

// 并
func (s Set) Union(o Set) Set {
    r := Newint()
    for v1 := range s {
        r.Add(v1)
    }
    for v2 := range o {
        r.Add(v2)
    }
    return r
}

// 补1
func (s Set) Difference(o Set) Set {
    r := New()
    for v := range s {
        if !o.Contains(v) {
            r.Add(v)
        }
    }
    return r
}

// 补2
func (s Set) SymmetricDifference(o Set) Set {
    return s.Difference(o).Union(o.Difference(s))
}

//func (s Set) CartesianProduct(o Set) {
//
//}

有疑问加站长微信联系（非本文作者）