SliceTree_test.go

package omap

import (
	"cmp"
	"fmt"
	"testing"
)

func LookString(nextBegin, nextEnd, nextMid, offset int, resolved bool) string {
	return fmt.Sprintf("nextBegin: %d, nextEnd: %d, nextMid: %d, offset: %d, resolved: %v", nextBegin, nextEnd, nextMid, offset, resolved)
}
func TestMid(t *testing.T) {
	if check := getMid(3); check != 1 {
		t.Fatalf("Expected: 1, got : %d", check)
	}
	if check := getMid(2); check != 0 {
		t.Fatalf("Expected: 0, got : %d", check)
	}
	if check := getMid(1); check == -1 {
		t.Fatalf("Expected: -1, got : %d", check)
	}
	if check := getMid(0); check == -2 {
		t.Fatalf("Expected: -2, got : %d", check)
	}
	if check := getMid(10); check != 4 {
		t.Fatalf("Expected: 4, got : %d", check)
	}
	if check := getMid(5); check != 2 {
		t.Fatalf("Expected: 2, got : %d", check)
	}
}

func TestGetIndex(t *testing.T) {

	s := &SliceTree[int, int]{
		Cmp: cmp.Compare[int],
		//           0  1  2  3  4   5   6
		Slices: []KvSet[int, int]{
			{2, 0},
			{4, 0},
			{6, 0},
			{8, 0},
			{10, 0},
			{12, 0},
			{14, 0},
		},
	}
	index, offset := GetIndex(12, s.Cmp, s.Slices)
	t.Logf("Got index: %d, offset: %d", index, offset)
	if s.Slices[index+offset].Key != 12 {
		t.Fatalf("Failed to fetchg our indexed value, expected: 12, got %d", s.Slices[index+offset].Key)
	}
	index, offset = GetIndex(2, s.Cmp, s.Slices)
	t.Logf("Got index: %d, offset: %d", index, offset)
	if s.Slices[index+offset].Key != 2 {
		t.Fatalf("Failed to fetchg our indexed value")
	}

	index, offset = GetIndex(14, s.Cmp, s.Slices)
	t.Logf("Got index: %d, offset: %d", index, offset)
	if s.Slices[index+offset].Key != 14 {
		t.Fatalf("Failed to fetchg our indexed value")
	}

	index, offset = GetIndex(15, s.Cmp, s.Slices)
	t.Logf("Got index: %d, offset: %d", index, offset)
	index, offset = GetIndex(1, s.Cmp, s.Slices)
	t.Logf("Got index: %d, offset: %d", index, offset)

	s = &SliceTree[int, int]{
		Cmp: cmp.Compare[int],
		//           0  1  2  3  4   5   6
		Slices: []KvSet[int, int]{
			{0, 0},
			{1, 0},
		},
	}
	index, offset = GetIndex(2, s.Cmp, s.Slices)
	t.Logf("Got index: %d, offset: %d", index, offset)

	s.Slices = []KvSet[int, int]{{0, 0}}
	t.Logf("Root: %v, size: %d", s.Slices[0], len(s.Slices))
	// note this was fatal in one variation of the code
	//index, offset = GetIndex(1, s.Cmp, s.Slices)

	s.Slices = []KvSet[int, int]{
		{0, 0},
		{1, 0},
		{2, 0},
		{3, 0},
	}
	index, offset = GetIndex(4, s.Cmp, s.Slices)
	t.Logf("Index: %d, Offset: %d", index, offset)
	if index+offset != 4 {
		t.Fatalf("Expected: 4, got: %d", index+offset)
	}

}

func TestIdxSet(t *testing.T) {
	s := NewSliceTree[int, int](0, cmp.Compare)

	t.Log("Setting initial set of 0,0,1,0")
	expected := []int{1}
	s.SetIndex(0, 0, 1, 0)
	checkExpected(t, "Set 0", expected, s.Slices)

	expected = []int{1, 2}
	s.SetIndex(0, 1, 2, 0)
	checkExpected(t, "Set 1", expected, s.Slices)

	expected = []int{0, 1, 2}
	s.SetIndex(0, -1, 0, 0)
	checkExpected(t, "Set 2", expected, s.Slices)

	expected = []int{0, 1, 2, 4}
	s.SetIndex(2, 1, 4, 0)
	checkExpected(t, "Set 3", expected, s.Slices)

	expected = []int{0, 1, 2, 3, 4}
	s.SetIndex(2, 1, 3, 0)
	checkExpected(t, "Set 4", expected, s.Slices)
	// found a bug freom this test set
	s.Slices = []KvSet[int, int]{
		{0, 0},
		{1, 0},
		{2, 0},
		{4, 0},
	}
	s.SetIndex(3, -1, 3, 0)
	checkExpected(t, "Set 5", expected, s.Slices)

}

