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