// 第 6 周 – Go 中的集合：map[T]struct{}（没有内置的集合类型）
// 运行：go run ./w06/builtin
package main

import (
	"fmt"
	"maps"
	"slices"
)

type Set map[string]struct{} // struct{} 占 0 字节

func NewSet(xs ...string) Set {
	s := Set{}
	for _, x := range xs {
		s[x] = struct{}{}
	}
	return s
}

func (s Set) Contains(x string) bool { _, ok := s[x]; return ok } // 平均 O(1)

func (s Set) Union(o Set) Set {
	r := maps.Clone(s)
	for x := range o {
		r[x] = struct{}{}
	}
	return r
}

func (s Set) Intersection(o Set) Set {
	r := Set{}
	for x := range s {
		if o.Contains(x) {
			r[x] = struct{}{}
		}
	}
	return r
}

func (s Set) Difference(o Set) Set {
	r := Set{}
	for x := range s {
		if !o.Contains(x) {
			r[x] = struct{}{}
		}
	}
	return r
}

// 排序：map 的遍历顺序是随机的，所以打印前先排序
func (s Set) Sorted() []string {
	return slices.Sorted(maps.Keys(s))
}

func main() {
	a := NewSet("Wuhan", "Beijing", "Eger", "Shanghai")
	b := NewSet("Eger", "Budapest", "Wuhan")
	fmt.Println("A ∪ B =", a.Union(b).Sorted())
	fmt.Println("A ∩ B =", a.Intersection(b).Sorted())
	fmt.Println(`A \ B =`, a.Difference(b).Sorted())
	fmt.Println(`Contains("Eger") =`, a.Contains("Eger"), ", len(A) =", len(a))

	// 过滤重复元素
	nums := []int{3, 1, 3, 2, 1, 3}
	seen := map[int]bool{}
	var distinct []int
	for _, x := range nums {
		if !seen[x] {
			seen[x] = true
			distinct = append(distinct, x)
		}
	}
	fmt.Println("distinct elements (in order of first occurrence):", distinct)
}