| 1 |
;;; Copyright (C) William D Clinger 2015. All Rights Reserved. |
| 2 |
;;; |
| 3 |
;;; Permission is hereby granted, free of charge, to any person |
| 4 |
;;; obtaining a copy of this software and associated documentation |
| 5 |
;;; files (the "Software"), to deal in the Software without restriction, |
| 6 |
;;; including without limitation the rights to use, copy, modify, merge, |
| 7 |
;;; publish, distribute, sublicense, and/or sell copies of the Software, |
| 8 |
;;; and to permit persons to whom the Software is furnished to do so, |
| 9 |
;;; subject to the following conditions: |
| 10 |
;;; |
| 11 |
;;; The above copyright notice and this permission notice shall be |
| 12 |
;;; included in all copies or substantial portions of the Software. |
| 13 |
;;; |
| 14 |
;;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
| 15 |
;;; EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
| 16 |
;;; MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. |
| 17 |
;;; IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY |
| 18 |
;;; CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, |
| 19 |
;;; TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE |
| 20 |
;;; SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
| 21 |
|
| 22 |
;;; [SK] test, test-assert and test-deny are commented out - provided by |
| 23 |
;;; test/srfi.scm |
| 24 |
;;; Gauche doesn't support immutable hashtables, so tests of hash-talbe-mutable? |
| 25 |
;;; are commented out. |
| 26 |
|
| 27 |
;;; This is a very shallow sanity test for hash tables. |
| 28 |
;;; |
| 29 |
;;; Tests marked by a "FIXME: glass-box" comment test behavior of the |
| 30 |
;;; reference implementation that is not required by the specification. |
| 31 |
|
| 32 |
(import (scheme base) |
| 33 |
(scheme char) |
| 34 |
(scheme write) |
| 35 |
(only (scheme process-context) exit) |
| 36 |
(scheme comparator) ; was (srfi 128) |
| 37 |
(only (scheme sort) list-sort) ; was (r6rs sorting) |
| 38 |
(rename (srfi 125) |
| 39 |
(string-hash deprecated:string-hash) |
| 40 |
(string-ci-hash deprecated:string-ci-hash))) |
| 41 |
|
| 42 |
(define (writeln . xs) |
| 43 |
(for-each write xs) |
| 44 |
(newline)) |
| 45 |
|
| 46 |
(define (displayln . xs) |
| 47 |
(for-each display xs) |
| 48 |
(newline)) |
| 49 |
|
| 50 |
(define ultimate-exit-status 0) |
| 51 |
|
| 52 |
(define (fail token . more) |
| 53 |
(set! ultimate-exit-status 1) |
| 54 |
(displayln "Error: test failed: ") |
| 55 |
(writeln token) |
| 56 |
(if (not (null? more)) |
| 57 |
(for-each writeln more)) |
| 58 |
(newline) |
| 59 |
#f) |
| 60 |
|
| 61 |
;;; FIXME: when debugging catastrophic failures, printing every expression |
| 62 |
;;; before it's executed may help. |
| 63 |
|
| 64 |
'(define-syntax test |
| 65 |
(syntax-rules () |
| 66 |
((_ expr expected) |
| 67 |
(let () |
| 68 |
; (write 'expr) (newline) |
| 69 |
(let ((actual expr)) |
| 70 |
(or (equal? actual expected) |
| 71 |
(fail 'expr actual expected))))))) |
| 72 |
|
| 73 |
'(define-syntax test-assert |
| 74 |
(syntax-rules () |
| 75 |
((_ expr) |
| 76 |
(or expr (fail 'expr))))) |
| 77 |
|
| 78 |
'(define-syntax test-deny |
| 79 |
(syntax-rules () |
| 80 |
((_ expr) |
| 81 |
(or (not expr) (fail 'expr))))) |
| 82 |
|
| 83 |
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| 84 |
;;; |
| 85 |
;;; Transition from SRFI 114 to SRFI 128. |
| 86 |
;;; |
| 87 |
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| 88 |
|
| 89 |
(define default-comparator (make-default-comparator)) |
| 90 |
|
| 91 |
;;; SRFI 128 says the following definition will work, but that's |
| 92 |
;;; an error in SRFI 128; the hash function produce non-integers. |
| 93 |
|
| 94 |
#; |
| 95 |
(define number-comparator |
| 96 |
(make-comparator real? = < (lambda (x) (exact (abs x))))) |
| 97 |
|
| 98 |
(define number-comparator |
| 99 |
(make-comparator real? = < (lambda (x) (exact (abs (round x)))))) |
| 100 |
|
| 101 |
(define string-comparator |
| 102 |
(make-comparator string? string=? string<? string-hash)) |
| 103 |
|
| 104 |
(define string-ci-comparator |
| 105 |
(make-comparator string? string-ci=? string-ci<? string-ci-hash)) |
| 106 |
|
| 107 |
(define eq-comparator (make-eq-comparator)) |
| 108 |
|
| 109 |
(define eqv-comparator (make-eqv-comparator)) |
| 110 |
|
| 111 |
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| 112 |
;;; |
| 113 |
;;; Transition from earlier draft of SRFI 125 to this draft. |
| 114 |
;;; |
| 115 |
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| 116 |
|
| 117 |
;;; Returns an immutable hash table. |
| 118 |
|
| 119 |
(define (hash-table-tabulate comparator n proc) |
| 120 |
(let ((ht (make-hash-table comparator))) |
| 121 |
(do ((i 0 (+ i 1))) |
| 122 |
((= i n) |
| 123 |
(hash-table-copy ht)) |
| 124 |
(call-with-values |
| 125 |
(lambda () |
| 126 |
(proc i)) |
| 127 |
(lambda (key val) |
| 128 |
(hash-table-set! ht key val)))))) |
| 129 |
|
| 130 |
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| 131 |
|
| 132 |
;;; Constructors. |
| 133 |
|
| 134 |
(define ht-default (make-hash-table default-comparator)) |
| 135 |
|
| 136 |
(define ht-eq (make-hash-table eq-comparator 'random-argument "another")) |
| 137 |
|
| 138 |
(define ht-eqv (make-hash-table eqv-comparator)) |
| 139 |
|
| 140 |
(define ht-eq2 (make-hash-table eq?)) |
| 141 |
|
| 142 |
(define ht-eqv2 (make-hash-table eqv?)) |
| 143 |
|
| 144 |
(define ht-equal (make-hash-table equal?)) |
| 145 |
|
| 146 |
(define ht-string (make-hash-table string=?)) |
| 147 |
|
| 148 |
(define ht-string-ci (make-hash-table string-ci=?)) |
| 149 |
|
| 150 |
(define ht-symbol (make-hash-table symbol=?)) ; FIXME: glass-box |
| 151 |
|
| 152 |
(define ht-fixnum (make-hash-table = abs)) |
| 153 |
|
| 154 |
(define ht-default2 |
| 155 |
(hash-table default-comparator 'foo 'bar 101.3 "fever" '(x y z) '#())) |
| 156 |
|
| 157 |
(define ht-fixnum2 |
| 158 |
(hash-table-tabulate number-comparator |
| 159 |
10 |
| 160 |
(lambda (i) (values (* i i) i)))) |
| 161 |
|
| 162 |
(define ht-string2 |
| 163 |
(hash-table-unfold (lambda (s) (= 0 (string-length s))) |
| 164 |
(lambda (s) (values s (string-length s))) |
| 165 |
(lambda (s) (substring s 0 (- (string-length s) 1))) |
| 166 |
"prefixes" |
| 167 |
string-comparator |
| 168 |
'ignored1 'ignored2 "ignored3" '#(ignored 4 5))) |
| 169 |
|
| 170 |
(define ht-string-ci2 |
| 171 |
(alist->hash-table '(("" . 0) ("Mary" . 4) ("Paul" . 4) ("Peter" . 5)) |
| 172 |
string-ci-comparator |
| 173 |
"ignored1" 'ignored2)) |
| 174 |
|
| 175 |
(define ht-symbol2 |
| 176 |
(alist->hash-table '((mary . travers) (noel . stookey) (peter .yarrow)) |
| 177 |
eq?)) |
| 178 |
|
| 179 |
(define ht-equal2 |
| 180 |
(alist->hash-table '(((edward) . abbey) |
| 181 |
((dashiell) . hammett) |
| 182 |
((edward) . teach) |
| 183 |
((mark) . twain)) |
| 184 |
equal? |
| 185 |
(comparator-hash-function default-comparator))) |
| 186 |
|
| 187 |
(define test-tables |
| 188 |
(list ht-default ht-default2 ; initial keys: foo, 101.3, (x y z) |
| 189 |
ht-eq ht-eq2 ; initially empty |
| 190 |
ht-eqv ht-eqv2 ; initially empty |
| 191 |
ht-equal ht-equal2 ; initial keys: (edward), (dashiell), (mark) |
| 192 |
ht-string ht-string2 ; initial keys: "p, "pr", ..., "prefixes" |
| 193 |
ht-string-ci ht-string-ci2 ; initial keys: "", "Mary", "Paul", "Peter" |
| 194 |
ht-symbol ht-symbol2 ; initial keys: mary, noel, peter |
| 195 |
ht-fixnum ht-fixnum2)) ; initial keys: 0, 1, 4, 9, ..., 81 |
| 196 |
|
| 197 |
;;; Predicates |
| 198 |
|
| 199 |
(test (map hash-table? |
| 200 |
(cons '#() |
| 201 |
(cons default-comparator |
| 202 |
test-tables))) |
| 203 |
(append '(#f #f) (map (lambda (x) #t) test-tables))) |
| 204 |
|
| 205 |
(test (map hash-table-contains? |
| 206 |
test-tables |
| 207 |
'(foo 101.3 |
| 208 |
x "y" |
| 209 |
(14 15) #\newline |
| 210 |
(edward) (mark) |
| 211 |
"p" "pref" |
| 212 |
"mike" "PAUL" |
| 213 |
jane noel |
| 214 |
0 4)) |
| 215 |
'(#f #t #f #f #f #f #f #t #f #t #f #t #f #t #f #t)) |
| 216 |
|
| 217 |
(test (map hash-table-contains? |
| 218 |
test-tables |
| 219 |
'(#u8() 47.9 |
| 220 |
'#() '() |
| 221 |
foo bar |
| 222 |
19 (henry) |
| 223 |
"p" "perp" |
| 224 |
"mike" "Noel" |
| 225 |
jane paul |
| 226 |
0 5)) |
| 227 |
(map (lambda (x) #f) test-tables)) |
| 228 |
|
| 229 |
(test (map hash-table-empty? test-tables) |
| 230 |
'(#t #f #t #t #t #t #t #f #t #f #t #f #t #f #t #f)) |
| 231 |
|
| 232 |
(test (map (lambda (ht1 ht2) (hash-table=? default-comparator ht1 ht2)) |
| 233 |
test-tables |
| 234 |
test-tables) |
| 235 |
(map (lambda (x) #t) test-tables)) |
| 236 |
|
| 237 |
;; [SK] This depends on hash-table=? implementation specifics |
| 238 |
'(test (map (lambda (ht1 ht2) (hash-table=? default-comparator ht1 ht2)) |
| 239 |
test-tables |
| 240 |
(do ((tables (reverse test-tables) (cddr tables)) |
| 241 |
(rev '() (cons (car tables) (cons (cadr tables) rev)))) |
| 242 |
((null? tables) |
| 243 |
rev))) |
| 244 |
'(#f #f #t #t #t #t #f #f #f #f #f #f #f #f #f #f)) |
| 245 |
|
| 246 |
'(test (map hash-table-mutable? test-tables) |
| 247 |
'(#t #f #t #t #t #t #t #t #t #t #t #t #t #t #t #f)) |
| 248 |
|
| 249 |
;;; FIXME: glass-box |
| 250 |
|
| 251 |
'(test (map hash-table-mutable? (map hash-table-copy test-tables)) |
| 252 |
(map (lambda (x) #f) test-tables)) |
| 253 |
|
| 254 |
'(test (hash-table-mutable? (hash-table-copy ht-fixnum2 #t)) |
| 255 |
#t) |
| 256 |
|
| 257 |
;;; Accessors. |
| 258 |
|
| 259 |
;;; FIXME: glass-box (implementations not required to raise an exception here) |
| 260 |
|
| 261 |
(test (map (lambda (ht) |
| 262 |
(guard (exn |
| 263 |
(else 'err)) |
| 264 |
(hash-table-ref ht 'not-a-key))) |
| 265 |
test-tables) |
| 266 |
(map (lambda (ht) 'err) test-tables)) |
| 267 |
|
| 268 |
;;; FIXME: glass-box (implementations not required to raise an exception here) |
| 269 |
|
| 270 |
(test (map (lambda (ht) |
| 271 |
(guard (exn |
| 272 |
(else 'err)) |
| 273 |
(hash-table-ref ht 'not-a-key (lambda () 'err)))) |
| 274 |
test-tables) |
| 275 |
(map (lambda (ht) 'err) test-tables)) |
| 276 |
|
| 277 |
;;; FIXME: glass-box (implementations not required to raise an exception here) |
| 278 |
|
| 279 |
(test (map (lambda (ht) |
| 280 |
(guard (exn |
| 281 |
(else 'err)) |
| 282 |
(hash-table-ref ht 'not-a-key (lambda () 'err) values))) |
| 283 |
test-tables) |
| 284 |
(map (lambda (ht) 'err) test-tables)) |
| 285 |
|
| 286 |
(test (map (lambda (ht key) |
| 287 |
(guard (exn |
| 288 |
(else 'err)) |
| 289 |
(hash-table-ref ht key))) |
| 290 |
test-tables |
| 291 |
'(foo 101.3 |
| 292 |
x "y" |
| 293 |
(14 15) #\newline |
| 294 |
(edward) (mark) |
| 295 |
"p" "pref" |
| 296 |
"mike" "PAUL" |
| 297 |
jane noel |
| 298 |
0 4)) |
| 299 |
'(err "fever" err err err err err twain err 4 err 4 err stookey err 2)) |
| 300 |
|
| 301 |
(test (map (lambda (ht key) |
| 302 |
(guard (exn |
| 303 |
(else 'err)) |
| 304 |
(hash-table-ref ht key (lambda () 'eh)))) |
| 305 |
test-tables |
| 306 |
'(foo 101.3 |
| 307 |
x "y" |
| 308 |
(14 15) #\newline |
| 309 |
(edward) (mark) |
| 310 |
"p" "pref" |
| 311 |
"mike" "PAUL" |
| 312 |
jane noel |
| 313 |
0 4)) |
| 314 |
'(eh "fever" eh eh eh eh eh twain eh 4 eh 4 eh stookey eh 2)) |
| 315 |
|
| 316 |
(test (map (lambda (ht key) |
| 317 |
(guard (exn |
| 318 |
(else 'err)) |
| 319 |
(hash-table-ref ht key (lambda () 'eh) list))) |
| 320 |
test-tables |
| 321 |
'(foo 101.3 |
| 322 |
x "y" |
| 323 |
(14 15) #\newline |
| 324 |
(edward) (mark) |
| 325 |
"p" "pref" |
| 326 |
"mike" "PAUL" |
| 327 |
jane noel |
| 328 |
0 4)) |
| 329 |
'(eh ("fever") eh eh eh eh eh (twain) eh (4) eh (4) eh (stookey) eh (2))) |
| 330 |
|
| 331 |
;;; FIXME: glass-box (implementations not required to raise an exception here) |
| 332 |
|
| 333 |
(test (map (lambda (ht) |
| 334 |
(guard (exn |
| 335 |
(else 'eh)) |
| 336 |
(hash-table-ref/default ht 'not-a-key 'eh))) |
| 337 |
test-tables) |
| 338 |
(map (lambda (ht) 'eh) test-tables)) |
| 339 |
|
| 340 |
(test (map (lambda (ht key) |
| 341 |
(guard (exn |
| 342 |
(else 'err)) |
| 343 |
(hash-table-ref/default ht key 'eh))) |
| 344 |
test-tables |
| 345 |
'(foo 101.3 |
| 346 |
x "y" |
| 347 |
(14 15) #\newline |
| 348 |
(edward) (mark) |
| 349 |
"p" "pref" |
| 350 |
"mike" "PAUL" |
| 351 |
jane noel |
| 352 |
0 4)) |
| 353 |
'(eh "fever" eh eh eh eh eh twain eh 4 eh 4 eh stookey eh 2)) |
| 354 |
|
| 355 |
(test (begin (hash-table-set! ht-fixnum) |
| 356 |
(list-sort < (hash-table-keys ht-fixnum))) |
| 357 |
'()) |
| 358 |
|
| 359 |
(test (begin (hash-table-set! ht-fixnum 121 11 144 12 169 13) |
| 360 |
(list-sort < (hash-table-keys ht-fixnum))) |
| 361 |
'(121 144 169)) |
| 362 |
|
| 363 |
(test (begin (hash-table-set! ht-fixnum |
| 364 |
0 0 1 1 4 2 9 3 16 4 25 5 36 6 49 7 64 8 81 9) |
| 365 |
(list-sort < (hash-table-keys ht-fixnum))) |
| 366 |
'(0 1 4 9 16 25 36 49 64 81 121 144 169)) |
| 367 |
|
| 368 |
(test (map (lambda (i) (hash-table-ref/default ht-fixnum i 'error)) |
| 369 |
'(169 144 121 0 1 4 9 16 25 36 49 64 81)) |
| 370 |
'(13 12 11 0 1 2 3 4 5 6 7 8 9)) |
| 371 |
|
| 372 |
(test (begin (hash-table-delete! ht-fixnum) |
| 373 |
(map (lambda (i) (hash-table-ref/default ht-fixnum i 'error)) |
| 374 |
'(169 144 121 0 1 4 9 16 25 36 49 64 81))) |
| 375 |
'(13 12 11 0 1 2 3 4 5 6 7 8 9)) |
| 376 |
|
| 377 |
(test (begin (hash-table-delete! ht-fixnum 1 9 25 49 81 200 121 169 81 1) |
| 378 |
(map (lambda (i) (hash-table-ref/default ht-fixnum i -1)) |
| 379 |
'(169 144 121 0 1 4 9 16 25 36 49 64 81))) |
| 380 |
'(-1 12 -1 0 -1 2 -1 4 -1 6 -1 8 -1)) |
| 381 |
|
| 382 |
(test (begin (hash-table-delete! ht-fixnum 200 100 0 81 36) |
| 383 |
(map (lambda (i) (hash-table-ref/default ht-fixnum i -1)) |
| 384 |
'(169 144 121 0 1 4 9 16 25 36 49 64 81))) |
| 385 |
'(-1 12 -1 -1 -1 2 -1 4 -1 -1 -1 8 -1)) |
| 386 |
|
| 387 |
(test (begin (hash-table-intern! ht-fixnum 169 (lambda () 13)) |
| 388 |
(hash-table-intern! ht-fixnum 121 (lambda () 11)) |
| 389 |
(hash-table-intern! ht-fixnum 0 (lambda () 0)) |
| 390 |
(hash-table-intern! ht-fixnum 1 (lambda () 1)) |
| 391 |
(hash-table-intern! ht-fixnum 1 (lambda () 99)) |
| 392 |
(hash-table-intern! ht-fixnum 121 (lambda () 66)) |
| 393 |
(map (lambda (i) (hash-table-ref/default ht-fixnum i -1)) |
| 394 |
'(169 144 121 0 1 4 9 16 25 36 49 64 81))) |
| 395 |
'(13 12 11 0 1 2 -1 4 -1 -1 -1 8 -1)) |
| 396 |
|
| 397 |
(test (list-sort (lambda (v1 v2) (< (vector-ref v1 0) (vector-ref v2 0))) |
| 398 |
(hash-table-map->list vector ht-fixnum)) |
| 399 |
'(#(0 0) #(1 1) #(4 2) #(16 4) #(64 8) #(121 11) #(144 12) #(169 13))) |
| 400 |
|
| 401 |
(test (begin (hash-table-prune! (lambda (key val) |
| 402 |
(and (odd? key) (> val 10))) |
| 403 |
ht-fixnum) |
| 404 |
(list-sort (lambda (l1 l2) |
| 405 |
(< (car l1) (car l2))) |
| 406 |
(hash-table-map->list list ht-fixnum))) |
| 407 |
'((0 0) (1 1) (4 2) (16 4) (64 8) #;(121 11) (144 12) #;(169 13))) |
| 408 |
|
| 409 |
(test (begin (hash-table-intern! ht-fixnum 169 (lambda () 13)) |
| 410 |
(hash-table-intern! ht-fixnum 144 (lambda () 9999)) |
| 411 |
(hash-table-intern! ht-fixnum 121 (lambda () 11)) |
| 412 |
(list-sort (lambda (l1 l2) |
| 413 |
(< (car l1) (car l2))) |
| 414 |
(hash-table-map->list list ht-fixnum))) |
| 415 |
'((0 0) (1 1) (4 2) (16 4) (64 8) (121 11) (144 12) (169 13))) |
| 416 |
|
| 417 |
(test (begin (hash-table-update! ht-fixnum 9 length (lambda () '(a b c))) |
| 418 |
(map (lambda (i) (hash-table-ref/default ht-fixnum i -1)) |
| 419 |
'(169 144 121 0 1 4 9 16 25 36 49 64 81))) |
| 420 |
'(13 12 11 0 1 2 3 4 -1 -1 -1 8 -1)) |
| 421 |
|
| 422 |
(test (begin (hash-table-update! ht-fixnum 16 -) |
| 423 |
(map (lambda (i) (hash-table-ref/default ht-fixnum i -1)) |
| 424 |
'(169 144 121 0 1 4 9 16 25 36 49 64 81))) |
| 425 |
'(13 12 11 0 1 2 3 -4 -1 -1 -1 8 -1)) |
| 426 |
|
| 427 |
(test (begin (hash-table-update! ht-fixnum 16 - abs) |
| 428 |
(map (lambda (i) (hash-table-ref/default ht-fixnum i -1)) |
| 429 |
'(169 144 121 0 1 4 9 16 25 36 49 64 81))) |
| 430 |
'(13 12 11 0 1 2 3 4 -1 -1 -1 8 -1)) |
| 431 |
|
| 432 |
(test (begin (hash-table-update!/default ht-fixnum 25 - 5) |
| 433 |
(map (lambda (i) (hash-table-ref/default ht-fixnum i -1)) |
| 434 |
'(169 144 121 0 1 4 9 16 25 36 49 64 81))) |
| 435 |
'(13 12 11 0 1 2 3 4 -5 -1 -1 8 -1)) |
| 436 |
|
| 437 |
(test (begin (hash-table-update!/default ht-fixnum 25 - 999) |
| 438 |
(map (lambda (i) (hash-table-ref/default ht-fixnum i -1)) |
| 439 |
'(169 144 121 0 1 4 9 16 25 36 49 64 81))) |
| 440 |
'(13 12 11 0 1 2 3 4 5 -1 -1 8 -1)) |
| 441 |
|
| 442 |
(test (let* ((n0 (hash-table-size ht-fixnum)) |
| 443 |
(ht (hash-table-copy ht-fixnum #t))) |
| 444 |
(call-with-values |
| 445 |
(lambda () (hash-table-pop! ht)) |
| 446 |
(lambda (key val) |
| 447 |
(list (= key (* val val)) |
| 448 |
(= (- n0 1) (hash-table-size ht)))))) |
| 449 |
'(#t #t)) |
| 450 |
|
| 451 |
(test (begin (hash-table-delete! ht-fixnum 75) |
| 452 |
(map (lambda (i) (hash-table-ref/default ht-fixnum i -1)) |
| 453 |
'(169 144 121 0 1 4 9 16 25 36 49 64 75 81))) |
| 454 |
'(13 12 11 0 1 2 3 4 5 -1 -1 8 -1 -1)) |
| 455 |
|
| 456 |
(let ((ht-eg (hash-table number-comparator 1 1 4 2 9 3 16 4 25 5 64 8))) |
| 457 |
(test (hash-table-delete! ht-eg) |
| 458 |
0) |
| 459 |
(test (hash-table-delete! ht-eg 2 7 2000) |
| 460 |
0) |
| 461 |
(test (hash-table-delete! ht-eg 1 2 4 7 64 2000) |
| 462 |
3) |
| 463 |
(test-assert (= 3 (length (hash-table-keys ht-eg))))) |
| 464 |
|
| 465 |
(test (map (lambda (i) (hash-table-ref/default ht-fixnum i -1)) |
| 466 |
'(169 144 121 0 1 4 9 16 25 36 49 64 81)) |
| 467 |
'(13 12 11 0 1 2 3 4 5 -1 -1 8 -1)) |
| 468 |
|
| 469 |
(test (begin (hash-table-set! ht-fixnum 36 6) |
| 470 |
(hash-table-set! ht-fixnum 81 9) |
| 471 |
(map (lambda (i) (hash-table-ref/default ht-fixnum i -1)) |
| 472 |
'(169 144 121 0 1 4 9 16 25 36 49 64 81))) |
| 473 |
'(13 12 11 0 1 2 3 4 5 6 -1 8 9)) |
| 474 |
|
| 475 |
(test (begin (hash-table-clear! ht-eq) |
| 476 |
(hash-table-size ht-eq)) |
| 477 |
0) |
| 478 |
|
| 479 |
;;; The whole hash table. |
| 480 |
|
| 481 |
(test (begin (hash-table-set! ht-eq 'foo 13 'bar 14 'baz 18) |
| 482 |
(hash-table-size ht-eq)) |
| 483 |
3) |
| 484 |
|
| 485 |
(test (let* ((ht (hash-table-empty-copy ht-eq)) |
| 486 |
(n0 (hash-table-size ht)) |
| 487 |
(ignored (hash-table-set! ht 'foo 13 'bar 14 'baz 18)) |
| 488 |
(n1 (hash-table-size ht))) |
| 489 |
(list n0 n1 (hash-table=? default-comparator ht ht-eq))) |
| 490 |
'(0 3 #t)) |
| 491 |
|
| 492 |
(test (begin (hash-table-clear! ht-eq) |
| 493 |
(hash-table-size ht-eq)) |
| 494 |
0) |
| 495 |
|
| 496 |
(test (hash-table-find (lambda (key val) |
| 497 |
(if (= 144 key (* val val)) |
| 498 |
(list key val) |
| 499 |
#f)) |
| 500 |
ht-fixnum |
| 501 |
(lambda () 99)) |
| 502 |
'(144 12)) |
| 503 |
|
| 504 |
(test (hash-table-find (lambda (key val) |
| 505 |
(if (= 144 key val) |
| 506 |
(list key val) |
| 507 |
#f)) |
| 508 |
ht-fixnum |
| 509 |
(lambda () 99)) |
| 510 |
99) |
| 511 |
|
| 512 |
(test (hash-table-count <= ht-fixnum) |
| 513 |
2) |
| 514 |
|
| 515 |
;;; Mapping and folding. |
| 516 |
|
| 517 |
(test (map (lambda (i) (hash-table-ref/default ht-fixnum i -1)) |
| 518 |
'(0 1 4 9 16 25 36 49 64 81 100 121 144 169 196)) |
| 519 |
'(0 1 2 3 4 5 6 -1 8 9 -1 11 12 13 -1)) |
| 520 |
|
| 521 |
(test (let ((ht (hash-table-map (lambda (val) (* val val)) |
| 522 |
eqv-comparator |
| 523 |
ht-fixnum))) |
| 524 |
(map (lambda (i) (hash-table-ref/default ht i -1)) |
| 525 |
'(0 1 4 9 16 25 36 49 64 81 100 121 144 169 196))) |
| 526 |
'(0 1 4 9 16 25 36 -1 64 81 -1 121 144 169 -1)) |
| 527 |
|
| 528 |
(test (let ((keys (make-vector 15 -1)) |
| 529 |
(vals (make-vector 15 -1))) |
| 530 |
(hash-table-for-each (lambda (key val) |
| 531 |
(vector-set! keys val key) |
| 532 |
(vector-set! vals val val)) |
| 533 |
ht-fixnum) |
| 534 |
(list keys vals)) |
| 535 |
'(#(0 1 4 9 16 25 36 -1 64 81 -1 121 144 169 -1) |
| 536 |
#(0 1 2 3 4 5 6 -1 8 9 -1 11 12 13 -1))) |
| 537 |
|
| 538 |
(test (begin (hash-table-map! (lambda (key val) |
| 539 |
(if (<= 10 key) |
| 540 |
(- val) |
| 541 |
val)) |
| 542 |
ht-fixnum) |
| 543 |
(map (lambda (i) (hash-table-ref/default ht-fixnum i -1)) |
| 544 |
'(0 1 4 9 16 25 36 49 64 81 100 121 144 169 196))) |
| 545 |
'(0 1 2 3 -4 -5 -6 -1 -8 -9 -1 -11 -12 -13 -1)) |
| 546 |
|
| 547 |
(test (hash-table-fold (lambda (key val acc) |
| 548 |
(+ val acc)) |
| 549 |
0 |
| 550 |
ht-string-ci2) |
| 551 |
13) |
| 552 |
|
| 553 |
(test (list-sort < (hash-table-fold (lambda (key val acc) |
| 554 |
(cons key acc)) |
| 555 |
'() |
| 556 |
ht-fixnum)) |
| 557 |
'(0 1 4 9 16 25 36 64 81 121 144 169)) |
| 558 |
|
| 559 |
;;; Copying and conversion. |
| 560 |
|
| 561 |
(test (hash-table=? number-comparator ht-fixnum (hash-table-copy ht-fixnum)) |
| 562 |
#t) |
| 563 |
|
| 564 |
(test (hash-table=? number-comparator ht-fixnum (hash-table-copy ht-fixnum #f)) |
| 565 |
#t) |
| 566 |
|
| 567 |
(test (hash-table=? number-comparator ht-fixnum (hash-table-copy ht-fixnum #t)) |
| 568 |
#t) |
| 569 |
|
| 570 |
'(test (hash-table-mutable? (hash-table-copy ht-fixnum)) |
| 571 |
#f) |
| 572 |
|
| 573 |
'(test (hash-table-mutable? (hash-table-copy ht-fixnum #f)) |
| 574 |
#f) |
| 575 |
|
| 576 |
'(test (hash-table-mutable? (hash-table-copy ht-fixnum #t)) |
| 577 |
#t) |
| 578 |
|
| 579 |
(test (hash-table->alist ht-eq) |
| 580 |
'()) |
| 581 |
|
| 582 |
(test (list-sort (lambda (x y) (< (car x) (car y))) |
| 583 |
(hash-table->alist ht-fixnum)) |
| 584 |
'((0 . 0) |
| 585 |
(1 . 1) |
| 586 |
(4 . 2) |
| 587 |
(9 . 3) |
| 588 |
(16 . -4) |
| 589 |
(25 . -5) |
| 590 |
(36 . -6) |
| 591 |
(64 . -8) |
| 592 |
(81 . -9) |
| 593 |
(121 . -11) |
| 594 |
(144 . -12) |
| 595 |
(169 . -13))) |
| 596 |
|
| 597 |
;;; Hash tables as sets. |
| 598 |
|
| 599 |
(test (begin (hash-table-union! ht-fixnum ht-fixnum2) |
| 600 |
(list-sort (lambda (x y) (< (car x) (car y))) |
| 601 |
(hash-table->alist ht-fixnum))) |
| 602 |
'((0 . 0) |
| 603 |
(1 . 1) |
| 604 |
(4 . 2) |
| 605 |
(9 . 3) |
| 606 |
(16 . -4) |
| 607 |
(25 . -5) |
| 608 |
(36 . -6) |
| 609 |
(49 . 7) |
| 610 |
(64 . -8) |
| 611 |
(81 . -9) |
| 612 |
(121 . -11) |
| 613 |
(144 . -12) |
| 614 |
(169 . -13))) |
| 615 |
|
| 616 |
(test (let ((ht (hash-table-copy ht-fixnum2 #t))) |
| 617 |
(hash-table-union! ht ht-fixnum) |
| 618 |
(list-sort (lambda (x y) (< (car x) (car y))) |
| 619 |
(hash-table->alist ht))) |
| 620 |
'((0 . 0) |
| 621 |
(1 . 1) |
| 622 |
(4 . 2) |
| 623 |
(9 . 3) |
| 624 |
(16 . 4) |
| 625 |
(25 . 5) |
| 626 |
(36 . 6) |
| 627 |
(49 . 7) |
| 628 |
(64 . 8) |
| 629 |
(81 . 9) |
| 630 |
(121 . -11) |
| 631 |
(144 . -12) |
| 632 |
(169 . -13))) |
| 633 |
|
| 634 |
;; [SK] These two tests depends on the implementation wrt. hashtables of |
| 635 |
;; different key comparator can be equal. |
| 636 |
'(test (begin (hash-table-union! ht-eqv2 ht-fixnum) |
| 637 |
(hash-table=? default-comparator ht-eqv2 ht-fixnum)) |
| 638 |
#t) |
| 639 |
|
| 640 |
'(test (begin (hash-table-intersection! ht-eqv2 ht-fixnum) |
| 641 |
(hash-table=? default-comparator ht-eqv2 ht-fixnum)) |
| 642 |
#t) |
| 643 |
|
| 644 |
(test (begin (hash-table-intersection! ht-eqv2 ht-eqv) |
| 645 |
(hash-table-empty? ht-eqv2)) |
| 646 |
#t) |
| 647 |
|
| 648 |
(test (begin (hash-table-intersection! ht-fixnum ht-fixnum2) |
| 649 |
(list-sort (lambda (x y) (< (car x) (car y))) |
| 650 |
(hash-table->alist ht-fixnum))) |
| 651 |
'((0 . 0) |
| 652 |
(1 . 1) |
| 653 |
(4 . 2) |
| 654 |
(9 . 3) |
| 655 |
(16 . -4) |
| 656 |
(25 . -5) |
| 657 |
(36 . -6) |
| 658 |
(49 . 7) |
| 659 |
(64 . -8) |
| 660 |
(81 . -9))) |
| 661 |
|
| 662 |
(test (begin (hash-table-intersection! |
| 663 |
ht-fixnum |
| 664 |
(alist->hash-table '((-1 . -1) (4 . 202) (25 . 205) (100 . 10)) |
| 665 |
number-comparator)) |
| 666 |
(list-sort (lambda (x y) (< (car x) (car y))) |
| 667 |
(hash-table->alist ht-fixnum))) |
| 668 |
'((4 . 2) |
| 669 |
(25 . -5))) |
| 670 |
|
| 671 |
(test (let ((ht (hash-table-copy ht-fixnum2 #t))) |
| 672 |
(hash-table-difference! |
| 673 |
ht |
| 674 |
(alist->hash-table '((-1 . -1) (4 . 202) (25 . 205) (100 . 10)) |
| 675 |
number-comparator)) |
| 676 |
(list-sort (lambda (x y) (< (car x) (car y))) |
| 677 |
(hash-table->alist ht))) |
| 678 |
'((0 . 0) |
| 679 |
(1 . 1) |
| 680 |
(9 . 3) |
| 681 |
(16 . 4) |
| 682 |
(36 . 6) |
| 683 |
(49 . 7) |
| 684 |
(64 . 8) |
| 685 |
(81 . 9))) |
| 686 |
|
| 687 |
(test (let ((ht (hash-table-copy ht-fixnum2 #t))) |
| 688 |
(hash-table-xor! |
| 689 |
ht |
| 690 |
(alist->hash-table '((-1 . -1) (4 . 202) (25 . 205) (100 . 10)) |
| 691 |
number-comparator)) |
| 692 |
(list-sort (lambda (x y) (< (car x) (car y))) |
| 693 |
(hash-table->alist ht))) |
| 694 |
'((-1 . -1) |
| 695 |
(0 . 0) |
| 696 |
(1 . 1) |
| 697 |
(9 . 3) |
| 698 |
(16 . 4) |
| 699 |
(36 . 6) |
| 700 |
(49 . 7) |
| 701 |
(64 . 8) |
| 702 |
(81 . 9) |
| 703 |
(100 . 10))) |
| 704 |
|
| 705 |
(test (guard (exn |
| 706 |
(else 'key-not-found)) |
| 707 |
(hash-table-ref ht-default "this key won't be present")) |
| 708 |
'key-not-found) |
| 709 |
|
| 710 |
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| 711 |
;;; |
| 712 |
;;; Desultory tests of deprecated procedures and usages. |
| 713 |
;;; Deprecated usage of make-hash-table and alist->hash-table |
| 714 |
;;; has already been tested above. |
| 715 |
;;; |
| 716 |
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| 717 |
|
| 718 |
(test (let* ((x (list 1 2 3)) |
| 719 |
(y (cons 1 (cdr x))) |
| 720 |
(h1 (hash x)) |
| 721 |
(h2 (hash y))) |
| 722 |
(list (exact-integer? h1) |
| 723 |
(exact-integer? h2) |
| 724 |
(= h1 h2))) |
| 725 |
'(#t #t #t)) |
| 726 |
|
| 727 |
(test (let* ((x "abcd") |
| 728 |
(y (string-append "ab" "cd")) |
| 729 |
(h1 (deprecated:string-hash x)) |
| 730 |
(h2 (deprecated:string-hash y))) |
| 731 |
(list (exact-integer? h1) |
| 732 |
(exact-integer? h2) |
| 733 |
(= h1 h2))) |
| 734 |
'(#t #t #t)) |
| 735 |
|
| 736 |
(test (let* ((x "Hello There!") |
| 737 |
(y "hello THERE!") |
| 738 |
(h1 (deprecated:string-ci-hash x)) |
| 739 |
(h2 (deprecated:string-ci-hash y))) |
| 740 |
(list (exact-integer? h1) |
| 741 |
(exact-integer? h2) |
| 742 |
(= h1 h2))) |
| 743 |
'(#t #t #t)) |
| 744 |
|
| 745 |
(test (let* ((x '#(a "bcD" #\c (d 2.718) -42 #u8() #() #u8(19 20))) |
| 746 |
(y x) |
| 747 |
(h1 (hash-by-identity x)) |
| 748 |
(h2 (hash-by-identity y))) |
| 749 |
(list (exact-integer? h1) |
| 750 |
(exact-integer? h2) |
| 751 |
(= h1 h2))) |
| 752 |
'(#t #t #t)) |
| 753 |
|
| 754 |
(test (let* ((x (list 1 2 3)) |
| 755 |
(y (cons 1 (cdr x))) |
| 756 |
(h1 (hash x 60)) |
| 757 |
(h2 (hash y 60))) |
| 758 |
(list (exact-integer? h1) |
| 759 |
(exact-integer? h2) |
| 760 |
(= h1 h2))) |
| 761 |
'(#t #t #t)) |
| 762 |
|
| 763 |
(test (let* ((x "abcd") |
| 764 |
(y (string-append "ab" "cd")) |
| 765 |
(h1 (deprecated:string-hash x 97)) |
| 766 |
(h2 (deprecated:string-hash y 97))) |
| 767 |
(list (exact-integer? h1) |
| 768 |
(exact-integer? h2) |
| 769 |
(= h1 h2))) |
| 770 |
'(#t #t #t)) |
| 771 |
|
| 772 |
(test (let* ((x "Hello There!") |
| 773 |
(y "hello THERE!") |
| 774 |
(h1 (deprecated:string-ci-hash x 101)) |
| 775 |
(h2 (deprecated:string-ci-hash y 101))) |
| 776 |
(list (exact-integer? h1) |
| 777 |
(exact-integer? h2) |
| 778 |
(= h1 h2))) |
| 779 |
'(#t #t #t)) |
| 780 |
|
| 781 |
(test (let* ((x '#(a "bcD" #\c (d 2.718) -42 #u8() #() #u8(19 20))) |
| 782 |
(y x) |
| 783 |
(h1 (hash-by-identity x 102)) |
| 784 |
(h2 (hash-by-identity y 102))) |
| 785 |
(list (exact-integer? h1) |
| 786 |
(exact-integer? h2) |
| 787 |
(= h1 h2))) |
| 788 |
'(#t #t #t)) |
| 789 |
|
| 790 |
(test (let ((f (hash-table-equivalence-function ht-fixnum))) |
| 791 |
(if (procedure? f) |
| 792 |
(f 34 34) |
| 793 |
#t)) |
| 794 |
#t) |
| 795 |
|
| 796 |
(test (let ((f (hash-table-hash-function ht-fixnum))) |
| 797 |
(if (procedure? f) |
| 798 |
(= (f 34) (f 34)) |
| 799 |
#t)) |
| 800 |
#t) |
| 801 |
|
| 802 |
(test (map (lambda (key) (hash-table-exists? ht-fixnum2 key)) |
| 803 |
'(0 1 2 3 4 5 6 7 8 9 10)) |
| 804 |
'(#t #t #f #f #t #f #f #f #f #t #f)) |
| 805 |
|
| 806 |
(test (let ((n 0)) |
| 807 |
(hash-table-walk ht-fixnum2 |
| 808 |
(lambda (key val) (set! n (+ n key)))) |
| 809 |
n) |
| 810 |
(apply + |
| 811 |
(map (lambda (x) (* x x)) |
| 812 |
'(0 1 2 3 4 5 6 7 8 9)))) |
| 813 |
|
| 814 |
(test (list-sort < (hash-table-fold ht-fixnum2 |
| 815 |
(lambda (key val acc) |
| 816 |
(cons key acc)) |
| 817 |
'())) |
| 818 |
'(0 1 4 9 16 25 36 49 64 81)) |
| 819 |
|
| 820 |
(test (let ((ht (hash-table-copy ht-fixnum2 #t)) |
| 821 |
(ht2 (hash-table number-comparator |
| 822 |
.25 .5 64 9999 81 9998 121 -11 144 -12))) |
| 823 |
(hash-table-merge! ht ht2) |
| 824 |
(list-sort (lambda (x y) (< (car x) (car y))) |
| 825 |
(hash-table->alist ht))) |
| 826 |
'((0 . 0) |
| 827 |
(.25 . .5) |
| 828 |
(1 . 1) |
| 829 |
(4 . 2) |
| 830 |
(9 . 3) |
| 831 |
(16 . 4) |
| 832 |
(25 . 5) |
| 833 |
(36 . 6) |
| 834 |
(49 . 7) |
| 835 |
(64 . 8) |
| 836 |
(81 . 9) |
| 837 |
(121 . -11) |
| 838 |
(144 . -12))) |
| 839 |
|
| 840 |
;;; Bugs reported on 5 January 2019 by Jéssica Milaré |
| 841 |
;;; ( https://srfi-email.schemers.org/srfi-125/msg/10177551 ) |
| 842 |
|
| 843 |
;;; Spec says hash-table returns an immutable hash table (if that |
| 844 |
;;; is supported) and signal an error if there are duplicate keys, |
| 845 |
;;; but standard implementation returns a mutable hash table and |
| 846 |
;;; signals no error with duplicate keys. |
| 847 |
;;; |
| 848 |
;;; Comment by Will Clinger: the spec says specifying a duplicate |
| 849 |
;;; key "is an error", so hash-table is not required to signal an |
| 850 |
;;; error when there are duplicate keys. That part of the spec |
| 851 |
;;; was added on 8 May 2016, which is why it was not implemented |
| 852 |
;;; by the sample implementation of 2 May 2016. Because a duplicate |
| 853 |
;;; key "is an error" rather than "signals an error", testing for |
| 854 |
;;; that situation is glass-box, as is testing for immutability. |
| 855 |
|
| 856 |
;;; FIXME: glass-box |
| 857 |
|
| 858 |
'(test (hash-table-mutable? |
| 859 |
(hash-table number-comparator |
| 860 |
.25 .5 64 9999 81 9998 121 -11 144 -12)) |
| 861 |
#f) |
| 862 |
|
| 863 |
;;; FIXME: glass-box (implementations not required to raise an exception here) |
| 864 |
|
| 865 |
'(test (guard (exn |
| 866 |
(else 'eh)) |
| 867 |
(hash-table number-comparator .25 .5 .25 -.5)) |
| 868 |
'eh) |
| 869 |
|
| 870 |
;;; Spec says hash-table-set! must go left to right, but in |
| 871 |
;;; standard implementation it goes right to left. |
| 872 |
;;; |
| 873 |
;;; Comment by Will Clinger: the left-to-right requirement was |
| 874 |
;;; added to the spec on 8 May 2016, which is why it was not |
| 875 |
;;; implemented by the sample implementation of 2 May 2016. |
| 876 |
|
| 877 |
(test (let* ((ht (hash-table-empty-copy ht-eq)) |
| 878 |
(ignored (hash-table-set! ht 'foo 13 'bar 14 'foo 18))) |
| 879 |
(hash-table-ref ht 'foo)) |
| 880 |
18) |
| 881 |
|
| 882 |
;;; Spec says hash-table-empty-copy returns a mutable hash table, |
| 883 |
;;; but in standard implementation it returns an immutable hash |
| 884 |
;;; table if the given hash table is immutable. |
| 885 |
|
| 886 |
;;; FIXME: glass-box (immutable tables need not be supported) |
| 887 |
|
| 888 |
'(test (hash-table-mutable? |
| 889 |
(hash-table number-comparator)) |
| 890 |
#f) |
| 891 |
|
| 892 |
'(test (hash-table-mutable? |
| 893 |
(hash-table-empty-copy |
| 894 |
(hash-table-copy (hash-table number-comparator) #f))) |
| 895 |
#t) |
| 896 |
|
| 897 |
;;; hash-table-delete! seems to loop infinitely once it finds a key. |
| 898 |
;;; |
| 899 |
;;; Comment by Will Clinger: that bug was added by |
| 900 |
;;; commit e17c15203a934ab741300e59619f880f363c2b2f |
| 901 |
;;; on 26 September 2018. I do not understand the purpose of that |
| 902 |
;;; commit, as its one change appears to have had no substantive |
| 903 |
;;; effect apart from inserting this bug. |
| 904 |
|
| 905 |
(test (let* ((ht |
| 906 |
(hash-table default-comparator 'foo 1 'bar 2 'baz 3)) |
| 907 |
(ht (hash-table-copy ht #t))) |
| 908 |
(hash-table-delete! ht 'foo) |
| 909 |
(hash-table-size ht)) |
| 910 |
2) |
| 911 |
|
| 912 |
(displayln "Done.") |
| 913 |
|
| 914 |
(exit ultimate-exit-status) |
| 915 |
|
| 916 |
; eof |