// Copyright 2020 The LUCI Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package common

import "sort"

// UniqueSorted sorts & removes duplicates in place.
//
// Returns the potentially shorter slice.
func UniqueSorted(v []int64) []int64 {
	if len(v) <= 1 {
		return v
	}

	sort.Slice(v, func(i, j int) bool { return v[i] < v[j] })
	n, prev, skipped := 0, v[0], false
	for _, id := range v[1:] {
		if id == prev {
			skipped = true
			continue
		}
		n++
		if skipped {
			v[n] = id
		}
		prev = id
	}
	return v[:n+1]
}

// DifferenceSorted returns all int64s in the first slice and not the second.
//
// Both slices must be sorted. Doesn't modify input slices.
func DifferenceSorted(a, b []int64) []int64 {
	var diff []int64
	for {
		if len(b) == 0 {
			return append(diff, a...)
		}
		if len(a) == 0 {
			return diff
		}
		x, y := a[0], b[0]
		switch {
		case x == y:
			a, b = a[1:], b[1:]
		case x < y:
			diff = append(diff, x)
			a = a[1:]
		default:
			b = b[1:]
		}
	}
}

// UnionSorted returns sorted unique int64s from two slices.
//
// Both slices must be sorted and unique. Doesn't modify input slices.
func UnionSorted(a, b []int64) []int64 {
	u := make([]int64, 0, len(a)+len(b))
	for {
		if len(b) == 0 {
			return append(u, a...)
		}
		if len(a) == 0 {
			return append(u, b...)
		}
		x, y := a[0], b[0]
		switch {
		case x == y:
			a, b = a[1:], b[1:]
			u = append(u, x)
		case x < y:
			u = append(u, x)
			a = a[1:]
		default:
			u = append(u, y)
			b = b[1:]
		}
	}
}