heap_test.gno

  1package heap
  2
  3import (
  4	"strconv"
  5	"testing"
  6
  7	"gno.land/p/nt/uassert/v0"
  8)
  9
 10func TestEmpty(t *testing.T) {
 11	h := New()
 12	uassert.Equal(t, 0, h.Len())
 13	uassert.True(t, h.IsEmpty(), "a new heap is empty")
 14
 15	_, _, ok := h.Peek()
 16	uassert.False(t, ok, "peek on empty returns not-ok")
 17	_, _, ok = h.Pop()
 18	uassert.False(t, ok, "pop on empty returns not-ok")
 19}
 20
 21func TestMinOrder(t *testing.T) {
 22	h := New()
 23	for _, c := range []struct {
 24		v string
 25		p int
 26	}{{"c", 3}, {"a", 1}, {"d", 4}, {"b", 2}} {
 27		uassert.True(t, h.Push(c.v, c.p), "push should succeed")
 28	}
 29	uassert.Equal(t, 4, h.Len())
 30
 31	v, p, ok := h.Peek()
 32	uassert.True(t, ok)
 33	uassert.Equal(t, "a", v)
 34	uassert.Equal(t, 1, p)
 35	uassert.Equal(t, 4, h.Len(), "peek must not remove")
 36
 37	uassert.Equal(t, "a,b,c,d", join(h.Drain()))
 38	uassert.True(t, h.IsEmpty(), "drain empties the heap")
 39}
 40
 41func TestMaxOrder(t *testing.T) {
 42	h := NewMax()
 43	uassert.True(t, h.IsMax(), "NewMax builds a max-heap")
 44	for _, c := range []struct {
 45		v string
 46		p int
 47	}{{"c", 3}, {"a", 1}, {"d", 4}, {"b", 2}} {
 48		h.Push(c.v, c.p)
 49	}
 50	uassert.Equal(t, "d,c,b,a", join(h.Drain()))
 51}
 52
 53// TestTiesBreakByInsertionOrder is the determinism guarantee: equal priorities
 54// pop oldest-first, so the same input always yields the same output.
 55func TestTiesBreakByInsertionOrder(t *testing.T) {
 56	h := New()
 57	h.Push("first", 5)
 58	h.Push("second", 5)
 59	h.Push("third", 5)
 60	uassert.Equal(t, "first,second,third", join(h.Drain()))
 61}
 62
 63// TestTiesBreakOldestFirstInMaxHeap pins that the tiebreak does NOT invert with
 64// the heap kind — only the priority comparison does.
 65func TestTiesBreakOldestFirstInMaxHeap(t *testing.T) {
 66	h := NewMax()
 67	h.Push("first", 5)
 68	h.Push("second", 5)
 69	h.Push("third", 5)
 70	uassert.Equal(t, "first,second,third", join(h.Drain()))
 71}
 72
 73// TestDeterministicAcrossEqualInput feeds two heaps identically and requires
 74// identical output — the property a Render depends on.
 75func TestDeterministicAcrossEqualInput(t *testing.T) {
 76	build := func() *Heap {
 77		h := New()
 78		for i := 0; i < 50; i++ {
 79			h.Push("v"+strconv.Itoa(i), i%7)
 80		}
 81		return h
 82	}
 83	uassert.Equal(t, join(build().Drain()), join(build().Drain()))
 84}
 85
 86func TestInterleavedPushPop(t *testing.T) {
 87	h := New()
 88	h.Push("b", 2)
 89	h.Push("d", 4)
 90
 91	v, _, _ := h.Pop()
 92	uassert.Equal(t, "b", v)
 93
 94	h.Push("a", 1)
 95	h.Push("c", 3)
 96
 97	uassert.Equal(t, "a,c,d", join(h.Drain()))
 98}
 99
100func TestNegativeAndZeroPriorities(t *testing.T) {
101	h := New()
102	h.Push("zero", 0)
103	h.Push("neg", -10)
104	h.Push("pos", 10)
105	uassert.Equal(t, "neg,zero,pos", join(h.Drain()))
106}
107
108func TestDuplicateValues(t *testing.T) {
109	h := New()
110	h.Push("same", 2)
111	h.Push("same", 1)
112	// Duplicate values are independent entries, ordered by priority.
113	uassert.Equal(t, 2, h.Len())
114	uassert.Equal(t, "same,same", join(h.Drain()))
115}
116
117func TestClone(t *testing.T) {
118	h := New()
119	h.Push("a", 1)
120	h.Push("b", 2)
121
122	cp := h.Clone()
123	cp.Pop()
124
125	uassert.Equal(t, 2, h.Len(), "clone must not share storage")
126	uassert.Equal(t, 1, cp.Len())
127	uassert.Equal(t, "a,b", join(h.Drain()))
128}
129
130func TestCloneKeepsKind(t *testing.T) {
131	uassert.True(t, NewMax().Clone().IsMax(), "clone of a max-heap is a max-heap")
132	uassert.False(t, New().Clone().IsMax(), "clone of a min-heap is a min-heap")
133}
134
135func TestMaxItems(t *testing.T) {
136	h := New()
137	for i := 0; i < MaxItems; i++ {
138		uassert.True(t, h.Push("v", i), "should accept up to MaxItems")
139	}
140	uassert.Equal(t, MaxItems, h.Len())
141	uassert.False(t, h.Push("overflow", 0), "a full heap refuses new items")
142	uassert.Equal(t, MaxItems, h.Len(), "a refused push must not grow the heap")
143}
144
145// TestHeapPropertyHolds drains a pseudo-random load and checks the sequence is
146// non-decreasing — the invariant, independent of the insertion pattern.
147func TestHeapPropertyHolds(t *testing.T) {
148	h := New()
149	x := 7
150	for i := 0; i < 200; i++ {
151		x = (x*31 + 17) % 101 // deterministic spread, no rand
152		h.Push("v"+strconv.Itoa(i), x)
153	}
154
155	prev := -1
156	for {
157		_, p, ok := h.Pop()
158		if !ok {
159			break
160		}
161		uassert.True(t, p >= prev, "pop order must be non-decreasing")
162		prev = p
163	}
164}
165
166func join(ss []string) string {
167	out := ""
168	for i, s := range ss {
169		if i > 0 {
170			out += ","
171		}
172		out += s
173	}
174	return out
175}