bidimap_test.gno
6.68 Kb · 254 lines
1package bidimap
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.Equal(t, 0, m.Len())
14 uassert.False(t, m.Has("a"))
15 uassert.False(t, m.HasValue("1"))
16 uassert.True(t, m.Consistent(), "an empty map is consistent")
17}
18
19func TestPutAndBothLookups(t *testing.T) {
20 m := New()
21 _, ok := m.Put("alice", "admin")
22 uassert.True(t, ok)
23
24 v, found := m.Get("alice")
25 uassert.True(t, found)
26 uassert.Equal(t, "admin", v)
27
28 k, found := m.GetKey("admin")
29 uassert.True(t, found)
30 uassert.Equal(t, "alice", k, "the reverse lookup is the point of the type")
31
32 uassert.True(t, m.Has("alice"))
33 uassert.True(t, m.HasValue("admin"))
34 uassert.True(t, m.Consistent())
35}
36
37func TestMissingLookups(t *testing.T) {
38 m := New()
39 m.Put("a", "1")
40
41 _, ok := m.Get("nope")
42 uassert.False(t, ok)
43 _, ok = m.GetKey("nope")
44 uassert.False(t, ok)
45}
46
47// TestPutReplacesOnKeySide is the invariant that a naive pair-of-maps breaks:
48// rebinding a key must drop the old value from the reverse index too.
49func TestPutReplacesOnKeySide(t *testing.T) {
50 m := New()
51 m.Put("alice", "admin")
52
53 evicted, ok := m.Put("alice", "auditor")
54 uassert.True(t, ok)
55 uassert.Equal(t, 1, len(evicted))
56 uassert.Equal(t, "alice", evicted[0][0])
57 uassert.Equal(t, "admin", evicted[0][1])
58
59 uassert.False(t, m.HasValue("admin"), "the stale value must leave the reverse index")
60 uassert.Equal(t, 1, m.Len())
61 uassert.True(t, m.Consistent())
62}
63
64// TestPutReplacesOnValueSide is the mirror case: stealing a value must unbind
65// whoever held it.
66func TestPutReplacesOnValueSide(t *testing.T) {
67 m := New()
68 m.Put("alice", "admin")
69
70 evicted, ok := m.Put("bob", "admin")
71 uassert.True(t, ok)
72 uassert.Equal(t, 1, len(evicted))
73 uassert.Equal(t, "alice", evicted[0][0])
74
75 uassert.False(t, m.Has("alice"), "alice lost her binding to bob")
76 k, _ := m.GetKey("admin")
77 uassert.Equal(t, "bob", k)
78 uassert.Equal(t, 1, m.Len())
79 uassert.True(t, m.Consistent())
80}
81
82// TestPutEvictsBothSides covers the case where the new pair displaces two
83// different existing pairs at once.
84func TestPutEvictsBothSides(t *testing.T) {
85 m := New()
86 m.Put("alice", "admin")
87 m.Put("bob", "auditor")
88
89 evicted, ok := m.Put("alice", "auditor")
90 uassert.True(t, ok)
91 uassert.Equal(t, 2, len(evicted), "displaces alice->admin and bob->auditor")
92
93 uassert.Equal(t, 1, m.Len())
94 uassert.False(t, m.Has("bob"))
95 uassert.False(t, m.HasValue("admin"))
96 uassert.True(t, m.Consistent())
97}
98
99func TestPutIdenticalPairIsNoop(t *testing.T) {
100 m := New()
101 m.Put("a", "1")
102 evicted, ok := m.Put("a", "1")
103 uassert.True(t, ok)
104 uassert.Equal(t, 0, len(evicted), "re-putting the same pair evicts nothing")
105 uassert.Equal(t, 1, m.Len())
106}
107
108func TestPutUniqueRefuses(t *testing.T) {
109 m := New()
110 uassert.True(t, m.PutUnique("alice", "admin"))
111
112 uassert.False(t, m.PutUnique("alice", "auditor"), "key already bound")
113 uassert.False(t, m.PutUnique("bob", "admin"), "value already bound")
114 uassert.True(t, m.PutUnique("alice", "admin"), "identical pair is idempotent")
115
116 // Nothing changed.
117 uassert.Equal(t, 1, m.Len())
118 v, _ := m.Get("alice")
119 uassert.Equal(t, "admin", v)
120 uassert.True(t, m.Consistent())
121}
122
123func TestDelete(t *testing.T) {
124 m := New()
125 m.Put("a", "1")
126
127 uassert.True(t, m.Delete("a"))
128 uassert.Equal(t, 0, m.Len())
129 uassert.False(t, m.HasValue("1"), "delete clears the reverse index too")
130 uassert.False(t, m.Delete("a"), "deleting twice reports false")
131 uassert.True(t, m.Consistent())
132}
133
134func TestDeleteValue(t *testing.T) {
135 m := New()
136 m.Put("a", "1")
137
138 uassert.True(t, m.DeleteValue("1"))
139 uassert.False(t, m.Has("a"), "delete-by-value clears the forward index too")
140 uassert.False(t, m.DeleteValue("1"))
141 uassert.True(t, m.Consistent())
142}
143
144// TestKeysAndValuesAreSorted is the determinism guarantee.
145func TestKeysAndValuesAreSorted(t *testing.T) {
146 m := New()
147 m.Put("delta", "4")
148 m.Put("alpha", "1")
149 m.Put("charlie", "3")
150
151 uassert.Equal(t, "alpha,charlie,delta", strings.Join(m.Keys(), ","))
152 uassert.Equal(t, "1,3,4", strings.Join(m.Values(), ","))
153}
154
155func TestIterateSortedAndStops(t *testing.T) {
156 m := New()
157 m.Put("b", "2")
158 m.Put("a", "1")
159 m.Put("c", "3")
160
161 var seen []string
162 m.Iterate(func(k, v string) bool {
163 seen = append(seen, k+"="+v)
164 return false
165 })
166 uassert.Equal(t, "a=1,b=2,c=3", strings.Join(seen, ","))
167
168 var first []string
169 m.Iterate(func(k, v string) bool {
170 first = append(first, k)
171 return true // stop immediately
172 })
173 uassert.Equal(t, 1, len(first))
174 uassert.Equal(t, "a", first[0])
175}
176
177func TestInvert(t *testing.T) {
178 m := New()
179 m.Put("alice", "admin")
180 m.Put("bob", "auditor")
181
182 inv := m.Invert()
183 v, ok := inv.Get("admin")
184 uassert.True(t, ok)
185 uassert.Equal(t, "alice", v)
186 uassert.True(t, inv.Consistent())
187
188 // Independent of the original.
189 inv.Delete("admin")
190 uassert.Equal(t, 2, m.Len())
191}
192
193func TestClone(t *testing.T) {
194 m := New()
195 m.Put("a", "1")
196
197 cp := m.Clone()
198 cp.Put("b", "2")
199
200 uassert.Equal(t, 1, m.Len(), "clone must not share storage")
201 uassert.Equal(t, 2, cp.Len())
202 uassert.True(t, cp.Consistent())
203}
204
205func TestMaxPairs(t *testing.T) {
206 m := New()
207 for i := 0; i < MaxPairs; i++ {
208 s := strconv.Itoa(i)
209 _, ok := m.Put("k"+s, "v"+s)
210 uassert.True(t, ok, "should accept up to MaxPairs")
211 }
212 uassert.Equal(t, MaxPairs, m.Len())
213
214 _, ok := m.Put("overflow", "value")
215 uassert.False(t, ok, "a full map refuses a wholly new pair")
216 uassert.False(t, m.PutUnique("overflow", "value"))
217 uassert.Equal(t, MaxPairs, m.Len())
218}
219
220// TestFullMapStillRebinds pins the subtler half of the capacity rule: a full
221// map still accepts a Put that rebinds an existing key or steals an existing
222// value, because that reuses a slot rather than growing the map. Only a pair
223// new on BOTH sides is refused.
224func TestFullMapStillRebinds(t *testing.T) {
225 m := New()
226 for i := 0; i < MaxPairs; i++ {
227 s := strconv.Itoa(i)
228 m.Put("k"+s, "v"+s)
229 }
230
231 // New value, existing key -> reuses k0's slot, so it is allowed.
232 evicted, ok := m.Put("k0", "brand-new-value")
233 uassert.True(t, ok, "rebinding an existing key does not grow a full map")
234 uassert.Equal(t, 1, len(evicted))
235 uassert.Equal(t, "v0", evicted[0][1])
236
237 v, _ := m.Get("k0")
238 uassert.Equal(t, "brand-new-value", v)
239 uassert.Equal(t, MaxPairs, m.Len(), "size is unchanged")
240 uassert.True(t, m.Consistent())
241
242 // New key, existing value -> reuses that value's slot, also allowed.
243 _, ok = m.Put("brand-new-key", "v1")
244 uassert.True(t, ok, "stealing an existing value does not grow a full map")
245 uassert.Equal(t, MaxPairs, m.Len())
246 uassert.False(t, m.Has("k1"), "k1 lost its binding")
247 uassert.True(t, m.Consistent())
248
249 // New on both sides -> refused, and nothing changes.
250 _, ok = m.Put("wholly", "new")
251 uassert.False(t, ok, "a full map refuses a pair new on both sides")
252 uassert.Equal(t, MaxPairs, m.Len())
253 uassert.True(t, m.Consistent())
254}
