multiset_test.gno

  1package multiset
  2
  3import (
  4	"strconv"
  5	"strings"
  6	"testing"
  7
  8	"gno.land/p/nt/uassert/v0"
  9)
 10
 11func TestEmpty(t *testing.T) {
 12	m := New()
 13	uassert.True(t, m.IsEmpty())
 14	uassert.Equal(t, 0, m.Distinct())
 15	uassert.Equal(t, 0, m.Total())
 16	uassert.Equal(t, 0, m.Count("nope"))
 17	uassert.False(t, m.Has("nope"))
 18}
 19
 20func TestAddAndCount(t *testing.T) {
 21	m := New()
 22	m.Add("apple")
 23	m.Add("apple")
 24	m.Add("pear")
 25
 26	uassert.Equal(t, 2, m.Count("apple"))
 27	uassert.Equal(t, 1, m.Count("pear"))
 28	uassert.Equal(t, 2, m.Distinct(), "distinct counts elements, not occurrences")
 29	uassert.Equal(t, 3, m.Total(), "total counts occurrences")
 30	uassert.True(t, m.Has("apple"))
 31}
 32
 33func TestAddN(t *testing.T) {
 34	m := New()
 35	uassert.True(t, m.AddN("x", 5))
 36	uassert.Equal(t, 5, m.Count("x"))
 37
 38	uassert.True(t, m.AddN("x", 0), "adding zero is a no-op that succeeds")
 39	uassert.True(t, m.AddN("x", -3), "adding a negative is a no-op that succeeds")
 40	uassert.Equal(t, 5, m.Count("x"), "count unchanged by non-positive AddN")
 41	uassert.Equal(t, 5, m.Total())
 42}
 43
 44func TestFromSlice(t *testing.T) {
 45	m := FromSlice([]string{"a", "b", "a", "c", "a"})
 46	uassert.Equal(t, 3, m.Count("a"))
 47	uassert.Equal(t, 1, m.Count("b"))
 48	uassert.Equal(t, 3, m.Distinct())
 49	uassert.Equal(t, 5, m.Total())
 50}
 51
 52func TestRemove(t *testing.T) {
 53	m := FromSlice([]string{"a", "a", "a"})
 54
 55	uassert.True(t, m.Remove("a"))
 56	uassert.Equal(t, 2, m.Count("a"))
 57	uassert.Equal(t, 2, m.Total())
 58
 59	uassert.False(t, m.Remove("absent"), "removing an absent element reports false")
 60}
 61
 62// TestRemoveDeletesAtZero pins that a count reaching zero drops the element
 63// rather than leaving a zero-count ghost that Distinct would still count.
 64func TestRemoveDeletesAtZero(t *testing.T) {
 65	m := New()
 66	m.Add("a")
 67
 68	uassert.True(t, m.Remove("a"))
 69	uassert.Equal(t, 0, m.Distinct(), "a zero count removes the element entirely")
 70	uassert.False(t, m.Has("a"))
 71	uassert.Equal(t, 0, m.Total())
 72}
 73
 74// TestRemoveNClamps pins that over-removing clears rather than going negative.
 75func TestRemoveNClamps(t *testing.T) {
 76	m := New()
 77	m.AddN("a", 3)
 78
 79	uassert.True(t, m.RemoveN("a", 100))
 80	uassert.Equal(t, 0, m.Count("a"))
 81	uassert.Equal(t, 0, m.Total(), "total must not go negative")
 82	uassert.Equal(t, 0, m.Distinct())
 83}
 84
 85func TestRemoveNPartial(t *testing.T) {
 86	m := New()
 87	m.AddN("a", 10)
 88	uassert.True(t, m.RemoveN("a", 4))
 89	uassert.Equal(t, 6, m.Count("a"))
 90	uassert.Equal(t, 6, m.Total())
 91	uassert.False(t, m.RemoveN("a", 0), "a non-positive n reports false")
 92}
 93
 94func TestRemoveAll(t *testing.T) {
 95	m := New()
 96	m.AddN("a", 7)
 97	m.Add("b")
 98
 99	uassert.True(t, m.RemoveAll("a"))
100	uassert.Equal(t, 0, m.Count("a"))
101	uassert.Equal(t, 1, m.Total(), "only b remains")
102	uassert.False(t, m.RemoveAll("a"), "already gone")
103}
104
105func TestElementsSorted(t *testing.T) {
106	m := FromSlice([]string{"delta", "alpha", "charlie", "alpha"})
107	uassert.Equal(t, "alpha,charlie,delta", strings.Join(m.Elements(), ","))
108}
109
110func TestExpand(t *testing.T) {
111	m := FromSlice([]string{"b", "a", "b"})
112	uassert.Equal(t, "a,b,b", strings.Join(m.Expand(), ","))
113	uassert.Equal(t, m.Total(), len(m.Expand()), "Expand length equals Total")
114}
115
116func TestMostCommon(t *testing.T) {
117	m := FromSlice([]string{"a", "a", "a", "b", "b", "c"})
118
119	top := m.MostCommon(2)
120	uassert.Equal(t, 2, len(top))
121	uassert.Equal(t, "a", top[0].Elem)
122	uassert.Equal(t, 3, top[0].Count)
123	uassert.Equal(t, "b", top[1].Elem)
124	uassert.Equal(t, 2, top[1].Count)
125}
126
127// TestMostCommonTiesAreAlphabetical is the determinism guarantee: equal counts
128// must not fall back on map order, which gno leaves unspecified.
129func TestMostCommonTiesAreAlphabetical(t *testing.T) {
130	m := FromSlice([]string{"zebra", "apple", "mango"}) // all count 1
131
132	got := m.MostCommon(0)
133	uassert.Equal(t, 3, len(got))
134	uassert.Equal(t, "apple", got[0].Elem)
135	uassert.Equal(t, "mango", got[1].Elem)
136	uassert.Equal(t, "zebra", got[2].Elem)
137}
138
139// TestMostCommonIsStableAcrossBuilds is the same property from the outside:
140// build the set twice, get the same ranking.
141func TestMostCommonIsStableAcrossBuilds(t *testing.T) {
142	build := func() *MultiSet {
143		m := New()
144		for i := 0; i < 60; i++ {
145			m.Add("e" + strconv.Itoa(i%9))
146		}
147		return m
148	}
149	uassert.Equal(t, rank(build().MostCommon(0)), rank(build().MostCommon(0)))
150}
151
152func TestMostCommonBounds(t *testing.T) {
153	m := FromSlice([]string{"a", "b"})
154	uassert.Equal(t, 2, len(m.MostCommon(0)), "n<=0 returns everything")
155	uassert.Equal(t, 2, len(m.MostCommon(-1)), "negative n returns everything")
156	uassert.Equal(t, 2, len(m.MostCommon(99)), "n beyond distinct returns everything")
157	uassert.Equal(t, 1, len(m.MostCommon(1)))
158	uassert.Equal(t, 0, len(New().MostCommon(5)), "empty set ranks nothing")
159}
160
161func TestUnionTakesMaximum(t *testing.T) {
162	a := FromSlice([]string{"x", "x", "y"})
163	b := FromSlice([]string{"x", "z", "z", "z"})
164
165	u := a.Union(b)
166	uassert.Equal(t, 2, u.Count("x"), "max(2,1)")
167	uassert.Equal(t, 1, u.Count("y"), "max(1,0)")
168	uassert.Equal(t, 3, u.Count("z"), "max(0,3)")
169	uassert.Equal(t, 6, u.Total())
170	uassert.Equal(t, 3, a.Total(), "operands are untouched")
171}
172
173func TestIntersectTakesMinimum(t *testing.T) {
174	a := FromSlice([]string{"x", "x", "x", "y"})
175	b := FromSlice([]string{"x", "x", "z"})
176
177	i := a.Intersect(b)
178	uassert.Equal(t, 2, i.Count("x"), "min(3,2)")
179	uassert.Equal(t, 0, i.Count("y"), "absent from b")
180	uassert.Equal(t, 0, i.Count("z"), "absent from a")
181	uassert.Equal(t, 1, i.Distinct())
182	uassert.Equal(t, 2, i.Total())
183}
184
185func TestSumAddsCounts(t *testing.T) {
186	a := FromSlice([]string{"x", "x", "y"})
187	b := FromSlice([]string{"x", "z"})
188
189	s := a.Sum(b)
190	uassert.Equal(t, 3, s.Count("x"), "2+1")
191	uassert.Equal(t, 1, s.Count("y"))
192	uassert.Equal(t, 1, s.Count("z"))
193	uassert.Equal(t, 5, s.Total())
194}
195
196func TestClone(t *testing.T) {
197	m := FromSlice([]string{"a", "a"})
198	cp := m.Clone()
199	cp.Add("b")
200
201	uassert.Equal(t, 1, m.Distinct(), "clone must not share storage")
202	uassert.Equal(t, 2, cp.Distinct())
203	uassert.Equal(t, 2, m.Total())
204	uassert.Equal(t, 3, cp.Total())
205}
206
207func TestMaxDistinct(t *testing.T) {
208	m := New()
209	for i := 0; i < MaxDistinct; i++ {
210		uassert.True(t, m.Add("e"+strconv.Itoa(i)), "should accept up to MaxDistinct")
211	}
212	uassert.Equal(t, MaxDistinct, m.Distinct())
213
214	uassert.False(t, m.Add("overflow"), "a full set refuses a new distinct element")
215	uassert.Equal(t, MaxDistinct, m.Distinct())
216
217	// Counts are NOT bounded: an existing element can still grow.
218	uassert.True(t, m.AddN("e0", 1000), "existing elements still accept occurrences")
219	uassert.Equal(t, 1001, m.Count("e0"))
220}
221
222func rank(es []Entry) string {
223	parts := make([]string, len(es))
224	for i, e := range es {
225		parts[i] = e.Elem + ":" + strconv.Itoa(e.Count)
226	}
227	return strings.Join(parts, ",")
228}