1package fenwick23import (4 "testing"56 "gno.land/p/nt/uassert/v0"7)89// naive is the reference implementation every structural test is checked10// against: the obvious O(n) loop nobody would ship. A data structure whose11// whole claim is "same answers, better complexity" is only worth trusting if12// the same answers half is pinned against something too simple to be wrong.13type naive []int641415func (s naive) prefix(i int) int64 {16 if i > len(s) {17 i = len(s)18 }19 var sum int6420 for k := 0; k < i; k++ {21 sum += s[k]22 }23 return sum24}2526func (s naive) searchPrefix(target int64) int {27 if target < 0 {28 return 029 }30 var run int6431 for i, v := range s {32 run += v33 if run > target {34 return i35 }36 }37 return len(s)38}3940func TestPrefixMatchesNaive(t *testing.T) {41 cases := []struct {42 name string43 vals []int6444 }{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 the49 // 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}7172// TestFromSliceEqualsRepeatedAdd pins the O(n) construction against the O(n log73// n) one. They are different code paths writing the same array, and only this74// says so.75func TestFromSliceEqualsRepeatedAdd(t *testing.T) {76 vals := []int64{4, 0, 9, 2, 7, 1, 1, 6, 3}7778 built := FromSlice(vals)79 added := New(len(vals))80 for i, v := range vals {81 added.Add(i, v)82 }8384 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}8990func TestRange(t *testing.T) {91 vals := []int64{1, 2, 3, 4, 5}92 tr := FromSlice(vals)9394 cases := []struct {95 name string96 lo, hi int97 want int6498 }{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}116117// 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 be119// 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}137138func 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}144145func 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}150151func TestAddAndSet(t *testing.T) {152 tr := FromSlice([]int64{1, 2, 3, 4})153154 tr.Add(1, 10)155 uassert.Equal(t, int64(12), tr.At(1))156 uassert.Equal(t, int64(20), tr.Total())157158 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())162163 tr.Add(3, -4)164 uassert.Equal(t, int64(0), tr.At(3))165 uassert.Equal(t, int64(6), tr.Total())166}167168// TestWritesArePanicking is the other half of the read/write asymmetry. A169// 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}179180func TestSearchPrefixMatchesNaive(t *testing.T) {181 cases := []struct {182 name string183 vals []int64184 }{185 {"empty", []int64{}},186 {"flat", []int64{1, 1, 1, 1}},187 // Zero weights must be unselectable: this is the property a weighted188 // draw depends on, and the one a naive scan gets wrong by returning the189 // 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}208209// 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 off221 // the end.222 uassert.Equal(t, tr.Len(), tr.SearchPrefix(tr.Total()))223}224225// 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}238239func 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}249250// 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] = 999255 uassert.Equal(t, int64(1), tr.At(0))256}257258func TestCovers(t *testing.T) {259 tr := New(8)260 cases := []struct {261 name string262 i int263 lo, hi int264 }{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}282283// TestCoversPartitions is the structural claim behind the whole package: the284// 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 = 13288 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] = true298 }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}307308func 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}316317func 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}325326// TestLargeTreeStaysConsistent exercises a size past the small hand-checked327// cases, where a wrong jump in SearchPrefix would still look plausible.328func TestLargeTreeStaysConsistent(t *testing.T) {329 const n = 500330 vals := make([]int64, n)331 // Deterministic, and deliberately not uniform: a constant weight hides a332 // SearchPrefix that is off by a slot.333 for i := range vals {334 vals[i] = int64((i*7919)%13) + 1335 }336 tr := FromSlice(vals)337 ref := naive(vals)338339 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 }346347 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}351Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.