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.
9 func 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)
17 func checkListPointers(t
*testing
.T
, l
*List
, es
[]*Element
) {
20 if !checkListLen(t
, l
, len(es
)) {
24 // zero length lists must be the zero value or properly initialized (sentinel circle)
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
)
33 // check internal and external prev/next connections
34 for i
, e
:= range es
{
36 Prev
:= (*Element
)(nil)
41 if p
:= e
.prev
; p
!= prev
{
42 t
.Errorf("elt[%d](%p).prev = %p, want %p", i
, e
, p
, prev
)
44 if p
:= e
.Prev(); p
!= Prev
{
45 t
.Errorf("elt[%d](%p).Prev() = %p, want %p", i
, e
, p
, Prev
)
49 Next
:= (*Element
)(nil)
54 if n
:= e
.next
; n
!= next
{
55 t
.Errorf("elt[%d](%p).next = %p, want %p", i
, e
, n
, next
)
57 if n
:= e
.Next(); n
!= Next
{
58 t
.Errorf("elt[%d](%p).Next() = %p, want %p", i
, e
, n
, Next
)
63 func TestList(t
*testing
.T
) {
65 checkListPointers(t
, l
, []*Element
{})
67 // Single element list
69 checkListPointers(t
, l
, []*Element
{e
})
71 checkListPointers(t
, l
, []*Element
{e
})
73 checkListPointers(t
, l
, []*Element
{e
})
75 checkListPointers(t
, l
, []*Element
{})
81 e4
:= l
.PushBack("banana")
82 checkListPointers(t
, l
, []*Element
{e1
, e2
, e3
, e4
})
85 checkListPointers(t
, l
, []*Element
{e1
, e3
, e4
})
87 l
.MoveToFront(e3
) // move from middle
88 checkListPointers(t
, l
, []*Element
{e3
, e1
, e4
})
91 l
.MoveToBack(e3
) // move from middle
92 checkListPointers(t
, l
, []*Element
{e1
, e4
, e3
})
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
})
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
})
104 e2
= l
.InsertBefore(2, e1
) // insert before front
105 checkListPointers(t
, l
, []*Element
{e2
, e1
, e4
, e3
})
107 e2
= l
.InsertBefore(2, e4
) // insert before middle
108 checkListPointers(t
, l
, []*Element
{e1
, e2
, e4
, e3
})
110 e2
= l
.InsertBefore(2, e3
) // insert before back
111 checkListPointers(t
, l
, []*Element
{e1
, e4
, e2
, e3
})
114 e2
= l
.InsertAfter(2, e1
) // insert after front
115 checkListPointers(t
, l
, []*Element
{e1
, e2
, e4
, e3
})
117 e2
= l
.InsertAfter(2, e4
) // insert after middle
118 checkListPointers(t
, l
, []*Element
{e1
, e4
, e2
, e3
})
120 e2
= l
.InsertAfter(2, e3
) // insert after back
121 checkListPointers(t
, l
, []*Element
{e1
, e4
, e3
, e2
})
124 // Check standard iteration.
126 for e
:= l
.Front(); e
!= nil; e
= e
.Next() {
127 if i
, ok
:= e
.Value
.(int); ok
{
132 t
.Errorf("sum over l = %d, want 4", sum
)
135 // Clear all elements by iterating
137 for e
:= l
.Front(); e
!= nil; e
= next
{
141 checkListPointers(t
, l
, []*Element
{})
144 func checkList(t
*testing
.T
, l
*List
, es
[]interface{}) {
145 if !checkListLen(t
, l
, len(es
)) {
150 for e
:= l
.Front(); e
!= nil; e
= e
.Next() {
153 t
.Errorf("elt[%d].Value = %v, want %v", i
, le
, es
[i
])
159 func TestExtending(t
*testing
.T
) {
172 checkList(t
, l3
, []interface{}{1, 2, 3})
174 checkList(t
, l3
, []interface{}{1, 2, 3, 4, 5})
178 checkList(t
, l3
, []interface{}{4, 5})
180 checkList(t
, l3
, []interface{}{1, 2, 3, 4, 5})
182 checkList(t
, l1
, []interface{}{1, 2, 3})
183 checkList(t
, l2
, []interface{}{4, 5})
187 checkList(t
, l3
, []interface{}{1, 2, 3})
189 checkList(t
, l3
, []interface{}{1, 2, 3, 1, 2, 3})
193 checkList(t
, l3
, []interface{}{1, 2, 3})
195 checkList(t
, l3
, []interface{}{1, 2, 3, 1, 2, 3})
199 checkList(t
, l1
, []interface{}{1, 2, 3})
201 checkList(t
, l1
, []interface{}{1, 2, 3})
204 func TestRemove(t
*testing
.T
) {
208 checkListPointers(t
, l
, []*Element
{e1
, e2
})
211 checkListPointers(t
, l
, []*Element
{e2
})
213 checkListPointers(t
, l
, []*Element
{e2
})
216 func TestIssue4103(t
*testing
.T
) {
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
)
231 l1
.InsertBefore(8, e
)
232 if n
:= l1
.Len(); n
!= 3 {
233 t
.Errorf("l1.Len() = %d, want 3", n
)
237 func TestIssue6349(t
*testing
.T
) {
245 t
.Errorf("e.value = %d, want 1", e
.Value
)
248 t
.Errorf("e.Next() != nil")
251 t
.Errorf("e.Prev() != nil")
255 func TestMove(t
*testing
.T
) {
263 checkListPointers(t
, l
, []*Element
{e1
, e2
, e3
, e4
})
265 checkListPointers(t
, l
, []*Element
{e1
, e2
, e3
, e4
})
268 checkListPointers(t
, l
, []*Element
{e1
, e2
, e3
, e4
})
270 checkListPointers(t
, l
, []*Element
{e1
, e2
, e3
, e4
})
273 checkListPointers(t
, l
, []*Element
{e1
, e3
, e2
, e4
})
277 checkListPointers(t
, l
, []*Element
{e4
, e1
, e2
, e3
})
278 e1
, e2
, e3
, e4
= e4
, e1
, e2
, e3
281 checkListPointers(t
, l
, []*Element
{e1
, e4
, e2
, e3
})
282 e2
, e3
, e4
= e4
, e2
, e3
285 checkListPointers(t
, l
, []*Element
{e1
, e3
, e2
, e4
})
289 // Test PushFront, PushBack, PushFrontList, PushBackList with uninitialized List
290 func TestZeroList(t
*testing
.T
) {
293 checkList(t
, l1
, []interface{}{1})
297 checkList(t
, l2
, []interface{}{1})
301 checkList(t
, l3
, []interface{}{1})
305 checkList(t
, l4
, []interface{}{1})
308 // Test that a list l is not modified when calling InsertBefore with a mark that is not an element of l.
309 func TestInsertBeforeUnknownMark(t
*testing
.T
) {
314 l
.InsertBefore(1, new(Element
))
315 checkList(t
, &l
, []interface{}{1, 2, 3})
318 // Test that a list l is not modified when calling InsertAfter with a mark that is not an element of l.
319 func TestInsertAfterUnknownMark(t
*testing
.T
) {
324 l
.InsertAfter(1, new(Element
))
325 checkList(t
, &l
, []interface{}{1, 2, 3})
328 // Test that a list l is not modified when calling MoveAfter or MoveBefore with a mark that is not an element of l.
329 func TestMoveUnknownMark(t
*testing
.T
) {
337 checkList(t
, &l1
, []interface{}{1})
338 checkList(t
, &l2
, []interface{}{2})
340 l1
.MoveBefore(e1
, e2
)
341 checkList(t
, &l1
, []interface{}{1})
342 checkList(t
, &l2
, []interface{}{2})