a57b771c2f793b9623d2b8db87ffcfbf7061b060
[software/python-on-guile.git] / modules / language / python / dict.scm
1 (define-module (language python dict)
2 #:use-module (language python list)
3 #:use-module (language python try)
4 #:use-module (language python hash)
5 #:use-module (language python yield)
6 #:use-module (language python def)
7 #:use-module (language python for)
8 #:use-module (language python exceptions)
9 #:use-module (language python persist)
10 #:use-module (ice-9 match)
11 #:use-module (ice-9 control)
12 #:use-module (oop goops)
13 #:use-module (oop pf-objects)
14 #:export (make-py-hashtable <py-hashtable>
15 py-copy py-fromkeys py-get py-has_key py-items py-iteritems
16 py-iterkeys py-itervalues py-keys py-values
17 py-popitem py-setdefault py-update py-clear
18 py-hash-ref dict pyhash-listing
19 ))
20
21 (define-syntax-rule (aif it p x y) (let ((it p)) (if it x y)))
22
23 (define (h x n) (modulo (py-hash x) n))
24 (define (py-assoc k l)
25 (if (pair? l)
26 (if (equal? (caar l) k)
27 (car l)
28 (py-assoc k (cdr l)))
29 #f))
30
31 (define (py-hash-ref . l)
32 (apply hashx-ref h py-assoc l))
33 (define (py-hash-set! . l)
34 (apply hashx-set! h py-assoc l))
35 (define (py-hash-remove! . l)
36 (apply hashx-remove! h py-assoc l))
37
38 (set! (@@ (language python def) hset!) py-hash-set!)
39
40 (define H (hash 1333674836 complexity))
41
42 (define-class <py-hashtable> () t h n)
43
44 (name-object <py-hashtable>)
45
46 (cpit <py-hashtable>
47 (o (lambda (o h n a)
48 (slot-set! o 'h h)
49 (slot-set! o 'n n)
50 (slot-set! o 't
51 (let ((t (make-hash-table)))
52 (let lp ((a a))
53 (if (pair? a)
54 (begin
55 (py-hash-set! t (caar a) (cdar a))
56 (lp (cdr a)))))
57 t)))
58 (let ((t (slot-ref o 't)))
59 (list
60 (slot-ref o 'h)
61 (slot-ref o 'n)
62 (hash-fold (lambda (k v s) (cons (cons k v) s)) '() t)))))
63
64 (define (make-py-hashtable)
65 (let* ((o (make <py-hashtable>))
66 (t (make-hash-table))
67 (h H))
68 (slot-set! o 't t)
69 (slot-set! o 'h h)
70 (slot-set! o 'n 0)
71 o))
72
73 (define miss (list 'miss))
74 (define-method (pylist-ref (o <hashtable>) x)
75 (let ((r (py-hash-ref o x miss)))
76 (if (eq? r miss)
77 (raise KeyError x)
78 r)))
79
80 (define-method (pylist-ref (o <py-hashtable>) x)
81 (let ((r (py-hash-ref (slot-ref o 't) x miss)))
82 (if (eq? r miss)
83 (raise KeyError x)
84 r)))
85
86 (define-method (pylist-delete! (o <hashtable>) k)
87 (pyhash-rem! o k))
88
89 (define-method (pylist-delete! (o <py-hashtable>) k)
90 (pyhash-rem! o k))
91
92 (define-method (py-hash (o <hashtable>))
93 (hash-fold
94 (lambda (k v s)
95 (logxor
96 (xy (py-hash k) (py-hash v))
97 s))
98 0 o))
99
100 (define-method (py-hash (o <py-hashtable>))
101 (slot-ref o 'h))
102
103 (define-method (len (o <hashtable>))
104 (hash-fold (lambda (k v s) (+ s 1)) 0 o))
105
106 (define-method (len (o <py-hashtable>))
107 (slot-ref o 'n))
108
109 (define-method (pylist-pop! (o <hashtable>) k . l)
110 (match l
111 ((v)
112 (let ((ret (py-hash-ref o k v)))
113 (py-hash-remove! o k)
114 ret))
115 (()
116 (let ((ret (hash-ref o k miss)))
117 (if (eq? ret miss)
118 (raise KeyError k)
119 (begin
120 (hash-remove! o k)
121 ret))))))
122
123 (define-method (pyhash-rem! (o <hashtable>) k)
124 (py-hash-remove! o k)
125 (values))
126
127 (define-method (pyhash-rem! (o <py-hashtable>) k)
128 (let ((t (slot-ref o 't))
129 (n (slot-ref o 'n))
130 (h (slot-ref o 'h)))
131 (let ((ret (py-hash-ref t k miss)))
132 (if (eq? ret miss)
133 (values)
134 (begin
135 (py-hash-remove! t k)
136 (slot-set! o 'n (- n 1))
137 (slot-set! o 'h (logxor h (xy (py-hash k) (py-hash ret))))
138 (values))))))
139
140 (define-method (pylist-pop! (o <py-hashtable>) k . l)
141 (let ((t (slot-ref o 't)))
142 (match l
143 ((v)
144 (let ((ret (py-hash-ref t k miss)))
145 (if (eq? ret miss)
146 v
147 (begin
148 (pyhash-rem! o k)
149 ret))))
150 (()
151 (let ((ret (hash-ref o k miss)))
152 (if (eq? ret miss)
153 (raise KeyError k)
154 (begin
155 (pyhash-rem! o k)
156 ret)))))))
157
158 (define-method (pylist-set! (o <hashtable>) key val)
159 (py-hash-set! o key val)
160 (values))
161
162 (define-method (pylist-set! (o <py-hashtable>) key val)
163 (let ((t (slot-ref o 't))
164 (n (slot-ref o 'n))
165 (h (slot-ref o 'h)))
166 (let ((ret (py-hash-ref t key miss)))
167 (if (eq? ret miss)
168 (begin
169 (py-hash-set! t key val)
170 (slot-set! o 'n (+ n 1))
171 (slot-set! o 'h (logxor (xy (py-hash key) (py-hash val)) h)))
172 (begin
173 (py-hash-set! t key val)
174 (slot-set! o 'h
175 (logxor (xy (py-hash key) (py-hash val))
176 (logxor
177 (xy (py-hash key) (py-hash ret))
178 h)))))))
179 (values))
180
181 (define-syntax define-py
182 (syntax-rules ()
183 ((_ (nm n o l ...) (class code ...) ...)
184 (begin
185 (define-method (nm (o class) l ...) code ...)
186 ...
187 (define-method (nm (o <p>) l ...)
188 (aif it (ref o 'n)
189 (it l ...)
190 (next-method)))))
191 ((_ (nm n o l ... . u) (class code ...) ...)
192 (begin
193 (define-method (nm (o class) l ... . u) code ...)
194 ...
195 (define-method (nm (o <p>) l ... . u)
196 (aif it (ref o 'n)
197 (apply it l ... u)
198 (next-method)))))))
199
200
201
202 (define-py (py-copy copy o)
203 (<hashtable>
204 (hash-fold
205 (lambda (k v h)
206 (py-hash-set! h k v)
207 h)
208 (make-hash-table)
209 o))
210
211 (<py-hashtable>
212 (let ((r (make <py-hashtable>)))
213 (slot-set! r 'h (slot-ref o 'h))
214 (slot-set! r 'n (slot-ref o 'n))
215 (slot-set! r 't (py-copy (slot-ref o 't)))
216 r)))
217
218 (define-py (py-fromkeys fromkeys o . l)
219 (<hashtable>
220 (let ((newval (match l
221 (() None)
222 ((v) v))))
223 (hash-fold
224 (lambda (k v h)
225 (py-hash-set! h k newval)
226 h)
227 (make-hash-table)
228 o)))
229
230 (<py-hashtable>
231 (let ((newval (match l
232 (() None)
233 ((v) v))))
234 (hash-fold
235 (lambda (k v h)
236 (pylist-set! h k newval)
237 h)
238 (make-py-hashtable)
239 (slot-ref o 't)))))
240
241 (define-py (py-get get o k . l)
242 (<hashtable>
243 (let ((elseval (match l
244 (() None)
245 ((v) v))))
246 (let ((ret (py-hash-ref o k miss)))
247 (if (eq? ret miss)
248 elseval
249 ret))))
250
251 (<py-hashtable>
252 (let ((elseval (match l
253 (() None)
254 ((v) v))))
255 (let ((ret (py-hash-ref (slot-ref o 't) k miss)))
256 (if (eq? ret miss)
257 elseval
258 ret)))))
259
260 (define-py (py-has_key has_key o k . l)
261 (<hashtable>
262 (let ((elseval (match l
263 (() None)
264 ((v) v))))
265 (let ((ret (py-hash-ref o k miss)))
266 (if (eq? ret miss)
267 #f
268 #t))))
269
270 (<py-hashtable>
271 (let ((elseval (match l
272 (() None)
273 ((v) v))))
274 (let ((ret (py-hash-ref (slot-ref o 't) k miss)))
275 (if (eq? ret miss)
276 #f
277 #t)))))
278
279 (define-py (py-items items o)
280 (<hashtable>
281 (to-pylist
282 (hash-fold
283 (lambda (k v l)
284 (cons (list k v) l))
285 '() o)))
286
287 (<py-hashtable>
288 (to-pylist
289 (hash-fold
290 (lambda (k v l)
291 (cons (list k v) l))
292 '() (slot-ref o 't)))))
293
294 (define-generator (hash-item-gen yield hash-table)
295 (let lp ((l (hash-fold cons* '() hash-table)))
296 (match l
297 ((k v . l)
298 (yield k v)
299 (lp l))
300 (()
301 #t))))
302
303 (define-generator (hash-values-gen yield hash-table)
304 (let lp ((l (hash-fold cons* '() hash-table)))
305 (match l
306 ((k v . l)
307 (yield v)
308 (lp l))
309 (()
310 #t))))
311
312 (define-generator (hash-keys-gen yield hash-table)
313 (let lp ((l (hash-fold cons* '() hash-table)))
314 (match l
315 ((k v . l)
316 (yield k)
317 (lp l))
318 (()
319 #t))))
320
321 (define-py (py-iteritems iteritems o)
322 (<hashtable>
323 (hash-item-gen o))
324
325 (<py-hashtable>
326 (hash-item-gen (slot-ref o 't))))
327
328 (define-py (py-iterkeys iterkeys o)
329 (<hashtable>
330 (hash-keys-gen o))
331
332 (<py-hashtable>
333 (hash-keys-gen (slot-ref o 't))))
334
335 (define-py (py-itervalues itervalues o)
336 (<hashtable>
337 (hash-values-gen o))
338
339 (<py-hashtable>
340 (hash-values-gen (slot-ref o 't))))
341
342 (define-py (py-keys keys o)
343 (<hashtable>
344 (to-pylist
345 (hash-fold
346 (lambda (k v l) (cons k l))
347 '()
348 o)))
349
350 (<py-hashtable>
351 (to-pylist
352 (hash-fold
353 (lambda (k v l) (cons k l))
354 '()
355 (slot-ref o 't)))))
356
357 (define-py (py-values values o)
358 (<hashtable>
359 (to-pylist
360 (hash-fold
361 (lambda (k v l) (cons v l))
362 '()
363 o)))
364
365 (<py-hashtable>
366 (to-pylist
367 (hash-fold
368 (lambda (k v l) (cons v l))
369 '()
370 (slot-ref o 't)))))
371
372 (define-py (py-popitem popitem o)
373 (<hashtable>
374 (let ((k.v (let/ec ret
375 (hash-for-each
376 (lambda (k v)
377 (ret (cons k v)))
378 o)
379 #f)))
380 (if k.v
381 (begin (pyhash-rem! o (car k.v)) k.v)
382 (raise KeyError "No elements in hash"))))
383
384 (<py-hashtable>
385 (let ((k.v (let/ec ret
386 (hash-for-each
387 (lambda (k v)
388 (ret (cons k v)))
389 (slot-ref o 't))
390 #f)))
391 (if k.v
392 (begin (pyhash-rem! o (car k.v)) k.v)
393 (raise KeyError "No elements in hash")))))
394
395 (define-py (py-setdefault setdefault o k . l)
396 (<hashtable>
397 (pylist-set! o k (apply py-get o k l)))
398 (<py-hashtable>
399 (pylist-set! o k (apply py-get o k l))))
400
401 (define update
402 (lam (o (* L) (** K))
403 (match L
404 ((L)
405 (for ((k v : L)) ()
406 (pylist-set! o k v)))
407 (_ #f))
408 (for ((k v : K)) ()
409 (pylist-set! o k v))))
410
411 (define-py (py-update update o . l)
412 (<hashtable>
413 (apply update o l))
414 (<py-hashtable>
415 (apply update o l)))
416
417 (define-py (py-clear clear o)
418 (<hashtable>
419 (hash-clear! o))
420 (<py-hashtable>
421 (let ((t (slot-ref o 't)))
422 (hash-clear! t)
423 (slot-set! o 'n 0)
424 (slot-set! o 'h H)
425 (values))))
426
427 #|
428 'viewitems'
429 'viewkeys'
430 'viewvalues'
431 |#
432
433 (define-syntax-rule (top <)
434 (begin
435 (define-method (< (o1 <hashtable>) (o2 <hashtable>))
436 (< (len o1) (len o2)))
437 (define-method (< (o1 <hashtable>) (o2 <py-hashtable>))
438 (< (len o1) (len o2)))
439 (define-method (< (o1 <py-hashtable>) (o2 <hashtable>))
440 (< (len o1) (len o2)))
441 (define-method (< (o1 <py-hashtable>) (o2 <py-hashtable>))
442 (< (len o1) (len o2)))))
443
444 (top <)
445 (top >)
446 (top <=)
447 (top >=)
448
449 (define (fold f s l)
450 (if (pair? l)
451 (f (car l) (fold f s (cdr l)))
452 s))
453
454 (define-method (write (o <py-hashtable>) . l)
455 (define port (match l (() #f) ((p) p)))
456 (define li (hash-fold cons* '() (slot-ref o 't)))
457 (if (null? li)
458 (format port "{}")
459 (format port "{~a: ~a~{, ~a: ~a~}}" (car li) (cadr li) (cddr li))))
460
461 (define-method (py-equal? (o1 <py-hashtable>) (o2 <py-hashtable>))
462 (and
463 (equal? (slot-ref o1 'n) (slot-ref o2 'n))
464 (equal? (slot-ref o1 'h) (slot-ref o2 'h))
465 (e? (slot-ref o1 't) (slot-ref o2 't))))
466
467 (define (e? t1 t2)
468 (let/ec ret
469 (hash-fold
470 (lambda (k v s)
471 (let ((r (py-hash-ref t2 k miss)))
472 (if (eq? r miss)
473 (ret #f)
474 (if (equal? r v)
475 #t
476 (ret #f)))))
477 #t
478 t1)))
479
480
481 (define-class <hashiter> () l)
482 (name-object <hashiter>)
483 (cpit <hashiter> (o (lambda (o l) (slot-set! o 'l l))
484 (list (slot-ref o 'l))))
485
486
487 (define-method (wrap-in (t <hashtable>))
488 (let ((o (make <hashiter>)))
489 (slot-set! o 'l (to-list (py-items t)))
490 o))
491
492 (define-method (wrap-in (t <py-hashtable>))
493 (let ((o (make <hashiter>)))
494 (slot-set! o 'l (to-list (py-items t)))
495 o))
496
497 (define-method (next (o <hashiter>))
498 (let ((l (slot-ref o 'l)))
499 (if (pair? l)
500 (let ((k (caar l))
501 (v (cadar l))
502 (l (cdr l)))
503 (slot-set! o 'l l)
504 (values k v))
505 (throw StopIteration))))
506
507
508 (define-method (in key (o <hashtable>))
509 (py-has_key o key))
510
511 (define-method (in key (o <py-hashtable>))
512 (py-has_key o key))
513
514 (define-python-class dict (<py-hashtable>)
515 (define __init__
516 (letrec ((__init__
517 (case-lambda
518 ((self)
519 (let ((r (make-py-hashtable)))
520 (slot-set! self 't (slot-ref r 't))
521 (slot-set! self 'h (slot-ref r 'h))
522 (slot-set! self 'n (slot-ref r 'n))))
523 ((self x)
524 (__init__ self)
525 (if (is-a? x <py-hashtable>)
526 (hash-for-each
527 (lambda (k v)
528 (pylist-set! self k v))
529 (slot-ref x 't)))))))
530 __init__)))
531
532 (name-object dict)
533
534 (define (pyhash-listing)
535 (let ((l (to-pylist
536 (map symbol->string
537 '(__class__ __cmp__ __contains__ __delattr__
538 __delitem__ __doc__ __eq__ __format__
539 __ge__ __getattribute__ __getitem__
540 __gt__ __hash__ __init__ __iter__
541 __le__ __len__ __lt__ __ne__ __new__
542 __reduce__ __reduce_ex__ __repr__
543 __setattr__ __setitem__ __sizeof__
544 __str__ __subclasshook__
545 clear copy fromkeys get has_key
546 items iteritems iterkeys itervalues
547 keys pop popitem setdefault update
548 values viewitems viewkeys viewvalues)))))
549 (pylist-sort! l)
550 l))
551
552
553 (define-method (py-class (o <hashtable>)) dict)
554 (define-method (py-class (o <py-hashtable>)) dict)