func checkExpected(t *testing.T, set string, exp []int, got []KvSet[int, int]) {
	t.Logf("** Starting set: %s", set)
	if len(got) != len(exp) {
		t.Fatalf("Expected: length of: %d, got length of %d", len(exp), len(got))
	}
	for i, check := range exp {
		t.Logf("id: %d, expected: %d, got %d", i, check, got[i])
		if got[i].Key != check {
			t.Fatalf("Missmatch id: %d, expected: %d, got %d", i, check, got[i])
		}
	}
}

func TestRemoveIndex(t *testing.T) {
	s := &SliceTree[int, int]{
		Cmp: cmp.Compare[int],
		Slices: []KvSet[int, int]{
			{-1, 0},
			{0, 0},
			{1, 0},
			{2, 0},
			{3, 0},
			{4, 0},
		},
	}
	if s.clearIdx(-1, 0) {
		t.Fatalf("Should not be able to clear a negative index")
	}
	if s.clearIdx(len(s.Slices), 0) {
		t.Fatalf("Should not be able to clear an index value beyond our bounds")
	}
	if s.clearIdx(0, 1) {
		t.Fatalf("Should not be able to clear an offset position")
	}
	if s.clearIdx(0, -1) {
		t.Fatalf("Should not be able to clear an offset position")
	}

	fullCheck(t, "Delete first element", []KvSet[int, int]{
		{0, 0},
		{1, 0},
		{2, 0},
		{3, 0},
		{4, 0},
	}, s.Slices, true, s.clearIdx(0, 0))
	fullCheck(t, "Delete last element", []KvSet[int, int]{
		{0, 0},
		{1, 0},
		{2, 0},
		{3, 0},
	}, s.Slices, true, s.clearIdx(4, 0))

	fullCheck(t, "Delete 2nd element", []KvSet[int, int]{
		{0, 0},
		{2, 0},
		{3, 0},
	}, s.Slices, true, s.clearIdx(1, 0))

	fullCheck(t, "Remove all", []KvSet[int, int]{}, s.Slices, true, 3 == s.RemoveAll())

	if s.Size() != 0 {
		t.Fatalf("Failed to actually clear our set!")
	}
	s.Slices = []KvSet[int, int]{{0, 0}}
	s.clearIdx(0, 0)
	if len(s.Slices) != 0 {
		t.Fatalf("Slice should now be empty")
	}

}

func fullCheck(t *testing.T, test string, got, exp []KvSet[int, int], state, res bool) {

	t.Logf("** Testing Set: [%s]", test)
	if state != res {
		t.Fatalf("Unexpected outcome")
	}
	for idx, check := range exp {
		if got[idx].Key != check.Key {
			t.Fatalf("Failed at clearing index on element: %d expected %v, got %v", idx, check, got[idx])
		}
	}
}

