Realm

1// Package fenwickdemo is a small gnoweb demo of the Binary Indexed Tree
2// provided by the [p/moul/x/daily/fenwick](/p/moul/x/daily/fenwick/v0)
3// library: prefix sums, range queries, the internal ranges that make the
4// structure legible, and the weighted draw that is the reason to use one.
5//
6// It contains no tree logic of its own. Stateless, so Render is deterministic:
7// every figure below is computed from the fixed tables at the top of this file,
8// never from chain state, which is what lets an example test pin the page.
9package fenwickdemo
10
11import (
12	"strconv"
13	"strings"
14
15	"gno.land/p/moul/kit/ui/v0"
16	"gno.land/p/moul/x/daily/fenwick/v0"
17)
18
19// scores is the worked example: eight slots, small enough to check by hand.
20var scores = []int64{3, 1, 4, 1, 5, 9, 2, 6}
21
22// stakes is the weighted-draw example. The zero is the interesting entry: a
23// holder with no stake must never be drawn, and that is a property of the
24// search, not of the caller remembering to skip them.
25var (
26	holders = []string{"alice", "bob", "carol", "dave", "erin"}
27	stakes  = []int64{30, 0, 45, 5, 20}
28)
29
30// Render renders the demo for gnoweb.
31//
32//	Render("") / Render("/") -> the full demo
33func Render(path string) string {
34	var b strings.Builder
35
36	b.WriteString("# Fenwick tree\n\n")
37	b.WriteString("A Binary Indexed Tree: prefix sums and point updates both in ")
38	b.WriteString("`O(log n)`, demoing the ")
39	b.WriteString("[`p/moul/x/daily/fenwick`](/p/moul/x/daily/fenwick/v0) library.\n\n")
40
41	tr := fenwick.FromSlice(scores)
42
43	b.WriteString("## The values\n\n")
44	b.WriteString("`" + joinInts(scores) + "` — " + strconv.Itoa(tr.Len()))
45	b.WriteString(" slots totalling `" + strconv.FormatInt(tr.Total(), 10) + "`.\n\n")
46
47	b.WriteString("## Prefix sums\n\n")
48	pt := ui.NewTable("i", "value", "Prefix(i+1)")
49	for i := 0; i < tr.Len(); i++ {
50		pt.Row(strconv.Itoa(i),
51			strconv.FormatInt(tr.At(i), 10),
52			strconv.FormatInt(tr.Prefix(i+1), 10))
53	}
54	b.WriteString(pt.String() + "\n")
55
56	b.WriteString("## Range queries\n\n")
57	rt := ui.NewTable("call", "meaning", "result")
58	rt.Row("`Range(2, 5)`", "slots 2, 3, 4", strconv.FormatInt(tr.Range(2, 5), 10))
59	rt.Row("`Range(0, 8)`", "everything", strconv.FormatInt(tr.Range(0, 8), 10))
60	rt.Row("`Range(5, 5)`", "empty", strconv.FormatInt(tr.Range(5, 5), 10))
61	rt.Row("`Range(-9, 99)`", "clamped to the ends", strconv.FormatInt(tr.Range(-9, 99), 10))
62	b.WriteString(rt.String() + "\n")
63	b.WriteString("Reads clamp instead of panicking. A realm cannot be redeployed on ")
64	b.WriteString("the same path, so a `Render` that panics on an out-of-range index ")
65	b.WriteString("is a page that is broken for good. Writes do panic: a bad `Add` is ")
66	b.WriteString("a transaction, and aborting it is the useful answer.\n\n")
67
68	b.WriteString("## What the tree actually stores\n\n")
69	b.WriteString("The array is not a copy of the values. Each internal slot holds the ")
70	b.WriteString("sum of a run of them, and the run lengths are the powers of two in ")
71	b.WriteString("the index. That is the whole trick, and `Covers` makes it visible.\n\n")
72	ct := ui.NewTable("node", "covers slots", "sum")
73	for i := 1; i <= tr.Len(); i++ {
74		lo, hi := tr.Covers(i)
75		ct.Row(strconv.Itoa(i),
76			"`["+strconv.Itoa(lo)+", "+strconv.Itoa(hi)+")`",
77			strconv.FormatInt(tr.Range(lo, hi), 10))
78	}
79	b.WriteString(ct.String() + "\n")
80	b.WriteString("A prefix walk visits one node per set bit of the index, and those ")
81	b.WriteString("nodes tile the prefix exactly: no gap, no overlap. Eight slots ")
82	b.WriteString("means at most three nodes per query.\n\n")
83
84	b.WriteString("## The weighted draw\n\n")
85	b.WriteString("`SearchPrefix(target)` names the slot that owns a target drawn ")
86	b.WriteString("below `Total`, in `O(log n)`. Each holder is picked in proportion ")
87	b.WriteString("to their stake, and a zero stake can never be picked at all.\n\n")
88	st := fenwick.FromSlice(stakes)
89	wt := ui.NewTable("holder", "stake", "owns targets", "share")
90	for i, h := range holders {
91		lo := st.Prefix(i)
92		hi := st.Prefix(i + 1)
93		owns := "none"
94		if hi > lo {
95			owns = "`[" + strconv.FormatInt(lo, 10) + ", " + strconv.FormatInt(hi, 10) + ")`"
96		}
97		wt.Row(ui.Cell(h),
98			strconv.FormatInt(stakes[i], 10),
99			owns,
100			pct(stakes[i], st.Total()))
101	}
102	b.WriteString(wt.String() + "\n")
103
104	dt := ui.NewTable("target", "SearchPrefix", "holder")
105	for _, target := range []int64{0, 29, 30, 74, 99} {
106		i := st.SearchPrefix(target)
107		dt.Row(strconv.FormatInt(target, 10), strconv.Itoa(i), ui.Cell(holders[i]))
108	}
109	b.WriteString(dt.String() + "\n")
110	b.WriteString("Note target `30`: it is the first one past alice's share, and it ")
111	b.WriteString("skips bob entirely rather than landing on a holder with nothing ")
112	b.WriteString("staked. The search steps over zero-weight slots because their ")
113	b.WriteString("prefix does not advance, not because anything checks for them.\n\n")
114
115	b.WriteString("## Why not a plain slice\n\n")
116	b.WriteString("Two obvious implementations each win one column and lose another. ")
117	b.WriteString("A realm whose scoreboard is written by every player and read by ")
118	b.WriteString("every page view pays both costs, which is where the middle row ")
119	b.WriteString("earns its keep.\n\n")
120	xt := ui.NewTable("structure", "point update", "prefix sum", "weighted draw")
121	xt.Row("plain slice", "`O(1)`", "`O(n)`", "`O(n)`")
122	xt.Row("**Fenwick tree**", "`O(log n)`", "`O(log n)`", "`O(log n)`")
123	xt.Row("running totals", "`O(n)`", "`O(1)`", "`O(log n)`")
124	b.WriteString(xt.String() + "\n")
125	b.WriteString("The tree also carries no storage overhead: it is exactly `n` ")
126	b.WriteString("values, rearranged.\n")
127
128	return b.String()
129}
130
131// joinInts formats a slice for display. Written out rather than reached for
132// from a library because there is no sensible shared home for it yet.
133func joinInts(vals []int64) string {
134	parts := make([]string, len(vals))
135	for i, v := range vals {
136		parts[i] = strconv.FormatInt(v, 10)
137	}
138	return strings.Join(parts, ", ")
139}
140
141// pct renders part/whole as a whole-number percentage.
142//
143// Integer arithmetic throughout: Render output has to be byte-identical on
144// every validating node, and floating point is the usual way that stops being
145// true.
146func pct(part, whole int64) string {
147	if whole == 0 {
148		return "0%"
149	}
150	return strconv.FormatInt(part*100/whole, 10) + "%"
151}
152