tree_test.gno
9.33 Kb · 392 lines
1package cow
2
3import (
4 "testing"
5)
6
7func TestNewTree(t *testing.T) {
8 tree := NewTree()
9 if tree.node != nil {
10 t.Error("Expected tree.node to be nil")
11 }
12}
13
14func TestTreeSize(t *testing.T) {
15 tree := NewTree()
16 if tree.Size() != 0 {
17 t.Error("Expected empty tree size to be 0")
18 }
19
20 tree.Set("key1", "value1")
21 tree.Set("key2", "value2")
22 if tree.Size() != 2 {
23 t.Error("Expected tree size to be 2")
24 }
25}
26
27func TestTreeHas(t *testing.T) {
28 tree := NewTree()
29 tree.Set("key1", "value1")
30
31 if !tree.Has("key1") {
32 t.Error("Expected tree to have key1")
33 }
34
35 if tree.Has("key2") {
36 t.Error("Expected tree to not have key2")
37 }
38}
39
40func TestTreeGet(t *testing.T) {
41 tree := NewTree()
42 tree.Set("key1", "value1")
43
44 value, exists := tree.Get("key1")
45 if !exists || value != "value1" {
46 t.Error("Expected Get to return value1 and true")
47 }
48
49 _, exists = tree.Get("key2")
50 if exists {
51 t.Error("Expected Get to return false for non-existent key")
52 }
53}
54
55func TestTreeGetByIndex(t *testing.T) {
56 tree := NewTree()
57 tree.Set("key1", "value1")
58 tree.Set("key2", "value2")
59
60 key, value := tree.GetByIndex(0)
61 if key != "key1" || value != "value1" {
62 t.Error("Expected GetByIndex(0) to return key1 and value1")
63 }
64
65 key, value = tree.GetByIndex(1)
66 if key != "key2" || value != "value2" {
67 t.Error("Expected GetByIndex(1) to return key2 and value2")
68 }
69
70 defer func() {
71 if r := recover(); r == nil {
72 t.Error("Expected GetByIndex to panic for out-of-range index")
73 }
74 }()
75 tree.GetByIndex(2)
76}
77
78func TestTreeRemove(t *testing.T) {
79 tree := NewTree()
80 tree.Set("key1", "value1")
81
82 value, removed := tree.Remove("key1")
83 if !removed || value != "value1" || tree.Size() != 0 {
84 t.Error("Expected Remove to remove key-value pair")
85 }
86
87 _, removed = tree.Remove("key2")
88 if removed {
89 t.Error("Expected Remove to return false for non-existent key")
90 }
91}
92
93func TestTreeIterate(t *testing.T) {
94 tree := NewTree()
95 tree.Set("key1", "value1")
96 tree.Set("key2", "value2")
97 tree.Set("key3", "value3")
98
99 var keys []string
100 tree.Iterate("", "", func(key string, value any) bool {
101 keys = append(keys, key)
102 return false
103 })
104
105 expectedKeys := []string{"key1", "key2", "key3"}
106 if !slicesEqual(keys, expectedKeys) {
107 t.Errorf("Expected keys %v, got %v", expectedKeys, keys)
108 }
109}
110
111func TestTreeReverseIterate(t *testing.T) {
112 tree := NewTree()
113 tree.Set("key1", "value1")
114 tree.Set("key2", "value2")
115 tree.Set("key3", "value3")
116
117 var keys []string
118 tree.ReverseIterate("", "", func(key string, value any) bool {
119 keys = append(keys, key)
120 return false
121 })
122
123 expectedKeys := []string{"key3", "key2", "key1"}
124 if !slicesEqual(keys, expectedKeys) {
125 t.Errorf("Expected keys %v, got %v", expectedKeys, keys)
126 }
127}
128
129func TestTreeIterateByOffset(t *testing.T) {
130 tree := NewTree()
131 tree.Set("key1", "value1")
132 tree.Set("key2", "value2")
133 tree.Set("key3", "value3")
134
135 var keys []string
136 tree.IterateByOffset(1, 2, func(key string, value any) bool {
137 keys = append(keys, key)
138 return false
139 })
140
141 expectedKeys := []string{"key2", "key3"}
142 if !slicesEqual(keys, expectedKeys) {
143 t.Errorf("Expected keys %v, got %v", expectedKeys, keys)
144 }
145}
146
147func TestTreeReverseIterateByOffset(t *testing.T) {
148 tree := NewTree()
149 tree.Set("key1", "value1")
150 tree.Set("key2", "value2")
151 tree.Set("key3", "value3")
152
153 var keys []string
154 tree.ReverseIterateByOffset(1, 2, func(key string, value any) bool {
155 keys = append(keys, key)
156 return false
157 })
158
159 expectedKeys := []string{"key2", "key1"}
160 if !slicesEqual(keys, expectedKeys) {
161 t.Errorf("Expected keys %v, got %v", expectedKeys, keys)
162 }
163}
164
165// Verify that Tree implements avl.ITree
166// var _ avl.ITree = (*Tree)(nil) // TODO: fix gnovm bug: ./examples/gno.land/p/nym-moultest123/cow: test pkg: panic: gno.land/p/nym-moultest123/cow/tree_test.gno:166:5: name avl not defined in fileset with files [node.gno tree.gno node_test.gno tree_test.gno]:
167
168func TestCopyOnWrite(t *testing.T) {
169 // Create original tree
170 original := NewTree()
171 original.Set("A", 1)
172 original.Set("B", 2)
173 original.Set("C", 3)
174
175 // Create a clone
176 clone := original.Clone()
177
178 // Modify clone
179 clone.Set("B", 20)
180 clone.Set("D", 4)
181
182 // Verify original is unchanged
183 if val, _ := original.Get("B"); val != 2 {
184 t.Errorf("Original tree was modified: expected B=2, got B=%v", val)
185 }
186 if original.Has("D") {
187 t.Error("Original tree was modified: found key D")
188 }
189
190 // Verify clone has new values
191 if val, _ := clone.Get("B"); val != 20 {
192 t.Errorf("Clone not updated: expected B=20, got B=%v", val)
193 }
194 if val, _ := clone.Get("D"); val != 4 {
195 t.Errorf("Clone not updated: expected D=4, got D=%v", val)
196 }
197}
198
199func TestCopyOnWriteEdgeCases(t *testing.T) {
200 t.Run("nil tree clone", func(t *testing.T) {
201 var original *Tree
202 clone := original.Clone()
203 if clone != nil {
204 t.Error("Expected nil clone from nil tree")
205 }
206 })
207
208 t.Run("empty tree clone", func(t *testing.T) {
209 original := NewTree()
210 clone := original.Clone()
211
212 // Modify clone
213 clone.Set("A", 1)
214
215 if original.Size() != 0 {
216 t.Error("Original empty tree was modified")
217 }
218 if clone.Size() != 1 {
219 t.Error("Clone was not modified")
220 }
221 })
222
223 t.Run("multiple clones", func(t *testing.T) {
224 original := NewTree()
225 original.Set("A", 1)
226 original.Set("B", 2)
227
228 // Create multiple clones
229 clone1 := original.Clone()
230 clone2 := original.Clone()
231 clone3 := clone1.Clone()
232
233 // Modify each clone differently
234 clone1.Set("A", 10)
235 clone2.Set("B", 20)
236 clone3.Set("C", 30)
237
238 // Check original remains unchanged
239 if val, _ := original.Get("A"); val != 1 {
240 t.Errorf("Original modified: expected A=1, got A=%v", val)
241 }
242 if val, _ := original.Get("B"); val != 2 {
243 t.Errorf("Original modified: expected B=2, got B=%v", val)
244 }
245
246 // Verify each clone has correct values
247 if val, _ := clone1.Get("A"); val != 10 {
248 t.Errorf("Clone1 incorrect: expected A=10, got A=%v", val)
249 }
250 if val, _ := clone2.Get("B"); val != 20 {
251 t.Errorf("Clone2 incorrect: expected B=20, got B=%v", val)
252 }
253 if val, _ := clone3.Get("C"); val != 30 {
254 t.Errorf("Clone3 incorrect: expected C=30, got C=%v", val)
255 }
256 })
257
258 t.Run("clone after removal", func(t *testing.T) {
259 original := NewTree()
260 original.Set("A", 1)
261 original.Set("B", 2)
262 original.Set("C", 3)
263
264 // Remove a node and then clone
265 original.Remove("B")
266 clone := original.Clone()
267
268 // Modify clone
269 clone.Set("B", 20)
270
271 // Verify original state
272 if original.Has("B") {
273 t.Error("Original tree should not have key B")
274 }
275
276 // Verify clone state
277 if val, _ := clone.Get("B"); val != 20 {
278 t.Errorf("Clone incorrect: expected B=20, got B=%v", val)
279 }
280 })
281
282 t.Run("concurrent modifications", func(t *testing.T) {
283 original := NewTree()
284 original.Set("A", 1)
285 original.Set("B", 2)
286
287 clone1 := original.Clone()
288 clone2 := original.Clone()
289
290 // Modify same key in different clones
291 clone1.Set("B", 20)
292 clone2.Set("B", 30)
293
294 // Each clone should have its own value
295 if val, _ := clone1.Get("B"); val != 20 {
296 t.Errorf("Clone1 incorrect: expected B=20, got B=%v", val)
297 }
298 if val, _ := clone2.Get("B"); val != 30 {
299 t.Errorf("Clone2 incorrect: expected B=30, got B=%v", val)
300 }
301 })
302
303 t.Run("deep tree modifications", func(t *testing.T) {
304 original := NewTree()
305 // Create a deeper tree
306 keys := []string{"M", "F", "T", "B", "H", "P", "Z"}
307 for _, k := range keys {
308 original.Set(k, k)
309 }
310
311 clone := original.Clone()
312
313 // Modify a deep node
314 clone.Set("H", "modified")
315
316 // Check original remains unchanged
317 if val, _ := original.Get("H"); val != "H" {
318 t.Errorf("Original modified: expected H='H', got H=%v", val)
319 }
320
321 // Verify clone modification
322 if val, _ := clone.Get("H"); val != "modified" {
323 t.Errorf("Clone incorrect: expected H='modified', got H=%v", val)
324 }
325 })
326
327 t.Run("rebalancing test", func(t *testing.T) {
328 original := NewTree()
329 // Insert nodes that will cause rotations
330 keys := []string{"A", "B", "C", "D", "E"}
331 for _, k := range keys {
332 original.Set(k, k)
333 }
334
335 clone := original.Clone()
336
337 // Add more nodes to clone to trigger rebalancing
338 clone.Set("F", "F")
339 clone.Set("G", "G")
340
341 // Verify original structure remains unchanged
342 originalKeys := collectKeys(original)
343 expectedOriginal := []string{"A", "B", "C", "D", "E"}
344 if !slicesEqual(originalKeys, expectedOriginal) {
345 t.Errorf("Original tree structure changed: got %v, want %v", originalKeys, expectedOriginal)
346 }
347
348 // Verify clone has all keys
349 cloneKeys := collectKeys(clone)
350 expectedClone := []string{"A", "B", "C", "D", "E", "F", "G"}
351 if !slicesEqual(cloneKeys, expectedClone) {
352 t.Errorf("Clone tree structure incorrect: got %v, want %v", cloneKeys, expectedClone)
353 }
354 })
355
356 t.Run("value mutation test", func(t *testing.T) {
357 type MutableValue struct {
358 Data string
359 }
360
361 original := NewTree()
362 mutable := &MutableValue{Data: "original"}
363 original.Set("key", mutable)
364
365 clone := original.Clone()
366
367 // Modify the mutable value
368 mutable.Data = "modified"
369
370 // Both original and clone should see the modification
371 // because we're not deep copying values
372 origVal, _ := original.Get("key")
373 cloneVal, _ := clone.Get("key")
374
375 if origVal.(*MutableValue).Data != "modified" {
376 t.Error("Original value not modified as expected")
377 }
378 if cloneVal.(*MutableValue).Data != "modified" {
379 t.Error("Clone value not modified as expected")
380 }
381 })
382}
383
384// Helper function to collect all keys in order
385func collectKeys(tree *Tree) []string {
386 var keys []string
387 tree.Iterate("", "", func(key string, _ any) bool {
388 keys = append(keys, key)
389 return false
390 })
391 return keys
392}
