heapdemo.gno

 1// Package heapdemo is a small gnoweb demo of the binary heap / priority queue
 2// provided by the [p/moul/x/daily/heap](/p/moul/x/daily/heap/v0) library: it
 3// shows min- and max-ordering and the deterministic tiebreak.
 4//
 5// It contains no heap logic of its own. Stateless, so Render is deterministic —
 6// which is precisely what the library is for.
 7package heapdemo
 8
 9import (
10	"strconv"
11	"strings"
12
13	"gno.land/p/moul/x/daily/heap/v0"
14)
15
16type job struct {
17	name     string
18	priority int
19}
20
21// queue is the shared workload used by every section below.
22var queue = []job{
23	{"send email", 5},
24	{"pay invoice", 1},
25	{"backup db", 3},
26	{"rotate keys", 1},
27	{"clear cache", 9},
28}
29
30// Render renders the demo for gnoweb.
31func Render(path string) string {
32	var b strings.Builder
33	b.WriteString("# Binary Heap\n\n")
34	b.WriteString("A priority queue, demoing the ")
35	b.WriteString("[`p/moul/x/daily/heap`](/p/moul/x/daily/heap/v0) library.\n\n")
36
37	b.WriteString("## The workload\n\n")
38	b.WriteString("| job | priority |\n|---|---|\n")
39	for _, j := range queue {
40		b.WriteString("| " + j.name + " | " + strconv.Itoa(j.priority) + " |\n")
41	}
42
43	b.WriteString("\n## Min-heap — lowest priority first\n\n")
44	b.WriteString(popOrder(fill(heap.New())))
45
46	b.WriteString("\n## Max-heap — highest priority first\n\n")
47	b.WriteString(popOrder(fill(heap.NewMax())))
48
49	b.WriteString("\n## Ties\n\n")
50	b.WriteString("`pay invoice` and `rotate keys` share priority 1. Both heaps pop them ")
51	b.WriteString("**oldest-first**: the tiebreak is insertion order and does *not* invert ")
52	b.WriteString("with the heap kind.\n\n")
53
54	b.WriteString("> Without a total order, two nodes could pop equal-priority items in ")
55	b.WriteString("different sequences and render different pages — a consensus bug, not a ")
56	b.WriteString("cosmetic one.\n")
57	return b.String()
58}
59
60func fill(h *heap.Heap) *heap.Heap {
61	for _, j := range queue {
62		h.Push(j.name, j.priority)
63	}
64	return h
65}
66
67func popOrder(h *heap.Heap) string {
68	var b strings.Builder
69	b.WriteString("| # | job | priority |\n|---|---|---|\n")
70	i := 0
71	for {
72		v, p, ok := h.Pop()
73		if !ok {
74			break
75		}
76		i++
77		b.WriteString("| " + strconv.Itoa(i) + " | " + v + " | " + strconv.Itoa(p) + " |\n")
78	}
79	return b.String()
80}