deque_test.gno

  1package deque
  2
  3import "testing"
  4
  5func TestNew(t *testing.T) {
  6	d := New()
  7	if d.Size() != 0 {
  8		t.Errorf("Expected size 0, got %d", d.Size())
  9	}
 10	if d.MaxSize() != 0 {
 11		t.Errorf("Expected max size 0 (unlimited), got %d", d.MaxSize())
 12	}
 13	if d.IsBounded() {
 14		t.Error("Expected unbounded deque")
 15	}
 16}
 17
 18func TestNewBounded(t *testing.T) {
 19	d := NewBounded(5)
 20	if d.MaxSize() != 5 {
 21		t.Errorf("Expected max size 5, got %d", d.MaxSize())
 22	}
 23	if d.Size() != 0 {
 24		t.Errorf("Expected size 0, got %d", d.Size())
 25	}
 26	if !d.IsBounded() {
 27		t.Error("Expected bounded deque")
 28	}
 29}
 30
 31func TestPushBackPopFront(t *testing.T) {
 32	d := New() // unbounded
 33
 34	// Test empty pop
 35	if d.PopFront() != nil {
 36		t.Error("Expected nil when popping from empty deque")
 37	}
 38
 39	d.PushBack("a", "b", "c")
 40	if d.Size() != 3 {
 41		t.Errorf("Expected size 3, got %d", d.Size())
 42	}
 43
 44	item := d.PopFront()
 45	if item != "a" {
 46		t.Errorf("Expected 'a', got %v", item)
 47	}
 48	if d.Size() != 2 {
 49		t.Errorf("Expected size 2, got %d", d.Size())
 50	}
 51}
 52
 53func TestPushFrontPopBack(t *testing.T) {
 54	d := New() // unbounded
 55
 56	d.PushFront("a", "b", "c")
 57	if d.Size() != 3 {
 58		t.Errorf("Expected size 3, got %d", d.Size())
 59	}
 60
 61	// Elements should be in reverse order: [c, b, a]
 62	if d.First() != "c" {
 63		t.Errorf("Expected 'c' as first, got %v", d.First())
 64	}
 65	if d.Last() != "a" {
 66		t.Errorf("Expected 'a' as last, got %v", d.Last())
 67	}
 68
 69	item := d.PopBack()
 70	if item != "a" {
 71		t.Errorf("Expected 'a', got %v", item)
 72	}
 73	if d.Size() != 2 {
 74		t.Errorf("Expected size 2, got %d", d.Size())
 75	}
 76}
 77
 78func TestBoundedEvictionBack(t *testing.T) {
 79	d := NewBounded(3)
 80
 81	// Fill to capacity
 82	d.PushBack("a", "b", "c")
 83	if d.Size() != 3 {
 84		t.Errorf("Expected size 3, got %d", d.Size())
 85	}
 86
 87	// Push beyond capacity - should evict "a" from front
 88	d.PushBack("d")
 89	if d.Size() != 3 {
 90		t.Errorf("Expected size 3, got %d", d.Size())
 91	}
 92	if d.First() != "b" {
 93		t.Errorf("Expected 'b' (oldest after eviction), got %v", d.First())
 94	}
 95	if d.Last() != "d" {
 96		t.Errorf("Expected 'd' (newest), got %v", d.Last())
 97	}
 98}
 99
