291CBF95F22A93…6FAD366F18FA

Arguments · 9

1. #1fenwick
2. #2README.md
3. #3# `gno.land/p/moul/x/daily/fenwick/v0` **A Binary Indexed Tree over `int64`**: `New`, `FromSlice`, `Add`, `Set`, `Prefix`, `Range`, `At`, `Total`, `SearchPrefix`, `Slice`, `Covers`. ```go import "gno.land/p/moul/x/daily/fenwick/v0" tr := fenwick.FromSlice([]int64{3, 1, 4, 1, 5}) tr.Prefix(3) // 8 sum of [0, 3) tr.Range(1, 4) // 6 sum of [1, 4) tr.Add(2, 10) // point update, O(log n) tr.SearchPrefix(7) // 2 the slot owning target 7 ``` A realm that keeps a running tally is choosing between two bad options without noticing. A plain slice updates in `O(1)` and sums in `O(n)`. A slice of running totals sums in `O(1)` and updates in `O(n)`. A scoreboard is written by every player *and* read by every page view, so it pays both costs. A Fenwick tree does both in `O(log n)`, in exactly `n` values of storage, rearranged. **The operation worth importing a package for is `SearchPrefix`**, not the prefix sums. Given a target below `Total` it names the slot that owns it, in `O(log n)`, by descending the tree rather than scanning it. That is the primitive behind a stake-weighted draw (pick a number, ask who holds it) and behind a leaderboard's rank lookup. Prefix sums alone would not justify a data structure. Three behaviours worth knowing before you use it: - **Reads are total, writes panic**, and the asymmetry is deliberate. `Prefix`, `Range`, `At`, `Covers` and `SearchPrefix` clamp whatever index they are handed; `Add`, `Set` and `New` panic. A read is what `Render` calls, and a realm cannot be redeployed on the same path, so a `Render` that panics on an out-of-range index is a page that is broken permanently. A write is a transaction, where aborting is the useful answer and the caller can still recover. - **A zero-weight slot is never selected by `SearchPrefix`.** It falls out of the descent rather than being checked for: a zero does not advance the prefix, so no target can land on it. That is the property a weighted draw depends on, and the one a naive "first running total `>=` target" scan gets wrong. - **`SearchPrefix` is only meaningful when every value is non-negative.** With a negative in the tree the prefix sums stop increasing and "the smallest index whose prefix exceeds the target" stops being well defined. Negative values are not forbidden, because `Add` with a negative delta is the ordinary way to decrement a counter; it is this one method that needs them absent. `MaxSize` caps construction at 65,536 slots. Queries are `O(log n)` whatever the size; the cap is there so the single `O(n)` operation, building the tree, cannot be sized from unbounded user input. Sums must fit in `int64`, which gno does not check and neither does this package. `Covers(i)` reports which slots an internal node summarizes. It is not needed to use the tree; it exists so the structure can be shown rather than asserted, and the demo realm renders it. Live demo: [`r/moul/x/daily/fenwickdemo`](/r/moul/x/daily/fenwickdemo/v0). <!-- BEGIN GNOCONTRACTS FOOTER (generated by `make readmes`; do not edit below) --> --- Part of **[moul/gno-contracts](https://github.com/moul/gno-contracts)** — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage. > 🧪 **Highly experimental — potentially vibe-coded.** Not audited; may break, change, or be removed at any time. Do not use with anything of value. Full disclaimer: [DISCLAIMER](https://github.com/moul/gno-contracts/blob/main/DISCLAIMER.md). <!-- END GNOCONTRACTS FOOTER -->
4. #4fenwick.gno
5. #5// Package fenwick is a Binary Indexed Tree (Peter Fenwick, 1994): an array of // int64 that answers a prefix sum and applies a point update in O(log n), with // no extra storage beyond the array itself. // // The tradeoff it occupies is the whole reason to reach for one. A plain slice // updates in O(1) and sums in O(n). A slice of running totals sums in O(1) and // updates in O(n). A Fenwick tree does both in O(log n), which is what a realm // wants when reads and writes are interleaved: a scoreboard written by every // player and read by every render. // // The operation that actually justifies the package is [Tree.SearchPrefix]: the // smallest index whose prefix sum exceeds a target, in O(log n), by descending // the tree rather than scanning it. That is the primitive behind a // stake-weighted draw (pick a number below Total, ask which holder owns it) and // behind a leaderboard's rank lookup. Prefix sums on their own would not be // worth a data structure. // // Reads are total and writes are strict, deliberately: see the package README. // // A live demo of this package is at // [r/moul/x/daily/fenwickdemo](/r/moul/x/daily/fenwickdemo/v0). package fenwick // MaxSize bounds the number of slots so a caller cannot size the tree from // unbounded user input and make the allocation itself the attack. It is not a // gas figure: a query costs O(log n) regardless, and the cap exists so the one // O(n) operation in the package, construction, stays bounded. const MaxSize = 65536 // Tree is a Binary Indexed Tree over int64 values, addressed 0-based. // // The zero value is not usable; build one with [New] or [FromSlice]. type Tree struct { n int // t is 1-based internally: t[i] holds the sum of the LowBit(i) values // ending at i. Index 0 is unused, which is what makes the bit tricks work. t []int64 } // New returns a Tree of n zero-valued slots. // // It panics if n is negative or above [MaxSize]: both are programmer errors // that a caller cannot recover from, and a silently clamped size would hand // back a tree that disagrees with the caller about its own length. func New(n int) *Tree { if n < 0 { panic("fenwick: negative size") } if n > MaxSize { panic("fenwick: size above MaxSize") } return &Tree{n: n, t: make([]int64, n+1)} } // FromSlice returns a Tree holding vals, built in O(n) rather than by n // successive Add calls, which would cost O(n log n). // // The slice is copied; later writes to vals do not reach the tree. func FromSlice(vals []int64) *Tree { tr := New(len(vals)) // Seed each slot, then push it into its parent once. Every slot is visited // exactly once, which is the whole O(n) construction. for i, v := range vals { tr.t[i+1] += v if parent := (i + 1) + lowBit(i+1); parent <= tr.n { tr.t[parent] += tr.t[i+1] } } return tr } // Len returns the number of slots. func (tr *Tree) Len() int { return tr.n } // Add adds delta to the value at i. // // It panics if i is out of range. A write is a transaction: failing loudly is // the correct outcome, and the caller still has the chance to abort. func (tr *Tree) Add(i int, delta int64) { if i < 0 || i >= tr.n { panic("fenwick: index out of range") } for j := i + 1; j <= tr.n; j += lowBit(j) { tr.t[j] += delta } } // Set replaces the value at i, returning the value it displaced. // // It panics if i is out of range, for the same reason [Tree.Add] does. func (tr *Tree) Set(i int, v int64) int64 { old := tr.At(i) if i < 0 || i >= tr.n { panic("fenwick: index out of range") } tr.Add(i, v-old) return old } // Prefix returns the sum of the first i values, that is of [0, i). // // It is total: i is clamped into [0, Len], so Prefix(-5) is 0 and Prefix(1e9) // is Total. Reads are what Render calls, and a panicking Render is a page that // can never be displayed again, on a path that can never be redeployed. func (tr *Tree) Prefix(i int) int64 { if i > tr.n { i = tr.n } var sum int64 for ; i > 0; i -= lowBit(i) { sum += tr.t[i] } return sum } // Range returns the sum of [lo, hi). It is total: bounds are clamped, and an // empty or inverted range is 0. func (tr *Tree) Range(lo, hi int) int64 { if lo < 0 { lo = 0 } if hi > tr.n { hi = tr.n } if lo >= hi { return 0 } return tr.Prefix(hi) - tr.Prefix(lo) } // At returns the value at i, or 0 if i is out of range. Total, like the other // reads. func (tr *Tree) At(i int) int64 { if i < 0 || i >= tr.n { return 0 } return tr.Range(i, i+1) } // Total returns the sum of every value. func (tr *Tree) Total() int64 { return tr.Prefix(tr.n) } // Slice materializes the tree back into a plain slice, in O(n log n). // // It exists for rendering and for tests. A hot path should not call it. func (tr *Tree) Slice() []int64 { out := make([]int64, tr.n) for i := 0; i < tr.n; i++ { out[i] = tr.At(i) } return out } // SearchPrefix returns the smallest index i for which Prefix(i+1) > target, // or Len if no prefix exceeds it. It runs in O(log n) by descending the tree. // // With non-negative values this is the weighted select: draw a target in // [0, Total) and SearchPrefix names the slot that owns it, each slot chosen in // proportion to its value. A zero-valued slot can never be selected, which is // the property that makes it usable for a stake-weighted draw. // // It is total, and a negative target returns 0. // // The result is only meaningful when every value is non-negative: with a // negative value in the tree the prefix sums stop increasing and "the smallest // index whose prefix exceeds target" stops being well defined. The package does // not forbid negative values, because Add with a negative delta is the ordinary // way to decrement a counter; it is SearchPrefix alone that needs them absent. func (tr *Tree) SearchPrefix(target int64) int { if target < 0 { return 0 } pos := 0 // Walk the powers of two downward, largest first. At each step, take the // jump if the value it would accumulate still does not exceed target. for step := highBit(tr.n); step > 0; step >>= 1 { if next := pos + step; next <= tr.n && tr.t[next] <= target { pos = next target -= tr.t[next] } } return pos } // lowBit returns the lowest set bit of i, the range width the slot covers. func lowBit(i int) int { return i & (-i) } // highBit returns the highest power of two that is <= n, or 0 when n is 0. func highBit(n int) int { p := 1 for p<<1 <= n { p <<= 1 } if n == 0 { return 0 } return p } // Covers returns the half-open range [lo, hi) of 0-based slots that the // internal node at 1-based position i summarizes, which is what makes the // structure legible rather than magic. It is exported for the demo and for // anyone trying to see the shape; it is not needed to use the tree. // // It returns (0, 0) when i is outside [1, Len]. func (tr *Tree) Covers(i int) (int, int) { if i < 1 || i > tr.n { return 0, 0 } return i - lowBit(i), i }
6. #6fenwick_test.gno
7. #7package fenwick import ( "testing" "gno.land/p/nt/uassert/v0" ) // naive is the reference implementation every structural test is checked // against: the obvious O(n) loop nobody would ship. A data structure whose // whole claim is "same answers, better complexity" is only worth trusting if // the same answers half is pinned against something too simple to be wrong. type naive []int64 func (s naive) prefix(i int) int64 { if i > len(s) { i = len(s) } var sum int64 for k := 0; k < i; k++ { sum += s[k] } return sum } func (s naive) searchPrefix(target int64) int { if target < 0 { return 0 } var run int64 for i, v := range s { run += v if run > target { return i } } return len(s) } func TestPrefixMatchesNaive(t *testing.T) { cases := []struct { name string vals []int64 }{ {"empty", []int64{}}, {"one", []int64{7}}, {"two", []int64{3, 4}}, // A power of two and one past it: the tree's shape changes at the // boundary, and an off-by-one in lowBit only shows on one side of it. {"eight", []int64{1, 2, 3, 4, 5, 6, 7, 8}}, {"nine", []int64{1, 2, 3, 4, 5, 6, 7, 8, 9}}, {"zeros", []int64{0, 0, 0, 0, 0}}, {"negatives", []int64{5, -3, 2, -10, 40}}, {"large", []int64{1 << 40, 1 << 40, -(1 << 41)}}, } for _, tc := range cases { t.Run(tc.name, func(t *testing.T) { tr := FromSlice(tc.vals) ref := naive(tc.vals) uassert.Equal(t, len(tc.vals), tr.Len()) for i := 0; i <= len(tc.vals); i++ { uassert.Equal(t, ref.prefix(i), tr.Prefix(i)) } for i := range tc.vals { uassert.Equal(t, tc.vals[i], tr.At(i)) } uassert.Equal(t, ref.prefix(len(tc.vals)), tr.Total()) }) } } // TestFromSliceEqualsRepeatedAdd pins the O(n) construction against the O(n log // n) one. They are different code paths writing the same array, and only this // says so. func TestFromSliceEqualsRepeatedAdd(t *testing.T) { vals := []int64{4, 0, 9, 2, 7, 1, 1, 6, 3} built := FromSlice(vals) added := New(len(vals)) for i, v := range vals { added.Add(i, v) } uassert.Equal(t, len(built.t), len(added.t)) for i := range built.t { uassert.Equal(t, built.t[i], added.t[i]) } } func TestRange(t *testing.T) { vals := []int64{1, 2, 3, 4, 5} tr := FromSlice(vals) cases := []struct { name string lo, hi int want int64 }{ {"whole", 0, 5, 15}, {"middle", 1, 4, 9}, {"single", 2, 3, 3}, {"empty", 2, 2, 0}, {"inverted", 4, 1, 0}, {"low clamped", -100, 2, 3}, {"high clamped", 3, 100, 9}, {"both clamped", -7, 700, 15}, {"wholly below", -9, -2, 0}, {"wholly above", 60, 90, 0}, } for _, tc := range cases { t.Run(tc.name, func(t *testing.T) { uassert.Equal(t, tc.want, tr.Range(tc.lo, tc.hi)) }) } } // TestReadsAreTotal is the package's load-bearing safety claim: no read panics, // whatever it is handed. A realm renders with these, a live realm cannot be // redeployed, so a panicking read is a permanently broken page. func TestReadsAreTotal(t *testing.T) { for _, n := range []int{0, 1, 5} { tr := New(n) for i := 0; i < n; i++ { tr.Add(i, int64(i+1)) } for _, i := range []int{-1 << 30, -1, 0, n, n + 1, 1 << 30} { tr.Prefix(i) tr.At(i) tr.Range(i, i+1) tr.Covers(i) tr.SearchPrefix(int64(i)) } tr.Total() tr.Slice() } } func TestAtOutOfRangeIsZero(t *testing.T) { tr := FromSlice([]int64{1, 2, 3}) uassert.Equal(t, int64(0), tr.At(-1)) uassert.Equal(t, int64(0), tr.At(3)) uassert.Equal(t, int64(0), tr.At(1<<20)) } func TestPrefixClampsRatherThanPanics(t *testing.T) { tr := FromSlice([]int64{1, 2, 3}) uassert.Equal(t, int64(0), tr.Prefix(-5)) uassert.Equal(t, int64(6), tr.Prefix(99)) } func TestAddAndSet(t *testing.T) { tr := FromSlice([]int64{1, 2, 3, 4}) tr.Add(1, 10) uassert.Equal(t, int64(12), tr.At(1)) uassert.Equal(t, int64(20), tr.Total()) old := tr.Set(1, 2) uassert.Equal(t, int64(12), old) uassert.Equal(t, int64(2), tr.At(1)) uassert.Equal(t, int64(10), tr.Total()) tr.Add(3, -4) uassert.Equal(t, int64(0), tr.At(3)) uassert.Equal(t, int64(6), tr.Total()) } // TestWritesArePanicking is the other half of the read/write asymmetry. A // write is a transaction and should abort; a read is a render and must not. func TestWritesArePanicking(cur realm, t *testing.T) { tr := New(3) uassert.PanicsWithMessage(t, cur, "fenwick: index out of range", func() { tr.Add(3, 1) }) uassert.PanicsWithMessage(t, cur, "fenwick: index out of range", func() { tr.Add(-1, 1) }) uassert.PanicsWithMessage(t, cur, "fenwick: index out of range", func() { tr.Set(9, 1) }) uassert.PanicsWithMessage(t, cur, "fenwick: negative size", func() { New(-1) }) uassert.PanicsWithMessage(t, cur, "fenwick: size above MaxSize", func() { New(MaxSize + 1) }) uassert.NotPanics(t, cur, func() { New(MaxSize) }) } func TestSearchPrefixMatchesNaive(t *testing.T) { cases := []struct { name string vals []int64 }{ {"empty", []int64{}}, {"flat", []int64{1, 1, 1, 1}}, // Zero weights must be unselectable: this is the property a weighted // draw depends on, and the one a naive scan gets wrong by returning the // first index whose running total is merely >= target. {"with zeros", []int64{0, 3, 0, 0, 2, 0}}, {"uneven", []int64{5, 0, 1, 9, 2}}, {"leading zero", []int64{0, 0, 7}}, {"eight", []int64{1, 2, 3, 4, 5, 6, 7, 8}}, {"nine", []int64{9, 1, 1, 1, 1, 1, 1, 1, 1}}, } for _, tc := range cases { t.Run(tc.name, func(t *testing.T) { tr := FromSlice(tc.vals) ref := naive(tc.vals) total := ref.prefix(len(tc.vals)) // Probe every reachable target plus both sides of the boundary. for target := int64(-2); target <= total+2; target++ { uassert.Equal(t, ref.searchPrefix(target), tr.SearchPrefix(target)) } }) } } // TestSearchPrefixNeverSelectsAZeroWeight states the draw property directly, // rather than leaving it implied by agreement with the reference. func TestSearchPrefixNeverSelectsAZeroWeight(t *testing.T) { vals := []int64{0, 5, 0, 0, 3, 0, 2, 0} tr := FromSlice(vals) for target := int64(0); target < tr.Total(); target++ { got := tr.SearchPrefix(target) if vals[got] == 0 { t.Errorf("target %d selected slot %d, which has weight 0", target, got) } } // Every draw lands inside the tree, and only an exhausted target runs off // the end. uassert.Equal(t, tr.Len(), tr.SearchPrefix(tr.Total())) } // TestSearchPrefixIsProportional checks the distribution, not just the bounds: // slot i must own exactly vals[i] of the Total targets. func TestSearchPrefixIsProportional(t *testing.T) { vals := []int64{3, 1, 0, 6, 2} tr := FromSlice(vals) hits := make([]int64, len(vals)) for target := int64(0); target < tr.Total(); target++ { hits[tr.SearchPrefix(target)]++ } for i := range vals { uassert.Equal(t, vals[i], hits[i]) } } func TestSlice(t *testing.T) { vals := []int64{6, 0, -2, 11} tr := FromSlice(vals) got := tr.Slice() uassert.Equal(t, len(vals), len(got)) for i := range vals { uassert.Equal(t, vals[i], got[i]) } uassert.Equal(t, 0, len(New(0).Slice())) } // TestFromSliceCopies pins that the tree does not alias the caller's slice. func TestFromSliceCopies(t *testing.T) { vals := []int64{1, 2, 3} tr := FromSlice(vals) vals[0] = 999 uassert.Equal(t, int64(1), tr.At(0)) } func TestCovers(t *testing.T) { tr := New(8) cases := []struct { name string i int lo, hi int }{ {"odd covers one", 1, 0, 1}, {"two covers two", 2, 0, 2}, {"three covers one", 3, 2, 3}, {"four covers four", 4, 0, 4}, {"six covers two", 6, 4, 6}, {"eight covers all", 8, 0, 8}, {"below range", 0, 0, 0}, {"above range", 9, 0, 0}, } for _, tc := range cases { t.Run(tc.name, func(t *testing.T) { lo, hi := tr.Covers(tc.i) uassert.Equal(t, tc.lo, lo) uassert.Equal(t, tc.hi, hi) }) } } // TestCoversPartitions is the structural claim behind the whole package: the // nodes a Prefix walk visits tile [0, i) exactly, with no gap and no overlap. // If that ever stops holding, every sum is wrong and this says so in one place. func TestCoversPartitions(t *testing.T) { const n = 13 tr := New(n) for i := 1; i <= n; i++ { covered := make([]bool, n) for j := i; j > 0; j -= lowBit(j) { lo, hi := tr.Covers(j) for k := lo; k < hi; k++ { if covered[k] { t.Errorf("prefix %d: slot %d covered twice", i, k) } covered[k] = true } } for k := 0; k < n; k++ { if covered[k] != (k < i) { t.Errorf("prefix %d: slot %d covered=%t, want %t", i, k, covered[k], k < i) } } } } func TestLowBit(t *testing.T) { cases := []struct{ in, want int }{ {1, 1}, {2, 2}, {3, 1}, {4, 4}, {6, 2}, {8, 8}, {12, 4}, {96, 32}, } for _, tc := range cases { uassert.Equal(t, tc.want, lowBit(tc.in)) } } func TestHighBit(t *testing.T) { cases := []struct{ in, want int }{ {0, 0}, {1, 1}, {2, 2}, {3, 2}, {4, 4}, {7, 4}, {8, 8}, {9, 8}, {1000, 512}, } for _, tc := range cases { uassert.Equal(t, tc.want, highBit(tc.in)) } } // TestLargeTreeStaysConsistent exercises a size past the small hand-checked // cases, where a wrong jump in SearchPrefix would still look plausible. func TestLargeTreeStaysConsistent(t *testing.T) { const n = 500 vals := make([]int64, n) // Deterministic, and deliberately not uniform: a constant weight hides a // SearchPrefix that is off by a slot. for i := range vals { vals[i] = int64((i*7919)%13) + 1 } tr := FromSlice(vals) ref := naive(vals) uassert.Equal(t, ref.prefix(n), tr.Total()) for _, i := range []int{0, 1, 63, 64, 65, 255, 256, 257, n - 1, n} { uassert.Equal(t, ref.prefix(i), tr.Prefix(i)) } for _, target := range []int64{0, 1, 100, 1000, tr.Total() - 1, tr.Total()} { uassert.Equal(t, ref.searchPrefix(target), tr.SearchPrefix(target)) } tr.Add(499, 1000) uassert.Equal(t, ref.prefix(n)+1000, tr.Total()) uassert.Equal(t, vals[499]+1000, tr.At(499)) }
8. #8gnomod.toml
9. #9module = "gno.land/p/moul/x/daily/fenwick/v0" gno = "0.9"