// 6. hét – Halmaz rendezetlen szelettel ábrázolva
// Futtatás: go run ./h06/unorderedset
package main

import "fmt"

type UnorderedSet struct {
	data []int
}

// Contains: lineáris keresés – O(n)
func (s *UnorderedSet) Contains(x int) bool {
	for _, v := range s.data {
		if v == x {
			return true
		}
	}
	return false
}

// Add: csak ha még nincs benne – O(n)
func (s *UnorderedSet) Add(x int) {
	if !s.Contains(x) {
		s.data = append(s.data, x)
	}
}

// Remove: az utolsó elemet tesszük a törölt helyére (a sorrend nem számít)
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("A.Remove(2) után:", a.data)
}