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 (
   8         "testing"
   9 )
  10
  11 func checkListPointers(t *testing.T, l *List, es []*Element) {
  12         if len(es) == 0 {
  13                 if l.front != nil || l.back != nil {
  14                         t.Errorf("l.front/l.back = %v/%v should be nil/nil", l.front, l.back)
  15                 }
  16                 return
  17         }
  18
  19         if l.front != es[0] {
  20                 t.Errorf("l.front = %v, want %v", l.front, es[0])
  21         }
  22         if last := es[len(es)-1]; l.back != last {
  23                 t.Errorf("l.back = %v, want %v", l.back, last)
  24         }
  25
  26         for i, e := range es {
  27                 var e_prev, e_next *Element = nil, nil
  28                 if i > 0 {
  29                         e_prev = es[i-1]
  30                 }
  31                 if i < len(es)-1 {
  32                         e_next = es[i+1]
  33                 }
  34                 if e.prev != e_prev {
  35                         t.Errorf("elt #%d (%v) has prev=%v, want %v", i, e, e.prev, e_prev)
  36                 }
  37                 if e.next != e_next {
  38                         t.Errorf("elt #%d (%v) has next=%v, want %v", i, e, e.next, e_next)
  39                 }
  40         }
  41 }
  42
  43 func checkListLen(t *testing.T, l *List, n int) {
  44         if an := l.Len(); an != n {
  45                 t.Errorf("l.Len() = %d, want %d", an, n)
  46         }
  47 }
  48
  49 func TestList(t *testing.T) {
  50         l := New()
  51         checkListPointers(t, l, []*Element{})
  52         checkListLen(t, l, 0)
  53
  54         // Single element list
  55         e := l.PushFront("a")
  56         checkListLen(t, l, 1)
  57         checkListPointers(t, l, []*Element{e})
  58         l.MoveToFront(e)
  59         checkListPointers(t, l, []*Element{e})
  60         l.MoveToBack(e)
  61         checkListPointers(t, l, []*Element{e})
  62         checkListLen(t, l, 1)
  63         l.Remove(e)
  64         checkListPointers(t, l, []*Element{})
  65         checkListLen(t, l, 0)
  66
  67         // Bigger list
  68         e2 := l.PushFront(2)
  69         e1 := l.PushFront(1)
  70         e3 := l.PushBack(3)
  71         e4 := l.PushBack("banana")
  72         checkListPointers(t, l, []*Element{e1, e2, e3, e4})
  73         checkListLen(t, l, 4)
  74
  75         l.Remove(e2)
  76         checkListPointers(t, l, []*Element{e1, e3, e4})
  77         checkListLen(t, l, 3)
  78
  79         l.MoveToFront(e3) // move from middle
  80         checkListPointers(t, l, []*Element{e3, e1, e4})
  81
  82         l.MoveToFront(e1)
  83         l.MoveToBack(e3) // move from middle
  84         checkListPointers(t, l, []*Element{e1, e4, e3})
  85
  86         l.MoveToFront(e3) // move from back
  87         checkListPointers(t, l, []*Element{e3, e1, e4})
  88         l.MoveToFront(e3) // should be no-op
  89         checkListPointers(t, l, []*Element{e3, e1, e4})
  90
  91         l.MoveToBack(e3) // move from front
  92         checkListPointers(t, l, []*Element{e1, e4, e3})
  93         l.MoveToBack(e3) // should be no-op
  94         checkListPointers(t, l, []*Element{e1, e4, e3})
  95
  96         e2 = l.InsertBefore(2, e1) // insert before front
  97         checkListPointers(t, l, []*Element{e2, e1, e4, e3})
  98         l.Remove(e2)
  99         e2 = l.InsertBefore(2, e4) // insert before middle
 100         checkListPointers(t, l, []*Element{e1, e2, e4, e3})
 101         l.Remove(e2)
 102         e2 = l.InsertBefore(2, e3) // insert before back
 103         checkListPointers(t, l, []*Element{e1, e4, e2, e3})
 104         l.Remove(e2)
 105
 106         e2 = l.InsertAfter(2, e1) // insert after front
 107         checkListPointers(t, l, []*Element{e1, e2, e4, e3})
 108         l.Remove(e2)
 109         e2 = l.InsertAfter(2, e4) // insert after middle
 110         checkListPointers(t, l, []*Element{e1, e4, e2, e3})
 111         l.Remove(e2)
 112         e2 = l.InsertAfter(2, e3) // insert after back
 113         checkListPointers(t, l, []*Element{e1, e4, e3, e2})
 114         l.Remove(e2)
 115
 116         // Check standard iteration.
 117         sum := 0
 118         for e := l.Front(); e != nil; e = e.Next() {
 119                 if i, ok := e.Value.(int); ok {
 120                         sum += i
 121                 }
 122         }
 123         if sum != 4 {
 124                 t.Errorf("sum over l.Iter() = %d, want 4", sum)
 125         }
 126
 127         // Clear all elements by iterating
 128         var next *Element
 129         for e := l.Front(); e != nil; e = next {
 130                 next = e.Next()
 131                 l.Remove(e)
 132         }
 133         checkListPointers(t, l, []*Element{})
 134         checkListLen(t, l, 0)
 135 }
 136
 137 func checkList(t *testing.T, l *List, es []interface{}) {
 138         if l.Len() != len(es) {
 139                 t.Errorf("list has len=%v, want %v", l.Len(), len(es))
 140                 return
 141         }
 142         i := 0
 143         for e := l.Front(); e != nil; e = e.Next() {
 144                 le := e.Value.(int)
 145                 if le != es[i] {
 146                         t.Errorf("elt #%d has value=%v, want %v", i, le, es[i])
 147                 }
 148                 i++
 149         }
 150 }
 151
 152 func TestExtending(t *testing.T) {
 153         l1 := New()
 154         l2 := New()
 155
 156         l1.PushBack(1)
 157         l1.PushBack(2)
 158         l1.PushBack(3)
 159
 160         l2.PushBack(4)
 161         l2.PushBack(5)
 162
 163         l3 := New()
 164         l3.PushBackList(l1)
 165         checkList(t, l3, []interface{}{1, 2, 3})
 166         l3.PushBackList(l2)
 167         checkList(t, l3, []interface{}{1, 2, 3, 4, 5})
 168
 169         l3 = New()
 170         l3.PushFrontList(l2)
 171         checkList(t, l3, []interface{}{4, 5})
 172         l3.PushFrontList(l1)
 173         checkList(t, l3, []interface{}{1, 2, 3, 4, 5})
 174
 175         checkList(t, l1, []interface{}{1, 2, 3})
 176         checkList(t, l2, []interface{}{4, 5})
 177
 178         l3 = New()
 179         l3.PushBackList(l1)
 180         checkList(t, l3, []interface{}{1, 2, 3})
 181         l3.PushBackList(l3)
 182         checkList(t, l3, []interface{}{1, 2, 3, 1, 2, 3})
 183
 184         l3 = New()
 185         l3.PushFrontList(l1)
 186         checkList(t, l3, []interface{}{1, 2, 3})
 187         l3.PushFrontList(l3)
 188         checkList(t, l3, []interface{}{1, 2, 3, 1, 2, 3})
 189
 190         l3 = New()
 191         l1.PushBackList(l3)
 192         checkList(t, l1, []interface{}{1, 2, 3})
 193         l1.PushFrontList(l3)
 194         checkList(t, l1, []interface{}{1, 2, 3})
 195 }
 196
 197 func TestRemove(t *testing.T) {
 198         l := New()
 199         e1 := l.PushBack(1)
 200         e2 := l.PushBack(2)
 201         checkListPointers(t, l, []*Element{e1, e2})
 202         e := l.Front()
 203         l.Remove(e)
 204         checkListPointers(t, l, []*Element{e2})
 205         checkListLen(t, l, 1)
 206         l.Remove(e)
 207         checkListPointers(t, l, []*Element{e2})
 208         checkListLen(t, l, 1)
 209 }