1// Copyright 2009 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package list
6
7import "testing"
8
9func checkListLen(t *testing.T, l *List, len int) bool {
10	if n := l.Len(); n != len {
11		t.Errorf("l.Len() = %d, want %d", n, len)
12		return false
13	}
14	return true
15}
16
17func checkListPointers(t *testing.T, l *List, es []*Element) {
18	root := &l.root
19
20	if !checkListLen(t, l, len(es)) {
21		return
22	}
23
24	// zero length lists must be the zero value or properly initialized (sentinel circle)
25	if len(es) == 0 {
26		if l.root.next != nil && l.root.next != root || l.root.prev != nil && l.root.prev != root {
27			t.Errorf("l.root.next = %p, l.root.prev = %p; both should both be nil or %p", l.root.next, l.root.prev, root)
28		}
29		return
30	}
31	// len(es) > 0
32
33	// check internal and external prev/next connections
34	for i, e := range es {
35		prev := root
36		Prev := (*Element)(nil)
37		if i > 0 {
38			prev = es[i-1]
39			Prev = prev
40		}
41		if p := e.prev; p != prev {
42			t.Errorf("elt[%d](%p).prev = %p, want %p", i, e, p, prev)
43		}
44		if p := e.Prev(); p != Prev {
45			t.Errorf("elt[%d](%p).Prev() = %p, want %p", i, e, p, Prev)
46		}
47
48		next := root
49		Next := (*Element)(nil)
50		if i < len(es)-1 {
51			next = es[i+1]
52			Next = next
53		}
54		if n := e.next; n != next {
55			t.Errorf("elt[%d](%p).next = %p, want %p", i, e, n, next)
56		}
57		if n := e.Next(); n != Next {
58			t.Errorf("elt[%d](%p).Next() = %p, want %p", i, e, n, Next)
59		}
60	}
61}
62
63func TestList(t *testing.T) {
64	l := New()
65	checkListPointers(t, l, []*Element{})
66
67	// Single element list
68	e := l.PushFront("a")
69	checkListPointers(t, l, []*Element{e})
70	l.MoveToFront(e)
71	checkListPointers(t, l, []*Element{e})
72	l.MoveToBack(e)
73	checkListPointers(t, l, []*Element{e})
74	l.Remove(e)
75	checkListPointers(t, l, []*Element{})
76
77	// Bigger list
78	e2 := l.PushFront(2)
79	e1 := l.PushFront(1)
80	e3 := l.PushBack(3)
81	e4 := l.PushBack("banana")
82	checkListPointers(t, l, []*Element{e1, e2, e3, e4})
83
84	l.Remove(e2)
85	checkListPointers(t, l, []*Element{e1, e3, e4})
86
87	l.MoveToFront(e3) // move from middle
88	checkListPointers(t, l, []*Element{e3, e1, e4})
89
90	l.MoveToFront(e1)
91	l.MoveToBack(e3) // move from middle
92	checkListPointers(t, l, []*Element{e1, e4, e3})
93
94	l.MoveToFront(e3) // move from back
95	checkListPointers(t, l, []*Element{e3, e1, e4})
96	l.MoveToFront(e3) // should be no-op
97	checkListPointers(t, l, []*Element{e3, e1, e4})
98
99	l.MoveToBack(e3) // move from front
100	checkListPointers(t, l, []*Element{e1, e4, e3})
101	l.MoveToBack(e3) // should be no-op
102	checkListPointers(t, l, []*Element{e1, e4, e3})
103
104	e2 = l.InsertBefore(2, e1) // insert before front
105	checkListPointers(t, l, []*Element{e2, e1, e4, e3})
106	l.Remove(e2)
107	e2 = l.InsertBefore(2, e4) // insert before middle
108	checkListPointers(t, l, []*Element{e1, e2, e4, e3})
109	l.Remove(e2)
110	e2 = l.InsertBefore(2, e3) // insert before back
111	checkListPointers(t, l, []*Element{e1, e4, e2, e3})
112	l.Remove(e2)
113
114	e2 = l.InsertAfter(2, e1) // insert after front
115	checkListPointers(t, l, []*Element{e1, e2, e4, e3})
116	l.Remove(e2)
117	e2 = l.InsertAfter(2, e4) // insert after middle
118	checkListPointers(t, l, []*Element{e1, e4, e2, e3})
119	l.Remove(e2)
120	e2 = l.InsertAfter(2, e3) // insert after back
121	checkListPointers(t, l, []*Element{e1, e4, e3, e2})
122	l.Remove(e2)
123
124	// Check standard iteration.
125	sum := 0
126	for e := l.Front(); e != nil; e = e.Next() {
127		if i, ok := e.Value.(int); ok {
128			sum += i
129		}
130	}
131	if sum != 4 {
132		t.Errorf("sum over l = %d, want 4", sum)
133	}
134
135	// Clear all elements by iterating
136	var next *Element
137	for e := l.Front(); e != nil; e = next {
138		next = e.Next()
139		l.Remove(e)
140	}
141	checkListPointers(t, l, []*Element{})
142}
143
144func checkList(t *testing.T, l *List, es []interface{}) {
145	if !checkListLen(t, l, len(es)) {
146		return
147	}
148
149	i := 0
150	for e := l.Front(); e != nil; e = e.Next() {
151		le := e.Value.(int)
152		if le != es[i] {
153			t.Errorf("elt[%d].Value = %v, want %v", i, le, es[i])
154		}
155		i++
156	}
157}
158
159func TestExtending(t *testing.T) {
160	l1 := New()
161	l2 := New()
162
163	l1.PushBack(1)
164	l1.PushBack(2)
165	l1.PushBack(3)
166
167	l2.PushBack(4)
168	l2.PushBack(5)
169
170	l3 := New()
171	l3.PushBackList(l1)
172	checkList(t, l3, []interface{}{1, 2, 3})
173	l3.PushBackList(l2)
174	checkList(t, l3, []interface{}{1, 2, 3, 4, 5})
175
176	l3 = New()
177	l3.PushFrontList(l2)
178	checkList(t, l3, []interface{}{4, 5})
179	l3.PushFrontList(l1)
180	checkList(t, l3, []interface{}{1, 2, 3, 4, 5})
181
182	checkList(t, l1, []interface{}{1, 2, 3})
183	checkList(t, l2, []interface{}{4, 5})
184
185	l3 = New()
186	l3.PushBackList(l1)
187	checkList(t, l3, []interface{}{1, 2, 3})
188	l3.PushBackList(l3)
189	checkList(t, l3, []interface{}{1, 2, 3, 1, 2, 3})
190
191	l3 = New()
192	l3.PushFrontList(l1)
193	checkList(t, l3, []interface{}{1, 2, 3})
194	l3.PushFrontList(l3)
195	checkList(t, l3, []interface{}{1, 2, 3, 1, 2, 3})
196
197	l3 = New()
198	l1.PushBackList(l3)
199	checkList(t, l1, []interface{}{1, 2, 3})
200	l1.PushFrontList(l3)
201	checkList(t, l1, []interface{}{1, 2, 3})
202}
203
204func TestRemove(t *testing.T) {
205	l := New()
206	e1 := l.PushBack(1)
207	e2 := l.PushBack(2)
208	checkListPointers(t, l, []*Element{e1, e2})
209	e := l.Front()
210	l.Remove(e)
211	checkListPointers(t, l, []*Element{e2})
212	l.Remove(e)
213	checkListPointers(t, l, []*Element{e2})
214}
215
216func TestIssue4103(t *testing.T) {
217	l1 := New()
218	l1.PushBack(1)
219	l1.PushBack(2)
220
221	l2 := New()
222	l2.PushBack(3)
223	l2.PushBack(4)
224
225	e := l1.Front()
226	l2.Remove(e) // l2 should not change because e is not an element of l2
227	if n := l2.Len(); n != 2 {
228		t.Errorf("l2.Len() = %d, want 2", n)
229	}
230
231	l1.InsertBefore(8, e)
232	if n := l1.Len(); n != 3 {
233		t.Errorf("l1.Len() = %d, want 3", n)
234	}
235}
236