render_example_test.gno

 1package fenwickdemo
 2
 3// ExampleRender pins the realm Render output as a testable example.
 4//
 5// The block below is copied verbatim from what gno printed, never hand
 6// typed: every figure in it is computed by the library under test, so a
 7// change in the tree shows up here as a diff rather than as prose.
 8func ExampleRender() {
 9	print(Render(""))
10	// Output:
11	// # Fenwick tree
12	//
13	// A Binary Indexed Tree: prefix sums and point updates both in `O(log n)`, demoing the [`p/moul/x/daily/fenwick`](/p/moul/x/daily/fenwick/v0) library.
14	//
15	// ## The values
16	//
17	// `3, 1, 4, 1, 5, 9, 2, 6` — 8 slots totalling `31`.
18	//
19	// ## Prefix sums
20	//
21	// | i | value | Prefix(i+1) |
22	// | --- | --- | --- |
23	// | 0 | 3 | 3 |
24	// | 1 | 1 | 4 |
25	// | 2 | 4 | 8 |
26	// | 3 | 1 | 9 |
27	// | 4 | 5 | 14 |
28	// | 5 | 9 | 23 |
29	// | 6 | 2 | 25 |
30	// | 7 | 6 | 31 |
31	//
32	// ## Range queries
33	//
34	// | call | meaning | result |
35	// | --- | --- | --- |
36	// | `Range(2, 5)` | slots 2, 3, 4 | 10 |
37	// | `Range(0, 8)` | everything | 31 |
38	// | `Range(5, 5)` | empty | 0 |
39	// | `Range(-9, 99)` | clamped to the ends | 31 |
40	//
41	// Reads clamp instead of panicking. 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 for good. Writes do panic: a bad `Add` is a transaction, and aborting it is the useful answer.
42	//
43	// ## What the tree actually stores
44	//
45	// The array is not a copy of the values. Each internal slot holds the sum of a run of them, and the run lengths are the powers of two in the index. That is the whole trick, and `Covers` makes it visible.
46	//
47	// | node | covers slots | sum |
48	// | --- | --- | --- |
49	// | 1 | `[0, 1)` | 3 |
50	// | 2 | `[0, 2)` | 4 |
51	// | 3 | `[2, 3)` | 4 |
52	// | 4 | `[0, 4)` | 9 |
53	// | 5 | `[4, 5)` | 5 |
54	// | 6 | `[4, 6)` | 14 |
55	// | 7 | `[6, 7)` | 2 |
56	// | 8 | `[0, 8)` | 31 |
57	//
58	// A prefix walk visits one node per set bit of the index, and those nodes tile the prefix exactly: no gap, no overlap. Eight slots means at most three nodes per query.
59	//
60	// ## The weighted draw
61	//
62	// `SearchPrefix(target)` names the slot that owns a target drawn below `Total`, in `O(log n)`. Each holder is picked in proportion to their stake, and a zero stake can never be picked at all.
63	//
64	// | holder | stake | owns targets | share |
65	// | --- | --- | --- | --- |
66	// | alice | 30 | `[0, 30)` | 30% |
67	// | bob | 0 | none | 0% |
68	// | carol | 45 | `[30, 75)` | 45% |
69	// | dave | 5 | `[75, 80)` | 5% |
70	// | erin | 20 | `[80, 100)` | 20% |
71	//
72	// | target | SearchPrefix | holder |
73	// | --- | --- | --- |
74	// | 0 | 0 | alice |
75	// | 29 | 0 | alice |
76	// | 30 | 2 | carol |
77	// | 74 | 2 | carol |
78	// | 99 | 4 | erin |
79	//
80	// Note target `30`: it is the first one past alice's share, and it skips bob entirely rather than landing on a holder with nothing staked. The search steps over zero-weight slots because their prefix does not advance, not because anything checks for them.
81	//
82	// ## Why not a plain slice
83	//
84	// Two obvious implementations each win one column and lose another. A realm whose scoreboard is written by every player and read by every page view pays both costs, which is where the middle row earns its keep.
85	//
86	// | structure | point update | prefix sum | weighted draw |
87	// | --- | --- | --- | --- |
88	// | plain slice | `O(1)` | `O(n)` | `O(n)` |
89	// | **Fenwick tree** | `O(log n)` | `O(log n)` | `O(log n)` |
90	// | running totals | `O(n)` | `O(1)` | `O(log n)` |
91	//
92	// The tree also carries no storage overhead: it is exactly `n` values, rearranged.
93}