package main

import (
	"math/rand/v2"
	"slices"
	"sort"
	"testing"
)

func TestLowerBound(t *testing.T) {
	r := rand.New(rand.NewPCG(7, 11))
	for n := 0; n < 80; n++ {
		a := make([]int, n)
		for i := range a {
			a[i] = r.IntN(20) - 10
		}
		slices.Sort(a)
		for x := -12; x <= 12; x++ {
			got := lowerBound(a, x)
			want := sort.SearchInts(a, x)
			if got != want {
				t.Fatalf("%v %d got %d want %d", a, x, got, want)
			}
		}
	}
}
func TestMergeSort(t *testing.T) {
	r := rand.New(rand.NewPCG(9, 13))
	for n := 0; n < 100; n++ {
		a := make([]int, n)
		for i := range a {
			a[i] = r.IntN(20)
		}
		want := slices.Clone(a)
		slices.Sort(want)
		if got := mergeSort(a); !slices.Equal(got, want) {
			t.Fatal(got, want)
		}
	}
}
func TestAlgorithms(t *testing.T) {
	if minCoins([]int{1, 3, 4}, 6) != 2 || minCoins([]int{2}, 3) != -1 || minCoins([]int{2}, 0) != 0 {
		t.Fatal("coin cases")
	}
	if len(subsets([]int{1, 2, 3})) != 8 {
		t.Fatal("subsets")
	}
	s := subsets([]int{1, 2})
	s[3][0] = 99
	if s[2][0] != 1 {
		t.Fatal("paths alias")
	}
	if _, _, ok := pairSum([]int{}, 1); ok {
		t.Fatal("empty pair")
	}
	if !slices.Equal(bfs([][]int{{1}, {0}, {}}, 0), []int{0, 1, -1}) {
		t.Fatal("BFS")
	}
}
func TestCache(t *testing.T) {
	c := newLRU(2)
	c.put("A", 1)
	c.put("B", 2)
	c.get("A")
	c.put("C", 3)
	if _, ok := c.get("B"); ok {
		t.Fatal("LRU wrong eviction")
	}
	c.put("A", 9)
	if v, ok := c.get("A"); !ok || v != 9 {
		t.Fatal("update")
	}
	z := newLRU(0)
	z.put("A", 1)
	if len(z.items) != 0 {
		t.Fatal("zero capacity")
	}
	f := newLFU(2)
	f.put("A", 1)
	f.put("B", 2)
	f.put("C", 3)
	if _, ok := f.get("A"); ok {
		t.Fatal("LFU tie rule")
	}
	f.get("B")
	f.put("D", 4)
	if _, ok := f.get("C"); ok {
		t.Fatal("LFU frequency")
	}
}
func TestBloomRingLSM(t *testing.T) {
	var b toyBloom
	for x := uint(0); x < 8; x++ {
		b.add(x)
		if !b.maybe(x) {
			t.Fatal("false negative")
		}
	}
	old := []ringPoint{{20, "A"}, {60, "B"}, {90, "C"}}
	added := []ringPoint{{20, "A"}, {40, "D"}, {60, "B"}, {90, "C"}}
	for k := 0; k < 100; k++ {
		if owner(old, k) != owner(added, k) && owner(added, k) != "D" {
			t.Fatal("unrelated movement")
		}
	}
	v, ok := lookup([][]record{{{"A", 0, true}}, {{"A", 1, false}}}, "A")
	if ok || v != 0 {
		t.Fatal("tombstone ignored")
	}
}