gno.land/p/nt/bptree/list/v0⧉

1package list23import (4	"testing"56	"gno.land/p/nt/ufmt/v0"7)89func TestList_Basic(t *testing.T) {10	var l List1112	// Test empty list13	if l.Len() != 0 {14		t.Errorf("new list should be empty, got len %d", l.Len())15	}1617	// Test append and length18	l.Append(1, 2, 3)19	if l.Len() != 3 {20		t.Errorf("expected len 3, got %d", l.Len())21	}2223	// Test get24	if v, _ := l.Get(0); v != 1 {25		t.Errorf("expected 1 at index 0, got %v", v)26	}27	if v, _ := l.Get(1); v != 2 {28		t.Errorf("expected 2 at index 1, got %v", v)29	}30	if v, _ := l.Get(2); v != 3 {31		t.Errorf("expected 3 at index 2, got %v", v)32	}3334	// Test out of bounds35	if _, ok := l.Get(-1); ok {36		t.Error("expected ok=false for negative index")37	}38	if _, ok := l.Get(3); ok {39		t.Error("expected ok=false for out of bounds index")40	}41}4243func TestList_Set(t *testing.T) {44	var l List45	l.Append(1, 2, 3)4647	// Test valid set within bounds48	if ok := l.Set(1, 42); !ok {49		t.Error("Set should return true for valid index")50	}51	if v, _ := l.Get(1); v != 42 {52		t.Errorf("expected 42 after Set, got %v", v)53	}5455	// Test set at size (append)56	if ok := l.Set(3, 4); !ok {57		t.Error("Set should return true when appending at size")58	}59	if v, _ := l.Get(3); v != 4 {60		t.Errorf("expected 4 after Set at size, got %v", v)61	}6263	// Test invalid sets64	if ok := l.Set(-1, 10); ok {65		t.Error("Set should return false for negative index")66	}67	if ok := l.Set(5, 10); ok {68		t.Error("Set should return false for index > size")69	}7071	// Verify list state hasn't changed after invalid operations72	expected := []any{1, 42, 3, 4}73	for i, want := range expected {74		if got, _ := l.Get(i); got != want {75			t.Errorf("index %d = %v; want %v", i, got, want)76		}77	}78}7980func TestList_Delete(t *testing.T) {81	var l List82	l.Append(1, 2, 3)8384	// Test valid delete85	if v, ok := l.Delete(1); !ok || v != 2 {86		t.Errorf("Delete(1) = %v, %v; want 2, true", v, ok)87	}88	if l.Len() != 2 {89		t.Errorf("expected len 2 after delete, got %d", l.Len())90	}91	if v, _ := l.Get(1); v != 3 {92		t.Errorf("expected 3 at index 1 after delete, got %v", v)93	}9495	// Test invalid delete96	if v, ok := l.Delete(-1); ok || v != nil {97		t.Errorf("Delete(-1) = %v, %v; want nil, false", v, ok)98	}99	if v, ok := l.Delete(2); ok || v != nil {100		t.Errorf("Delete(2) = %v, %v; want nil, false", v, ok)101	}102}103104func TestList_Slice(t *testing.T) {105	var l List106	l.Append(1, 2, 3, 4, 5)107108	// Test valid ranges109	values := l.Slice(1, 4)110	expected := []any{2, 3, 4}111	if !sliceEqual(values, expected) {112		t.Errorf("Slice(1,4) = %v; want %v", values, expected)113	}114115	// Test edge cases116	if values := l.Slice(-1, 2); !sliceEqual(values, []any{1, 2}) {117		t.Errorf("Slice(-1,2) = %v; want [1 2]", values)118	}119	if values := l.Slice(3, 10); !sliceEqual(values, []any{4, 5}) {120		t.Errorf("Slice(3,10) = %v; want [4 5]", values)121	}122	if values := l.Slice(3, 2); values != nil {123		t.Errorf("Slice(3,2) = %v; want nil", values)124	}125}126127func TestList_ForEach(t *testing.T) {128	var l List129	l.Append(1, 2, 3)130131	sum := 0132	l.ForEach(func(index int, value any) bool {133		sum += value.(int)134		return false135	})136137	if sum != 6 {138		t.Errorf("ForEach sum = %d; want 6", sum)139	}140141	// Test early termination142	count := 0143	l.ForEach(func(index int, value any) bool {144		count++145		return true // stop after first item146	})147148	if count != 1 {149		t.Errorf("ForEach early termination count = %d; want 1", count)150	}151}152153func TestList_Clone(t *testing.T) {154	var l List155	l.Append(1, 2, 3)156157	clone := l.Clone()158159	// Test same length160	if clone.Len() != l.Len() {161		t.Errorf("clone.Len() = %d; want %d", clone.Len(), l.Len())162	}163164	// Test same values165	for i := 0; i < l.Len(); i++ {166		cv, _ := clone.Get(i)167		lv, _ := l.Get(i)168		if cv != lv {169			t.Errorf("clone.Get(%d) = %v; want %v", i, cv, lv)170		}171	}172173	// Test independence174	l.Set(0, 42)175	cv, _ := clone.Get(0)176	lv, _ := l.Get(0)177	if cv == lv {178		t.Error("clone should be independent of original")179	}180181	// Test that appending to both after clone works independently.182	var l2 List183	l2.Append("a", "b", "c")184	clone2 := l2.Clone()185186	l2.Append("d", "e")187	clone2.Append("x", "y")188189	if l2.Len() != 5 {190		t.Errorf("original after append: Len() = %d; want 5", l2.Len())191	}192	if clone2.Len() != 5 {193		t.Errorf("clone after append: Len() = %d; want 5", clone2.Len())194	}195	origExpected := []any{"a", "b", "c", "d", "e"}196	cloneExpected := []any{"a", "b", "c", "x", "y"}197	for i := 0; i < 5; i++ {198		ov, _ := l2.Get(i)199		if ov != origExpected[i] {200			t.Errorf("original.Get(%d) = %v; want %v", i, ov, origExpected[i])201		}202		cv, _ := clone2.Get(i)203		if cv != cloneExpected[i] {204			t.Errorf("clone.Get(%d) = %v; want %v", i, cv, cloneExpected[i])205		}206	}207}208209func TestList_DeleteRange(t *testing.T) {210	var l List211	l.Append(1, 2, 3, 4, 5)212213	// Test valid range delete214	deleted := l.DeleteRange(1, 4)215	if deleted != 3 {216		t.Errorf("DeleteRange(1,4) deleted %d elements; want 3", deleted)217	}218	if l.Len() != 2 {219		t.Errorf("after DeleteRange(1,4) len = %d; want 2", l.Len())220	}221	expected := []any{1, 5}222	for i, want := range expected {223		if got, _ := l.Get(i); got != want {224			t.Errorf("after DeleteRange(1,4) index %d = %v; want %v", i, got, want)225		}226	}227228	// Test edge cases229	l = List{}230	l.Append(1, 2, 3)231232	// Delete with negative start233	if deleted := l.DeleteRange(-1, 2); deleted != 2 {234		t.Errorf("DeleteRange(-1,2) deleted %d elements; want 2", deleted)235	}236237	// Delete with end > length238	l = List{}239	l.Append(1, 2, 3)240	if deleted := l.DeleteRange(1, 5); deleted != 2 {241		t.Errorf("DeleteRange(1,5) deleted %d elements; want 2", deleted)242	}243244	// Delete invalid range245	if deleted := l.DeleteRange(2, 1); deleted != 0 {246		t.Errorf("DeleteRange(2,1) deleted %d elements; want 0", deleted)247	}248249	// Delete empty range250	if deleted := l.DeleteRange(1, 1); deleted != 0 {251		t.Errorf("DeleteRange(1,1) deleted %d elements; want 0", deleted)252	}253}254255func TestList_Tree(t *testing.T) {256	var l List257	l.Append(1, 2, 3)258259	rotree := l.Tree()260	expected := 3261262	// Reverse iterate through the ReadOnlyTree263	rotree.ReverseIterateByOffset(0, rotree.Size(), func(key string, value any) bool {264		intValue := value.(int)265		if intValue != expected {266			t.Errorf("ReadOnlyTree expected %d, got %d", expected, intValue)267		}268		expected--269		return false270	})271}272273func TestList_EmptyOperations(t *testing.T) {274	var l List275276	// Operations on empty list277	if _, ok := l.Get(0); ok {278		t.Error("Get(0) on empty list should return ok=false")279	}280281	// Set should work at index 0 for empty list (append case)282	if ok := l.Set(0, 1); !ok {283		t.Error("Set(0,1) on empty list = false; want true")284	}285	if v, _ := l.Get(0); v != 1 {286		t.Errorf("Get(0) after Set = %v; want 1", v)287	}288289	l = List{} // Reset to empty list290	if v, ok := l.Delete(0); ok || v != nil {291		t.Errorf("Delete(0) on empty list = %v, %v; want nil, false", v, ok)292	}293	if values := l.Slice(0, 1); values != nil {294		t.Errorf("Range(0,1) on empty list = %v; want nil", values)295	}296}297298func TestList_DifferentTypes(t *testing.T) {299	var l List300301	// Test with different types302	l.Append(42, "hello", true, 3.14)303304	v0, _ := l.Get(0)305	if v := v0.(int); v != 42 {306		t.Errorf("Get(0) = %v; want 42", v)307	}308	v1, _ := l.Get(1)309	if v := v1.(string); v != "hello" {310		t.Errorf("Get(1) = %v; want 'hello'", v)311	}312	v2, _ := l.Get(2)313	if v := v2.(bool); !v {314		t.Errorf("Get(2) = %v; want true", v)315	}316	v3, _ := l.Get(3)317	if v := v3.(float64); v != 3.14 {318		t.Errorf("Get(3) = %v; want 3.14", v)319	}320}321322func TestList_LargeOperations(t *testing.T) {323	var l List324325	// Test with larger number of elements326	n := 1000327	for i := 0; i < n; i++ {328		l.Append(i)329	}330331	if l.Len() != n {332		t.Errorf("Len() = %d; want %d", l.Len(), n)333	}334335	// Test range on large list336	values := l.Slice(n-3, n)337	expected := []any{n - 3, n - 2, n - 1}338	if !sliceEqual(values, expected) {339		t.Errorf("Range(%d,%d) = %v; want %v", n-3, n, values, expected)340	}341342	// Test large range deletion343	deleted := l.DeleteRange(100, 900)344	if deleted != 800 {345		t.Errorf("DeleteRange(100,900) = %d; want 800", deleted)346	}347	if l.Len() != 200 {348		t.Errorf("Len() after large delete = %d; want 200", l.Len())349	}350}351352func TestList_ChainedOperations(t *testing.T) {353	var l List354355	// Test sequence of operations356	l.Append(1, 2, 3)357	l.Delete(1)358	l.Append(4)359	l.Set(1, 5)360361	expected := []any{1, 5, 4}362	for i, want := range expected {363		if got, _ := l.Get(i); got != want {364			t.Errorf("index %d = %v; want %v", i, got, want)365		}366	}367}368369func TestList_RangeEdgeCases(t *testing.T) {370	var l List371	l.Append(1, 2, 3, 4, 5)372373	// Test various edge cases for Range374	cases := []struct {375		start, end int376		want       []any377	}{378		{-10, 2, []any{1, 2}},379		{3, 10, []any{4, 5}},380		{0, 0, nil},381		{5, 5, nil},382		{4, 3, nil},383		{-1, -1, nil},384	}385386	for _, tc := range cases {387		got := l.Slice(tc.start, tc.end)388		if !sliceEqual(got, tc.want) {389			t.Errorf("Slice(%d,%d) = %v; want %v", tc.start, tc.end, got, tc.want)390		}391	}392}393394func TestList_IndexConsistency(t *testing.T) {395	var l List396397	// Initial additions398	l.Append(1, 2, 3, 4, 5) // [1,2,3,4,5]399400	// Delete from middle401	l.Delete(2) // [1,2,4,5]402403	// Add more elements404	l.Append(6, 7) // [1,2,4,5,6,7]405406	// Delete range from middle407	l.DeleteRange(1, 4) // [1,6,7]408409	// Add more elements410	l.Append(8, 9, 10) // [1,6,7,8,9,10]411412	// Verify sequence is continuous413	expected := []any{1, 6, 7, 8, 9, 10}414	for i, want := range expected {415		if got, _ := l.Get(i); got != want {416			t.Errorf("index %d = %v; want %v", i, got, want)417		}418	}419420	// Verify no extra elements exist421	if l.Len() != len(expected) {422		t.Errorf("length = %d; want %d", l.Len(), len(expected))423	}424425	// Verify all indices are accessible426	allValues := l.Slice(0, l.Len())427	if !sliceEqual(allValues, expected) {428		t.Errorf("Slice(0, Len()) = %v; want %v", allValues, expected)429	}430431	// Verify no gaps in iteration432	var iteratedValues []any433	var indices []int434	l.ForEach(func(index int, value any) bool {435		iteratedValues = append(iteratedValues, value)436		indices = append(indices, index)437		return false438	})439440	// Check values from iteration441	if !sliceEqual(iteratedValues, expected) {442		t.Errorf("ForEach values = %v; want %v", iteratedValues, expected)443	}444445	// Check indices are sequential446	for i, idx := range indices {447		if idx != i {448			t.Errorf("ForEach index %d = %d; want %d", i, idx, i)449		}450	}451}452453func TestList_RecursiveSafety(t *testing.T) {454	// Create a new list455	l := &List{}456457	// Add some initial values458	l.Append("id1")459	l.Append("id2")460	l.Append("id3")461462	// Test deep list traversal463	found := false464	l.ForEach(func(i int, v any) bool {465		if str, ok := v.(string); ok {466			if str == "id2" {467				found = true468				return true // stop iteration469			}470		}471		return false // continue iteration472	})473474	if !found {475		t.Error("Failed to find expected value in list")476	}477478	short := testing.Short()479480	// Test recursive safety by performing multiple operations481	for i := 0; i < 1000; i++ {482		// Add new value483		l.Append(ufmt.Sprintf("id%d", i+4))484485		if !short {486			// Search for a value487			var lastFound bool488			l.ForEach(func(j int, v any) bool {489				if str, ok := v.(string); ok {490					if str == ufmt.Sprintf("id%d", i+3) {491						lastFound = true492						return true493					}494				}495				return false496			})497498			if !lastFound {499				t.Errorf("Failed to find value id%d after insertion", i+3)500			}501		}502	}503504	// Verify final length505	expectedLen := 1003 // 3 initial + 1000 added506	if l.Len() != expectedLen {507		t.Errorf("Expected length %d, got %d", expectedLen, l.Len())508	}509510	if short {511		t.Skip("skipping extended recursive safety test in short mode")512	}513}514515func TestList_NilValueDistinguishable(t *testing.T) {516	var l List517	l.Append(nil)518	l.Append("hello")519520	// Stored nil is distinguishable from out-of-bounds.521	v, ok := l.Get(0)522	if !ok {523		t.Error("Get(0) should return ok=true for stored nil")524	}525	if v != nil {526		t.Errorf("Get(0) should return nil value, got %v", v)527	}528529	// Out of bounds returns false.530	_, ok = l.Get(5)531	if ok {532		t.Error("Get(5) should return ok=false for out of bounds")533	}534535	// Normal value still works.536	v, ok = l.Get(1)537	if !ok || v != "hello" {538		t.Errorf("Get(1) = (%v, %v); want (hello, true)", v, ok)539	}540}541542// Helper function to compare slices543func sliceEqual(a, b []any) bool {544	if len(a) != len(b) {545		return false546	}547	for i := range a {548		if a[i] != b[i] {549			return false550		}551	}552	return true553}554