111 lines
2.2 KiB
Go
111 lines
2.2 KiB
Go
package utils
|
|
|
|
// 定义一个集合接口
|
|
type ISet[T comparable] interface {
|
|
Add(...T) // 增加集合元素
|
|
Remove(...T) // 删除集合元素
|
|
Contains(T) bool // 集合是否包含元素
|
|
Inter(ISet[T]) ISet[T] // 集合求交集
|
|
Union(ISet[T]) ISet[T] // 集合求合集
|
|
Diff(ISet[T]) ISet[T] // 集合求差集
|
|
Equal(ISet[T]) bool // 集合是否相等
|
|
Traver(func(T)) // 遍历集合元素
|
|
Elements() []T // 获取集合所有元素列表
|
|
IsEmpty() bool // 集合是否为空
|
|
}
|
|
|
|
// Set 使用字典实现集合
|
|
type Set[T comparable] struct {
|
|
dict map[T]struct{}
|
|
}
|
|
|
|
func NewSet[T comparable](src []T) ISet[T] {
|
|
ret := &Set[T]{dict: make(map[T]struct{})}
|
|
for _, t := range src {
|
|
ret.dict[t] = struct{}{}
|
|
}
|
|
return ret
|
|
}
|
|
|
|
// Add 实现集合接口
|
|
func (s *Set[T]) Add(items ...T) {
|
|
for _, t := range items {
|
|
s.dict[t] = struct{}{}
|
|
}
|
|
}
|
|
|
|
func (s *Set[T]) Remove(items ...T) {
|
|
for _, t := range items {
|
|
delete(s.dict, t)
|
|
}
|
|
}
|
|
|
|
func (s *Set[T]) Contains(item T) bool {
|
|
if _, ok := s.dict[item]; ok {
|
|
return true
|
|
}
|
|
return false
|
|
}
|
|
|
|
func (s *Set[T]) Inter(other ISet[T]) ISet[T] {
|
|
result := &Set[T]{
|
|
dict: make(map[T]struct{}),
|
|
}
|
|
for k, _ := range s.dict {
|
|
if other.Contains(k) {
|
|
result.Add(k)
|
|
}
|
|
}
|
|
return result
|
|
}
|
|
|
|
func (s *Set[T]) Union(other ISet[T]) ISet[T] {
|
|
result := &Set[T]{
|
|
dict: make(map[T]struct{}),
|
|
}
|
|
s.Traver(func(item T) {
|
|
result.Add(item)
|
|
})
|
|
other.Traver(func(item T) {
|
|
result.Add(item)
|
|
})
|
|
return result
|
|
}
|
|
|
|
func (s *Set[T]) Diff(other ISet[T]) ISet[T] {
|
|
result := &Set[T]{
|
|
dict: make(map[T]struct{}),
|
|
}
|
|
s.Traver(func(item T) {
|
|
if !other.Contains(item) {
|
|
result.Add(item)
|
|
}
|
|
})
|
|
return result
|
|
}
|
|
|
|
func (s *Set[T]) Equal(other ISet[T]) bool {
|
|
// 如果 (A - B) 和 (B - A) 都是空集，则说明两个集合的元素完全相同，因此它们相等
|
|
d1 := s.Diff(other)
|
|
d2 := other.Diff(s)
|
|
return d1.IsEmpty() && d2.IsEmpty()
|
|
}
|
|
|
|
func (s *Set[T]) Traver(onItem func(item T)) {
|
|
for k, _ := range s.dict {
|
|
onItem(k)
|
|
}
|
|
}
|
|
|
|
func (s *Set[T]) Elements() []T {
|
|
ret := make([]T, 0)
|
|
for k, _ := range s.dict {
|
|
ret = append(ret, k)
|
|
}
|
|
return ret
|
|
}
|
|
|
|
func (s *Set[T]) IsEmpty() bool {
|
|
return len(s.dict) == 0
|
|
}
|