flatmapdemo.gno

 1// Package flatmapdemo is a small gnoweb demo of the sorted-vector map provided
 2// by the [p/moul/x/daily/flatmap](/p/moul/x/daily/flatmap/v0) library: sorted
 3// storage, indexed access and range queries.
 4//
 5// It contains no map logic of its own. Stateless, so Render is deterministic —
 6// which is precisely what the library is for.
 7package flatmapdemo
 8
 9import (
10	"strconv"
11	"strings"
12
13	"gno.land/p/moul/x/daily/flatmap/v0"
14)
15
16// Render renders the demo for gnoweb.
17func Render(path string) string {
18	var b strings.Builder
19	b.WriteString("# Flat Map\n\n")
20	b.WriteString("A map backed by sorted slices, demoing the ")
21	b.WriteString("[`p/moul/x/daily/flatmap`](/p/moul/x/daily/flatmap/v0) library.\n\n")
22
23	f := flatmap.New()
24	inserted := []string{"delta", "alpha", "echo", "bravo", "charlie"}
25	for i, k := range inserted {
26		f.Set(k, strconv.Itoa(i+1))
27	}
28
29	b.WriteString("## Sorted by construction\n\n")
30	b.WriteString("Inserted as `" + strings.Join(inserted, ", ") + "` — stored sorted:\n\n")
31	b.WriteString(table(f))
32	b.WriteString("\nNo sort on read, and no dependence on map iteration order — which ")
33	b.WriteString("gno leaves unspecified, and which would let two nodes render different ")
34	b.WriteString("pages from the same state.\n\n")
35
36	b.WriteString("## Indexed access\n\n")
37	b.WriteString("Sorted storage gives positional lookup that a hash map cannot:\n\n")
38	for _, i := range []int{0, 2, 4} {
39		k, v, _ := f.At(i)
40		b.WriteString("- `At(" + strconv.Itoa(i) + ")` → `" + k + "` = `" + v + "`\n")
41	}
42
43	b.WriteString("\n## Range queries\n\n")
44	b.WriteString("Two binary searches and a walk — `lo` inclusive, `hi` exclusive:\n\n")
45	b.WriteString("| range | keys |\n|---|---|\n")
46	b.WriteString("| `[\"bravo\", \"delta\")` | " + rng(f, "bravo", "delta") + " |\n")
47	b.WriteString("| `[\"charlie\", ∞)` | " + rng(f, "charlie", "") + " |\n")
48	b.WriteString("| `[\"b\", \"d\")` | " + rng(f, "b", "d") + " |\n")
49	b.WriteString("\nThe last one asks for bounds that are not keys at all — the search ")
50	b.WriteString("still lands in the right place.\n\n")
51
52	b.WriteString("## The trade\n\n")
53	b.WriteString("| operation | cost |\n|---|---|\n")
54	b.WriteString("| `Get` | O(log n) binary search over contiguous memory |\n")
55	b.WriteString("| iteration | O(n), already ordered, nothing to sort |\n")
56	b.WriteString("| `Set` in the middle | **O(n)** — the tail shifts |\n")
57	b.WriteString("| `Set` at the end | O(1) amortised — the fast path |\n")
58	b.WriteString("\nCheap reads and cheap ordered iteration, paid for at write time.\n")
59	return b.String()
60}
61
62func table(f *flatmap.FlatMap) string {
63	var b strings.Builder
64	b.WriteString("| # | key | value |\n|---|---|---|\n")
65	i := 0
66	f.Iterate(func(k, v string) bool {
67		b.WriteString("| " + strconv.Itoa(i) + " | `" + k + "` | `" + v + "` |\n")
68		i++
69		return false
70	})
71	return b.String()
72}
73
74func rng(f *flatmap.FlatMap, lo, hi string) string {
75	var out []string
76	f.Range(lo, hi, func(k, v string) bool {
77		out = append(out, "`"+k+"`")
78		return false
79	})
80	if len(out) == 0 {
81		return "_none_"
82	}
83	return strings.Join(out, ", ")
84}