Debian Codegraph @

test/include/srfi-146-hash-tests.scm

raw
1 ;; -*- coding:utf-8 -*-
2 ;; Copyright (C) Marc Nieper-Wißkirchen (2016, 2017). All Rights
3 ;; Reserved.
4
5 ;; Permission is hereby granted, free of charge, to any person
6 ;; obtaining a copy of this software and associated documentation
7 ;; files (the "Software"), to deal in the Software without
8 ;; restriction, including without limitation the rights to use, copy,
9 ;; modify, merge, publish, distribute, sublicense, and/or sell copies
10 ;; of the Software, and to permit persons to whom the Software is
11 ;; furnished to do so, subject to the following conditions:
12
13 ;; The above copyright notice and this permission notice shall be
14 ;; included in all copies or substantial portions of the Software.
15
16 ;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 ;; EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 ;; MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
19 ;; NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
20 ;; BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
21 ;; ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
22 ;; CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 ;; SOFTWARE.
24
25 (define-library (srfi 146 hash test)
26 (export run-tests)
27 (import (scheme base)
28 (srfi 1)
29 (srfi 8)
30 (srfi 64)
31 (srfi 146 hash)
32 (srfi 128))
33 (begin
34 (define comparator (make-default-comparator))
35
36 (define (run-tests)
37 (test-begin "SRFI 146: Hashmaps")
38
39 (test-group "Predicates"
40 (define hashmap0 (hashmap comparator))
41 (define hashmap1 (hashmap comparator 'a 1 'b 2 'c 3))
42 (define hashmap2 (hashmap comparator 'c 1 'd 2 'e 3))
43 (define hashmap3 (hashmap comparator 'd 1 'e 2 'f 3))
44
45 (test-assert "hashmap?: a hashmap"
46 (hashmap? (hashmap comparator)))
47
48 (test-assert "hashmap?: not a hashmap"
49 (not (hashmap? (list 1 2 3))))
50
51 (test-assert "hashmap-empty?: empty hashmap"
52 (hashmap-empty? hashmap0))
53
54 (test-assert "hashmap-empty?: non-empty hashmap"
55 (not (hashmap-empty? hashmap1)))
56
57 (test-assert "hashmap-contains?: containing"
58 (hashmap-contains? hashmap1 'b))
59
60 (test-assert "hashmap-contains?: not containing"
61 (not (hashmap-contains? hashmap1 '2)))
62
63 (test-assert "hashmap-disjoint?: disjoint"
64 (hashmap-disjoint? hashmap1 hashmap3))
65
66 (test-assert "hashmap-disjoint?: not disjoint"
67 (not (hashmap-disjoint? hashmap1 hashmap2))))
68
69 (test-group "Accessors"
70 (define hashmap1 (hashmap comparator 'a 1 'b 2 'c 3))
71
72 (test-equal "hashmap-ref: key found"
73 2
74 (hashmap-ref hashmap1 'b))
75
76 (test-equal "hashmap-ref: key not found/with failure"
77 42
78 (hashmap-ref hashmap1 'd (lambda () 42)))
79
80 (test-error "hashmap-ref: key not found/without failure"
81 (hashmap-ref hashmap1 'd))
82
83 (test-equal "hashmap-ref: with success procedure"
84 (* 2 2)
85 (hashmap-ref hashmap1 'b (lambda () #f) (lambda (x) (* x x))))
86
87 (test-equal "hashmap-ref/default: key found"
88 3
89 (hashmap-ref/default hashmap1 'c 42))
90
91 (test-equal "hashmap-ref/default: key not found"
92 42
93 (hashmap-ref/default hashmap1 'd 42))
94
95 (test-equal "hashmap-key-comparator"
96 comparator
97 (hashmap-key-comparator hashmap1)))
98
99 (test-group "Updaters"
100 (define hashmap1 (hashmap comparator 'a 1 'b 2 'c 3))
101 (define hashmap2 (hashmap-set hashmap1 'c 4 'd 4 'd 5))
102 (define hashmap3 (hashmap-update hashmap1 'b (lambda (x) (* x x))))
103 (define hashmap4 (hashmap-update/default hashmap1 'd (lambda (x) (* x x)) 4))
104 (define hashmap5 (hashmap-adjoin hashmap1 'c 4 'd 4 'd 5))
105 (define hashmap0 (hashmap comparator))
106
107 (test-equal "hashmap-adjoin: key already in hashmap"
108 3
109 (hashmap-ref hashmap5 'c))
110
111 (test-equal "hashmap-adjoin: key set earlier"
112 4
113 (hashmap-ref hashmap5 'd))
114
115 (test-equal "hashmap-set: key already in hashmap"
116 4
117 (hashmap-ref hashmap2 'c))
118
119 (test-equal "hashmap-set: key set earlier"
120 5
121 (hashmap-ref hashmap2 'd))
122
123 (test-equal "hashmap-replace: key not in hashmap"
124 #f
125 (hashmap-ref/default (hashmap-replace hashmap1 'd 4) 'd #f))
126
127 (test-equal "hashmap-replace: key in hashmap"
128 6
129 (hashmap-ref (hashmap-replace hashmap1 'c 6) 'c))
130
131 (test-equal "hashmap-delete"
132 42
133 (hashmap-ref/default (hashmap-delete hashmap1 'b) 'b 42))
134
135 (test-equal "hashmap-delete-all"
136 42
137 (hashmap-ref/default (hashmap-delete-all hashmap1 '(a b)) 'b 42))
138
139 (test-equal "hashmap-intern: key in hashmap"
140 (list hashmap1 2)
141 (receive result
142 (hashmap-intern hashmap1 'b (lambda () (error "should not have been invoked")))
143 result))
144
145 (test-equal "hashmap-intern: key not in hashmap"
146 (list 42 42)
147 (receive (hashmap value)
148 (hashmap-intern hashmap1 'd (lambda () 42))
149 (list value (hashmap-ref hashmap 'd))))
150
151 (test-equal "hashmap-update"
152 4
153 (hashmap-ref hashmap3 'b))
154
155 (test-equal "hashmap-update/default"
156 16
157 (hashmap-ref hashmap4 'd))
158
159 (test-equal "hashmap-pop: empty hashmap"
160 'empty
161 (hashmap-pop hashmap0 (lambda () 'empty)))
162
163 (test-assert "hashmap-pop: non-empty hashmap"
164 (member
165 (receive (hashmap key value)
166 (hashmap-pop hashmap1)
167 (list (hashmap-size hashmap) key value))
168 '((2 a 1) (2 b 2) (2 c 3)))))
169
170 (test-group "The whole hashmap"
171 (define hashmap0 (hashmap comparator))
172 (define hashmap1 (hashmap comparator 'a 1 'b 2 'c 3))
173
174 (test-equal "hashmap-size: empty hashmap"
175 0
176 (hashmap-size hashmap0))
177
178 (test-equal "hashmap-size: non-empty hashmap"
179 3
180 (hashmap-size hashmap1))
181
182 (test-equal "hashmap-find: found in hashmap"
183 (list 'b 2)
184 (receive result
185 (hashmap-find (lambda (key value)
186 (and (eq? key 'b)
187 (= value 2)))
188 hashmap1
189 (lambda () (error "should not have been called")))
190 result))
191
192 (test-equal "hashmap-find: not found in hashmap"
193 (list 42)
194 (receive result
195 (hashmap-find (lambda (key value)
196 (eq? key 'd))
197 hashmap1
198 (lambda ()
199 42))
200 result))
201
202 (test-equal "hashmap-count"
203 2
204 (hashmap-count (lambda (key value)
205 (>= value 2))
206 hashmap1))
207
208 (test-assert "hashmap-any?: found"
209 (hashmap-any? (lambda (key value)
210 (= value 3))
211 hashmap1))
212
213 (test-assert "hashmap-any?: not found"
214 (not (hashmap-any? (lambda (key value)
215 (= value 4))
216 hashmap1)))
217
218 (test-assert "hashmap-every?: true"
219 (hashmap-every? (lambda (key value)
220 (<= value 3))
221 hashmap1))
222
223 (test-assert "hashmap-every?: false"
224 (not (hashmap-every? (lambda (key value)
225 (<= value 2))
226 hashmap1)))
227
228 (test-equal "hashmap-keys"
229 3
230 (length (hashmap-keys hashmap1)))
231
232 (test-equal "hashmap-values"
233 6
234 (fold + 0 (hashmap-values hashmap1)))
235
236 (test-equal "hashmap-entries"
237 (list 3 6)
238 (receive (keys values)
239 (hashmap-entries hashmap1)
240 (list (length keys) (fold + 0 values)))))
241
242 (test-group "Hashmap and folding"
243 (define hashmap1 (hashmap comparator 'a 1 'b 2 'c 3))
244 (define hashmap2 (hashmap-map (lambda (key value)
245 (values (symbol->string key)
246 (* 10 value)))
247 comparator
248 hashmap1))
249
250 (test-equal "hashmap-map"
251 20
252 (hashmap-ref hashmap2 "b"))
253
254 (test-equal "hashmap-for-each"
255 6
256 (let ((counter 0))
257 (hashmap-for-each (lambda (key value)
258 (set! counter (+ counter value)))
259 hashmap1)
260 counter))
261
262 (test-equal "hashmap-fold"
263 6
264 (hashmap-fold (lambda (key value acc)
265 (+ value acc))
266 0
267 hashmap1))
268
269 (test-equal "hashmap-map->list"
270 (+ (* 1 1) (* 2 2) (* 3 3))
271 (fold + 0 (hashmap-map->list (lambda (key value)
272 (* value value))
273 hashmap1)))
274
275 (test-equal "hashmap-filter"
276 2
277 (hashmap-size (hashmap-filter (lambda (key value)
278 (<= value 2))
279 hashmap1)))
280
281 (test-equal "hashmap-remove"
282 1
283 (hashmap-size (hashmap-remove (lambda (key value)
284 (<= value 2))
285 hashmap1)))
286
287 (test-equal "hashmap-partition"
288 (list 1 2)
289 (receive result
290 (hashmap-partition (lambda (key value)
291 (eq? 'b key))
292 hashmap1)
293 (map hashmap-size result)))
294
295 (test-group "Copying and conversion"
296 (define hashmap1 (hashmap comparator 'a 1 'b 2 'c 3))
297 (define hashmap2 (alist->hashmap comparator '((a . 1) (b . 2) (c . 3))))
298 (define hashmap3 (alist->hashmap! (hashmap-copy hashmap1) '((d . 4) '(c . 5))))
299
300 (test-equal "hashmap-copy: same size"
301 3
302 (hashmap-size (hashmap-copy hashmap1)))
303
304 (test-equal "hashmap-copy: same comparator"
305 comparator
306 (hashmap-key-comparator (hashmap-copy hashmap1)))
307
308 (test-equal "hashmap->alist"
309 (cons 'b 2)
310 (assq 'b (hashmap->alist hashmap1)))
311
312 (test-equal "alist->hashmap"
313 2
314 (hashmap-ref hashmap2 'b)
315 )
316
317 (test-equal "alist->hashmap!: new key"
318 4
319 (hashmap-ref hashmap3 'd))
320
321 (test-equal "alist->hashmap!: existing key"
322 3
323 (hashmap-ref hashmap3 'c)))
324
325 (test-group "Subhashmaps"
326 (define hashmap1 (hashmap comparator 'a 1 'b 2 'c 3))
327 (define hashmap2 (hashmap comparator 'a 1 'b 2 'c 3))
328 (define hashmap3 (hashmap comparator 'a 1 'c 3))
329 (define hashmap4 (hashmap comparator 'a 1 'c 3 'd 4))
330 (define hashmap5 (hashmap comparator 'a 1 'b 2 'c 6))
331 (define hashmap6 (hashmap (make-comparator (comparator-type-test-predicate comparator)
332 (comparator-equality-predicate comparator)
333 (comparator-ordering-predicate comparator)
334 (comparator-hash-function comparator))
335 'a 1 'b 2 'c 3))
336
337
338 (test-assert "hashmap=?: equal hashmaps"
339 (hashmap=? comparator hashmap1 hashmap2))
340
341 (test-assert "hashmap=?: unequal hashmaps"
342 (not (hashmap=? comparator hashmap1 hashmap4)))
343
344 (test-assert "hashmap=?: different comparators"
345 (not (hashmap=? comparator hashmap1 hashmap6)))
346
347 (test-assert "hashmap<?: proper subset"
348 (hashmap<? comparator hashmap3 hashmap1))
349
350 (test-assert "hashmap<?: improper subset"
351 (not (hashmap<? comparator hashmap3 hashmap1 hashmap2)))
352
353 (test-assert "hashmap>?: proper superset"
354 (hashmap>? comparator hashmap2 hashmap3))
355
356 (test-assert "hashmap>?: improper superset"
357 (not (hashmap>? comparator hashmap1 hashmap2 hashmap3)))
358
359 (test-assert "hashmap<=?: subset"
360 (hashmap<=? comparator hashmap3 hashmap2 hashmap1))
361
362 (test-assert "hashmap<=?: non-matching values"
363 (not (hashmap<=? comparator hashmap3 hashmap5)))
364
365 (test-assert "hashmap<=?: not a subset"
366 (not (hashmap<=? comparator hashmap2 hashmap4)))
367
368 (test-assert "hashmap>=?: superset"
369 (hashmap>=? comparator hashmap4 hashmap3))
370
371 (test-assert "hashmap>=?: not a superset"
372 (not (hashmap>=? comparator hashmap5 hashmap3))))
373
374 (test-group "Set theory operations"
375 (define hashmap1 (hashmap comparator 'a 1 'b 2 'c 3))
376 (define hashmap2 (hashmap comparator 'a 1 'b 2 'd 4))
377 (define hashmap3 (hashmap comparator 'a 1 'b 2))
378 (define hashmap4 (hashmap comparator 'a 1 'b 2 'c 4))
379 (define hashmap5 (hashmap comparator 'a 1 'c 3))
380 (define hashmap6 (hashmap comparator 'd 4 'e 5 'f 6))
381
382 (test-equal "hashmap-union: new association"
383 4
384 (hashmap-ref (hashmap-union hashmap1 hashmap2) 'd))
385
386 (test-equal "hashmap-union: existing association"
387 3
388 (hashmap-ref (hashmap-union hashmap1 hashmap4) 'c))
389
390 (test-equal "hashmap-union: three hashmaps"
391 6
392 (hashmap-size (hashmap-union hashmap1 hashmap2 hashmap6)))
393
394 (test-equal "hashmap-intersection: existing association"
395 3
396 (hashmap-ref (hashmap-intersection hashmap1 hashmap4) 'c))
397
398 (test-equal "hashmap-intersection: removed association"
399 42
400 (hashmap-ref/default (hashmap-intersection hashmap1 hashmap5) 'b 42))
401
402 (test-equal "hashmap-difference"
403 2
404 (hashmap-size (hashmap-difference hashmap2 hashmap6)))
405
406 (test-equal "hashmap-xor"
407 4
408 (hashmap-size (hashmap-xor hashmap2 hashmap6))))
409
410 (test-group "Comparators"
411 (define hashmap1 (hashmap comparator 'a 1 'b 2 'c 3))
412 (define hashmap2 (hashmap comparator 'a 1 'b 2 'c 3))
413 (define hashmap3 (hashmap comparator 'a 1 'b 2))
414 (define hashmap4 (hashmap comparator 'a 1 'b 2 'c 4))
415 (define hashmap5 (hashmap comparator 'a 1 'c 3))
416 (define hashmap0 (hashmap comparator
417 hashmap1 "a"
418 hashmap2 "b"
419 hashmap3 "c"
420 hashmap4 "d"
421 hashmap5 "e"))
422
423 (test-assert "hashmap-comparator"
424 (comparator? hashmap-comparator))
425
426 (test-equal "hashmap-keyed hashmap"
427 (list "a" "a" "c" "d" "e")
428 (list (hashmap-ref hashmap0 hashmap1)
429 (hashmap-ref hashmap0 hashmap2)
430 (hashmap-ref hashmap0 hashmap3)
431 (hashmap-ref hashmap0 hashmap4)
432 (hashmap-ref hashmap0 hashmap5)
433 ))
434
435 (test-group "Ordering comparators"
436 (test-assert "=?: equal hashmaps"
437 (=? comparator hashmap1 hashmap2))
438
439 (test-assert "=?: unequal hashmaps"
440 (not (=? comparator hashmap1 hashmap4))))))
441
442 (test-end "SRFI 146: Hashmaps"))))