v1.0.0v1.0.0

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))
+	}
+}