fenwick_test.gno
9.63 Kb · 350 lines
1package fenwick
2
3import (
4 "testing"
5
6 "gno.land/p/nt/uassert/v0"
7)
8
9// naive is the reference implementation every structural test is checked
10// against: the obvious O(n) loop nobody would ship. A data structure whose
11// whole claim is "same answers, better complexity" is only worth trusting if
12// the same answers half is pinned against something too simple to be wrong.
13type naive []int64
14
15func (s naive) prefix(i int) int64 {
16 if i > len(s) {
17 i = len(s)
18 }
19 var sum int64
20 for k := 0; k < i; k++ {
21 sum += s[k]
22 }
23 return sum
24}
25
26func (s naive) searchPrefix(target int64) int {
27 if target < 0 {
28 return 0
29 }
30 var run int64
31 for i, v := range s {
32 run += v
33 if run > target {
34 return i
35 }
36 }
37 return len(s)
38}
39
40func TestPrefixMatchesNaive(t *testing.T) {
41 cases := []struct {
42 name string
43 vals []int64
44 }{
45 {"empty", []int64{}},
46 {"one", []int64{7}},
47 {"two", []int64{3, 4}},
48 // A power of two and one past it: the tree's shape changes at the
49 // boundary, and an off-by-one in lowBit only shows on one side of it.
50 {"eight", []int64{1, 2, 3, 4, 5, 6, 7, 8}},
51 {"nine", []int64{1, 2, 3, 4, 5, 6, 7, 8, 9}},
52 {"zeros", []int64{0, 0, 0, 0, 0}},
53 {"negatives", []int64{5, -3, 2, -10, 40}},
54 {"large", []int64{1 << 40, 1 << 40, -(1 << 41)}},
55 }
56 for _, tc := range cases {
57 t.Run(tc.name, func(t *testing.T) {
58 tr := FromSlice(tc.vals)
59 ref := naive(tc.vals)
60 uassert.Equal(t, len(tc.vals), tr.Len())
61 for i := 0; i <= len(tc.vals); i++ {
62 uassert.Equal(t, ref.prefix(i), tr.Prefix(i))
63 }
64 for i := range tc.vals {
65 uassert.Equal(t, tc.vals[i], tr.At(i))
66 }
67 uassert.Equal(t, ref.prefix(len(tc.vals)), tr.Total())
68 })
69 }
70}
71
72// TestFromSliceEqualsRepeatedAdd pins the O(n) construction against the O(n log
73// n) one. They are different code paths writing the same array, and only this
74// says so.
75func TestFromSliceEqualsRepeatedAdd(t *testing.T) {
76 vals := []int64{4, 0, 9, 2, 7, 1, 1, 6, 3}
77
78 built := FromSlice(vals)
79 added := New(len(vals))
80 for i, v := range vals {
81 added.Add(i, v)
82 }
83
84 uassert.Equal(t, len(built.t), len(added.t))
85 for i := range built.t {
86 uassert.Equal(t, built.t[i], added.t[i])
87 }
88}
89
90func TestRange(t *testing.T) {
91 vals := []int64{1, 2, 3, 4, 5}
92 tr := FromSlice(vals)
93
94 cases := []struct {
95 name string
96 lo, hi int
97 want int64
98 }{
99 {"whole", 0, 5, 15},
100 {"middle", 1, 4, 9},
101 {"single", 2, 3, 3},
102 {"empty", 2, 2, 0},
103 {"inverted", 4, 1, 0},
104 {"low clamped", -100, 2, 3},
105 {"high clamped", 3, 100, 9},
106 {"both clamped", -7, 700, 15},
107 {"wholly below", -9, -2, 0},
108 {"wholly above", 60, 90, 0},
109 }
110 for _, tc := range cases {
111 t.Run(tc.name, func(t *testing.T) {
112 uassert.Equal(t, tc.want, tr.Range(tc.lo, tc.hi))
113 })
114 }
115}
116
117// TestReadsAreTotal is the package's load-bearing safety claim: no read panics,
118// whatever it is handed. A realm renders with these, a live realm cannot be
119// redeployed, so a panicking read is a permanently broken page.
120func TestReadsAreTotal(t *testing.T) {
121 for _, n := range []int{0, 1, 5} {
122 tr := New(n)
123 for i := 0; i < n; i++ {
124 tr.Add(i, int64(i+1))
125 }
126 for _, i := range []int{-1 << 30, -1, 0, n, n + 1, 1 << 30} {
127 tr.Prefix(i)
128 tr.At(i)
129 tr.Range(i, i+1)
130 tr.Covers(i)
131 tr.SearchPrefix(int64(i))
132 }
133 tr.Total()
134 tr.Slice()
135 }
136}
137
138func TestAtOutOfRangeIsZero(t *testing.T) {
139 tr := FromSlice([]int64{1, 2, 3})
140 uassert.Equal(t, int64(0), tr.At(-1))
141 uassert.Equal(t, int64(0), tr.At(3))
142 uassert.Equal(t, int64(0), tr.At(1<<20))
143}
144
145func TestPrefixClampsRatherThanPanics(t *testing.T) {
146 tr := FromSlice([]int64{1, 2, 3})
147 uassert.Equal(t, int64(0), tr.Prefix(-5))
148 uassert.Equal(t, int64(6), tr.Prefix(99))
149}
150
151func TestAddAndSet(t *testing.T) {
152 tr := FromSlice([]int64{1, 2, 3, 4})
153
154 tr.Add(1, 10)
155 uassert.Equal(t, int64(12), tr.At(1))
156 uassert.Equal(t, int64(20), tr.Total())
157
158 old := tr.Set(1, 2)
159 uassert.Equal(t, int64(12), old)
160 uassert.Equal(t, int64(2), tr.At(1))
161 uassert.Equal(t, int64(10), tr.Total())
162
163 tr.Add(3, -4)
164 uassert.Equal(t, int64(0), tr.At(3))
165 uassert.Equal(t, int64(6), tr.Total())
166}
167
168// TestWritesArePanicking is the other half of the read/write asymmetry. A
169// write is a transaction and should abort; a read is a render and must not.
170func TestWritesArePanicking(cur realm, t *testing.T) {
171 tr := New(3)
172 uassert.PanicsWithMessage(t, cur, "fenwick: index out of range", func() { tr.Add(3, 1) })
173 uassert.PanicsWithMessage(t, cur, "fenwick: index out of range", func() { tr.Add(-1, 1) })
174 uassert.PanicsWithMessage(t, cur, "fenwick: index out of range", func() { tr.Set(9, 1) })
175 uassert.PanicsWithMessage(t, cur, "fenwick: negative size", func() { New(-1) })
176 uassert.PanicsWithMessage(t, cur, "fenwick: size above MaxSize", func() { New(MaxSize + 1) })
177 uassert.NotPanics(t, cur, func() { New(MaxSize) })
178}
179
180func TestSearchPrefixMatchesNaive(t *testing.T) {
181 cases := []struct {
182 name string
183 vals []int64
184 }{
185 {"empty", []int64{}},
186 {"flat", []int64{1, 1, 1, 1}},
187 // Zero weights must be unselectable: this is the property a weighted
188 // draw depends on, and the one a naive scan gets wrong by returning the
189 // first index whose running total is merely >= target.
190 {"with zeros", []int64{0, 3, 0, 0, 2, 0}},
191 {"uneven", []int64{5, 0, 1, 9, 2}},
192 {"leading zero", []int64{0, 0, 7}},
193 {"eight", []int64{1, 2, 3, 4, 5, 6, 7, 8}},
194 {"nine", []int64{9, 1, 1, 1, 1, 1, 1, 1, 1}},
195 }
196 for _, tc := range cases {
197 t.Run(tc.name, func(t *testing.T) {
198 tr := FromSlice(tc.vals)
199 ref := naive(tc.vals)
200 total := ref.prefix(len(tc.vals))
201 // Probe every reachable target plus both sides of the boundary.
202 for target := int64(-2); target <= total+2; target++ {
203 uassert.Equal(t, ref.searchPrefix(target), tr.SearchPrefix(target))
204 }
205 })
206 }
207}
208
209// TestSearchPrefixNeverSelectsAZeroWeight states the draw property directly,
210// rather than leaving it implied by agreement with the reference.
211func TestSearchPrefixNeverSelectsAZeroWeight(t *testing.T) {
212 vals := []int64{0, 5, 0, 0, 3, 0, 2, 0}
213 tr := FromSlice(vals)
214 for target := int64(0); target < tr.Total(); target++ {
215 got := tr.SearchPrefix(target)
216 if vals[got] == 0 {
217 t.Errorf("target %d selected slot %d, which has weight 0", target, got)
218 }
219 }
220 // Every draw lands inside the tree, and only an exhausted target runs off
221 // the end.
222 uassert.Equal(t, tr.Len(), tr.SearchPrefix(tr.Total()))
223}
224
225// TestSearchPrefixIsProportional checks the distribution, not just the bounds:
226// slot i must own exactly vals[i] of the Total targets.
227func TestSearchPrefixIsProportional(t *testing.T) {
228 vals := []int64{3, 1, 0, 6, 2}
229 tr := FromSlice(vals)
230 hits := make([]int64, len(vals))
231 for target := int64(0); target < tr.Total(); target++ {
232 hits[tr.SearchPrefix(target)]++
233 }
234 for i := range vals {
235 uassert.Equal(t, vals[i], hits[i])
236 }
237}
238
239func TestSlice(t *testing.T) {
240 vals := []int64{6, 0, -2, 11}
241 tr := FromSlice(vals)
242 got := tr.Slice()
243 uassert.Equal(t, len(vals), len(got))
244 for i := range vals {
245 uassert.Equal(t, vals[i], got[i])
246 }
247 uassert.Equal(t, 0, len(New(0).Slice()))
248}
249
250// TestFromSliceCopies pins that the tree does not alias the caller's slice.
251func TestFromSliceCopies(t *testing.T) {
252 vals := []int64{1, 2, 3}
253 tr := FromSlice(vals)
254 vals[0] = 999
255 uassert.Equal(t, int64(1), tr.At(0))
256}
257
258func TestCovers(t *testing.T) {
259 tr := New(8)
260 cases := []struct {
261 name string
262 i int
263 lo, hi int
264 }{
265 {"odd covers one", 1, 0, 1},
266 {"two covers two", 2, 0, 2},
267 {"three covers one", 3, 2, 3},
268 {"four covers four", 4, 0, 4},
269 {"six covers two", 6, 4, 6},
270 {"eight covers all", 8, 0, 8},
271 {"below range", 0, 0, 0},
272 {"above range", 9, 0, 0},
273 }
274 for _, tc := range cases {
275 t.Run(tc.name, func(t *testing.T) {
276 lo, hi := tr.Covers(tc.i)
277 uassert.Equal(t, tc.lo, lo)
278 uassert.Equal(t, tc.hi, hi)
279 })
280 }
281}
282
283// TestCoversPartitions is the structural claim behind the whole package: the
284// nodes a Prefix walk visits tile [0, i) exactly, with no gap and no overlap.
285// If that ever stops holding, every sum is wrong and this says so in one place.
286func TestCoversPartitions(t *testing.T) {
287 const n = 13
288 tr := New(n)
289 for i := 1; i <= n; i++ {
290 covered := make([]bool, n)
291 for j := i; j > 0; j -= lowBit(j) {
292 lo, hi := tr.Covers(j)
293 for k := lo; k < hi; k++ {
294 if covered[k] {
295 t.Errorf("prefix %d: slot %d covered twice", i, k)
296 }
297 covered[k] = true
298 }
299 }
300 for k := 0; k < n; k++ {
301 if covered[k] != (k < i) {
302 t.Errorf("prefix %d: slot %d covered=%t, want %t", i, k, covered[k], k < i)
303 }
304 }
305 }
306}
307
308func TestLowBit(t *testing.T) {
309 cases := []struct{ in, want int }{
310 {1, 1}, {2, 2}, {3, 1}, {4, 4}, {6, 2}, {8, 8}, {12, 4}, {96, 32},
311 }
312 for _, tc := range cases {
313 uassert.Equal(t, tc.want, lowBit(tc.in))
314 }
315}
316
317func TestHighBit(t *testing.T) {
318 cases := []struct{ in, want int }{
319 {0, 0}, {1, 1}, {2, 2}, {3, 2}, {4, 4}, {7, 4}, {8, 8}, {9, 8}, {1000, 512},
320 }
321 for _, tc := range cases {
322 uassert.Equal(t, tc.want, highBit(tc.in))
323 }
324}
325
326// TestLargeTreeStaysConsistent exercises a size past the small hand-checked
327// cases, where a wrong jump in SearchPrefix would still look plausible.
328func TestLargeTreeStaysConsistent(t *testing.T) {
329 const n = 500
330 vals := make([]int64, n)
331 // Deterministic, and deliberately not uniform: a constant weight hides a
332 // SearchPrefix that is off by a slot.
333 for i := range vals {
334 vals[i] = int64((i*7919)%13) + 1
335 }
336 tr := FromSlice(vals)
337 ref := naive(vals)
338
339 uassert.Equal(t, ref.prefix(n), tr.Total())
340 for _, i := range []int{0, 1, 63, 64, 65, 255, 256, 257, n - 1, n} {
341 uassert.Equal(t, ref.prefix(i), tr.Prefix(i))
342 }
343 for _, target := range []int64{0, 1, 100, 1000, tr.Total() - 1, tr.Total()} {
344 uassert.Equal(t, ref.searchPrefix(target), tr.SearchPrefix(target))
345 }
346
347 tr.Add(499, 1000)
348 uassert.Equal(t, ref.prefix(n)+1000, tr.Total())
349 uassert.Equal(t, vals[499]+1000, tr.At(499))
350}
