compact_test.gno

  1package ulist
  2
  3import (
  4	"testing"
  5
  6	"gno.land/p/nt/uassert/v0"
  7)
  8
  9// countNodes walks the tree directly, so the tests assert against the real
 10// structure rather than against Compact's own bookkeeping.
 11func countNodes(n *treeNode) int {
 12	if n == nil {
 13		return 0
 14	}
 15	return 1 + countNodes(n.left) + countNodes(n.right)
 16}
 17
 18func TestCompactEmptyAndNil(t *testing.T) {
 19	var nilList *List
 20	uassert.Equal(t, 0, nilList.Compactable())
 21	uassert.Equal(t, 0, nilList.Compact())
 22
 23	l := New()
 24	uassert.Equal(t, 0, l.Compactable())
 25	uassert.Equal(t, 0, l.Compact())
 26}
 27
 28func TestCompactNothingDeleted(t *testing.T) {
 29	l := New()
 30	l.Append(generateSequence(20)...)
 31	before := countNodes(l.root)
 32
 33	uassert.Equal(t, 0, l.Compactable())
 34	uassert.Equal(t, 0, l.Compact())
 35	uassert.Equal(t, before, countNodes(l.root))
 36	uassert.Equal(t, 20, l.Size())
 37	uassert.Equal(t, 20, l.TotalSize())
 38}
 39
 40func TestCompactFreesOnlyFullyDeadSubtrees(t *testing.T) {
 41	tests := []struct {
 42		name    string
 43		size    int
 44		deleted []int
 45	}{
 46		{"nothing deleted", 16, nil},
 47		{"one deleted", 16, []int{9}},
 48		{"leading run", 32, []int{0, 1, 2, 3, 4, 5, 6, 7}},
 49		{"trailing run", 32, []int{24, 25, 26, 27, 28, 29, 30, 31}},
 50		{"every other", 32, []int{1, 3, 5, 7, 9, 11, 13, 15}},
 51		{"all but one", 16, []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}},
 52		{"all of them", 16, []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14}},
 53	}
 54
 55	for _, tt := range tests {
 56		t.Run(tt.name, func(t *testing.T) {
 57			l := New()
 58			l.Append(generateSequence(tt.size)...)
 59			for _, i := range tt.deleted {
 60				uassert.NoError(t, l.Delete(i))
 61			}
 62
 63			// Every surviving element, recorded before the compaction.
 64			survivors := map[int]any{}
 65			for i := 0; i < tt.size; i++ {
 66				if v := l.Get(i); v != nil {
 67					survivors[i] = v
 68				}
 69			}
 70
 71			predicted := l.Compactable()
 72			nodesBefore := countNodes(l.root)
 73			freed := l.Compact()
 74
 75			// Compactable and Compact must agree, and both must match the tree.
 76			uassert.Equal(t, predicted, freed)
 77			uassert.Equal(t, nodesBefore-freed, countNodes(l.root))
 78
 79			// A second pass has nothing left to do: Compact is idempotent.
 80			uassert.Equal(t, 0, l.Compactable())
 81			uassert.Equal(t, 0, l.Compact())
 82
 83			// Indices are preserved: every survivor is still at its own index,
 84			// and the sizes are untouched.
 85			uassert.Equal(t, tt.size, l.TotalSize())
 86			uassert.Equal(t, len(survivors), l.Size())
 87			for i, want := range survivors {
 88				uassert.Equal(t, want, l.Get(i))
 89			}
 90
 91			// Appends continue from the same number.
 92			l.Append("after")
 93			uassert.Equal(t, "after", l.Get(tt.size))
 94			uassert.Equal(t, tt.size+1, l.TotalSize())
 95		})
 96	}
 97}
 98
 99func TestCompactNeverFreesTheRoot(t *testing.T) {
100	// Index 0 is the root. Deleting everything must still leave it, or
101	// findNode would treat the list as empty and write the next append to
102	// index 0.
103	l := New()
104	l.Append("a", "b", "c")
105	uassert.NoError(t, l.Delete(0, 1, 2))
106	l.Compact()
107
108	uassert.True(t, l.root != nil)
109	uassert.Equal(t, 1, countNodes(l.root))
110	uassert.Equal(t, 0, l.Size())
111	uassert.Equal(t, 3, l.TotalSize())
112
113	l.Append("d")
114	uassert.Equal(t, "d", l.Get(3))
115	uassert.Equal(t, nil, l.Get(0))
116}
117
118func TestCompactMakesDeletedElementsUnrestorable(t *testing.T) {
119	// The documented behaviour change against v0: a soft-deleted element can
120	// be restored with Set, but not once its node has been freed and the
121	// storage deposit refunded.
122	l := New()
123	l.Append(generateSequence(8)...)
124	uassert.NoError(t, l.Delete(4, 5, 6, 7))
125
126	// Before compaction: restoring works.
127	uassert.NoError(t, l.Set(5, "restored"))
128	uassert.Equal(t, "restored", l.Get(5))
129	uassert.NoError(t, l.Delete(5))
130
131	uassert.True(t, l.Compact() > 0)
132
133	// After compaction: the node is gone, so there is nothing to restore.
134	uassert.Error(t, l.Set(5, "restored again"))
135	uassert.Equal(t, nil, l.Get(5))
136	// And a live element is still perfectly settable.
137	uassert.NoError(t, l.Set(1, "still here"))
138	uassert.Equal(t, "still here", l.Get(1))
139}
140
141func TestCompactLeavesIterationUnchanged(t *testing.T) {
142	collect := func(l *List) []Entry {
143		var got []Entry
144		l.Iterator(0, l.TotalSize()-1, func(i int, v any) bool {
145			got = append(got, Entry{Index: i, Value: v})
146			return false
147		})
148		return got
149	}
150
151	l := New()
152	l.Append(generateSequence(24)...)
153	uassert.NoError(t, l.Delete(16, 17, 18, 19, 20, 21, 22, 23))
154
155	before := collect(l)
156	l.Compact()
157	after := collect(l)
158
159	uassert.Equal(t, len(before), len(after))
160	for i := range before {
161		uassert.Equal(t, before[i].Index, after[i].Index)
162		uassert.Equal(t, before[i].Value, after[i].Value)
163	}
164}