flatmap_test.gno

  1package flatmap
  2
  3import (
  4	"strconv"
  5	"strings"
  6	"testing"
  7
  8	"gno.land/p/nt/uassert/v0"
  9)
 10
 11func TestEmpty(t *testing.T) {
 12	f := New()
 13	uassert.Equal(t, 0, f.Len())
 14	uassert.True(t, f.IsEmpty())
 15	uassert.False(t, f.Has("a"))
 16	uassert.True(t, f.Sorted(), "an empty map is trivially sorted")
 17
 18	_, ok := f.Get("a")
 19	uassert.False(t, ok)
 20	_, _, ok = f.At(0)
 21	uassert.False(t, ok)
 22}
 23
 24// TestStaysSortedRegardlessOfInsertionOrder is the core invariant.
 25func TestStaysSortedRegardlessOfInsertionOrder(t *testing.T) {
 26	f := New()
 27	for _, k := range []string{"delta", "alpha", "echo", "bravo", "charlie"} {
 28		f.Set(k, "v-"+k)
 29	}
 30	uassert.Equal(t, "alpha,bravo,charlie,delta,echo", strings.Join(f.Keys(), ","))
 31	uassert.True(t, f.Sorted())
 32}
 33
 34func TestGetSet(t *testing.T) {
 35	f := New()
 36	uassert.True(t, f.Set("b", "2"))
 37	uassert.True(t, f.Set("a", "1"))
 38
 39	v, ok := f.Get("a")
 40	uassert.True(t, ok)
 41	uassert.Equal(t, "1", v)
 42
 43	_, ok = f.Get("zzz")
 44	uassert.False(t, ok)
 45}
 46
 47func TestSetUpdatesInPlace(t *testing.T) {
 48	f := New()
 49	f.Set("a", "1")
 50	f.Set("b", "2")
 51
 52	uassert.True(t, f.Set("a", "99"))
 53	uassert.Equal(t, 2, f.Len(), "updating must not add an entry")
 54
 55	v, _ := f.Get("a")
 56	uassert.Equal(t, "99", v)
 57	uassert.True(t, f.Sorted())
 58}
 59
 60func TestValuesFollowKeyOrder(t *testing.T) {
 61	f := New()
 62	f.Set("c", "3")
 63	f.Set("a", "1")
 64	f.Set("b", "2")
 65	uassert.Equal(t, "1,2,3", strings.Join(f.Values(), ","))
 66}
 67
 68func TestDelete(t *testing.T) {
 69	f := New()
 70	for _, k := range []string{"a", "b", "c", "d"} {
 71		f.Set(k, k)
 72	}
 73
 74	uassert.True(t, f.Delete("b"))
 75	uassert.Equal(t, "a,c,d", strings.Join(f.Keys(), ","), "the gap must close")
 76	uassert.Equal(t, "a,c,d", strings.Join(f.Values(), ","), "values shift with keys")
 77	uassert.Equal(t, 3, f.Len())
 78	uassert.True(t, f.Sorted())
 79
 80	uassert.False(t, f.Delete("b"), "deleting twice reports false")
 81}
 82
 83func TestDeleteEnds(t *testing.T) {
 84	f := New()
 85	for _, k := range []string{"a", "b", "c"} {
 86		f.Set(k, k)
 87	}
 88	uassert.True(t, f.Delete("a"))
 89	uassert.True(t, f.Delete("c"))
 90	uassert.Equal(t, "b", strings.Join(f.Keys(), ","))
 91	uassert.True(t, f.Delete("b"))
 92	uassert.True(t, f.IsEmpty())
 93}
 94
 95func TestAt(t *testing.T) {
 96	f := New()
 97	f.Set("b", "2")
 98	f.Set("a", "1")
 99
100	k, v, ok := f.At(0)
101	uassert.True(t, ok)
102	uassert.Equal(t, "a", k)
103	uassert.Equal(t, "1", v)
104
105	_, _, ok = f.At(-1)
106	uassert.False(t, ok)
107	_, _, ok = f.At(2)
108	uassert.False(t, ok)
109}
110
111func TestIterateAndStop(t *testing.T) {
112	f := New()
113	for _, k := range []string{"c", "a", "b"} {
114		f.Set(k, strings.ToUpper(k))
115	}
116
117	var seen []string
118	f.Iterate(func(k, v string) bool {
119		seen = append(seen, k+"="+v)
120		return false
121	})
122	uassert.Equal(t, "a=A,b=B,c=C", strings.Join(seen, ","))
123
124	count := 0
125	f.Iterate(func(k, v string) bool { count++; return true })
126	uassert.Equal(t, 1, count, "returning true stops iteration")
127}
128
129// TestRange is the query sorted storage makes cheap.
130func TestRange(t *testing.T) {
131	f := New()
132	for _, k := range []string{"a", "b", "c", "d", "e"} {
133		f.Set(k, k)
134	}
135
136	uassert.Equal(t, "b,c,d", collect(f, "b", "e"), "lo inclusive, hi exclusive")
137	uassert.Equal(t, "c,d,e", collect(f, "c", ""), "empty hi runs to the end")
138	uassert.Equal(t, "a,b,c,d,e", collect(f, "", ""), "empty bounds cover everything")
139	uassert.Equal(t, "", collect(f, "x", "z"), "a range past the end yields nothing")
140	uassert.Equal(t, "", collect(f, "c", "c"), "an empty half-open range yields nothing")
141}
142
143func TestRangeStops(t *testing.T) {
144	f := New()
145	for _, k := range []string{"a", "b", "c"} {
146		f.Set(k, k)
147	}
148	n := 0
149	f.Range("", "", func(k, v string) bool { n++; return true })
150	uassert.Equal(t, 1, n)
151}
152
153func TestRangeOnAbsentBoundary(t *testing.T) {
154	f := New()
155	for _, k := range []string{"a", "c", "e"} {
156		f.Set(k, k)
157	}
158	// "b" and "d" are not present; the range still lands correctly.
159	uassert.Equal(t, "c", collect(f, "b", "d"))
160}
161
162func TestKeysAndValuesAreCopies(t *testing.T) {
163	f := New()
164	f.Set("a", "1")
165	f.Set("b", "2")
166
167	ks := f.Keys()
168	ks[0] = "mutated"
169	vs := f.Values()
170	vs[0] = "mutated"
171
172	uassert.Equal(t, "a,b", strings.Join(f.Keys(), ","), "callers cannot reorder the map through Keys")
173	uassert.Equal(t, "1,2", strings.Join(f.Values(), ","))
174}
175
176func TestClone(t *testing.T) {
177	f := New()
178	f.Set("a", "1")
179
180	cp := f.Clone()
181	cp.Set("b", "2")
182
183	uassert.Equal(t, 1, f.Len(), "clone must not share storage")
184	uassert.Equal(t, 2, cp.Len())
185	uassert.True(t, cp.Sorted())
186}
187
188func TestMaxEntries(t *testing.T) {
189	f := New()
190	for i := 0; i < MaxEntries; i++ {
191		uassert.True(t, f.Set(pad(i), "v"), "should accept up to MaxEntries")
192	}
193	uassert.Equal(t, MaxEntries, f.Len())
194
195	uassert.False(t, f.Set("zzz-overflow", "v"), "a full map refuses a new key")
196	uassert.Equal(t, MaxEntries, f.Len())
197
198	uassert.True(t, f.Set(pad(0), "updated"), "a full map still accepts updates")
199	v, _ := f.Get(pad(0))
200	uassert.Equal(t, "updated", v)
201}
202
203// TestDescendingInsertionIsTheSlowPath exercises the worst case for a sorted
204// vector — every insert shifts the whole tail — and checks it stays correct.
205func TestDescendingInsertionIsTheSlowPath(t *testing.T) {
206	f := New()
207	for i := 200; i > 0; i-- {
208		f.Set(pad(i), strconv.Itoa(i))
209	}
210	uassert.Equal(t, 200, f.Len())
211	uassert.True(t, f.Sorted(), "still sorted after 200 head insertions")
212
213	k, v, _ := f.At(0)
214	uassert.Equal(t, pad(1), k)
215	uassert.Equal(t, "1", v, "keys and values must stay in step through every shift")
216}
217
218func collect(f *FlatMap, lo, hi string) string {
219	var out []string
220	f.Range(lo, hi, func(k, v string) bool {
221		out = append(out, k)
222		return false
223	})
224	return strings.Join(out, ",")
225}
226
227// pad zero-pads so string order matches numeric order. ufmt has no width
228// flags in gno, so this is done by hand.
229func pad(i int) string {
230	s := strconv.Itoa(i)
231	for len(s) < 6 {
232		s = "0" + s
233	}
234	return s
235}