tree_test.gno

  1package avl
  2
  3import "testing"
  4
  5func TestNewTree(t *testing.T) {
  6	tree := NewTree()
  7	if tree.node != nil {
  8		t.Error("Expected tree.node to be nil")
  9	}
 10}
 11
 12func TestTreeSize(t *testing.T) {
 13	tree := NewTree()
 14	if tree.Size() != 0 {
 15		t.Error("Expected empty tree size to be 0")
 16	}
 17
 18	tree.Set("key1", "value1")
 19	tree.Set("key2", "value2")
 20	if tree.Size() != 2 {
 21		t.Error("Expected tree size to be 2")
 22	}
 23}
 24
 25func TestTreeHas(t *testing.T) {
 26	tree := NewTree()
 27	tree.Set("key1", "value1")
 28
 29	if !tree.Has("key1") {
 30		t.Error("Expected tree to have key1")
 31	}
 32
 33	if tree.Has("key2") {
 34		t.Error("Expected tree to not have key2")
 35	}
 36}
 37
 38func TestTreeGet(t *testing.T) {
 39	tree := NewTree()
 40	tree.Set("key1", "value1")
 41
 42	value, exists := tree.Get("key1")
 43	if !exists || value != "value1" {
 44		t.Error("Expected Get to return value1 and true")
 45	}
 46
 47	_, exists = tree.Get("key2")
 48	if exists {
 49		t.Error("Expected Get to return false for non-existent key")
 50	}
 51}
 52
 53func TestTreeGetByIndex(t *testing.T) {
 54	tree := NewTree()
 55	tree.Set("key1", "value1")
 56	tree.Set("key2", "value2")
 57
 58	key, value := tree.GetByIndex(0)
 59	if key != "key1" || value != "value1" {
 60		t.Error("Expected GetByIndex(0) to return key1 and value1")
 61	}
 62
 63	key, value = tree.GetByIndex(1)
 64	if key != "key2" || value != "value2" {
 65		t.Error("Expected GetByIndex(1) to return key2 and value2")
 66	}
 67
 68	defer func() {
 69		if r := recover(); r == nil {
 70			t.Error("Expected GetByIndex to panic for out-of-range index")
 71		}
 72	}()
 73	tree.GetByIndex(2)
 74}
 75
 76func TestTreeRemove(t *testing.T) {
 77	tree := NewTree()
 78	tree.Set("key1", "value1")
 79
 80	value, removed := tree.Remove("key1")
 81	if !removed || value != "value1" || tree.Size() != 0 {
 82		t.Error("Expected Remove to remove key-value pair")
 83	}
 84
 85	_, removed = tree.Remove("key2")
 86	if removed {
 87		t.Error("Expected Remove to return false for non-existent key")
 88	}
 89}
 90
 91func TestTreeIterate(t *testing.T) {
 92	tree := NewTree()
 93	tree.Set("key1", "value1")
 94	tree.Set("key2", "value2")
 95	tree.Set("key3", "value3")
 96
 97	var keys []string
 98	tree.Iterate("", "", func(key string, value any) bool {
 99		keys = append(keys, key)
100		return false
101	})
102
103	expectedKeys := []string{"key1", "key2", "key3"}
104	if !slicesEqual(keys, expectedKeys) {
105		t.Errorf("Expected keys %v, got %v", expectedKeys, keys)
106	}
107}
108
109func TestTreeReverseIterate(t *testing.T) {
110	tree := NewTree()
111	tree.Set("key1", "value1")
112	tree.Set("key2", "value2")
113	tree.Set("key3", "value3")
114
115	var keys []string
116	tree.ReverseIterate("", "", func(key string, value any) bool {
117		keys = append(keys, key)
118		return false
119	})
120
121	expectedKeys := []string{"key3", "key2", "key1"}
122	if !slicesEqual(keys, expectedKeys) {
123		t.Errorf("Expected keys %v, got %v", expectedKeys, keys)
124	}
125}
126
127func TestTreeIterateByOffset(t *testing.T) {
128	tree := NewTree()
129	tree.Set("key1", "value1")
130	tree.Set("key2", "value2")
131	tree.Set("key3", "value3")
132
133	var keys []string
134	tree.IterateByOffset(1, 2, func(key string, value any) bool {
135		keys = append(keys, key)
136		return false
137	})
138
139	expectedKeys := []string{"key2", "key3"}
140	if !slicesEqual(keys, expectedKeys) {
141		t.Errorf("Expected keys %v, got %v", expectedKeys, keys)
142	}
143}
144
145func TestTreeReverseIterateByOffset(t *testing.T) {
146	tree := NewTree()
147	tree.Set("key1", "value1")
148	tree.Set("key2", "value2")
149	tree.Set("key3", "value3")
150
151	var keys []string
152	tree.ReverseIterateByOffset(1, 2, func(key string, value any) bool {
153		keys = append(keys, key)
154		return false
155	})
156
157	expectedKeys := []string{"key2", "key1"}
158	if !slicesEqual(keys, expectedKeys) {
159		t.Errorf("Expected keys %v, got %v", expectedKeys, keys)
160	}
161}
162
163func TestTreeReverseIterateByOffsetVaried(t *testing.T) {
164	tree := NewTree()
165	tree.Set("a", 1)
166	tree.Set("b", 2)
167	tree.Set("c", 3)
168	tree.Set("d", 4)
169	tree.Set("e", 5)
170
171	// All keys in reverse: e d c b a
172	cases := []struct {
173		offset int
174		limit  int
175		want   []string
176	}{
177		{0, 5, []string{"e", "d", "c", "b", "a"}},
178		{0, 1, []string{"e"}},
179		{0, 3, []string{"e", "d", "c"}},
180		{1, 2, []string{"d", "c"}},
181		{2, 2, []string{"c", "b"}},
182		{3, 5, []string{"b", "a"}},
183		{4, 1, []string{"a"}},
184		{4, 10, []string{"a"}},
185		{5, 1, nil},
186		{0, 0, nil},
187		{10, 1, nil},
188	}
189
190	for _, tc := range cases {
191		var got []string
192		tree.ReverseIterateByOffset(tc.offset, tc.limit, func(key string, value any) bool {
193			got = append(got, key)
194			return false
195		})
196		if !slicesEqual(got, tc.want) {
197			t.Errorf("ReverseIterateByOffset(%d, %d): got %v, want %v",
198				tc.offset, tc.limit, got, tc.want)
199		}
200	}
201
202	// Early termination: stop after 2 items from offset 1.
203	var got []string
204	tree.ReverseIterateByOffset(1, 5, func(key string, value any) bool {
205		got = append(got, key)
206		return len(got) >= 2
207	})
208	want := []string{"d", "c"}
209	if !slicesEqual(got, want) {
210		t.Errorf("ReverseIterateByOffset early stop: got %v, want %v", got, want)
211	}
212}