k8s set类型实现

Golang是没有像python一样本身实现set类型，如果在开发过程中需要使用set类型的话则需要自己实现。
今天我们来学习一下k8s源码中的int类型的set实现。
代码位于
https://github.com/kubernetes/kubernetes/tree/master/staging/src/k8s.io/apimachinery/pkg/util/sets目录下。

1.set可以看作值为空的map，为了节省内存，这里使用struct{}来充当map中的值。因为空的struct{}大小可以看作为零，因为空的struct{}是指向同一个地址。

// 定义值为空结构体
type Empty struct {}

// Int类型set,值为Empty
type Int map[int]Empty

2.sets中提供一个将字典转换为set类型的方法

// 将键为int的map转换成set,set的元素为map的key
// 如果theMap的键不为int则会产生panic
func IntKeySet(theMap interface{}) Int {
	v := reflect.ValueOf(theMap)
	ret := Int{}

	for _, keyValue := range v.MapKeys() {
		ret.Insert(keyValue.Interface().(int))
	}
	return ret
}

3.初始化元素为int类型的set

func NewInt(items ...int) Int {
	ss := Int{}
	ss.Insert(items...)
	return ss
}

4.下面是set的一些常见的方法实现

// 将int类型的元素添加到set中
func (s Int) Insert(items ...int) Int {
	for _, item := range items {
		s[item] = Empty{}
	}
	return s
}

// 删除set中的所有元素
func (s Int) Delete(items ...int) Int {
	for _, item := range items {
		delete(s, item)
	}
	return s
}

// 判断一个元素是否存在set,存在返回true,否则返回false
func (s Int) Has(item int) bool {
	_, contained := s[item]
	return contained
}

// 判断是否所有元素都存在于set集合中，如果是返回true,否则返回false
func (s Int) HasAll(items ...int) bool {
	for _, item := range items {
		if !s.Has(item) {
			return false
		}
	}
	return true
}


// 判断任意一个元素是否存在于set中，如果存在返回true,否则返回false
func (s Int) HasAny(items ...int) bool {
	for _, item := range items {
		if s.Has(item) {
			return true
		}
	}
	return false
}

// 计算在s中存在，在s2中不存在的元素集合
// s1 = {a1, a2, a3}
// s2 = {a1, a2, a4, a5}
// s1.Difference(s2) = {a3}
// s2.Difference(s1) = {a4, a5}
func (s Int) Difference(s2 Int) Int {
	result := NewInt()
	for key := range s {
		if !s2.Has(key) {
			result.Insert(key)
		}
	}
	return result
}

// 计算集合并集
// s1 = {a1, a2}
// s2 = {a3, a4}
// s1.Union(s2) = {a1, a2, a3, a4}
// s2.Union(s1) = {a1, a2, a3, a4}
func (s1 Int) Union(s2 Int) Int {
	result := NewInt()
	for key := range s1 {
		result.Insert(key)
	}
	for key := range s2 {
		result.Insert(key)
	}
	return result
}

// 计算集合的交集
// s1 = {a1, a2}
// s2 = {a2, a3}
// s1.Intersection(s2) = {a2}
func (s1 Int) Intersection(s2 Int) Int {
	var walk, other Int
	result := NewInt()
	if s1.Len() < s2.Len() {
		walk = s1
		other = s2
	} else {
		walk = s2
		other = s1
	}
	for key := range walk {
		if other.Has(key) {
			result.Insert(key)
		}
	}
	return result
}

// 判断s1是否是s2的超集，如果是返回true,否则返回false
func (s1 Int) IsSuperset(s2 Int) bool {
	for item := range s2 {
		if !s1.Has(item) {
			return false
		}
	}
	return true
}

// 判断两个集合是否相等
func (s1 Int) Equal(s2 Int) bool {
	return len(s1) == len(s2) && s1.IsSuperset(s2)
}

type sortableSliceOfInt []int

// 为sortableSliceOfInt类型实现排序方法 
func (s sortableSliceOfInt) Len() int           { return len(s) }
func (s sortableSliceOfInt) Less(i, j int) bool { return lessInt(s[i], s[j]) }
func (s sortableSliceOfInt) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

// 根据集合内容返回排序好的切片
func (s Int) List() []int {
	res := make(sortableSliceOfInt, 0, len(s))
	for key := range s {
		res = append(res, key)
	}
	sort.Sort(res)
	return []int(res)
}

// 返回未排序的切片
func (s Int) UnsortedList() []int {
	res := make([]int, 0, len(s))
	for key := range s {
		res = append(res, key)
	}
	return res
}

// 返回一个元素(key, true)并将其删除，如果集合为空则返回(0,false)
func (s Int) PopAny() (int, bool) {
	for key := range s {
		s.Delete(key)
		return key, true
	}
	var zeroValue int
	return zeroValue, false
}

// 返回set长度
func (s Int) Len() int {
	return len(s)
}

// 对两个元素进行比较
func lessInt(lhs, rhs int) bool {
	return lhs < rhs
}