immutable_test.go raw
1 package treap
2
3 import (
4 "bytes"
5 "crypto/sha256"
6 "testing"
7 )
8
9 // TestImmutableEmpty ensures calling functions on an empty immutable treap works as expected.
10 func TestImmutableEmpty(t *testing.T) {
11 t.Parallel()
12 // Ensure the treap length is the expected value.
13 testTreap := NewImmutable()
14 if gotLen := testTreap.Len(); gotLen != 0 {
15 t.Fatalf("Len: unexpected length - got %d, want %d", gotLen, 0)
16 }
17 // Ensure the reported size is 0.
18 if gotSize := testTreap.Size(); gotSize != 0 {
19 t.Fatalf("Size: unexpected byte size - got %d, want 0",
20 gotSize,
21 )
22 }
23 // Ensure there are no errors with requesting keys from an empty treap.
24 key := serializeUint32(0)
25 if gotVal := testTreap.Has(key); gotVal {
26 t.Fatalf("Has: unexpected result - got %v, want false", gotVal)
27 }
28 if gotVal := testTreap.Get(key); gotVal != nil {
29 t.Fatalf("Get: unexpected result - got %x, want nil", gotVal)
30 }
31 // Ensure there are no panics when deleting keys from an empty treap.
32 testTreap.Delete(key)
33 // Ensure the number of keys iterated by ForEach on an empty treap is
34 // zero.
35 var numIterated int
36 testTreap.ForEach(func(k, v []byte) bool {
37 numIterated++
38 return true
39 },
40 )
41 if numIterated != 0 {
42 t.Fatalf("ForEach: unexpected iterate count - got %d, want 0",
43 numIterated,
44 )
45 }
46 }
47
48 // TestImmutableSequential ensures that putting keys into an immutable treap in sequential order works as expected.
49 func TestImmutableSequential(t *testing.T) {
50 t.Parallel()
51 // Insert a bunch of sequential keys while checking several of the treap functions work as expected.
52 expectedSize := uint64(0)
53 numItems := 1000
54 testTreap := NewImmutable()
55 for i := 0; i < numItems; i++ {
56 key := serializeUint32(uint32(i))
57 testTreap = testTreap.Put(key, key)
58 // Ensure the treap length is the expected value.
59 if gotLen := testTreap.Len(); gotLen != i+1 {
60 t.Fatalf("Len #%d: unexpected length - got %d, want %d",
61 i, gotLen, i+1,
62 )
63 }
64 // Ensure the treap has the key.
65 if !testTreap.Has(key) {
66 t.Fatalf("Has #%d: key %q is not in treap", i, key)
67 }
68 // Get the key from the treap and ensure it is the expected value.
69 if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, key) {
70 t.Fatalf("Get #%d: unexpected value - got %x, want %x",
71 i, gotVal, key,
72 )
73 }
74 // Ensure the expected size is reported.
75 expectedSize += nodeFieldsSize + 8
76 if gotSize := testTreap.Size(); gotSize != expectedSize {
77 t.Fatalf("Size #%d: unexpected byte size - got %d, "+
78 "want %d", i, gotSize, expectedSize,
79 )
80 }
81 }
82 // Ensure the all keys are iterated by ForEach in order.
83 var numIterated int
84 testTreap.ForEach(func(k, v []byte) bool {
85 wantKey := serializeUint32(uint32(numIterated))
86 // Ensure the key is as expected.
87 if !bytes.Equal(k, wantKey) {
88 t.Fatalf("ForEach #%d: unexpected key - got %x, want %x",
89 numIterated, k, wantKey,
90 )
91 }
92 // Ensure the value is as expected.
93 if !bytes.Equal(v, wantKey) {
94 t.Fatalf("ForEach #%d: unexpected value - got %x, want %x",
95 numIterated, v, wantKey,
96 )
97 }
98 numIterated++
99 return true
100 },
101 )
102 // Ensure all items were iterated.
103 if numIterated != numItems {
104 t.Fatalf("ForEach: unexpected iterate count - got %d, want %d",
105 numIterated, numItems,
106 )
107 }
108 // Delete the keys one-by-one while checking several of the treap functions work as expected.
109 for i := 0; i < numItems; i++ {
110 key := serializeUint32(uint32(i))
111 testTreap = testTreap.Delete(key)
112 // Ensure the treap length is the expected value.
113 if gotLen := testTreap.Len(); gotLen != numItems-i-1 {
114 t.Fatalf("Len #%d: unexpected length - got %d, want %d",
115 i, gotLen, numItems-i-1,
116 )
117 }
118 // Ensure the treap no longer has the key.
119 if testTreap.Has(key) {
120 t.Fatalf("Has #%d: key %q is in treap", i, key)
121 }
122 // Get the key that no longer exists from the treap and ensure it is nil.
123 if gotVal := testTreap.Get(key); gotVal != nil {
124 t.Fatalf("Get #%d: unexpected value - got %x, want nil",
125 i, gotVal,
126 )
127 }
128 // Ensure the expected size is reported.
129 expectedSize -= nodeFieldsSize + 8
130 if gotSize := testTreap.Size(); gotSize != expectedSize {
131 t.Fatalf("Size #%d: unexpected byte size - got %d, "+
132 "want %d", i, gotSize, expectedSize,
133 )
134 }
135 }
136 }
137
138 // TestImmutableReverseSequential ensures that putting keys into an immutable treap in reverse sequential order works as
139 // expected.
140 func TestImmutableReverseSequential(t *testing.T) {
141 t.Parallel()
142 // Insert a bunch of sequential keys while checking several of the treap functions work as expected.
143 expectedSize := uint64(0)
144 numItems := 1000
145 testTreap := NewImmutable()
146 for i := 0; i < numItems; i++ {
147 key := serializeUint32(uint32(numItems - i - 1))
148 testTreap = testTreap.Put(key, key)
149 // Ensure the treap length is the expected value.
150 if gotLen := testTreap.Len(); gotLen != i+1 {
151 t.Fatalf("Len #%d: unexpected length - got %d, want %d",
152 i, gotLen, i+1,
153 )
154 }
155 // Ensure the treap has the key.
156 if !testTreap.Has(key) {
157 t.Fatalf("Has #%d: key %q is not in treap", i, key)
158 }
159 // Get the key from the treap and ensure it is the expected
160 // value.
161 if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, key) {
162 t.Fatalf("Get #%d: unexpected value - got %x, want %x",
163 i, gotVal, key,
164 )
165 }
166 // Ensure the expected size is reported.
167 expectedSize += nodeFieldsSize + 8
168 if gotSize := testTreap.Size(); gotSize != expectedSize {
169 t.Fatalf("Size #%d: unexpected byte size - got %d, "+
170 "want %d", i, gotSize, expectedSize,
171 )
172 }
173 }
174 // Ensure the all keys are iterated by ForEach in order.
175 var numIterated int
176 testTreap.ForEach(func(k, v []byte) bool {
177 wantKey := serializeUint32(uint32(numIterated))
178 // Ensure the key is as expected.
179 if !bytes.Equal(k, wantKey) {
180 t.Fatalf("ForEach #%d: unexpected key - got %x, want %x",
181 numIterated, k, wantKey,
182 )
183 }
184 // Ensure the value is as expected.
185 if !bytes.Equal(v, wantKey) {
186 t.Fatalf("ForEach #%d: unexpected value - got %x, want %x",
187 numIterated, v, wantKey,
188 )
189 }
190 numIterated++
191 return true
192 },
193 )
194 // Ensure all items were iterated.
195 if numIterated != numItems {
196 t.Fatalf("ForEach: unexpected iterate count - got %d, want %d",
197 numIterated, numItems,
198 )
199 }
200 // Delete the keys one-by-one while checking several of the treap functions work as expected.
201 for i := 0; i < numItems; i++ {
202 // Intentionally use the reverse order they were inserted here.
203 key := serializeUint32(uint32(i))
204 testTreap = testTreap.Delete(key)
205 // Ensure the treap length is the expected value.
206 if gotLen := testTreap.Len(); gotLen != numItems-i-1 {
207 t.Fatalf("Len #%d: unexpected length - got %d, want %d",
208 i, gotLen, numItems-i-1,
209 )
210 }
211 // Ensure the treap no longer has the key.
212 if testTreap.Has(key) {
213 t.Fatalf("Has #%d: key %q is in treap", i, key)
214 }
215 // Get the key that no longer exists from the treap and ensure
216 // it is nil.
217 if gotVal := testTreap.Get(key); gotVal != nil {
218 t.Fatalf("Get #%d: unexpected value - got %x, want nil",
219 i, gotVal,
220 )
221 }
222 // Ensure the expected size is reported.
223 expectedSize -= nodeFieldsSize + 8
224 if gotSize := testTreap.Size(); gotSize != expectedSize {
225 t.Fatalf("Size #%d: unexpected byte size - got %d, "+
226 "want %d", i, gotSize, expectedSize,
227 )
228 }
229 }
230 }
231
232 // TestImmutableUnordered ensures that putting keys into an immutable treap in no particular order works as expected.
233 func TestImmutableUnordered(t *testing.T) {
234 t.Parallel()
235 // Insert a bunch of out-of-order keys while checking several of the treap functions work as expected.
236 expectedSize := uint64(0)
237 numItems := 1000
238 testTreap := NewImmutable()
239 for i := 0; i < numItems; i++ {
240 // Hash the serialized int to generate out-of-order keys.
241 hash := sha256.Sum256(serializeUint32(uint32(i)))
242 key := hash[:]
243 testTreap = testTreap.Put(key, key)
244 // Ensure the treap length is the expected value.
245 if gotLen := testTreap.Len(); gotLen != i+1 {
246 t.Fatalf("Len #%d: unexpected length - got %d, want %d",
247 i, gotLen, i+1,
248 )
249 }
250 // Ensure the treap has the key.
251 if !testTreap.Has(key) {
252 t.Fatalf("Has #%d: key %q is not in treap", i, key)
253 }
254 // Get the key from the treap and ensure it is the expected value.
255 if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, key) {
256 t.Fatalf("Get #%d: unexpected value - got %x, want %x",
257 i, gotVal, key,
258 )
259 }
260 // Ensure the expected size is reported.
261 expectedSize += nodeFieldsSize + uint64(len(key)+len(key))
262 if gotSize := testTreap.Size(); gotSize != expectedSize {
263 t.Fatalf("Size #%d: unexpected byte size - got %d, "+
264 "want %d", i, gotSize, expectedSize,
265 )
266 }
267 }
268 // Delete the keys one-by-one while checking several of the treap functions work as expected.
269 for i := 0; i < numItems; i++ {
270 // Hash the serialized int to generate out-of-order keys.
271 hash := sha256.Sum256(serializeUint32(uint32(i)))
272 key := hash[:]
273 testTreap = testTreap.Delete(key)
274 // Ensure the treap length is the expected value.
275 if gotLen := testTreap.Len(); gotLen != numItems-i-1 {
276 t.Fatalf("Len #%d: unexpected length - got %d, want %d",
277 i, gotLen, numItems-i-1,
278 )
279 }
280 // Ensure the treap no longer has the key.
281 if testTreap.Has(key) {
282 t.Fatalf("Has #%d: key %q is in treap", i, key)
283 }
284 // Get the key that no longer exists from the treap and ensure it is nil.
285 if gotVal := testTreap.Get(key); gotVal != nil {
286 t.Fatalf("Get #%d: unexpected value - got %x, want nil",
287 i, gotVal,
288 )
289 }
290 // Ensure the expected size is reported.
291 expectedSize -= nodeFieldsSize + 64
292 if gotSize := testTreap.Size(); gotSize != expectedSize {
293 t.Fatalf("Size #%d: unexpected byte size - got %d, "+
294 "want %d", i, gotSize, expectedSize,
295 )
296 }
297 }
298 }
299
300 // TestImmutableDuplicatePut ensures that putting a duplicate key into an immutable treap works as expected.
301 func TestImmutableDuplicatePut(t *testing.T) {
302 t.Parallel()
303 expectedVal := []byte("testval")
304 expectedSize := uint64(0)
305 numItems := 1000
306 testTreap := NewImmutable()
307 for i := 0; i < numItems; i++ {
308 key := serializeUint32(uint32(i))
309 testTreap = testTreap.Put(key, key)
310 expectedSize += nodeFieldsSize + uint64(len(key)+len(key))
311 // Put a duplicate key with the the expected final value.
312 testTreap = testTreap.Put(key, expectedVal)
313 // Ensure the key still exists and is the new value.
314 if gotVal := testTreap.Has(key); !gotVal {
315 t.Fatalf("Has: unexpected result - got %v, want true",
316 gotVal,
317 )
318 }
319 if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, expectedVal) {
320 t.Fatalf("Get: unexpected result - got %x, want %x",
321 gotVal, expectedVal,
322 )
323 }
324 // Ensure the expected size is reported.
325 expectedSize -= uint64(len(key))
326 expectedSize += uint64(len(expectedVal))
327 if gotSize := testTreap.Size(); gotSize != expectedSize {
328 t.Fatalf("Size: unexpected byte size - got %d, want %d",
329 gotSize, expectedSize,
330 )
331 }
332 }
333 }
334
335 // TestImmutableNilValue ensures that putting a nil value into an immutable treap results in a key being added with an
336 // empty byte slice.
337 func TestImmutableNilValue(t *testing.T) {
338 t.Parallel()
339 key := serializeUint32(0)
340 // Put the key with a nil value.
341 testTreap := NewImmutable()
342 testTreap = testTreap.Put(key, nil)
343 // Ensure the key exists and is an empty byte slice.
344 if gotVal := testTreap.Has(key); !gotVal {
345 t.Fatalf("Has: unexpected result - got %v, want true", gotVal)
346 }
347 if gotVal := testTreap.Get(key); gotVal == nil {
348 t.Fatalf("Get: unexpected result - got nil, want empty slice")
349 }
350 if gotVal := testTreap.Get(key); len(gotVal) != 0 {
351 t.Fatalf("Get: unexpected result - got %x, want empty slice",
352 gotVal,
353 )
354 }
355 }
356
357 // TestImmutableForEachStopIterator ensures that returning false from the ForEach callback on an immutable treap stops
358 // iteration early.
359 func TestImmutableForEachStopIterator(t *testing.T) {
360 t.Parallel()
361 // Insert a few keys.
362 numItems := 10
363 testTreap := NewImmutable()
364 for i := 0; i < numItems; i++ {
365 key := serializeUint32(uint32(i))
366 testTreap = testTreap.Put(key, key)
367 }
368 // Ensure ForEach exits early on false return by caller.
369 var numIterated int
370 testTreap.ForEach(func(k, v []byte) bool {
371 numIterated++
372 return numIterated != numItems/2
373 },
374 )
375 if numIterated != numItems/2 {
376 t.Fatalf("ForEach: unexpected iterate count - got %d, want %d",
377 numIterated, numItems/2,
378 )
379 }
380 }
381
382 // TestImmutableSnapshot ensures that immutable treaps are actually immutable by keeping a reference to the previous
383 // treap, performing a mutation, and then ensuring the referenced treap does not have the mutation applied.
384 func TestImmutableSnapshot(t *testing.T) {
385 t.Parallel()
386 // Insert a bunch of sequential keys while checking several of the treap functions work as expected.
387 expectedSize := uint64(0)
388 numItems := 1000
389 testTreap := NewImmutable()
390 for i := 0; i < numItems; i++ {
391 treapSnap := testTreap
392 key := serializeUint32(uint32(i))
393 testTreap = testTreap.Put(key, key)
394 // Ensure the length of the treap snapshot is the expected
395 // value.
396 if gotLen := treapSnap.Len(); gotLen != i {
397 t.Fatalf("Len #%d: unexpected length - got %d, want %d",
398 i, gotLen, i,
399 )
400 }
401 // Ensure the treap snapshot does not have the key.
402 if treapSnap.Has(key) {
403 t.Fatalf("Has #%d: key %q is in treap", i, key)
404 }
405 // Get the key that doesn't exist in the treap snapshot and
406 // ensure it is nil.
407 if gotVal := treapSnap.Get(key); gotVal != nil {
408 t.Fatalf("Get #%d: unexpected value - got %x, want nil",
409 i, gotVal,
410 )
411 }
412 // Ensure the expected size is reported.
413 if gotSize := treapSnap.Size(); gotSize != expectedSize {
414 t.Fatalf("Size #%d: unexpected byte size - got %d, "+
415 "want %d", i, gotSize, expectedSize,
416 )
417 }
418 expectedSize += nodeFieldsSize + 8
419 }
420 // Delete the keys one-by-one while checking several of the treap functions work as expected.
421 for i := 0; i < numItems; i++ {
422 treapSnap := testTreap
423 key := serializeUint32(uint32(i))
424 testTreap = testTreap.Delete(key)
425 // Ensure the length of the treap snapshot is the expected value.
426 if gotLen := treapSnap.Len(); gotLen != numItems-i {
427 t.Fatalf("Len #%d: unexpected length - got %d, want %d",
428 i, gotLen, numItems-i,
429 )
430 }
431 // Ensure the treap snapshot still has the key.
432 if !treapSnap.Has(key) {
433 t.Fatalf("Has #%d: key %q is not in treap", i, key)
434 }
435 // Get the key from the treap snapshot and ensure it is still the expected value.
436 if gotVal := treapSnap.Get(key); !bytes.Equal(gotVal, key) {
437 t.Fatalf("Get #%d: unexpected value - got %x, want %x",
438 i, gotVal, key,
439 )
440 }
441 // Ensure the expected size is reported.
442 if gotSize := treapSnap.Size(); gotSize != expectedSize {
443 t.Fatalf("Size #%d: unexpected byte size - got %d, "+
444 "want %d", i, gotSize, expectedSize,
445 )
446 }
447 expectedSize -= nodeFieldsSize + 8
448 }
449 }
450