100func TestBoundedEvictionFront(t *testing.T) {
101	d := NewBounded(3)
102
103	// Fill to capacity
104	d.PushBack("a", "b", "c")
105
106	// Push to front beyond capacity - should evict "c" from back
107	d.PushFront("x")
108	if d.Size() != 3 {
109		t.Errorf("Expected size 3, got %d", d.Size())
110	}
111	if d.First() != "x" {
112		t.Errorf("Expected 'x' (newest at front), got %v", d.First())
113	}
114	if d.Last() != "b" {
115		t.Errorf("Expected 'b' (oldest after back eviction), got %v", d.Last())
116	}
117}
118
119func TestFirstLast(t *testing.T) {
120	d := New()
121
122	// Empty deque
123	if d.First() != nil {
124		t.Error("Expected nil for empty deque first")
125	}
126	if d.Last() != nil {
127		t.Error("Expected nil for empty deque last")
128	}
129
130	d.PushBack("x", "y", "z")
131	if d.First() != "x" {
132		t.Errorf("Expected 'x', got %v", d.First())
133	}
134	if d.Last() != "z" {
135		t.Errorf("Expected 'z', got %v", d.Last())
136	}
137}
138
139func TestGet(t *testing.T) {
140	d := New()
141	d.PushBack("a", "b", "c")
142
143	if d.Get(0) != "a" {
144		t.Errorf("Expected 'a' at index 0, got %v", d.Get(0))
145	}
146	if d.Get(1) != "b" {
147		t.Errorf("Expected 'b' at index 1, got %v", d.Get(1))
148	}
149	if d.Get(2) != "c" {
150		t.Errorf("Expected 'c' at index 2, got %v", d.Get(2))
151	}
152	if d.Get(3) != nil {
153		t.Error("Expected nil for out-of-bounds index")
154	}
155	if d.Get(-1) != nil {
156		t.Error("Expected nil for negative index")
157	}
158}
159
160func TestList(t *testing.T) {
161	d := New()
162
163	// Empty deque
164	list := d.List()
165	if list != nil {
166		t.Errorf("Expected nil for empty deque, got %v", list)
167	}
168
169	d.PushBack("x", "y", "z")
170	list = d.List()
171	if len(list) != 3 {
172		t.Errorf("Expected length 3, got %d", len(list))
173	}
174	if list[0] != "x" || list[1] != "y" || list[2] != "z" {
175		t.Errorf("Expected [x, y, z], got %v", list)
176	}
177}
178
179func TestEnumerate(t *testing.T) {
180	d := New()
181	d.PushBack("a", "b", "c")
182
183	var enumerated []string
184	var indices []int
185
186	d.Enumerate(func(index int, item any) bool {
187		indices = append(indices, index)
188		enumerated = append(enumerated, item.(string))
189		return false // continue
190	})
191
192	if len(enumerated) != 3 {
193		t.Errorf("Expected 3 enumerated items, got %d", len(enumerated))
194	}
195	if enumerated[0] != "a" || enumerated[1] != "b" || enumerated[2] != "c" {
196		t.Errorf("Expected [a, b, c], got %v", enumerated)
197	}
198	if indices[0] != 0 || indices[1] != 1 || indices[2] != 2 {
199		t.Errorf("Expected [0, 1, 2], got %v", indices)
200	}
201}
202
203func TestEnumerateEarlyStop(t *testing.T) {
204	d := New()
205	d.PushBack("a", "b", "c")
206
207	var enumerated []string
208
209	d.Enumerate(func(index int, item any) bool {
210		enumerated = append(enumerated, item.(string))
211		return item == "b" // stop after b
212	})
213
214	if len(enumerated) != 2 {
215		t.Errorf("Expected 2 enumerated items, got %d", len(enumerated))
216	}
217	if enumerated[0] != "a" || enumerated[1] != "b" {
218		t.Errorf("Expected [a, b], got %v", enumerated)
219	}
220}
221
222func TestSetMaxSize(t *testing.T) {
223	d := New()
224	d.PushBack("a", "b", "c", "d", "e")
225
226	// Reduce max size - should trim from front
227	d.SetMaxSize(3)
228	if d.Size() != 3 {
229		t.Errorf("Expected size 3 after reducing max size, got %d", d.Size())
230	}
231	if d.First() != "c" {
232		t.Errorf("Expected 'c' as first after trim, got %v", d.First())
233	}
234
235	// Increase max size
236	d.SetMaxSize(10)
237	if d.MaxSize() != 10 {
238		t.Errorf("Expected max size 10, got %d", d.MaxSize())
239	}
240}
241
242func TestClear(t *testing.T) {
243	d := New()
244	d.PushBack("a", "b", "c")
245
246	d.Clear()
247
248	if d.Size() != 0 {
249		t.Errorf("Expected size 0 after clear, got %d", d.Size())
250	}
251	if d.First() != nil {
252		t.Error("Expected nil first after clear")
253	}
254	if d.Last() != nil {
255		t.Error("Expected nil last after clear")
256	}
257	if !d.IsEmpty() {
258		t.Error("Expected deque to be empty after clear")
259	}
260}
261
262func TestUnboundedGrowth(t *testing.T) {
263	d := New() // unbounded
264
265	// Add many items
266	for i := 0; i < 100; i++ {
267		d.PushBack(i)
268	}
269
270	if d.Size() != 100 {
271		t.Errorf("Expected size 100, got %d", d.Size())
272	}
273	if d.First() != 0 {
274		t.Errorf("Expected 0 as first, got %v", d.First())
275	}
276	if d.Last() != 99 {
277		t.Errorf("Expected 99 as last, got %v", d.Last())
278	}
279}
280
281func TestMixedOperations(t *testing.T) {
282	d := NewBounded(4)
283
284	// Test mixed push front and back operations
285	d.PushBack("b", "c")
286	d.PushFront("a")
287	d.PushBack("d")
288
289	// Should have [a, b, c, d]
290	list := d.List()
291	if len(list) != 4 || list[0] != "a" || list[1] != "b" || list[2] != "c" || list[3] != "d" {
292		t.Errorf("Expected [a, b, c, d], got %v", list)
293	}
294
295	// Push beyond capacity
296	d.PushFront("x") // Should evict "d" from back
297
298	// Should have [x, a, b, c]
299	list = d.List()
300	if len(list) != 4 || list[0] != "x" || list[1] != "a" || list[2] != "b" || list[3] != "c" {
301		t.Errorf("Expected [x, a, b, c], got %v", list)
302	}
303
304	// Mixed pop operations
305	front := d.PopFront() // "x"
306	back := d.PopBack()   // "c"
307
308	if front != "x" {
309		t.Errorf("Expected 'x' from front, got %v", front)
310	}
311	if back != "c" {
312		t.Errorf("Expected 'c' from back, got %v", back)
313	}
314
315	// Should have [a, b]
316	list = d.List()
317	if len(list) != 2 || list[0] != "a" || list[1] != "b" {
318		t.Errorf("Expected [a, b], got %v", list)
319	}
320}
321
322func TestAllIterator(t *testing.T) {
323	d := New()
324	d.PushBack("x", "y", "z")
325
326	var items []any
327	iter := d.All()
328	iter(func(value any) bool {
329		items = append(items, value)
330		return true // continue
331	})
332
333	if len(items) != 3 {
334		t.Errorf("Expected 3 items, got %d", len(items))
335	}
336	if items[0] != "x" || items[1] != "y" || items[2] != "z" {
337		t.Errorf("Expected [x, y, z], got %v", items)
338	}
339}
340
341func TestBackwardIterator(t *testing.T) {
342	d := New()
343	d.PushBack("x", "y", "z")
344
345	var items []any
346	iter := d.Backward()
347	iter(func(value any) bool {
348		items = append(items, value)
349		return true // continue
350	})
351
352	if len(items) != 3 {
353		t.Errorf("Expected 3 items, got %d", len(items))
354	}
355	if items[0] != "z" || items[1] != "y" || items[2] != "x" {
356		t.Errorf("Expected [z, y, x] (reverse), got %v", items)
357	}
358}
359
360func TestAllIteratorEarlyBreak(t *testing.T) {
361	d := New()
362	d.PushBack("a", "b", "c", "d", "e")
363
364	var items []any
365	iter := d.All()
366	iter(func(value any) bool {
367		items = append(items, value)
368		if value == "c" {
369			return false // stop
370		}
371		return true // continue
372	})
373
374	if len(items) != 3 {
375		t.Errorf("Expected 3 items after break, got %d", len(items))
376	}
377	if items[0] != "a" || items[1] != "b" || items[2] != "c" {
378		t.Errorf("Expected [a, b, c], got %v", items)
379	}
380}