// Week 6 – Sets in Go: map[T]struct{} (there is no built-in set type)
// Run: go run ./w06/builtin
package main

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

type Set map[string]struct{} // struct{} takes 0 bytes

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) on average

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
}

// Sorted: the iteration order of a map is random, so we sort for printing
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))

	// Filtering out duplicates
	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)
}