// 第 6 周 – 用无序切片表示的集合
// 运行：go run ./w06/unorderedset
package main

import "fmt"

type UnorderedSet struct {
	data []int
}

// Contains：顺序查找 – O(n)
func (s *UnorderedSet) Contains(x int) bool {
	for _, v := range s.data {
		if v == x {
			return true
		}
	}
	return false
}

// Add：只在尚不存在时加入 – O(n)
func (s *UnorderedSet) Add(x int) {
	if !s.Contains(x) {
		s.data = append(s.data, x)
	}
}

// Remove：把最后一个元素移到被删除的位置（顺序无关紧要）
func (s *UnorderedSet) Remove(x int) {
	for i, v := range s.data {
		if v == x {
			last := len(s.data) - 1
			s.data[i] = s.data[last]
			s.data = s.data[:last]
			return
		}
	}
}

func (s *UnorderedSet) SubsetOf(b *UnorderedSet) bool { // O(n·m)
	for _, v := range s.data {
		if !b.Contains(v) {
			return false
		}
	}
	return true
}

func (s *UnorderedSet) Union(b *UnorderedSet) *UnorderedSet { // O(n·m)
	r := &UnorderedSet{}
	for _, v := range s.data {
		r.Add(v)
	}
	for _, v := range b.data {
		r.Add(v)
	}
	return r
}

func (s *UnorderedSet) Intersection(b *UnorderedSet) *UnorderedSet {
	r := &UnorderedSet{}
	for _, v := range s.data {
		if b.Contains(v) {
			r.Add(v)
		}
	}
	return r
}

func (s *UnorderedSet) Difference(b *UnorderedSet) *UnorderedSet {
	r := &UnorderedSet{}
	for _, v := range s.data {
		if !b.Contains(v) {
			r.Add(v)
		}
	}
	return r
}

func of(xs ...int) *UnorderedSet {
	s := &UnorderedSet{}
	for _, x := range xs {
		s.Add(x)
	}
	return s
}

func main() {
	a := of(8, 2, 11, 5, 2, 8)
	b := of(9, 5, 14, 3, 11)
	fmt.Println("A =", a.data, ", B =", b.data)
	fmt.Println("A ∪ B =", a.Union(b).data)
	fmt.Println("A ∩ B =", a.Intersection(b).data)
	fmt.Println(`A \ B =`, a.Difference(b).data)
	fmt.Println("{5, 11} ⊆ A?", of(5, 11).SubsetOf(a), ", A ⊆ B?", a.SubsetOf(b))
	a.Remove(2)
	fmt.Println("after A.Remove(2):", a.data)
}