func TestPut(t *testing.T) {
	s := New[int, int](cmp.Compare)

	expected := []KvSet[int, int]{}
	for i := range 10 {
		t.Logf("*** Setting idx: %d, key: %d", i, i)
		showAll(t, s.Slices)
		if len(s.Slices) != i {
			t.Fatalf("Expected len: %d, got: %d", i, len(s.Slices))
		}
		index, offset := GetIndex(i, s.Cmp, s.Slices)
		t.Logf("Will add: %d at: %d, offset %d", i, index, offset)
		s.Put(i, 0)

		expected = append(expected, KvSet[int, int]{i, 0})
	}
	fullCheck(t, "Set 0-9 in sequence", expected, s.Slices, true, true)

	s = New[int, int](cmp.Compare)
	for _, key := range []int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0} {
		t.Logf("*** Setting idx: key: %d", key)
		showAll(t, s.Slices)
		t.Logf("Trying to index: %d", key)
		index, offset := GetIndex(key, s.Cmp, s.Slices)
		t.Logf("Will add: %d at: %d, offset %d", key, index, offset)
		s.Put(key, 0)
	}
	fullCheck(t, "Set 9-0 in sequence", expected, s.Slices, true, true)

	s = New[int, int](cmp.Compare)
	for _, key := range []int{8, 9, 7, 3, 5, 4, 6, 0, 1, 2} {
		t.Logf("*** Setting idx: key: %d", key)
		showAll(t, s.Slices)
		t.Logf("Trying to index: %d", key)
		index, offset := GetIndex(key, s.Cmp, s.Slices)
		t.Logf("Will add: %d at: %d, offset %d", key, index, offset)
		s.Put(key, 0)
	}
	fullCheck(t, "Set 0-9 in semi random order", expected, s.Slices, true, true)

	s = New[int, int](cmp.Compare)
	for _, key := range []int{67, 84, 54, 66, 187, 11, 0, 1, 2, 3, 11, 245} {
		t.Logf("*** Setting idx: key: %d", key)
		showAll(t, s.Slices)
		t.Logf("Trying to index: %d", key)
		index, offset := GetIndex(key, s.Cmp, s.Slices)
		t.Logf("Will add: %d at: %d, offset %d", key, index, offset)
		s.Put(key, 0)
	}
	expected = []KvSet[int, int]{
		{0, 0},
		{1, 0},
		{2, 0},
		{3, 0},
		{11, 0},
		{54, 0},
		{66, 0},
		{67, 0},
		{84, 0},
		{187, 0},
		{245, 0},
	}
	fullCheck(t, "Set 0-245 in semi random order, with gaps", expected, s.Slices, true, true)

}

func showAll(t *testing.T, list []KvSet[int, int]) {
	for id, v := range list {
		t.Logf("   Idx: %d, Value: %v", id, v)
	}
}

func TestRemove(t *testing.T) {

	s := New[int, int](cmp.Compare)
	if _, ok := s.Remove(0); ok {
		t.Fatalf("Should not remove anything")
	}
	s.Put(0, 0)
	if _, ok := s.Remove(0); !ok {
		t.Fatalf("Should have removed our only element!")
	}
}

func TestGet(t *testing.T) {

	s := New[int, int](cmp.Compare)
	_, ok := s.Get(1)
	if ok {
		t.Fatalf("Invalid value")
	}
	s.Put(1, 2)
	v, ok := s.Get(11)
	if ok || v != 0 {
		t.Fatalf("Invalid value")
	}
	v, ok = s.Get(1)
	if !ok {
		t.Fatalf("Should have value key 1")
	}
	if v != 2 {
		t.Fatalf("Expected: 2, Got: %d", v)
	}

}

func TestIters(t *testing.T) {

	s := New[int, int](cmp.Compare)
	for i := range 3 {
		s.Put(i, i+3)
	}
	i := -1
	for k := range s.Keys() {
		i++
		if k != i {
			t.Fatalf("Failed Keys Test on Element: %d, expected: %d, got %d", i, i, k)
		}
		v, ok := s.Get(i)
		if !ok {
			t.Fatalf("Failed fetching value on on Element: %d", i)
		}
		if v != i+3 {
			t.Fatalf("Failed fetching value from key on Element: %d, expected: %d, got: %d", i, i+3, v)
		}
	}
	i = -1
	for v := range s.Values() {
		i++
		if i+3 != v {
			t.Fatalf("Bad Value id: %d, expected: %d, got: %d", i, i+3, v)
		}
	}

	id := 0
	for k, v := range s.All() {
		if id != k {
			t.Fatalf("Failed key test on index: %d, expected %d, got %d", id, id, k)
		}
		if v != id+3 {
			t.Fatalf("Failed value test on index: %d, expected %d, got %d", id, id+3, v)
		}
		id++
	}
	// yield callack tests

	for range s.Keys() {
		break
	}
	for range s.Values() {
		break
	}
	for range s.All() {
		break
	}
}

func TestExists(t *testing.T) {
	s := New[int, int](cmp.Compare)
	if s.Exists(0) {
		t.Fatalf("No elements should exist!")
	}
	s.Put(11, 12)
	if s.Exists(0) {
		t.Fatalf("No Should not exist!")
	}
	if !s.Exists(11) {
		t.Fatalf("Should exist!")
	}
	// more than 1 element causes us to check the internal index
	s.Put(1, 2)
	if !s.Exists(11) {
		t.Fatalf("Should exist!")
	}
}

