bitsetdemo.gno

 1// Package bitsetdemo is a small gnoweb demo of the dense bit vector provided by
 2// the [p/moul/x/daily/bitset](/p/moul/x/daily/bitset/v0) library: it sieves the
 3// primes under 100 into a bit set and shows the set algebra on two small sets.
 4//
 5// It contains no bit-twiddling of its own — storage, popcount and the set
 6// operations all come from the library. Stateless, so Render is deterministic.
 7package bitsetdemo
 8
 9import (
10	"strconv"
11	"strings"
12
13	"gno.land/p/moul/x/daily/bitset/v0"
14)
15
16// limit bounds the sieve shown on the page.
17const limit = 100
18
19// primes returns a bit set of the primes below limit, sieved with the bit set
20// itself as the composite marker.
21func primes() *bitset.BitSet {
22	composite := bitset.New(limit)
23	out := bitset.New(limit)
24	for p := 2; p < limit; p++ {
25		if composite.Has(p) {
26			continue
27		}
28		out.Set(p)
29		for m := p * p; m < limit; m += p {
30			composite.Set(m)
31		}
32	}
33	return out
34}
35
36// Render renders the demo for gnoweb.
37func Render(path string) string {
38	var b strings.Builder
39	b.WriteString("# BitSet\n\n")
40	b.WriteString("A dense bit vector, demoing the ")
41	b.WriteString("[`p/moul/x/daily/bitset`](/p/moul/x/daily/bitset/v0) library.\n\n")
42
43	p := primes()
44	b.WriteString("## Primes under ")
45	b.WriteString(strconv.Itoa(limit))
46	b.WriteString("\n\n**")
47	b.WriteString(strconv.Itoa(p.Count()))
48	b.WriteString("** set bits in ")
49	b.WriteString(strconv.Itoa(p.Cap()))
50	b.WriteString(" bits of capacity:\n\n")
51	b.WriteString(list(p.Slice()))
52
53	small := bitset.FromSlice(16, []int{1, 2, 3, 5, 8})
54	even := bitset.FromSlice(16, []int{2, 4, 6, 8, 10})
55	b.WriteString("\n## Set algebra\n\n")
56	b.WriteString("| set | bits |\n|---|---|\n")
57	row(&b, "a", small)
58	row(&b, "b", even)
59	row(&b, "a ∪ b", bitset.Union(small, even))
60	row(&b, "a ∩ b", bitset.Intersect(small, even))
61	row(&b, "a \\ b", bitset.Difference(small, even))
62	row(&b, "a △ b", bitset.SymmetricDifference(small, even))
63	return b.String()
64}
65
66func row(b *strings.Builder, name string, s *bitset.BitSet) {
67	b.WriteString("| ")
68	b.WriteString(name)
69	b.WriteString(" | `")
70	b.WriteString(list1(s.Slice()))
71	b.WriteString("` |\n")
72}
73
74func list(xs []int) string {
75	if len(xs) == 0 {
76		return "_none_\n"
77	}
78	return "`" + list1(xs) + "`\n"
79}
80
81func list1(xs []int) string {
82	parts := []string{}
83	for _, x := range xs {
84		parts = append(parts, strconv.Itoa(x))
85	}
86	return strings.Join(parts, " ")
87}