libgo/go/container/list/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 []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 }