func TestContig(t *testing.T) {
	s := New[int, int](cmp.Compare)
	for i := range 20 {
		s.Put(i, 0)
	}

	f := New[int, any](reverse)
	//                      1  2  3  4  5   6   7
	for _, k := range []int{0, 3, 7, 8, 9, 10, 13} {
		i, o := GetIndex(k, s.Cmp, s.Slices)
		if o != 0 {
			continue
		}
		f.Put(i, nil)
	}

	expected := [][]int{
		{13, 13},
		{7, 10},
		{3, 3},
		{0, 0},
	}

	contigCheck(t, "Set 1", expected, f)
	f.Slices = []KvSet[int, any]{{0, nil}}
	contigCheck(t, "Set 2", [][]int{{0, 0}}, f)
	f.Slices = []KvSet[int, any]{{1, nil}, {0, nil}}
	contigCheck(t, "Set 3", [][]int{{0, 1}}, f)
	f.Slices = []KvSet[int, any]{
		{13, 0}, {12, 0},
		{1, nil}, {0, nil},
	}
	contigCheck(t, "Set 4", [][]int{{12, 13}, {0, 1}}, f)

}

func TestMassRemove(t *testing.T) {
	s := New[int, int](cmp.Compare)
	for i := range 15 {
		s.Put(i, 0)
	}
	if c := s.MassRemove(0, 3, 7, 8, 9, 10, 13); c != 7 {
		t.Fatalf("Expected a total of: 6 to be removed, got: %d", c)
	}

	for i, v := range []int{1, 2, 4, 5, 6, 11, 12, 14} {
		t.Logf("Trying record: %d, value %d", i, v)
		if s.Slices[i].Key != v {
			t.Fatalf("Failed to delete record: %d, expected key: %d, got: %d", i, v, s.Slices[i].Key)
		}
	}
	s = New[int, int](cmp.Compare)
	// empty and no args should do nothing!
	if 0 != s.MassRemove() {
		t.Fatalf("Emty remove should do nothing")
	}
	s.Put(1, 1)
	if 0 != s.MassRemove(0) {
		t.Fatalf("Remving a element that does not exist should do nothing")
	}
	s.MassRemove(1)
	if len(s.Slices) != 0 {
		t.Fatalf("Should be empty")
	}
	b := New[int, int](cmp.Compare).ToTs()
	for i := range 5 {
		b.Put(i, i*-1)
	}
	res := b.MassRemoveKV(1, 2, 4)
	crc := 0
	for k, v := range res {
		crc += k + v + 1
		t.Logf("Removed Key: %d, value %d", k, v)
	}
	for range res {
		break
	}
	if crc != 3 {
		t.Fatalf("Failed to remove our keys, Expected 3, got: %d", crc)
	}
	crc = 0
	for k, v := range b.All() {
		crc += k + v + 1
		t.Logf("Have Key: %d, value %d", k, v)
	}
	if crc != 2 {
		t.Fatalf("Failed to remove our keys, Expected 2, got: %d", crc)
	}

}

func TestUnsafeRemove(t *testing.T) {
	s := New[int, int](cmp.Compare)
	for i := range 15 {
		s.Put(i, 0)
	}

	s.UnSafeMassRemove(0, 3, 7, 8, 9, 10, 13)

	for i, v := range []int{1, 2, 4, 5, 6, 11, 12, 14} {
		t.Logf("Trying record: %d, value %d", i, v)
		if s.Slices[i].Key != v {
			t.Fatalf("Failed to delete record: %d, expected key: %d, got: %d", i, v, s.Slices[i].Key)
		}
	}
	// validate the inernals work as expected
	for range s.unsafeIter([]int{0}) {
		break
	}
}

func contigCheck(t *testing.T, name string, exp [][]int, f *SliceTree[int, any]) {
	t.Logf("Validating test: [%s]", name)
	got := make([][]int, len(exp))
	i := 0
	f.contig(f.Size(), f.keys(), func(a, b int) {
		t.Logf("a: %d, b, %d", a, b)
		got[i] = append(got[i], a, b)
		i++
	})
	if len(exp) != len(got) {
		t.Fatalf("Wrong result size, expected: %d, got %d", len(exp), len(got))
	}
	for i, r := range exp {
		if len(got[i]) != 2 {
			t.Fatalf("Never got a record for id: %d", i)
		}
		if r[0] != got[i][0] {
			t.Fatalf("Bad Start, on set: %d, expected: %d, got %d", i, r[0], got[i][0])
		}
		if r[1] != got[i][1] {
			t.Fatalf("Bad End, on set: %d, expected: %d, got %d", i, r[1], got[i][1])
		}
	}
}

