list_test.go

Documentation: container/list

		 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  	e2, e3 = e3, e2
	 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  	e2, e3, e4 = e4, e2, e3
	 283  
	 284  	l.MoveAfter(e2, e3)
	 285  	checkListPointers(t, l, []*Element{e1, e3, e2, e4})
	 286  	e2, e3 = e3, e2
	 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 TestMoveUnknownMark(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
View as plain text