byteinterval/tree_test.go at main · logbn/byteinterval · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
package byteinterval

import (
	"testing"

	"github.com/stretchr/testify/assert"
	"github.com/stretchr/testify/require"
)

func TestTree(t *testing.T) {
	tr := New[int]()
	t.Run("insert", func(t *testing.T) {
		tr.Insert([]byte(`100`), []byte(`200`), 1)
		tr.Insert([]byte(`200`), []byte(`300`), 2)
		tr.Insert([]byte(`300`), []byte(`400`), 3)
		tr.Insert([]byte(`400`), []byte(`500`), 4)
		tr.Insert([]byte(`900`), []byte(`900`), 90)
		tr.Insert([]byte(`901`), nil, 91)
		less := tr.Insert([]byte(`300`), []byte(`200`), 400)
		assert.Nil(t, less)
	})
	c := tr.Insert([]byte(`350`), []byte(`600`), 11)
	d := tr.Insert([]byte(`010`), []byte(`100`), 11)
	e := tr.Insert([]byte(`020`), []byte(`100`), 11)
	f := tr.Insert([]byte(`700`), []byte(`800`), 7)
	g := tr.Insert([]byte(`701`), []byte(`799`), 8)
	h := tr.Insert([]byte(`702`), []byte(`798`), 9)
	t.Run("find", func(t *testing.T) {
		vals := tr.Find([]byte(`001`))
		require.Len(t, vals, 0)
		vals = tr.Find([]byte(`100`))
		require.Len(t, vals, 1)
		assert.Equal(t, vals[0], 1)
		vals = tr.Find([]byte(`101`))
		require.Len(t, vals, 1)
		assert.Equal(t, vals[0], 1)
		vals = tr.Find([]byte(`200`))
		require.Len(t, vals, 1)
		assert.Equal(t, vals[0], 2)
		vals = tr.Find([]byte(`350`))
		require.Len(t, vals, 2)
		for _, v := range vals {
			assert.True(t, v == 3 || v == 11)
		}
		vals = tr.Find([]byte(`500`))
		require.Len(t, vals, 1)
		assert.Equal(t, vals[0], 11)
		vals = tr.Find([]byte(`600`))
		require.Len(t, vals, 0)
		vals = tr.Find([]byte(`900`))
		require.Len(t, vals, 1)
		require.Equal(t, vals, []int{90})
		vals = tr.Find([]byte(`901`))
		require.Len(t, vals, 1)
		require.Equal(t, vals, []int{91})
	})
	t.Run("remove", func(t *testing.T) {
		t.Run("once", func(t *testing.T) {
			vals := tr.Find([]byte(`700`))
			require.Len(t, vals, 1)
			vals = tr.Find([]byte(`701`))
			require.Len(t, vals, 2)
			vals = tr.Find([]byte(`702`))
			require.Len(t, vals, 3)
			h.Remove()
			vals = tr.Find([]byte(`702`))
			require.Len(t, vals, 2)
			g.Remove()
			vals = tr.Find([]byte(`702`))
			require.Len(t, vals, 1)
			f.Remove()
			vals = tr.Find([]byte(`702`))
			require.Len(t, vals, 0)
			c.Remove()
			vals = tr.Find([]byte(`350`))
			require.Len(t, vals, 1)
			assert.Equal(t, vals[0], 3)
			vals = tr.Find([]byte(`450`))
			require.Len(t, vals, 1)
			assert.Equal(t, vals[0], 4)
			vals = tr.Find([]byte(`550`))
			require.Len(t, vals, 0)
			vals = tr.Find([]byte(`650`))
			require.Len(t, vals, 0)
			vals = tr.Find([]byte(`000`))
			require.Len(t, vals, 0)
			d.Remove()
			vals = tr.Find([]byte(`010`))
			require.Len(t, vals, 0)
			vals = tr.Find([]byte(`100`))
			require.Len(t, vals, 1)
			vals = tr.Find([]byte(`020`))
			require.Len(t, vals, 1)
			e.Remove()
			vals = tr.Find([]byte(`020`))
			require.Len(t, vals, 0)
			vals = tr.Find([]byte(`100`))
			require.Len(t, vals, 1)
		})
		t.Run("twice", func(t *testing.T) {
			e.Remove()
			d.rem = false
			d.Remove()
		})
		t.Run("duplicate", func(t *testing.T) {
			i := tr.Insert([]byte(`801`), []byte(`802`), 1)
			tr.Insert([]byte(`801`), []byte(`802`), 2)
			i.Remove()
			vals := tr.Find([]byte(`801`))
			require.Len(t, vals, 1)
		})

	})
	t.Run("findAny", func(t *testing.T) {
		vals := tr.FindAny([]byte(`101`), []byte(`102`), []byte(`103`))
		require.Len(t, vals, 1)
		assert.Equal(t, vals[0], 1)
		vals = tr.FindAny([]byte(`100`), []byte(`200`), []byte(`300`))
		require.Len(t, vals, 3)
		vals = tr.FindAny([]byte(`000`), []byte(`100`))
		require.Len(t, vals, 1)
		vals = tr.FindAny([]byte(`000`), []byte(`001`), []byte(`002`))
		require.Len(t, vals, 0)
		vals = tr.FindAny([]byte(`999`))
		require.Len(t, vals, 0)
	})
}

func TestReadme(t *testing.T) {
	tree := New[int]()
	tree.Insert([]byte(`alpha`), []byte(`bravo`), 100)
	tree.Insert([]byte(`bravo`), []byte(`charlie`), 200)
	c := tree.Insert([]byte(`bravo`), []byte(`delta`), 300)

	items := tree.Find([]byte(`bravo`))
	require.Equal(t, items, []int{200, 300})

	items = tree.Find([]byte(`charlie`))
	require.Equal(t, items, []int{300})

	items = tree.FindAny([]byte(`alpha`), []byte(`bravo`), []byte(`charlie`))
	require.Equal(t, items, []int{100, 200, 300})

	c.Remove()

	items = tree.Find([]byte(`bravo`))
	require.Equal(t, items, []int{200})

	items = tree.Find([]byte(`charlie`))
	require.Equal(t, items, []int(nil))
}