countminsketch_test.gno

  1package countminsketch
  2
  3import (
  4	"strconv"
  5	"testing"
  6
  7	"gno.land/p/nt/uassert/v0"
  8)
  9
 10func TestNewValidation(t *testing.T) {
 11	_, err := New(MinWidth-1, 4)
 12	uassert.ErrorIs(t, err, ErrBadWidth)
 13	_, err = New(MaxWidth+1, 4)
 14	uassert.ErrorIs(t, err, ErrBadWidth)
 15	_, err = New(256, MinDepth-1)
 16	uassert.ErrorIs(t, err, ErrBadDepth)
 17	_, err = New(256, MaxDepth+1)
 18	uassert.ErrorIs(t, err, ErrBadDepth)
 19
 20	_, err = New(MinWidth, MinDepth)
 21	uassert.NoError(t, err, "the minimum dimensions are valid")
 22	_, err = New(MaxWidth, MaxDepth)
 23	uassert.NoError(t, err, "the maximum dimensions are valid")
 24}
 25
 26func TestDimensions(t *testing.T) {
 27	s, _ := New(64, 3)
 28	uassert.Equal(t, 64, s.Width())
 29	uassert.Equal(t, 3, s.Depth())
 30	uassert.Equal(t, 192, s.Counters(), "storage is width*depth, fixed")
 31
 32	d := NewDefault()
 33	uassert.Equal(t, 256, d.Width())
 34	uassert.Equal(t, 4, d.Depth())
 35}
 36
 37func TestEmptyEstimatesZero(t *testing.T) {
 38	s := NewDefault()
 39	uassert.Equal(t, int64(0), s.Estimate("anything"))
 40	uassert.False(t, s.MightHave("anything"))
 41	uassert.Equal(t, int64(0), s.Total())
 42}
 43
 44func TestAddAndEstimate(t *testing.T) {
 45	s := NewDefault()
 46	for i := 0; i < 5; i++ {
 47		s.Add("apple")
 48	}
 49	s.Add("pear")
 50
 51	uassert.Equal(t, int64(5), s.Estimate("apple"))
 52	uassert.Equal(t, int64(1), s.Estimate("pear"))
 53	uassert.Equal(t, int64(6), s.Total())
 54	uassert.True(t, s.MightHave("apple"))
 55}
 56
 57func TestAddNRejectsNonPositive(t *testing.T) {
 58	s := NewDefault()
 59	uassert.ErrorIs(t, s.AddN("x", 0), ErrBadCount)
 60	uassert.ErrorIs(t, s.AddN("x", -3), ErrBadCount)
 61	uassert.Equal(t, int64(0), s.Total(), "a rejected add changes nothing")
 62}
 63
 64func TestAddNAccumulates(t *testing.T) {
 65	s := NewDefault()
 66	uassert.NoError(t, s.AddN("x", 100))
 67	uassert.NoError(t, s.AddN("x", 50))
 68	uassert.Equal(t, int64(150), s.Estimate("x"))
 69	uassert.Equal(t, int64(150), s.Total())
 70}
 71
 72// TestNeverUndercounts is THE contract. A tiny sketch guarantees collisions;
 73// the estimate must still never fall below the truth.
 74func TestNeverUndercounts(t *testing.T) {
 75	s, _ := New(MinWidth, 2) // deliberately tiny: 4 columns, collisions certain
 76
 77	truth := map[string]int64{}
 78	for i := 0; i < 300; i++ {
 79		e := "e" + strconv.Itoa(i%40)
 80		s.Add(e)
 81		truth[e]++
 82	}
 83
 84	for e, want := range truth {
 85		got := s.Estimate(e)
 86		uassert.True(t, got >= want,
 87			"estimate must never undercount "+e+": got "+strconv.FormatInt(got, 10)+
 88				" want >= "+strconv.FormatInt(want, 10))
 89	}
 90}
 91
 92// TestExactWhenNoCollisions checks a generously sized sketch is exact for a
 93// handful of elements — the common case.
 94func TestExactWhenNoCollisions(t *testing.T) {
 95	s, _ := New(MaxWidth, 4)
 96	s.AddN("alpha", 7)
 97	s.AddN("bravo", 3)
 98	s.AddN("charlie", 11)
 99
100	uassert.Equal(t, int64(7), s.Estimate("alpha"))
101	uassert.Equal(t, int64(3), s.Estimate("bravo"))
102	uassert.Equal(t, int64(11), s.Estimate("charlie"))
103}
104
105// TestAbsentIsDefinitiveWhenZero pins the useful direction of the one-sided
106// error: zero means definitely never added.
107func TestAbsentIsDefinitiveWhenZero(t *testing.T) {
108	s, _ := New(MaxWidth, 4)
109	s.Add("present")
110	uassert.False(t, s.MightHave("definitely-absent"), "a zero estimate is definitive")
111}
112
113// TestEstimateBoundedByTotal pins the other side: an estimate can never exceed
114// everything that was ever added.
115func TestEstimateBoundedByTotal(t *testing.T) {
116	s, _ := New(MinWidth, 1)
117	for i := 0; i < 100; i++ {
118		s.Add("e" + strconv.Itoa(i))
119	}
120	for i := 0; i < 100; i++ {
121		uassert.True(t, s.Estimate("e"+strconv.Itoa(i)) <= s.Total(),
122			"no estimate may exceed the total")
123	}
124}
125
126// TestDeterministicAcrossInstances is what makes this safe on chain: the same
127// input yields the same counters everywhere, with no map-order dependence.
128func TestDeterministicAcrossInstances(t *testing.T) {
129	build := func() *Sketch {
130		s, _ := New(32, 3)
131		for i := 0; i < 200; i++ {
132			s.Add("elem" + strconv.Itoa(i%25))
133		}
134		return s
135	}
136	a, b := build(), build()
137
138	for r := 0; r < a.Depth(); r++ {
139		ra, rb := a.Row(r), b.Row(r)
140		for c := range ra {
141			uassert.Equal(t, ra[c], rb[c], "counters must match across instances")
142		}
143	}
144	uassert.Equal(t, a.Estimate("elem7"), b.Estimate("elem7"))
145}
146
147func TestIndexIsStableAndInRange(t *testing.T) {
148	s, _ := New(64, 3)
149	for r := 0; r < 3; r++ {
150		i := s.Index("hello", r)
151		uassert.True(t, i >= 0 && i < 64, "index must be within the row")
152		uassert.Equal(t, i, s.Index("hello", r), "index must be stable")
153	}
154	uassert.Equal(t, -1, s.Index("hello", -1), "out-of-range row")
155	uassert.Equal(t, -1, s.Index("hello", 3))
156}
157
158// TestRowsHashIndependently checks the per-row seed actually changes the column,
159// which is what makes taking the minimum meaningful.
160func TestRowsHashIndependently(t *testing.T) {
161	s, _ := New(MaxWidth, MaxDepth)
162	first := s.Index("some-element", 0)
163	differs := false
164	for r := 1; r < s.Depth(); r++ {
165		if s.Index("some-element", r) != first {
166			differs = true
167		}
168	}
169	uassert.True(t, differs, "rows must not all map to the same column")
170}
171
172func TestMerge(t *testing.T) {
173	a, _ := New(128, 3)
174	b, _ := New(128, 3)
175	a.AddN("x", 5)
176	b.AddN("x", 7)
177	b.AddN("y", 2)
178
179	uassert.NoError(t, a.Merge(b))
180	uassert.Equal(t, int64(12), a.Estimate("x"), "merged counts add")
181	uassert.Equal(t, int64(2), a.Estimate("y"))
182	uassert.Equal(t, int64(14), a.Total())
183}
184
185func TestMergeRejectsMismatchedShape(t *testing.T) {
186	a, _ := New(128, 3)
187	uassert.ErrorIs(t, a.Merge(mustNew(t, 64, 3)), ErrBadWidth)
188	uassert.ErrorIs(t, a.Merge(mustNew(t, 128, 2)), ErrBadDepth)
189	uassert.Equal(t, int64(0), a.Total(), "a rejected merge changes nothing")
190}
191
192func TestReset(t *testing.T) {
193	s := NewDefault()
194	s.AddN("x", 10)
195	s.Reset()
196
197	uassert.Equal(t, int64(0), s.Estimate("x"))
198	uassert.Equal(t, int64(0), s.Total())
199	uassert.Equal(t, 256, s.Width(), "dimensions survive a reset")
200}
201
202func TestClone(t *testing.T) {
203	s := NewDefault()
204	s.AddN("x", 4)
205
206	cp := s.Clone()
207	cp.AddN("x", 6)
208
209	uassert.Equal(t, int64(4), s.Estimate("x"), "clone must not share storage")
210	uassert.Equal(t, int64(10), cp.Estimate("x"))
211	uassert.Equal(t, s.Width(), cp.Width())
212}
213
214func TestRowCopy(t *testing.T) {
215	s, _ := New(8, 2)
216	s.Add("x")
217
218	row := s.Row(0)
219	uassert.Equal(t, 8, len(row))
220	row[0] = 999
221	uassert.False(t, s.Row(0)[0] == 999, "Row returns a copy")
222
223	uassert.True(t, s.Row(-1) == nil)
224	uassert.True(t, s.Row(2) == nil)
225}
226
227func mustNew(t *testing.T, w, d int) *Sketch {
228	s, err := New(w, d)
229	uassert.NoError(t, err)
230	return s
231}