libgo/go/container/ring/ring_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 ring
   6
   7 import (
   8         "fmt"
   9         "testing"
  10 )
  11
  12
  13 // For debugging - keep around.
  14 func dump(r *Ring) {
  15         if r == nil {
  16                 fmt.Println("empty")
  17                 return
  18         }
  19         i, n := 0, r.Len()
  20         for p := r; i < n; p = p.next {
  21                 fmt.Printf("%4d: %p = {<- %p | %p ->}\n", i, p, p.prev, p.next)
  22                 i++
  23         }
  24         fmt.Println()
  25 }
  26
  27
  28 func verify(t *testing.T, r *Ring, N int, sum int) {
  29         // Len
  30         n := r.Len()
  31         if n != N {
  32                 t.Errorf("r.Len() == %d; expected %d", n, N)
  33         }
  34
  35         // iteration
  36         n = 0
  37         s := 0
  38         for p := range r.Iter() {
  39                 n++
  40                 if p != nil {
  41                         s += p.(int)
  42                 }
  43         }
  44         if n != N {
  45                 t.Errorf("number of forward iterations == %d; expected %d", n, N)
  46         }
  47         if sum >= 0 && s != sum {
  48                 t.Errorf("forward ring sum = %d; expected %d", s, sum)
  49         }
  50
  51         if r == nil {
  52                 return
  53         }
  54
  55         // connections
  56         if r.next != nil {
  57                 var p *Ring // previous element
  58                 for q := r; p == nil || q != r; q = q.next {
  59                         if p != nil && p != q.prev {
  60                                 t.Errorf("prev = %p, expected q.prev = %p\n", p, q.prev)
  61                         }
  62                         p = q
  63                 }
  64                 if p != r.prev {
  65                         t.Errorf("prev = %p, expected r.prev = %p\n", p, r.prev)
  66                 }
  67         }
  68
  69         // Next, Prev
  70         if r.Next() != r.next {
  71                 t.Errorf("r.Next() != r.next")
  72         }
  73         if r.Prev() != r.prev {
  74                 t.Errorf("r.Prev() != r.prev")
  75         }
  76
  77         // Move
  78         if r.Move(0) != r {
  79                 t.Errorf("r.Move(0) != r")
  80         }
  81         if r.Move(N) != r {
  82                 t.Errorf("r.Move(%d) != r", N)
  83         }
  84         if r.Move(-N) != r {
  85                 t.Errorf("r.Move(%d) != r", -N)
  86         }
  87         for i := 0; i < 10; i++ {
  88                 ni := N + i
  89                 mi := ni % N
  90                 if r.Move(ni) != r.Move(mi) {
  91                         t.Errorf("r.Move(%d) != r.Move(%d)", ni, mi)
  92                 }
  93                 if r.Move(-ni) != r.Move(-mi) {
  94                         t.Errorf("r.Move(%d) != r.Move(%d)", -ni, -mi)
  95                 }
  96         }
  97 }
  98
  99
 100 func TestCornerCases(t *testing.T) {
 101         var (
 102                 r0 *Ring
 103                 r1 Ring
 104         )
 105         // Basics
 106         verify(t, r0, 0, 0)
 107         verify(t, &r1, 1, 0)
 108         // Insert
 109         r1.Link(r0)
 110         verify(t, r0, 0, 0)
 111         verify(t, &r1, 1, 0)
 112         // Insert
 113         r1.Link(r0)
 114         verify(t, r0, 0, 0)
 115         verify(t, &r1, 1, 0)
 116         // Unlink
 117         r1.Unlink(0)
 118         verify(t, &r1, 1, 0)
 119 }
 120
 121
 122 func makeN(n int) *Ring {
 123         r := New(n)
 124         for i := 1; i <= n; i++ {
 125                 r.Value = i
 126                 r = r.Next()
 127         }
 128         return r
 129 }
 130
 131
 132 func sum(r *Ring) int {
 133         s := 0
 134         for p := range r.Iter() {
 135                 s += p.(int)
 136         }
 137         return s
 138 }
 139
 140
 141 func sumN(n int) int { return (n*n + n) / 2 }
 142
 143
 144 func TestNew(t *testing.T) {
 145         for i := 0; i < 10; i++ {
 146                 r := New(i)
 147                 verify(t, r, i, -1)
 148         }
 149         for i := 0; i < 10; i++ {
 150                 r := makeN(i)
 151                 verify(t, r, i, sumN(i))
 152         }
 153 }
 154
 155
 156 func TestLink1(t *testing.T) {
 157         r1a := makeN(1)
 158         var r1b Ring
 159         r2a := r1a.Link(&r1b)
 160         verify(t, r2a, 2, 1)
 161         if r2a != r1a {
 162                 t.Errorf("a) 2-element link failed")
 163         }
 164
 165         r2b := r2a.Link(r2a.Next())
 166         verify(t, r2b, 2, 1)
 167         if r2b != r2a.Next() {
 168                 t.Errorf("b) 2-element link failed")
 169         }
 170
 171         r1c := r2b.Link(r2b)
 172         verify(t, r1c, 1, 1)
 173         verify(t, r2b, 1, 0)
 174 }
 175
 176
 177 func TestLink2(t *testing.T) {
 178         var r0 *Ring
 179         r1a := &Ring{Value: 42}
 180         r1b := &Ring{Value: 77}
 181         r10 := makeN(10)
 182
 183         r1a.Link(r0)
 184         verify(t, r1a, 1, 42)
 185
 186         r1a.Link(r1b)
 187         verify(t, r1a, 2, 42+77)
 188
 189         r10.Link(r0)
 190         verify(t, r10, 10, sumN(10))
 191
 192         r10.Link(r1a)
 193         verify(t, r10, 12, sumN(10)+42+77)
 194 }
 195
 196
 197 func TestLink3(t *testing.T) {
 198         var r Ring
 199         n := 1
 200         for i := 1; i < 100; i++ {
 201                 n += i
 202                 verify(t, r.Link(New(i)), n, -1)
 203         }
 204 }
 205
 206
 207 func TestUnlink(t *testing.T) {
 208         r10 := makeN(10)
 209         s10 := r10.Move(6)
 210
 211         sum10 := sumN(10)
 212
 213         verify(t, r10, 10, sum10)
 214         verify(t, s10, 10, sum10)
 215
 216         r0 := r10.Unlink(0)
 217         verify(t, r0, 0, 0)
 218
 219         r1 := r10.Unlink(1)
 220         verify(t, r1, 1, 2)
 221         verify(t, r10, 9, sum10-2)
 222
 223         r9 := r10.Unlink(9)
 224         verify(t, r9, 9, sum10-2)
 225         verify(t, r10, 9, sum10-2)
 226 }
 227
 228
 229 func TestLinkUnlink(t *testing.T) {
 230         for i := 1; i < 4; i++ {
 231                 ri := New(i)
 232                 for j := 0; j < i; j++ {
 233                         rj := ri.Unlink(j)
 234                         verify(t, rj, j, -1)
 235                         verify(t, ri, i-j, -1)
 236                         ri.Link(rj)
 237                         verify(t, ri, i, -1)
 238                 }
 239         }
 240 }