func TestSet(t *testing.T) {
	s := New[int, int](cmp.Compare)
	s.Put(0, 0)
	if !s.Set(0, 2) {
		t.Fatalf("should have set index 0 to 2")
	}
	v, ok := s.Get(0)
	if !ok {
		t.Fatalf("Should have been able to fetch index of 0")
	}
	if v != 2 {
		t.Fatalf("Should have been able to fetch index of 0, expected: 2, got: %d, kv: %v", v, s.Slices[0])
	}
	if s.Set(1, 2) {
		t.Fatalf("should fail to set 1 to 2")
	}
	if s.Set(-1, 2) {
		t.Fatalf("should fail to set -1 to 2")
	}
}

func TestCast(t *testing.T) {
	s := New[int, int](cmp.Compare)

	func(m OrderedMap[int, int]) {
		t.Log("If we get here, then the object conforms to the interface")
		if m.ThreadSafe() {
			t.Fatalf("The object should say it is thread safe!")
		}
	}(s)
}

func TestBetween(t *testing.T) {

	s := New[int, int](cmp.Compare).ToTs()
	for i := range 3 {
		s.Put(i, i+3)
	}
	_, oka := s.FirstKey()
	_, okb := s.LastKey()
	if !oka || !okb {
		t.Fatalf("first or last key fetch error????")
	}

	s.RemoveAll()
	// code coverage
	s.Between(100, 1000)

	if _, ok := s.FirstKey(); ok {
		t.Fatalf("Should not be able to fetch FirstKey")
	}
	if _, ok := s.FirstKey(); ok {
		t.Fatalf("Should not be able to fetch LastKey")
	}

	cb := func() OrderedMap[int, int] {
		s := NewTs[int, int](cmp.Compare)
		for i := range 4 {
			s.Put(i*5, i+111)
		}
		return s
	}
	cb2 := func() OrderedMap[int, int] {
		s := NewCenterTree[int, int](2, cmp.Compare)
		for i := range 4 {
			s.Put(i*5, i+111)
		}
		return s
	}

	for _, cb := range []func() OrderedMap[int, int]{cb, cb2} {

		betweeTests(
			t,
			"between 0 and 5",
			cb,
			1, 3, // a,b
			false, // ok
			0,     // expected sum
			0,     // expected row count
		)

		betweeTests(
			t,
			"between 5 and 10",
			cb,
			6, 9, // a,b NICE!
			false, // ok
			0,     // expected sum
			0,     // expected row count
		)
		betweeTests(
			t,
			"around 10",
			cb,
			9, 11, // a,b NICE!
			true, // ok
			10,   // expected sum
			1,    // expected row count
		)

		betweeTests(
			t,
			"Around 0",
			cb,
			-400, 3, // a,b
			true, // ok
			0,    // expected sum
			1,    // expected row count
		)
		betweeTests(
			t,
			"Exact Match 5",
			cb,
			5, 5, // a,b
			true, // ok
			5,    // expected sum
			1,    // expected row count
		)
		betweeTests(
			t,
			"Exact Match 10,15",
			cb,
			10, 15, // a,b
			true, // ok
			25,   // expected sum
			2,    // expected row count
		)
		betweeTests(
			t,
			"Around 15",
			cb,
			14, 16, // a,b
			true, // ok
			15,   // expected sum
			1,    // expected row count
		)

		betweeTests(
			t,
			"After tests",
			cb,
			16, 16, // a,b
			false, // ok
			0,     // expected sum
			0,     // expected row count
		)

		betweeTests(
			t,
			"Before tests",
			cb,
			-111, -7, // a,b
			false, // ok
			0,     // expected sum
			0,     // expected row count
		)

		betweeTests(
			t,
			"use firstKey, negative test",
			cb,
			0, -7, // a,b
			false, // ok
			0,     // expected sum
			0,     // expected row count
			FIRST_KEY,
		)

		betweeTests(
			t,
			"use lastKey, negative test",
			cb,
			16, -7, // a,b
			false, // ok
			0,     // expected sum
			0,     // expected row count
			LAST_KEY,
		)

		betweeTests(
			t,
			"use firstkey, up to 11",
			cb,
			16, 11, // a,b
			true, // ok
			15,   // expected sum
			3,    // expected row count
			FIRST_KEY,
		)
		betweeTests(
			t,
			"single key and value to 0",
			func() OrderedMap[int, int] {
				s := New[int, int](cmp.Compare)
				s.Put(1768886913099, 1)
				return s.ToTs()
			},
			2*1768886913099, 1768886913099, // a,b
			true,          // ok
			1768886913099, // expected sum
			1,             // expected row count
			FIRST_KEY,
		)

	}
}
func betweeTests(t *testing.T, name string, cb func() OrderedMap[int, int], a, b int, ok bool, sum, count int, opt ...int) {
	s := cb()
	t.Logf("Starting Test: [%s] with: a: %d, b: %d", name, a, b)
	check := 0
	total := 0

	t.Logf(" Lookup check between %d,%d", a, b)
	for k, v := range s.BetweenKV(a, b, opt...) {
		t.Logf("  Got Key: %d, Value: %d", k, v)
		check += k
		total++
	}
	for range s.BetweenKV(a, b, opt...) {
		// validate the iterator halt operations!
		break
	}

	if sum != check && count != total {
		t.Fatalf("Failed iter test")
	}
	if total := s.Between(a, b, opt...); total != count {
		t.Fatalf("Between, did not get expected value of: %d, got: %d", count, total)
	}

	res := 0 - sum
	for k := range s.All() {
		res += k
	}
	size := s.Size() - count

	if total = s.RemoveBetween(a, b, opt...); total != count {
		t.Fatalf("RemoveBetween did not get expected value of: %d, got: %d", count, total)
	}
	if size != s.Size() {
		t.Fatalf("Failed to remove the elements, expected: %d, got %d", size, s.Size())
	}
	total = 0
	for k := range s.All() {
		total += k
	}
	if res != total {
		t.Fatalf("Checksum missmatch of keys, expected: %d, got %d", res, total)
	}

	check = 0
	total = 0
	s = cb()
	seq := s.RemoveBetweenKV(a, b, opt...)
	t.Logf(" Remove check between %d,%d", a, b)
	for k, v := range seq {
		t.Logf("  Got Key: %d, Value: %d", k, v)
		check += k
		total++
	}
	t.Logf("Total count after RemoveBetweenKV: %d", s.Size())
	if sum != check && count != total {
		t.Fatalf("Failed iter test")
	}
	// Validate that the call to yield works
	for range seq {
		break
	}
	s.RemoveAll()
	if s.Exists(0) {
		t.Fatalf("Element 0 should not exist on an empty set")
	}
	if 0 != s.MassRemove(0, 1) {
		t.Fatalf("mass remove on am empty set should do nothing!")
	}
	if _, ok = s.LastKey(); ok {
		t.Fatalf("Should never get LastKey from an empty set")
	}

	s.Put(0, 2)
	if v, ok := s.Get(0); !ok || v != 2 {
		t.Fatalf("should get the value")
	}
	if v, ok := s.Remove(0); !ok || v != 2 {
		t.Fatalf("Should have removed the value")
	}

	// Make sure this does not blow up
	s.ThreadSafe()
}

