gno.land/r/moul/x/daily/disjointsetdemo/v0⧉

1// Package disjointsetdemo is a small gnoweb demo of the union-find structure2// provided by the [p/moul/x/daily/disjointset](/p/moul/x/daily/disjointset/v0)3// library: it merges a fixed list of pairs and shows the resulting partition.4//5// It contains no union-find logic of its own. Stateless, so Render is6// deterministic — and the library's Partition is order-independent, which is7// what makes the output safe to pin.8package disjointsetdemo910import (11	"strconv"12	"strings"1314	"gno.land/p/moul/x/daily/disjointset/v0"15)1617// n is the universe size; pairs are the merges applied, in order.18const n = 101920var pairs = [][2]int{{0, 1}, {2, 3}, {1, 3}, {5, 6}, {7, 8}, {8, 9}}2122func build() *disjointset.DisjointSet {23	d := disjointset.New(n)24	for _, p := range pairs {25		d.Union(p[0], p[1])26	}27	return d28}2930// Render renders the demo for gnoweb.31func Render(path string) string {32	d := build()3334	var b strings.Builder35	b.WriteString("# Union-Find\n\n")36	b.WriteString("Disjoint-set forest with path compression and union by rank, demoing the ")37	b.WriteString("[`p/moul/x/daily/disjointset`](/p/moul/x/daily/disjointset/v0) library.\n\n")3839	b.WriteString("## Merges applied\n\n")40	for _, p := range pairs {41		b.WriteString("- `Union(")42		b.WriteString(strconv.Itoa(p[0]))43		b.WriteString(", ")44		b.WriteString(strconv.Itoa(p[1]))45		b.WriteString(")`\n")46	}4748	b.WriteString("\n## Partition of [0, ")49	b.WriteString(strconv.Itoa(n))50	b.WriteString(")\n\n**")51	b.WriteString(strconv.Itoa(d.Groups()))52	b.WriteString("** groups:\n\n")53	for _, g := range d.Partition() {54		b.WriteString("- `{")55		nums := []string{}56		for _, x := range g {57			nums = append(nums, strconv.Itoa(x))58		}59		b.WriteString(strings.Join(nums, ", "))60		b.WriteString("}`\n")61	}6263	b.WriteString("\n> Groups come out sorted, ordered by their smallest member, ")64	b.WriteString("so the partition is identical whatever order the merges arrive in.\n")65	return b.String()66}67