Debian Codegraph @

ext/sparse/sparse.scm

raw
1 ;;;
2 ;;; data.sparse - sparse data structures
3 ;;;
4 ;;; Copyright (c) 2007-2024 Shiro Kawai <[email protected]>
5 ;;;
6 ;;; Redistribution and use in source and binary forms, with or without
7 ;;; modification, are permitted provided that the following conditions
8 ;;; are met:
9 ;;;
10 ;;; 1. Redistributions of source code must retain the above copyright
11 ;;; notice, this list of conditions and the following disclaimer.
12 ;;;
13 ;;; 2. Redistributions in binary form must reproduce the above copyright
14 ;;; notice, this list of conditions and the following disclaimer in the
15 ;;; documentation and/or other materials provided with the distribution.
16 ;;;
17 ;;; 3. Neither the name of the authors nor the names of its contributors
18 ;;; may be used to endorse or promote products derived from this
19 ;;; software without specific prior written permission.
20 ;;;
21 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ;;;
33
34
35 (define-module data.sparse
36 (use gauche.collection)
37 (use gauche.dictionary)
38 (export <sparse-table> make-sparse-table sparse-table-num-entries
39 sparse-table-ref sparse-table-set! sparse-table-exists?
40 sparse-table-clear! sparse-table-delete! sparse-table-copy
41 sparse-table-update! sparse-table-push! sparse-table-pop!
42 sparse-table-fold sparse-table-map sparse-table-for-each
43 sparse-table-find sparse-table-keys sparse-table-values
44 sparse-table-comparator
45 %sparse-table-dump %sparse-table-check
46
47 <sparse-vector-base> <sparse-vector> <sparse-s8vector>
48 <sparse-u8vector> <sparse-s16vector> <sparse-u16vector>
49 <sparse-s32vector> <sparse-u32vector> <sparse-s64vector>
50 <sparse-u64vector> <sparse-f16vector> <sparse-f32vector>
51 <sparse-f64vector>
52 sparse-vector-max-index-bits
53 make-sparse-vector sparse-vector-num-entries
54 sparse-vector-ref sparse-vector-set! sparse-vector-exists?
55 sparse-vector-clear! sparse-vector-delete! sparse-vector-copy
56 sparse-vector-update! sparse-vector-inc!
57 sparse-vector-push! sparse-vector-pop!
58 sparse-vector-fold sparse-vector-map sparse-vector-for-each
59 sparse-vector-find sparse-vector-keys sparse-vector-values
60 %sparse-vector-dump
61
62 <sparse-matrix-base> <sparse-matrix> <sparse-s8matrix>
63 <sparse-u8matrix> <sparse-s16matrix> <sparse-u16matrix>
64 <sparse-s32matrix> <sparse-u32matrix> <sparse-s64matrix>
65 <sparse-u64matrix> <sparse-f16matrix> <sparse-f32matrix>
66 <sparse-f64matrix>
67 make-sparse-matrix sparse-matrix-num-entries
68 sparse-matrix-ref sparse-matrix-set! sparse-matrix-exists?
69 sparse-matrix-clear! sparse-matrix-delete! sparse-matrix-copy
70 sparse-matrix-update! sparse-matrix-inc!
71 sparse-matrix-push! sparse-matrix-pop!
72 sparse-matrix-fold sparse-matrix-map sparse-matrix-for-each
73 sparse-matrix-keys sparse-matrix-values
74 )
75 )
76 (select-module data.sparse)
77
78 (inline-stub
79 (declcode
80 (.include "ctrie.h")
81 (.include "spvec.h")
82 (.include "sptab.h")
83 (.include <gauche/bits_inline.h>)))
84
85 (define-macro (define-stuff type class iter ref set)
86 (let ([x-fold (string->symbol #"~|type|-fold")]
87 [x-map (string->symbol #"~|type|-map")]
88 [x-for-each (string->symbol #"~|type|-for-each")]
89 [x-find (string->symbol #"~|type|-find")]
90 [x-keys (string->symbol #"~|type|-keys")]
91 [x-values (string->symbol #"~|type|-values")]
92 [x-update! (string->symbol #"~|type|-update!")]
93 [x-push! (string->symbol #"~|type|-push!")]
94 [x-pop! (string->symbol #"~|type|-pop!")]
95 [x-pop!-aux (string->symbol #"%~|type|-pop!-aux")])
96 `(begin
97 (define (,x-fold st proc seed)
98 (let ([iter (,iter st)]
99 [end (list #f)])
100 (let loop ((seed seed))
101 (receive (key val) (iter end)
102 (if (eq? key end)
103 seed
104 (loop (proc key val seed)))))))
105 (define (,x-map st proc)
106 (,x-fold st (^[k v s] (cons (proc k v) s)) '()))
107 (define (,x-for-each st proc)
108 (,x-fold st (^[k v _] (proc k v)) #f))
109 (define (,x-find pred st :optional (failure (lambda () (values #f #f))))
110 (let ([iter (,iter st)]
111 [end (list #f)])
112 (let loop ()
113 (receive (key val) (iter end)
114 (cond [(eq? key end) (failure)]
115 [(pred key val) (values key val)]
116 [else (loop)])))))
117 (define (,x-keys st)
118 (,x-fold st (^[k v s] (cons k s)) '()))
119 (define (,x-values st)
120 (,x-fold st (^[k v s] (cons v s)) '()))
121
122 ;; TODO: rewrite these more efficiently
123 (define (,x-update! sv k proc . fallback)
124 (rlet1 tmp (proc (apply ,ref sv k fallback))
125 (,set sv k tmp)))
126 ;; Treatment of defaultValue differ between sptab and spvec atm,
127 ;; so we define push! separately.
128 ;; (define (,x-push! sv k val)
129 ;; (,set sv k (cons val (,ref sv k '()))))
130 (define (,x-pop! sv k . fallback)
131 (if (null? fallback)
132 (,x-pop!-aux sv k (,ref sv k))
133 ;; A trick to use the argument list as a unique object to see if
134 ;; sv doesn't have an entry
135 (let1 p (,ref sv k fallback)
136 (if (eq? p fallback) (car p) (,x-pop!-aux sv k p)))))
137 (define (,x-pop!-aux sv k p)
138 (unless (pair? p)
139 (errorf "~s's value for key ~s is not a pair: ~s" sv k p))
140 (,set sv k (cdr p))
141 (car p))
142
143 ;; basic generic operations
144 (define-method call-with-iterator ((s ,class) proc)
145 (let ([iter (,iter s)]
146 [sentinel (list #f)])
147 (define (next) (receive (k v) (iter sentinel) (cons k v)))
148 (define cache (next))
149 (proc (^[] (eq? (car cache) sentinel))
150 (^[] (rlet1 v cache (set! cache (next)))))))
151 )))
152
153 ;;===============================================================
154 ;; Sparse hashtables
155 ;;
156
157 (inline-stub
158 (initcode "Scm_Init_sptab(Scm_CurrentModule());")
159
160 (declare-stub-type <sparse-table> "SparseTable*" "sparse table"
161 "SPARSE_TABLE_P" "SPARSE_TABLE")
162
163 (define-cproc %make-sparse-table (type cmpr::<comparator>)
164 (let* ([t::ScmHashType SCM_HASH_EQ])
165 (cond
166 [(SCM_EQ type 'eq?) (set! t SCM_HASH_EQ)]
167 [(SCM_EQ type 'eqv?) (set! t SCM_HASH_EQV)]
168 [(SCM_EQ type 'equal?) (set! t SCM_HASH_EQUAL)]
169 [(SCM_EQ type 'string=?) (set! t SCM_HASH_STRING)]
170 [else (set! t SCM_HASH_GENERAL)])
171 (return (MakeSparseTable t cmpr 0))))
172
173 (define-cproc sparse-table-comparator (st::<sparse-table>)
174 (return (SCM_OBJ (-> st comparator))))
175
176 (define-cproc sparse-table-num-entries (st::<sparse-table>) ::<ulong>
177 (return (-> st numEntries)))
178
179 (define-cproc sparse-table-set! (st::<sparse-table> key value)
180 (return (SparseTableSet st key value 0)))
181
182 (define-cproc sparse-table-ref (st::<sparse-table> key :optional fallback)
183 (setter sparse-table-set!)
184 (let* ([r (SparseTableRef st key fallback)])
185 (when (SCM_UNBOUNDP r)
186 (Scm_Error "%S doesn't have an entry for key %S" (SCM_OBJ st) key))
187 (return r)))
188
189 (define-cproc sparse-table-exists? (st::<sparse-table> key) ::<boolean>
190 (let* ([r (SparseTableRef st key SCM_UNBOUND)])
191 (return (not (SCM_UNBOUNDP r)))))
192
193 (define-cproc sparse-table-delete! (st::<sparse-table> key) ::<boolean>
194 (return (not (SCM_UNBOUNDP (SparseTableDelete st key)))))
195
196 (define-cproc sparse-table-clear! (st::<sparse-table>) ::<void>
197 SparseTableClear)
198
199 (define-cproc sparse-table-copy (sv::<sparse-table>) SparseTableCopy)
200
201 (define-cfn sparse-table-iter (args::ScmObj* _::int data::void*) :static
202 (let* ([iter::SparseTableIter* (cast SparseTableIter* data)]
203 [r (SparseTableIterNext iter)]
204 [eofval (aref args 0)])
205 (if (SCM_FALSEP r)
206 (return (values eofval eofval))
207 (return (values (SCM_CAR r) (SCM_CDR r))))))
208
209 (define-cproc %sparse-table-iter (st::<sparse-table>)
210 (let* ([iter::SparseTableIter* (SCM_NEW SparseTableIter)])
211 (SparseTableIterInit iter st)
212 (return (Scm_MakeSubr sparse-table-iter iter 1 0 '"sparse-table-iterator"))))
213
214 (define-cproc %sparse-table-dump (st::<sparse-table>) ::<void>
215 SparseTableDump)
216
217 (define-cproc %sparse-table-check (st::<sparse-table>) ::<void>
218 SparseTableCheck)
219 )
220
221 ;; This is a bit complicated, for we want to recognize common cases
222 ;; (eq?, eqv?, equal? and string=?) to allow efficient shortcut.
223 (define *shortcut-comparators*
224 `((eq? . ,eq-comparator)
225 (eqv? . ,eqv-comparator)
226 (equal? . ,equal-comparator)
227 (string=? . ,string-comparator)))
228
229 (define (make-sparse-table comparator)
230 (define (bad)
231 (error "make-sparse-table needs a comparator or one of the symbols eq?, \
232 eqv?, equal? or string=?, as an argument, but got:" comparator))
233 (receive (type cmpr)
234 (cond [(symbol? comparator)
235 (if-let1 cmpr (assq-ref *shortcut-comparators* comparator)
236 (values comparator cmpr)
237 (bad))]
238 [(comparator? comparator)
239 (if-let1 type (rassq-ref *shortcut-comparators* comparator)
240 (values type comparator)
241 (values #f comparator))]
242 [else (bad)])
243 (%make-sparse-table type cmpr)))
244
245 (define (sparse-table-push! sptab key val)
246 ;; Can be optimized
247 (sparse-table-set! sptab key (cons val (sparse-table-ref sptab key '()))))
248
249 (define-stuff sparse-table <sparse-table> %sparse-table-iter
250 sparse-table-ref sparse-table-set!)
251
252 (define-method ref ((t <sparse-table>) k)
253 (sparse-table-ref t k))
254 (define-method ref ((t <sparse-table>) k fallback)
255 (sparse-table-ref t k fallback))
256 (define-method (setter ref) ((t <sparse-table>) k value)
257 (sparse-table-set! t k value))
258
259 ;;===============================================================
260 ;; Sparse vectors
261 ;;
262
263 (define (make-sparse-vector :optional (type #f)
264 :key (flags 0) default)
265 (%make-sparse-vector type default flags))
266
267 (inline-stub
268 (initcode "Scm_Init_spvec(Scm_CurrentModule());")
269
270 (declare-stub-type <sparse-vector> "SparseVector*" "sparse vector"
271 "SPARSE_VECTOR_BASE_P" "SPARSE_VECTOR")
272
273 (define-cproc %make-sparse-vector (type default-value _::<ulong>)
274 (let* ([klass::ScmClass* NULL])
275 (cond [(SCM_CLASSP type) (set! klass (SCM_CLASS type))]
276 [(SCM_FALSEP type) (set! klass SCM_CLASS_SPARSE_VECTOR)]
277 [(SCM_EQ type 's8) (set! klass SCM_CLASS_SPARSE_S8VECTOR)]
278 [(SCM_EQ type 'u8) (set! klass SCM_CLASS_SPARSE_U8VECTOR)]
279 [(SCM_EQ type 's16) (set! klass SCM_CLASS_SPARSE_S16VECTOR)]
280 [(SCM_EQ type 'u16) (set! klass SCM_CLASS_SPARSE_U16VECTOR)]
281 [(SCM_EQ type 's32) (set! klass SCM_CLASS_SPARSE_S32VECTOR)]
282 [(SCM_EQ type 'u32) (set! klass SCM_CLASS_SPARSE_U32VECTOR)]
283 [(SCM_EQ type 's64) (set! klass SCM_CLASS_SPARSE_S64VECTOR)]
284 [(SCM_EQ type 'u64) (set! klass SCM_CLASS_SPARSE_U64VECTOR)]
285 [(SCM_EQ type 'f16) (set! klass SCM_CLASS_SPARSE_F16VECTOR)]
286 [(SCM_EQ type 'f32) (set! klass SCM_CLASS_SPARSE_F32VECTOR)]
287 [(SCM_EQ type 'f64) (set! klass SCM_CLASS_SPARSE_F64VECTOR)]
288 [else (Scm_TypeError "type"
289 "subclass of <sparse-vector-base>, #f, or \
290 one of symbols s8, u8, s16, u16, s32, u32, \
291 s64, u64, f16, f32, f64"
292 type)])
293 (return (MakeSparseVector klass default-value 0))))
294
295 (define-cproc sparse-vector-max-index-bits () ::<int>
296 (return SPARSE_VECTOR_MAX_INDEX_BITS))
297
298 (define-cproc sparse-vector-num-entries (sv::<sparse-vector>) ::<ulong>
299 (return (-> sv numEntries)))
300
301 (define-cproc sparse-vector-set!
302 (sv::<sparse-vector> index::<ulong> value) ::<void>
303 SparseVectorSet)
304
305 (define-cproc sparse-vector-ref
306 (sv::<sparse-vector> index::<integer> :optional fallback)
307 (setter sparse-vector-set!)
308 (let* ([oor::int FALSE]
309 [i::u_long (Scm_GetIntegerUClamp index SCM_CLAMP_NONE (& oor))]
310 [r SCM_UNBOUND])
311 (when (not oor)
312 (set! r (SparseVectorRef sv i fallback)))
313 (if (SCM_UNBOUNDP r)
314 (begin
315 (when (SCM_UNDEFINEDP (-> sv defaultValue))
316 (Scm_Error "%S doesn't have an entry at index %S" (SCM_OBJ sv) index))
317 (return (-> sv defaultValue)))
318 (return r))))
319
320 (define-cproc sparse-vector-exists?
321 (sv::<sparse-vector> index::<integer>) ::<boolean>
322 (let* ([oor::int FALSE]
323 [i::u_long (Scm_GetIntegerUClamp index SCM_CLAMP_NONE (& oor))]
324 [r SCM_UNBOUND])
325 (when (not oor)
326 (set! r (SparseVectorRef sv i SCM_UNBOUND)))
327 (return (not (SCM_UNBOUNDP r)))))
328
329 (define-cproc sparse-vector-default-value (sv::<sparse-vector>)
330 (return (-> sv defaultValue)))
331
332 (define-cproc sparse-vector-delete! (sv::<sparse-vector> index::<ulong>)
333 ::<boolean>
334 (return (not (SCM_UNBOUNDP (SparseVectorDelete sv index)))))
335
336 (define-cproc sparse-vector-clear! (sv::<sparse-vector>) ::<void>
337 SparseVectorClear)
338
339 (define-cproc sparse-vector-copy (sv::<sparse-vector>) SparseVectorCopy)
340
341 (define-cproc sparse-vector-inc! (sv::<sparse-vector>
342 index::<ulong>
343 delta::<number>
344 :optional fallback)
345 SparseVectorInc)
346
347 (define-cfn sparse-vector-iter (args::ScmObj* _::int data::void*) :static
348 (let* ([iter::SparseVectorIter* (cast SparseVectorIter* data)]
349 [r (SparseVectorIterNext iter)]
350 [eofval (aref args 0)])
351 (if (SCM_FALSEP r)
352 (return (values eofval eofval))
353 (return (values (SCM_CAR r) (SCM_CDR r))))))
354
355 (define-cproc %sparse-vector-iter (sv::<sparse-vector>)
356 (let* ([iter::SparseVectorIter* (SCM_NEW SparseVectorIter)])
357 (SparseVectorIterInit iter sv)
358 (return
359 (Scm_MakeSubr sparse-vector-iter iter 1 0 '"sparse-vector-iterator"))))
360
361 (define-cproc %sparse-vector-dump (sv::<sparse-vector>) ::<void>
362 SparseVectorDump)
363 )
364
365 (define (sparse-vector-push! spvec key val)
366 ;; Can be optimized
367 (if (undefined? (sparse-vector-default-value spvec))
368 (sparse-vector-set! spvec key (cons val (sparse-vector-ref spvec key '())))
369 (sparse-vector-set! spvec key (cons val (sparse-vector-ref spvec key)))))
370
371 (define-stuff sparse-vector <sparse-vector-base> %sparse-vector-iter
372 sparse-vector-ref sparse-vector-set!)
373
374 (define-macro (define-refset class)
375 `(begin
376 (define-method ref ((v ,class) k)
377 (sparse-vector-ref v k))
378 (define-method ref ((v ,class) k fallback)
379 (sparse-vector-ref v k fallback))
380 (define-method (setter ref) ((v ,class) k value)
381 (sparse-vector-set! v k value))))
382
383 (define-refset <sparse-vector>)
384 (define-refset <sparse-u8vector>)
385 (define-refset <sparse-s8vector>)
386 (define-refset <sparse-u16vector>)
387 (define-refset <sparse-s16vector>)
388 (define-refset <sparse-u32vector>)
389 (define-refset <sparse-s32vector>)
390 (define-refset <sparse-u64vector>)
391 (define-refset <sparse-s64vector>)
392 (define-refset <sparse-f16vector>)
393 (define-refset <sparse-f32vector>)
394 (define-refset <sparse-f64vector>)
395
396 ;; sparse vector comparator is just a singleton.
397 (define *sparse-vector-comparator*
398 (make-comparator/compare (^x (and (exact? x) (integer? x) (>= x 0)))
399 eqv? compare eqv-hash
400 'sparse-vector-comparator))
401
402 (define-method dict-comparator ((spvec <sparse-vector-base>))
403 *sparse-vector-comparator*)
404
405 ;;===============================================================
406 ;; Sparse matrix
407 ;;
408
409 ;; 2-dimensional matrix; it is just a disguise of sparse vector,
410 ;; with a twist of indexing.
411
412 ;; NB: We're planning to make sparse vector index range unlimited.
413 ;; Then we don't need to worry about the range of each index.
414
415 (inline-stub
416 (declare-stub-type <sparse-matrix> "SparseVector*" "sparse matrix"
417 "SPARSE_MATRIX_BASE_P" "SPARSE_MATRIX")
418
419 (.define X_OOR 1)
420 (.define Y_OOR 2)
421
422 (define-cise-stmt oor-check
423 [(_ oor which oorval)
424 `(if (== ,oor NULL)
425 (Scm_Error ,#"~|which| index is out of range: %S" ,which)
426 (begin (set! (* ,oor) ,oorval) (return 0)))])
427
428 ;; Calculate linear index from 2d indexes (x,y) by interleaving the bits.
429 ;; When the input is out of range, if OOR is provided it is set;
430 ;; otherwise an error is signaled.
431 ;; We initially thought of taking 5 bits at a time to match up the node
432 ;; size; however it made code complicated to deal with the last
433 ;; 2 or 4 bits in 32bit/64bit integer. Also, if key is distributed
434 ;; enough, we wonder if there's much sense aligning to the node boundary.
435 ;; So we adopt 4 bits interleaving instead.
436 (.define INTERLEAVE_SHIFT 4)
437 (.define INTERLEAVE_MASK (- (<< 1UL INTERLEAVE_SHIFT) 1))
438
439 (define-cfn index-combine-2d (x y oor::int*)
440 ::u_long :static
441 (unless (SCM_INTEGERP x)
442 (Scm_Error "Exact integer required for x, but got %S" x))
443 (unless (SCM_INTEGERP y)
444 (Scm_Error "Exact integer required for y, but got %S" y))
445 (let* ([oorx::int FALSE] [oory::int FALSE]
446 [ix::u_long (Scm_GetIntegerUClamp x SCM_CLAMP_NONE (& oorx))]
447 [iy::u_long (Scm_GetIntegerUClamp y SCM_CLAMP_NONE (& oory))]
448 [bx::int (Scm__HighestBitNumber ix)]
449 [by::int (Scm__HighestBitNumber iy)])
450 (when oorx (oor-check oor x X_OOR))
451 (when oory (oor-check oor y Y_OOR))
452 (when (>= ix (<< (cast (u_long) 1) (/ SPARSE_VECTOR_MAX_INDEX_BITS 2)))
453 (oor-check oor x X_OOR))
454 (when (>= iy (<< (cast (u_long) 1) (/ SPARSE_VECTOR_MAX_INDEX_BITS 2)))
455 (oor-check oor y Y_OOR))
456 (let* ([bmax::int (?: (> bx by) bx by)]
457 [shift::int 0]
458 [ind::u_long 0])
459 (while (< shift (+ bmax 1))
460 (set! ind (logior ind (<< (logand ix (<< INTERLEAVE_MASK shift))
461 shift)))
462 (set! ind (logior ind (<< (logand iy (<< INTERLEAVE_MASK shift))
463 (+ shift INTERLEAVE_SHIFT))))
464 (set! shift (+ shift INTERLEAVE_SHIFT)))
465 (when oor (set! (* oor) 0))
466 (return ind))))
467
468 (define-cfn index-split-2d (index::ScmObj px::(u_long*) py::(u_long*))
469 ::void :static
470 (let* ([x::u_long 0] [y::u_long 0] [shift::int 0]
471 [i::u_long (Scm_GetIntegerU index)])
472 (while i
473 (set! x (logior x (<< (logand i INTERLEAVE_MASK) shift)))
474 (set! i (>> i INTERLEAVE_SHIFT))
475 (set! y (logior y (<< (logand i INTERLEAVE_MASK) shift)))
476 (set! i (>> i INTERLEAVE_SHIFT))
477 (set! shift (+ shift INTERLEAVE_SHIFT)))
478 (set! (* px) x)
479 (set! (* py) y)))
480 )
481
482 (define (make-sparse-matrix :optional (type #f)
483 :key (flags 0) default)
484 (let1 class
485 (case type
486 [(#f) <sparse-matrix>]
487 [(s8) <sparse-s8matrix>]
488 [(u8) <sparse-u8matrix>]
489 [(s16) <sparse-s16matrix>]
490 [(u16) <sparse-u16matrix>]
491 [(s32) <sparse-s32matrix>]
492 [(u32) <sparse-u32matrix>]
493 [(s64) <sparse-s64matrix>]
494 [(u64) <sparse-u64matrix>]
495 [(f16) <sparse-f16matrix>]
496 [(f32) <sparse-f32matrix>]
497 [(f64) <sparse-f64matrix>]
498 [else (if (and (subtype? type <sparse-matrix-base>)
499 (not (eq? type <sparse-matrix-base>)))
500 type
501 (error "type argument must be a subclass of \
502 <sparse-matrix-base>, #f, or one of \
503 s8, u8, s16, u16, s32, u32, s64, u64, \
504 f16, f32 or f64, but got:" type))])
505 (%make-sparse-vector class default flags)))
506
507 (define-cproc sparse-matrix-num-entries (sv::<sparse-matrix>) ::<ulong>
508 (return (-> sv numEntries)))
509
510 (define-cproc sparse-matrix-set! (sv::<sparse-matrix> x y val) ::<void>
511 (SparseVectorSet sv (index-combine-2d x y NULL) val))
512
513 (define-cproc sparse-matrix-ref
514 (sv::<sparse-matrix> x y :optional fallback)
515 (setter sparse-matrix-set!)
516 (let* ([oor::int 0]
517 [i::u_long (index-combine-2d x y (& oor))]
518 [r SCM_UNBOUND])
519 (when (not oor)
520 (set! r (SparseVectorRef sv i fallback)))
521 (if (SCM_UNBOUNDP r)
522 (begin
523 (when (SCM_UNDEFINEDP (-> sv defaultValue))
524 (Scm_Error "%S doesn't have an entry at index (%S %S)"
525 (SCM_OBJ sv) x y))
526 (return (-> sv defaultValue)))
527 (return r))))
528
529 (define-cproc sparse-matrix-exists?
530 (sv::<sparse-matrix> x y) ::<boolean>
531 (let* ([oor::int 0]
532 [i::u_long (index-combine-2d x y (& oor))]
533 [r SCM_UNBOUND])
534 (when (not oor)
535 (set! r (SparseVectorRef sv i SCM_UNBOUND)))
536 (return (not (SCM_UNBOUNDP r)))))
537
538 (define-cproc sparse-matrix-default-value (sv::<sparse-matrix>)
539 (return (-> sv defaultValue)))
540
541 (define-cproc sparse-matrix-delete! (sv::<sparse-matrix> x y) ::<boolean>
542 (return (not (SCM_UNBOUNDP (SparseVectorDelete sv (index-combine-2d x y NULL))))))
543
544 (define-cproc sparse-matrix-clear! (sv::<sparse-matrix>) ::<void>
545 SparseVectorClear)
546
547 (define-cproc sparse-matrix-copy (sv::<sparse-matrix>) SparseVectorCopy)
548
549 (define-cproc sparse-matrix-inc! (sv::<sparse-matrix>
550 x y
551 delta::<number>
552 :optional fallback)
553 (return (SparseVectorInc sv (index-combine-2d x y NULL) delta fallback)))
554
555 (inline-stub
556 (define-cfn sparse-matrix-iter (args::ScmObj* _::int data::void*) :static
557 (let* ([iter::SparseVectorIter* (cast SparseVectorIter* data)]
558 [r (SparseVectorIterNext iter)]
559 [eofval (aref args 0)])
560 (if (SCM_FALSEP r)
561 (return (values eofval eofval eofval))
562 (let* ([x::u_long 0] [y::u_long 0])
563 (index-split-2d (SCM_CAR r) (& x) (& y))
564 (return (values (Scm_MakeIntegerU x)
565 (Scm_MakeIntegerU y)
566 (SCM_CDR r)))))))
567 )
568
569 (define-cproc %sparse-matrix-iter (sv::<sparse-matrix>)
570 (let* ([iter::SparseVectorIter* (SCM_NEW SparseVectorIter)])
571 (SparseVectorIterInit iter sv)
572 (return
573 (Scm_MakeSubr sparse-matrix-iter iter 1 0 '"sparse-matrix-iterator"))))
574
575 (define-cproc sparse-matrix-update! (sv::<sparse-matrix> x y proc
576 :optional fallback)
577 ;; NB: We use j to pass the index to continuation proc, for it will be
578 ;; cast to/fro pointer, and sizeof(u_long) may be smaller than the size
579 ;; of the pointer.
580 (let* ([i::u_long (index-combine-2d x y NULL)]
581 [j::uintptr_t i]
582 [v (SparseVectorRef sv i fallback)])
583 (when (SCM_UNBOUNDP v)
584 (when (SCM_UNDEFINEDP (-> sv defaultValue))
585 (Scm_Error "%S doesn't hav an entry at (%S %S)" sv x y))
586 (set! v (-> sv defaultValue)))
587 (let1/cps r (Scm_VMApply1 proc v)
588 [sv::SparseVector* j::uintptr_t]
589 (SparseVectorSet sv (cast u_long j) r)
590 (return SCM_UNDEFINED))))
591
592 (define-cproc sparse-matrix-push! (sv::<sparse-matrix> x y val) ::<void>
593 (let* ([i::u_long (index-combine-2d x y NULL)]
594 [v (SparseVectorRef sv i SCM_UNBOUND)])
595 (when (SCM_UNBOUNDP v)
596 (if (SCM_UNDEFINEDP (-> sv defaultValue))
597 (set! v SCM_NIL)
598 (set! v (-> sv defaultValue))))
599 (SparseVectorSet sv i (Scm_Cons val v))))
600
601 (define-cproc sparse-matrix-pop! (sv::<sparse-matrix> x y)
602 (let* ([i::u_long (index-combine-2d x y NULL)]
603 [v (SparseVectorRef sv i SCM_UNBOUND)])
604 (when (SCM_UNBOUNDP v)
605 (if (SCM_UNDEFINEDP (-> sv defaultValue))
606 (set! v SCM_NIL)
607 (set! v (-> sv defaultValue))))
608 (unless (SCM_PAIRP v)
609 (Scm_Error "%S's value for key (%S %S) is not a pair: %S" sv x y v))
610 (SparseVectorSet sv i (SCM_CDR v))
611 (return (SCM_CAR v))))
612
613 (define (sparse-matrix-fold sv proc seed)
614 (let ([iter (%sparse-matrix-iter sv)]
615 [end (list #f)])
616 (let loop ([seed seed])
617 (receive (x y val) (iter end)
618 (if (eq? val end)
619 seed
620 (loop (proc x y val seed)))))))
621
622 (define (sparse-matrix-map sv proc)
623 (sparse-matrix-fold sv (^[x y v s] (cons (proc x y v) s)) '()))
624
625 (define (sparse-matrix-for-each sv proc)
626 (sparse-matrix-fold sv (^[x y v _] (proc x y v)) #f))
627
628 (define (sparse-matrix-keys sv)
629 (sparse-matrix-fold sv (^[x y _ s] (cons (list x y) s)) '()))
630
631 (define (sparse-matrix-values sv)
632 (sparse-matrix-fold sv (^[x y v s] (cons v s)) '()))
633
634 ;;===============================================================
635 ;; protocols
636 ;;
637
638 (define-dict-interface <sparse-table>
639 :get sparse-table-ref
640 :put! sparse-table-set!
641 :delete! sparse-table-delete!
642 :exists? sparse-table-exists?
643 :fold sparse-table-fold
644 :for-each sparse-table-for-each
645 :map sparse-table-map
646 :keys sparse-table-keys
647 :values sparse-table-values
648 :pop! sparse-table-pop!
649 :push! sparse-table-push!
650 :update! sparse-table-update!
651 :comparator sparse-table-comparator)
652
653 (define-dict-interface <sparse-vector-base>
654 :get sparse-vector-ref
655 :put! sparse-vector-set!
656 :delete! sparse-vector-delete!
657 :exists? sparse-vector-exists?
658 :fold sparse-vector-fold
659 :for-each sparse-vector-for-each
660 :map sparse-vector-map
661 :keys sparse-vector-keys
662 :values sparse-vector-values
663 :pop! sparse-vector-pop!
664 :push! sparse-vector-push!
665 :update! sparse-vector-update!)
666
667 (define-method size-of ((s <sparse-table>)) (sparse-table-num-entries s))
668 (define-method size-of ((s <sparse-vector-base>)) (sparse-vector-num-entries s))