package main

import (
	"reflect"
	"sort"
	"testing"
)

func filterByAppend(input []int) []int {
	output := input[:0]
	for _, num := range input {
		if num != 0 {
			output = append(output, num)
		}
	}
	return output
}

func filterBySwap(input []int) []int {
	var zero int
	for i, num := range input {
		if num != 0 {
			input[i], input[zero] = input[zero], input[i]
			zero++
		}
	}
	return input[:zero]
}

func filterBySort(input []int) []int {
	var border int
	sort.Ints(input)
	for i, num := range input {
		if num != 0 {
			border = i
			break
		}
	}
	return input[border:]
}

func TestFilter(t *testing.T) {
	tests := []struct {
		name            string
		algorithm       func([]int) []int
		input, expected []int
	}{
		{"filter by append", filterByAppend, []int{0, 1, 0, 0, 2, 3, 4, 0, 5, 0}, []int{1, 2, 3, 4, 5}},
		{"filter by swap", filterBySwap, []int{0, 1, 0, 0, 2, 3, 4, 0, 5, 0}, []int{1, 2, 3, 4, 5}},
		{"filter by sort", filterBySort, []int{0, 1, 0, 0, 2, 3, 4, 0, 5, 0}, []int{1, 2, 3, 4, 5}},
	}
	for _, test := range tests {
		tc := test
		t.Run(test.name, func(t *testing.T) {
			tc.input = tc.algorithm(tc.input)
			if !reflect.DeepEqual(tc.input, tc.expected) {
				t.Errorf("expected %+v, obtained %+v", tc.expected, tc.input)
			}
		})
	}
}

// goos: darwin
// goarch: amd64
// BenchmarkFilter/filter_by_append-4         	50000000	        20.9 ns/op	       0 B/op	       0 allocs/op
// BenchmarkFilter/filter_by_swap-4           	100000000	        20.5 ns/op	       0 B/op	       0 allocs/op
// BenchmarkFilter/filter_by_sort-4           	10000000	       185 ns/op	      32 B/op	       1 allocs/op
func BenchmarkFilter(b *testing.B) {
	benchmarks := []struct {
		name      string
		algorithm func([]int) []int
		input     []int
	}{
		{"filter by append", filterByAppend, []int{0, 1, 0, 0, 2, 3, 4, 0, 5, 0}},
		{"filter by swap", filterBySwap, []int{0, 1, 0, 0, 2, 3, 4, 0, 5, 0}},
		{"filter by sort", filterBySort, []int{0, 1, 0, 0, 2, 3, 4, 0, 5, 0}},
	}
	for _, bm := range benchmarks {
		tc := bm
		b.Run(bm.name, func(b *testing.B) {
			copied := make([]int, len(tc.input))
			b.ReportAllocs()
			b.ResetTimer()
			for i := 0; i < b.N; i++ {
				copy(copied, tc.input)
				_ = tc.algorithm(tc.input)
			}
		})
	}
}