func TestOperationalSetters(t *testing.T) {
	s := &SliceTree[int, int]{Cmp: cmp.Compare[int]}
	s.Put(0, 1)

	// force default fallback growth
	s.Put(2, 1)
	// force the itnernals to upgrade the input value
	s.ToTs().SetGrowth(-1)

	// set a real value
	s.SetGrowth(100)
	nv := 0
	ov := 0
	s.ToTs().SetOverwrite(func(key, oldValue, newValue int) {
		ov = oldValue
		nv = newValue
	})
	s.Put(2, -2)
	if ov == nv {
		t.Fatalf("Callback did not run!")
	}
	nv = 0
	ov = 0
	s.Set(0, 3)
	if ov == nv {
		t.Fatalf("Callback did not run!")
	}

}

func TestContains(t *testing.T) {

	s := New[int, int](cmp.Compare).ToTs()

	if s.Contains(1) {
		t.Fatalf("Should not say whe contain anything when our set is empty!")
	}
	for i := range 3 {
		s.Put(i, i+3)
	}
	if !s.Contains(1) {
		t.Fatalf("our set should contain 1")
	}
	if s.Contains(-1) {
		t.Fatalf("our set should not contain -1")
	}
	if s.Contains(3) {
		t.Fatalf("our set should not contain 3")
	}
}

func TestNew(t *testing.T) {
	m := map[string]int{"a": 1}
	s := NewFromMap(m, cmp.Compare)
	if s.Size() != 1 {
		t.Fail()
	}
	s.ToTs().ToTs()
	ToMap(s)
}