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
5package ring
6
7import (
8	"fmt"
9	"testing"
10)
11
12// For debugging - keep around.
13func 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
26func 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 any) {
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
97func 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
118func 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
127func sumN(n int) int { return (n*n + n) / 2 }
128
129func 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
140func 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
160func 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
179func TestLink3(t *testing.T) {
180	var r Ring
181	n := 1
182	for i := 1; i < 10; i++ {
183		n += i
184		verify(t, r.Link(New(i)), n, -1)
185	}
186}
187
188func 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
209func 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.
223func TestMoveEmptyRing(t *testing.T) {
224	var r Ring
225
226	r.Move(1)
227	verify(t, &r, 1, 0)
228}
229