list_test.go

     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 []any) {
   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, []any{1, 2, 3})
   173  	l3.PushBackList(l2)
   174  	checkList(t, l3, []any{1, 2, 3, 4, 5})
   175  
   176  	l3 = New()
   177  	l3.PushFrontList(l2)
   178  	checkList(t, l3, []any{4, 5})
   179  	l3.PushFrontList(l1)
   180  	checkList(t, l3, []any{1, 2, 3, 4, 5})
   181  
   182  	checkList(t, l1, []any{1, 2, 3})
   183  	checkList(t, l2, []any{4, 5})
   184  
   185  	l3 = New()
   186  	l3.PushBackList(l1)
   187  	checkList(t, l3, []any{1, 2, 3})
   188  	l3.PushBackList(l3)
   189  	checkList(t, l3, []any{1, 2, 3, 1, 2, 3})
   190  
   191  	l3 = New()
   192  	l3.PushFrontList(l1)
   193  	checkList(t, l3, []any{1, 2, 3})
   194  	l3.PushFrontList(l3)
   195  	checkList(t, l3, []any{1, 2, 3, 1, 2, 3})
   196  
   197  	l3 = New()
   198  	l1.PushBackList(l3)
   199  	checkList(t, l1, []any{1, 2, 3})
   200  	l1.PushFrontList(l3)
   201  	checkList(t, l1, []any{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  }
   287  
   288  // Test PushFront, PushBack, PushFrontList, PushBackList with uninitialized List
   289  func TestZeroList(t *testing.T) {
   290  	var l1 = new(List)
   291  	l1.PushFront(1)
   292  	checkList(t, l1, []any{1})
   293  
   294  	var l2 = new(List)
   295  	l2.PushBack(1)
   296  	checkList(t, l2, []any{1})
   297  
   298  	var l3 = new(List)
   299  	l3.PushFrontList(l1)
   300  	checkList(t, l3, []any{1})
   301  
   302  	var l4 = new(List)
   303  	l4.PushBackList(l2)
   304  	checkList(t, l4, []any{1})
   305  }
   306  
   307  // Test that a list l is not modified when calling InsertBefore with a mark that is not an element of l.
   308  func TestInsertBeforeUnknownMark(t *testing.T) {
   309  	var l List
   310  	l.PushBack(1)
   311  	l.PushBack(2)
   312  	l.PushBack(3)
   313  	l.InsertBefore(1, new(Element))
   314  	checkList(t, &l, []any{1, 2, 3})
   315  }
   316  
   317  // Test that a list l is not modified when calling InsertAfter with a mark that is not an element of l.
   318  func TestInsertAfterUnknownMark(t *testing.T) {
   319  	var l List
   320  	l.PushBack(1)
   321  	l.PushBack(2)
   322  	l.PushBack(3)
   323  	l.InsertAfter(1, new(Element))
   324  	checkList(t, &l, []any{1, 2, 3})
   325  }
   326  
   327  // Test that a list l is not modified when calling MoveAfter or MoveBefore with a mark that is not an element of l.
   328  func TestMoveUnknownMark(t *testing.T) {
   329  	var l1 List
   330  	e1 := l1.PushBack(1)
   331  
   332  	var l2 List
   333  	e2 := l2.PushBack(2)
   334  
   335  	l1.MoveAfter(e1, e2)
   336  	checkList(t, &l1, []any{1})
   337  	checkList(t, &l2, []any{2})
   338  
   339  	l1.MoveBefore(e1, e2)
   340  	checkList(t, &l1, []any{1})
   341  	checkList(t, &l2, []any{2})
   342  }
   343
View as plain text