// 第 6 周 – 用有序切片表示的集合：基于归并的运算
// 运行：go run ./w06/sortedset
package main

import "fmt"

// 切片严格递增（没有重复元素）。

func contains(a []int, x int) bool { // 二分查找 – O(log n)
	lo, hi := 0, len(a)-1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		switch {
		case a[mid] == x:
			return true
		case a[mid] < x:
			lo = mid + 1
		default:
			hi = mid - 1
		}
	}
	return false
}

func union(a, b []int) []int { // O(n + m)
	c := make([]int, 0, len(a)+len(b))
	i, j := 0, 0
	for i < len(a) && j < len(b) {
		switch {
		case a[i] < b[j]:
			c = append(c, a[i])
			i++
		case a[i] > b[j]:
			c = append(c, b[j])
			j++
		default:
			c = append(c, a[i])
			i++
			j++
		}
	}
	c = append(c, a[i:]...)
	return append(c, b[j:]...)
}

func intersection(a, b []int) []int {
	var c []int
	i, j := 0, 0
	for i < len(a) && j < len(b) {
		switch {
		case a[i] < b[j]:
			i++
		case a[i] > b[j]:
			j++
		default:
			c = append(c, a[i])
			i++
			j++
		}
	}
	return c
}

func difference(a, b []int) []int {
	var c []int
	i, j := 0, 0
	for i < len(a) && j < len(b) {
		switch {
		case a[i] < b[j]:
			c = append(c, a[i])
			i++
		case a[i] > b[j]:
			j++
		default:
			i++
			j++
		}
	}
	return append(c, a[i:]...)
}

func subsetOf(a, b []int) bool {
	i, j := 0, 0
	for i < len(a) && j < len(b) {
		if a[i] < b[j] {
			return false
		}
		if a[i] == b[j] {
			i++
		}
		j++
	}
	return i == len(a)
}

func main() {
	a := []int{2, 5, 8, 11}
	b := []int{3, 5, 9, 11, 14}
	fmt.Println("A =", a, ", B =", b)
	fmt.Println("A ∪ B =", union(a, b))
	fmt.Println("A ∩ B =", intersection(a, b))
	fmt.Println(`A \ B =`, difference(a, b))
	fmt.Println("8 ∈ A?", contains(a, 8), ", 9 ∈ A?", contains(a, 9))
	fmt.Println("{5, 11} ⊆ B?", subsetOf([]int{5, 11}, b), ", A ⊆ B?", subsetOf(a, b))
}