Home | History | Annotate | Download | only in ring 
      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 }
    221 
    222 // Test that calling Move() on an empty Ring initializes it.
    223 func TestMoveEmptyRing(t *testing.T) {
    224 	var r Ring
    225 
    226 	r.Move(1)
    227 	verify(t, &r, 1, 0)
    228 }
    229