aboutsummaryrefslogtreecommitdiff
path: root/trie_test.go
diff options
context:
space:
mode:
Diffstat (limited to 'trie_test.go')
-rw-r--r--trie_test.go302
1 files changed, 302 insertions, 0 deletions
diff --git a/trie_test.go b/trie_test.go
new file mode 100644
index 0000000..540cf35
--- /dev/null
+++ b/trie_test.go
@@ -0,0 +1,302 @@
+package eventbus
+
+import (
+ "testing"
+)
+
+func TestNodeGetAndRemove(t *testing.T) {
+ root := &node[int]{
+ children: make(map[string]*node[int], defaultCapacity),
+ values: make([]int, 0, defaultCapacity),
+ }
+
+ root.Put([]string{"node1"}, 1)
+ root.Put([]string{"node1", "node1-1"}, 2)
+ root.Put([]string{"node1", "node1-2"}, 3)
+ root.Put([]string{"node1", "node1-2", "node1-2-1"}, 4)
+ root.Put([]string{"node1", "node1-2", "node1-2-2"}, 5)
+ root.Put([]string{"node1", "node1-2", "node1-2-3"}, 6)
+ root.Put([]string{"node1", "node1-2", "node1-2-3", "node1-2-3-1"}, 7)
+
+ // node1(1)
+ // |
+ // +-------+-----+
+ // | |
+ // node1-1(2) node1-2(3)
+ // |
+ // +--+------------+---------------+
+ // | | |
+ // node1-2-1(4) node1-2-2(5) node1-2-3(6)
+ // |
+ // node1-2-3-1(7)
+
+ tests := []struct {
+ prefix []string
+ expected []int
+ remove int
+ }{
+ {
+ prefix: []string{"node1"},
+ expected: []int{1},
+ },
+ {
+ prefix: []string{"node1", "node1-1"},
+ expected: []int{1, 2},
+ },
+ {
+ prefix: []string{"node1", "node1-2"},
+ expected: []int{1, 3},
+ },
+ {
+ prefix: []string{"node1", "node1-2", "node1-2-1"},
+ expected: []int{1, 3, 4},
+ },
+ {
+ prefix: []string{"node1", "node1-2", "node1-2-2"},
+ expected: []int{1, 3, 5},
+ },
+ {
+ prefix: []string{"node1", "node1-2", "node1-2-3"},
+ expected: []int{1, 6},
+ remove: 3,
+ },
+ {
+ prefix: []string{"node1", "node1-2", "node1-2-3", "node1-2-3-1"},
+ expected: []int{1, 7},
+ remove: 6,
+ },
+ {
+ prefix: []string{"node1", "node1-2", "node1-2-3", "node1-2-3-2"},
+ expected: []int{1},
+ },
+ {
+ prefix: []string{"node1", "node1-2", "node1-2-3", "node1-2-3-1"},
+ expected: []int{1},
+ remove: 7,
+ },
+ }
+
+ for _, test := range tests {
+ if test.remove != 0 {
+ root.Remove(test.remove)
+ }
+ result := root.Get(test.prefix, "*")
+ if len(result) != len(test.expected) {
+ t.Errorf("Get(%v) returned %d items, expected %d", test.prefix, len(result), len(test.expected))
+ continue
+ }
+
+ for i, expectedValue := range test.expected {
+ if result[i] != expectedValue {
+ t.Errorf("Get(%v) at index %d: got %d, expected %d", test.prefix, i, result[i], expectedValue)
+ }
+ }
+ }
+}
+
+func TestNodeGetWithWildcard(t *testing.T) {
+ root := &node[int]{
+ children: make(map[string]*node[int], defaultCapacity),
+ values: make([]int, 0, defaultCapacity),
+ }
+
+ root.Put([]string{"node1"}, 1)
+ root.Put([]string{"node1"}, 2)
+ root.Put([]string{"node1", "node1-2"}, 3)
+ root.Put([]string{"node1", "node1-2"}, 4)
+ root.Put([]string{"node1", "node1-2", "node1-2-3"}, 5)
+ root.Put([]string{"node1", "node1-2", "node1-2-3"}, 6)
+ root.Put([]string{"node1", "node1-2", "node1-2-4"}, 7)
+ root.Put([]string{"node1", "node1-2", "node1-2-4"}, 8)
+ root.Put([]string{"node2"}, 9)
+ root.Put([]string{"node2"}, 10)
+ root.Put([]string{"node2", "node2-1"}, 11)
+ root.Put([]string{"node2", "node2-1"}, 12)
+ root.Put([]string{"node2", "node2-1", "node2-1-2"}, 13)
+ root.Put([]string{"node2", "node2-1", "node2-1-2"}, 14)
+ root.Put([]string{"node2", "*"}, 15)
+ root.Put([]string{"node2", "*"}, 16)
+
+ // node1(1,2) node2(9,10)
+ // | |
+ // | +-------+-------+
+ // | | |
+ // node1-2(3,4) *(15,16) node2-1(11,12)
+ // | |
+ // +--------+--------+ node2-1-2(13,14)
+ // | |
+ // node1-2-3(5,6) node1-2-4(7,8)
+
+ tests := []struct {
+ prefix []string
+ expected []int
+ }{
+ {
+ prefix: []string{"node1", "node1-2"},
+ expected: []int{1, 2, 3, 4},
+ },
+ {
+ prefix: []string{"node2", "node2-1"},
+ expected: []int{9, 10, 11, 12, 15, 16},
+ },
+ {
+ prefix: []string{"node1", "node1-2", "node1-2-3"},
+ expected: []int{1, 2, 3, 4, 5, 6},
+ },
+ {
+ prefix: []string{"node2", "node2-1", "node2-1-2"},
+ expected: []int{9, 10, 11, 12, 13, 14, 15, 16},
+ },
+ {
+ prefix: []string{"node2", "*"},
+ expected: []int{9, 10, 15, 16},
+ },
+ }
+
+ for _, test := range tests {
+ result := root.Get(test.prefix, "*")
+ if len(result) != len(test.expected) {
+ t.Errorf("Get(%v) returned %d items, expected %d", test.prefix, len(result), len(test.expected))
+ continue
+ }
+
+ for i, expectedValue := range test.expected {
+ if result[i] != expectedValue {
+ t.Errorf("Get(%v) at index %d: got %d, expected %d", test.prefix, i, result[i], expectedValue)
+ }
+ }
+ }
+}
+
+func TestNodeRemove(t *testing.T) {
+ root := &node[int]{
+ children: make(map[string]*node[int], defaultCapacity),
+ values: make([]int, 0, defaultCapacity),
+ }
+
+ // Добавляем значения в дерево
+ root.Put([]string{"node1"}, 1)
+ root.Put([]string{"node1", "node1-1"}, 2)
+ root.Put([]string{"node1", "node1-2"}, 3)
+ root.Put([]string{"node1", "node1-2", "node1-2-1"}, 4)
+ root.Put([]string{"node1", "node1-2", "node1-2-2"}, 5)
+
+ // node1(1)
+ // |
+ // +-------+-----+
+ // | |
+ // node1-1(2) node1-2(3)
+ // |
+ // +--+------------+
+ // | |
+ // node1-2-1(4) node1-2-2(5)
+
+ // Проверяем начальное состояние
+ result := root.Get([]string{"node1", "node1-2"}, "*")
+ expected := []int{1, 3}
+ if len(result) != len(expected) {
+ t.Errorf("Initial Get returned %d items, expected %d", len(result), len(expected))
+ }
+ for i, v := range expected {
+ if result[i] != v {
+ t.Errorf("Initial Get at index %d: got %d, expected %d", i, result[i], v)
+ }
+ }
+
+ // Удаляем значение 3
+ root.Remove(3)
+
+ // Проверяем, что значение 3 удалено из узла node1-2
+ result = root.Get([]string{"node1", "node1-2"}, "*")
+ expected = []int{1}
+ if len(result) != len(expected) {
+ t.Errorf("After Remove(3) Get returned %d items, expected %d", len(result), len(expected))
+ }
+ for i, v := range expected {
+ if result[i] != v {
+ t.Errorf("After Remove(3) Get at index %d: got %d, expected %d", i, result[i], v)
+ }
+ }
+
+ // Проверяем, что дочерние узлы node1-2-1 и node1-2-2 все еще доступны через node1
+ result = root.Get([]string{"node1", "node1-2", "node1-2-1"}, "*")
+ expected = []int{1, 4}
+ if len(result) != len(expected) {
+ t.Errorf("After Remove(3) Get node1-2-1 returned %d items, expected %d", len(result), len(expected))
+ }
+ for i, v := range expected {
+ if result[i] != v {
+ t.Errorf("After Remove(3) Get node1-2-1 at index %d: got %d, expected %d", i, result[i], v)
+ }
+ }
+}
+
+func TestNodeClear(t *testing.T) {
+ root := &node[int]{
+ children: make(map[string]*node[int], defaultCapacity),
+ values: make([]int, 0, defaultCapacity),
+ }
+
+ // Добавляем значения в дерево
+ root.Put([]string{"node1"}, 1)
+ root.Put([]string{"node1", "node1-1"}, 2)
+ root.Put([]string{"node1", "node1-2"}, 3)
+ root.Put([]string{"node1", "node1-2", "node1-2-1"}, 4)
+ root.Put([]string{"node1", "node1-2", "node1-2-2"}, 5)
+
+ // node1(1)
+ // |
+ // +-------+-----+
+ // | |
+ // node1-1(2) node1-2(3)
+ // |
+ // +--+------------+
+ // | |
+ // node1-2-1(4) node1-2-2(5)
+
+ // Проверяем начальное состояние
+ result := root.Get([]string{"node1", "node1-2"}, "*")
+ expected := []int{1, 3}
+ if len(result) != len(expected) {
+ t.Errorf("Initial Get returned %d items, expected %d", len(result), len(expected))
+ }
+ for i, v := range expected {
+ if result[i] != v {
+ t.Errorf("Initial Get at index %d: got %d, expected %d", i, result[i], v)
+ }
+ }
+
+ // Создаем счетчик для проверки вызова remover
+ removedValues := make([]int, 0)
+
+ // Очищаем дерево
+ root.Clear(func(value int) {
+ removedValues = append(removedValues, value)
+ })
+
+ // Проверяем, что все значения были переданы в remover
+ // Так как порядок обхода может быть произвольным, проверяем только содержимое
+ if len(removedValues) != 5 {
+ t.Errorf("Clear remover called %d times, expected 5", len(removedValues))
+ }
+
+ // Проверяем, что все значения присутствуют
+ expectedValues := map[int]bool{1: true, 2: true, 3: true, 4: true, 5: true}
+ for _, v := range removedValues {
+ if !expectedValues[v] {
+ t.Errorf("Clear remover received unexpected value: %d", v)
+ }
+ delete(expectedValues, v)
+ }
+
+ // Проверяем, что все ожидаемые значения были получены
+ if len(expectedValues) > 0 {
+ t.Errorf("Not all expected values were passed to remover: %v", expectedValues)
+ }
+
+ // Проверяем, что дерево пустое
+ result = root.Get([]string{"node1", "node1-2"}, "*")
+ if len(result) != 0 {
+ t.Errorf("After Clear Get returned %d items, expected 0", len(result))
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2026-03-23 02:14:03 +0000