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 5 package list 6 7 import "testing" 8 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) 12 return false 13 } 14 return true 15 } 16 17 func 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 63 func 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 144 func 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 159 func 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 204 func 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 216 func 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 237 func TestIssue6349(t *testing.T) { 238 l := New() 239 l.PushBack(1) 240 l.PushBack(2) 241 242 e := l.Front() 243 l.Remove(e) 244 if e.Value != 1 { 245 t.Errorf("e.value = %d, want 1", e.Value) 246 } 247 if e.Next() != nil { 248 t.Errorf("e.Next() != nil") 249 } 250 if e.Prev() != nil { 251 t.Errorf("e.Prev() != nil") 252 } 253 } 254 255 func TestMove(t *testing.T) { 256 l := New() 257 e1 := l.PushBack(1) 258 e2 := l.PushBack(2) 259 e3 := l.PushBack(3) 260 e4 := l.PushBack(4) 261 262 l.MoveAfter(e3, e3) 263 checkListPointers(t, l, []*Element{e1, e2, e3, e4}) 264 l.MoveBefore(e2, e2) 265 checkListPointers(t, l, []*Element{e1, e2, e3, e4}) 266 267 l.MoveAfter(e3, e2) 268 checkListPointers(t, l, []*Element{e1, e2, e3, e4}) 269 l.MoveBefore(e2, e3) 270 checkListPointers(t, l, []*Element{e1, e2, e3, e4}) 271 272 l.MoveBefore(e2, e4) 273 checkListPointers(t, l, []*Element{e1, e3, e2, e4}) 274 e1, e2, e3, e4 = e1, e3, e2, e4 275 276 l.MoveBefore(e4, e1) 277 checkListPointers(t, l, []*Element{e4, e1, e2, e3}) 278 e1, e2, e3, e4 = e4, e1, e2, e3 279 280 l.MoveAfter(e4, e1) 281 checkListPointers(t, l, []*Element{e1, e4, e2, e3}) 282 e1, e2, e3, e4 = e1, e4, e2, e3 283 284 l.MoveAfter(e2, e3) 285 checkListPointers(t, l, []*Element{e1, e3, e2, e4}) 286 e1, e2, e3, e4 = e1, e3, e2, e4 287 } 288 289 // Test PushFront, PushBack, PushFrontList, PushBackList with uninitialized List 290 func TestZeroList(t *testing.T) { 291 var l1 = new(List) 292 l1.PushFront(1) 293 checkList(t, l1, []interface{}{1}) 294 295 var l2 = new(List) 296 l2.PushBack(1) 297 checkList(t, l2, []interface{}{1}) 298 299 var l3 = new(List) 300 l3.PushFrontList(l1) 301 checkList(t, l3, []interface{}{1}) 302 303 var l4 = new(List) 304 l4.PushBackList(l2) 305 checkList(t, l4, []interface{}{1}) 306 } 307 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) { 310 var l List 311 l.PushBack(1) 312 l.PushBack(2) 313 l.PushBack(3) 314 l.InsertBefore(1, new(Element)) 315 checkList(t, &l, []interface{}{1, 2, 3}) 316 } 317 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) { 320 var l List 321 l.PushBack(1) 322 l.PushBack(2) 323 l.PushBack(3) 324 l.InsertAfter(1, new(Element)) 325 checkList(t, &l, []interface{}{1, 2, 3}) 326 } 327 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 TestMoveUnkownMark(t *testing.T) { 330 var l1 List 331 e1 := l1.PushBack(1) 332 333 var l2 List 334 e2 := l2.PushBack(2) 335 336 l1.MoveAfter(e1, e2) 337 checkList(t, &l1, []interface{}{1}) 338 checkList(t, &l2, []interface{}{2}) 339 340 l1.MoveBefore(e1, e2) 341 checkList(t, &l1, []interface{}{1}) 342 checkList(t, &l2, []interface{}{2}) 343 } 344
