// Created by vinson on 2021/11/30.
// Intersect set between 2 slice
// Case: inter, addition := Intersect([]int(), []int())
// Case: inter, removing := Intersect([]int(), []int())
// inter Returns the element that exists in both A and B
// h Returns the element of the set B that is not in the set A
func Intersect(a []int, b []int) (inter []int, r []int) {
// interacting on the smallest list first can potentially be faster...but not by much,worse case is the same
low := a
high := make([]int, len(b))
copy(high, b)
done := false
for i, l := range low {
for j, h := range high {
// get future index values
f1 := i + 1
f2 := j + 1
if l != h {
continue
}
inter = append(inter, h)
if f1 < len(low) && f2 < len(high) {
// if the future values aren't the same then that's the end of the intersection
if low[f1] != high[f2] {
done = true
}
}
// we don't want to iterate on the entire list everytime,so remove the parts we already looped on will make it faster each pass
high = high[:j+copy(high[j:], high[j+1:])]
break
}
// nothing in the future so we are done
if done {
break
}
}
return inter, high
}
