Go语言实现set

package set



type Set interface {

        Add(e interface{}) bool

        Remove(e interface{})

        Clear()

        Contains(e interface{}) bool

        Len() int

        Same(other Set) bool

        Elements() []interface{}

        String() string

}



// 判断集合 one 是否是集合 other 的超集

func IsSuperset(one Set, other Set) bool {

        if one == nil || other == nil {

                return false

        }

        oneLen := one.Len()

        otherLen := other.Len()

        if oneLen == 0 || oneLen == otherLen {

                return false

        }

        if oneLen > 0 && otherLen == 0 {

                return true

        }

        for _, v := range other.Elements() {

                if !one.Contains(v) {

                        return false

                }

        }

        return true

}



// 生成集合 one 和集合 other 的并集

func Union(one Set, other Set) Set {

        if one == nil || other == nil {

                return nil

        }

        unionedSet := NewSimpleSet()

        for _, v := range one.Elements() {

                unionedSet.Add(v)

        }

        if other.Len() == 0 {

                return unionedSet

        }

        for _, v := range other.Elements() {

                unionedSet.Add(v)

        }

        return unionedSet

}



// 生成集合 one 和集合 other 的交集

func Intersect(one Set, other Set) Set {

        if one == nil || other == nil {

                return nil

        }

        intersectedSet := NewSimpleSet()

        if other.Len() == 0 {

                return intersectedSet

        }

        if one.Len() < other.Len() {

                for _, v := range one.Elements() {

                        if other.Contains(v) {

                                intersectedSet.Add(v)

                        }

                }

        } else {

                for _, v := range other.Elements() {

                        if one.Contains(v) {

                                intersectedSet.Add(v)

                        }

                }

        }

        return intersectedSet

}



// 生成集合 one 对集合 other 的差集

func Difference(one Set, other Set) Set {

        if one == nil || other == nil {

                return nil

        }

        differencedSet := NewSimpleSet()

        if other.Len() == 0 {

                for _, v := range one.Elements() {

                        differencedSet.Add(v)

                }

                return differencedSet

        }

        for _, v := range one.Elements() {

                if !other.Contains(v) {

                        differencedSet.Add(v)

                }

        }

        return differencedSet

}



// 生成集合 one 和集合 other 的对称差集

func SymmetricDifference(one Set, other Set) Set {

        if one == nil || other == nil {

                return nil

        }

        diffA := Difference(one, other)

        if other.Len() == 0 {

                return diffA

        }

        diffB := Difference(other, one)

        return Union(diffA, diffB)

}



func NewSimpleSet() Set {

        return NewHashSet()

}



func IsSet(value interface{}) bool {

        if _, ok := value.(Set); ok {

                return true

        }

        return false

}

HashSet:



package set



import (

        "bytes"

        "fmt"

)



type HashSet struct {

        m map[interface{}]bool

}



func NewHashSet() *HashSet {

        return &HashSet{m: make(map[interface{}]bool)}

}



func (set *HashSet) Add(e interface{}) bool {

        if !set.m[e] {

                set.m[e] = true

                return true

        }

        return false

}



func (set *HashSet) Remove(e interface{}) {

        delete(set.m, e)

}



func (set *HashSet) Clear() {

        set.m = make(map[interface{}]bool)

}



func (set *HashSet) Contains(e interface{}) bool {

        return set.m[e]

}



func (set *HashSet) Len() int {

        return len(set.m)

}



func (set *HashSet) Same(other Set) bool {

        if other == nil {

                return false

        }

        if set.Len() != other.Len() {

                return false

        }

        for key := range set.m {

                if !other.Contains(key) {

                        return false

                }

        }

        return true

}



func (set *HashSet) Elements() []interface{} {

        initialLen := len(set.m)

        snapshot := make([]interface{}, initialLen)

        actualLen := 0

        for key := range set.m {

                if actualLen < initialLen {

                        snapshot[actualLen] = key

                } else {

                        snapshot = append(snapshot, key)

                }

                actualLen++

        }

        if actualLen < initialLen {

                snapshot = snapshot[:actualLen]

        }

        return snapshot

}



func (set *HashSet) String() string {

        var buf bytes.Buffer

        buf.WriteString("HashSet{")

        first := true

        for key := range set.m {

                if first {

                        first = false

                } else {

                        buf.WriteString(" ")

                }

                buf.WriteString(fmt.Sprintf("%v", key))

        }

        buf.WriteString("}")

        return buf.String()

}


原文发布于微信公众号 - Golang语言社区(Golangweb)

原文发表时间:2016-11-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏武培轩的专栏

剑指Offer-从尾到头打印链表

package LinkedList; import java.util.ArrayDeque; import java.util.ArrayList; im...

3176
来自专栏小樱的经验随笔

线性表的链式存储结构的实现及其应用(C/C++实现)

存档----------- 1 #include <iostream.h> 2 typedef char ElemType; 3 #include "Li...

3377
来自专栏Python专栏

【数据结构与算法】一起搞定面试中的二叉树题目(二)

1933
来自专栏曾大稳的博客

树(Tree)以及二叉树的遍历

树(tree) 是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次...

1711
来自专栏C#

DotNet加密方式解析--非对称加密

    新年新气象,也希望新年可以挣大钱。不管今年年底会不会跟去年一样,满怀抱负却又壮志未酬。(不过没事,我已为各位卜上一卦,卦象显示各位都能挣钱...)...

6908
来自专栏lgp20151222

Java获取当日的起始时间,结束时间,现在时间,是否在时间段中。

1702
来自专栏赵俊的Java专栏

对称的二叉树

1462
来自专栏desperate633

LintCode 二叉树的层次遍历 II题目代码

给出一棵二叉树,返回其节点值从底向上的层次序遍历(按从叶节点所在层到根节点所在的层遍历,然后逐层从左往右遍历)

924
来自专栏武培轩的专栏

剑指Offer-二叉树的镜像

package Tree; import java.util.ArrayDeque; import java.util.ArrayList; import j...

3304
来自专栏菩提树下的杨过

数据结构C#版笔记--树与二叉树

                图1 上图描述的数据结构就是“树”,其中最上面那个圈圈A称之为根节点(root),其它圈圈称为节点(node),当然root可以...

2598

扫码关注云+社区