trie_test.go

     1  // Copyright 2026 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package types2
     6  
     7  import (
     8  	"fmt"
     9  	"testing"
    10  )
    11  
    12  func TestTrie(t *testing.T) {
    13  	strie := make(trie[string])
    14  
    15  	okay := func(index ...int) {
    16  		s := fmt.Sprintf("%x", index)
    17  		if p, n := strie.insert(index, s); n != 0 {
    18  			t.Errorf("%s collided with %s (n = %d)", s, p, n)
    19  		}
    20  	}
    21  
    22  	fail := func(collision string, index ...int) {
    23  		s := fmt.Sprintf("%x", index)
    24  		if p, n := strie.insert(index, s); n == 0 {
    25  			t.Errorf("%s did not collide", s)
    26  		} else if p != collision {
    27  			t.Errorf("%s collided with %s (n == %d), want %s", s, p, n, collision)
    28  		}
    29  	}
    30  
    31  	clear(strie)
    32  	okay(0)
    33  	fail("[0]", 0)
    34  
    35  	clear(strie)
    36  	okay(0)
    37  	fail("[0]", 0, 1, 2, 3, 4, 5)
    38  
    39  	clear(strie)
    40  	okay(1, 2)
    41  	okay(1, 3)
    42  	okay(1, 4, 5)
    43  	okay(1, 4, 2)
    44  	fail("[1 4 2]", 1, 4)
    45  	fail("[1 4 5]", 1, 4, 5)
    46  	okay(1, 4, 3)
    47  	okay(2, 1)
    48  	okay(2, 2)
    49  	fail("[2 2]", 2, 2, 3)
    50  
    51  	clear(strie)
    52  	okay(0, 1, 2, 3, 4, 5)
    53  	okay(0, 1, 2, 3, 4, 6)
    54  	okay(0, 1, 2, 3, 4, 7)
    55  	okay(0, 1, 2, 3, 4, 8, 1)
    56  	okay(0, 1, 2, 3, 4, 4)
    57  	fail("[0 1 2 3 4 4]", 0, 1, 2, 3)
    58  }
    59  
    60  func TestAnyValue(t *testing.T) {
    61  	atrie := make(trie[any]) // allow values of any type
    62  
    63  	val := new(42)
    64  	alt, n := atrie.insert([]int{0}, val)
    65  	if n != 0 {
    66  		t.Errorf("unexpected collision (n = %d)", n)
    67  	}
    68  	if alt != val {
    69  		t.Errorf("unexpected result (alt = %#x, val = %#x)", alt, val)
    70  	}
    71  
    72  	alt, n = atrie.insert([]int{0}, val) // nil is a valid value
    73  	if n == 0 {
    74  		t.Errorf("expected collision")
    75  	}
    76  	if alt != val {
    77  		t.Errorf("unexpected result (alt = %#x, val = %#x)", alt, val)
    78  	}
    79  }
    80
View as plain text