Debian Codegraph @

libsrc/scheme/vector.scm

raw
1 ;;;
2 ;;; scheme.vector - vector library (R7RS Red)
3 ;;;
4 ;;; Copyright (c) 2016-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 ;; Originally SRFI-133
35 (define-module scheme.vector
36 (use util.match)
37 (export
38 ;; constructors
39 make-vector vector vector-unfold vector-unfold-right
40 vector-copy vector-reverse-copy
41 vector-append vector-concatenate vector-append-subvectors
42
43 ;; Predicates
44 vector? vector-empty? vector=
45
46 ;; Selectors
47 vector-ref vector-length
48
49 ;; Iteration
50 vector-fold vector-fold-right
51 vector-map vector-map!
52 vector-for-each vector-count
53 vector-cumulate
54
55 ;; Searching
56 vector-index vector-index-right
57 vector-skip vector-skip-right
58 vector-binary-search
59 vector-any vector-every
60 vector-partition
61
62 ;; Mutators
63 vector-set! vector-swap!
64 vector-fill! vector-reverse!
65 vector-copy! vector-reverse-copy!
66 vector-unfold! vector-unfold-right!
67
68 ;; Conversion
69 vector->list reverse-vector->list
70 list->vector reverse-list->vector
71 vector->string string->vector
72 ))
73
74 (select-module scheme.vector)
75
76 ;; Built-ins:
77 ;; make-vector vector vector-copy vector-append
78 ;; vector? vector-ref vector-length
79 ;; vector-map vector-map! vector-for-each
80 ;; vector-set! vector-fill! vector-copy!
81 ;; vector->list list->vector reverse-list->vector
82 ;; vector->string string->vector
83
84 ;; common checker. returns start and end index.
85 ;; if open-end? is #t, accept -1 as e, and we make it the length of vec.
86 (define (%vector-check-start+end v s e open-end?)
87 (assume-type v <vector>)
88 (let1 len (vector-length v)
89 (unless (<= 0 s len)
90 (errorf "start index (~s) out of range of a vector: ~s" s v))
91 (unless (or (and open-end? (<= e len))
92 (<= 0 e len))
93 (errorf "end index (~s) out of range of a vector: ~s" e v))
94 (unless (or (and open-end? (< e 0)) (<= s e))
95 (errorf "start index (~s) is greater than end index (~s)" s e))
96 (values s (if (and open-end? (< e 0)) len e))))
97
98 ;; vector mutability check
99 ;; currently Gauche doesn't track vector mutability (which is a bad thing)
100 ;; eventually we'll check immutable vectors here.
101 (define-inline (%ensure-mutable v) (values))
102
103 (define %vector-unfold!
104 (case-lambda
105 [(f rvec s e)
106 (let loop ([i s])
107 (when (< i e)
108 (let1 elt (f i)
109 (vector-set! rvec i elt)
110 (loop (+ i 1)))))]
111 [(f rvec s e seed)
112 (let loop ([i s] [seed seed])
113 (when (< i e)
114 (receive (elt seed) (f i seed)
115 (vector-set! rvec i elt)
116 (loop (+ i 1) seed))))]
117 [(f rvec s e . seeds)
118 (let loop ([i s] [seeds seeds])
119 (when (< i e)
120 (receive (elt . seeds) (apply f i seeds)
121 (vector-set! rvec i elt)
122 (loop (+ i 1) seeds))))]))
123
124 (define %vector-unfold-right!
125 (case-lambda
126 [(f rvec s e)
127 (let loop ([i (- e 1)])
128 (when (<= s i)
129 (let1 elt (f i)
130 (vector-set! rvec i elt)
131 (loop (- i 1)))))]
132 [(f rvec s e seed)
133 (let loop ([i (- e 1)] [seed seed])
134 (when (<= s i)
135 (receive (elt seed) (f i seed)
136 (vector-set! rvec i elt)
137 (loop (- i 1) seed))))]
138 [(f rvec s e . seeds)
139 (let loop ([i (- e 1)] [seeds seeds])
140 (when (<= s i)
141 (receive (elt . seeds) (apply f i seeds)
142 (vector-set! rvec i elt)
143 (loop (- i 1) seeds))))]))
144
145 (define (vector-unfold f len . seeds)
146 (rlet1 rvec (make-vector len)
147 (apply %vector-unfold! f rvec 0 len seeds)))
148
149 (define (vector-unfold-right f len . seeds)
150 (rlet1 rvec (make-vector len)
151 (apply %vector-unfold-right! f rvec 0 len seeds)))
152
153 (define (vector-unfold! f rvec s e . seeds)
154 (assume-type rvec <vector>)
155 (%ensure-mutable rvec)
156 (let1 len (vector-length rvec)
157 (unless (<= 0 s len) (error "start index out of range:" s))
158 (unless (<= 0 e len) (error "end index out of range:" e))
159 (unless (<= s e)
160 (errorf "start index (~s) is greater than end index (~s)" s e))
161 (apply %vector-unfold! f rvec s e seeds)))
162
163 (define (vector-unfold-right! f rvec s e . seeds)
164 (assume-type rvec <vector>)
165 (%ensure-mutable rvec)
166 (let1 len (vector-length rvec)
167 (unless (<= 0 s len) (error "start index out of range:" s))
168 (unless (<= 0 e len) (error "end index out of range:" e))
169 (unless (<= s e)
170 (errorf "start index (~s) is greater than end index (~s)" s e))
171 (apply %vector-unfold-right! f rvec s e seeds)))
172
173 (define (%vector-reverse-copy! target tstart source sstart send)
174 ;; assumes args are all valid
175 (do ([i tstart (+ i 1)]
176 [j (- send 1) (- j 1)])
177 [(< j sstart)]
178 (vector-set! target i (vector-ref source j))))
179
180 (define (vector-reverse-copy vec :optional (start 0) (end -1))
181 (receive (s e) (%vector-check-start+end vec start end #t)
182 (rlet1 rvec (make-vector (- e s))
183 (%vector-reverse-copy! rvec 0 vec s e))))
184
185 (define (vector-reverse-copy! target tstart src :optional (sstart 0) (send -1))
186 (assume-type target <vector>)
187 (%ensure-mutable target)
188 (let1 tlen (vector-length target)
189 (unless (<= 0 tstart tlen)
190 (errorf "target start index (~s) out of range of a target vector" tstart))
191 (receive (s e) (%vector-check-start+end src sstart send #t)
192 (unless (<= (- e s) (- tlen tstart))
193 (errorf "source range (~s,~s) is greater than the target vector" s e))
194 (if (and (eq? target src)
195 (or (and (<= s tstart) (< tstart e))
196 (and (< tstart s) (< s (+ tstart (- e s))))))
197 ;; overlapping self copy. we need extra step not to overwrite
198 ;; before copy.
199 (begin
200 (vector-copy! target tstart src s e)
201 (%vector-reverse! target tstart (+ tstart (- e s))))
202 (%vector-reverse-copy! target tstart src s e)))))
203
204 (define (vector-concatenate vecs) (apply vector-append vecs))
205
206 (define (vector-append-subvectors . args)
207 (let* ([subvecs (slices args 3)]
208 [len (fold (^[sv c]
209 (match sv
210 [(v s e)
211 (unless (vector? v)
212 (error "vector expected, but got:" v))
213 (let1 l (vector-length v)
214 (unless (and (<= 0 s l) (<= 0 e l) (<= s e))
215 (errorf "invalid subvector range, \
216 start:~s end:~s subvec:~s" s e v))
217 (+ c (- e s)))]
218 [_ (error "length of argument is not a multiple of 3:"
219 args)]))
220 0 subvecs)])
221 (rlet1 rvec (make-vector len)
222 (fold (^[sv c]
223 (match-let1 (v s e) sv
224 (vector-copy! rvec c v s e)
225 (+ c (- e s))))
226 0 subvecs))))
227
228 (define (vector-empty? vec)
229 (assume-type vec <vector>)
230 (zero? (vector-length vec)))
231
232 (define (vector= elt= . vecs)
233 (match vecs
234 [() #t]
235 [(vec) (assume-type vec <vector>) #t]
236 [(v . vecs)
237 ;; we could use SRFI-114 make-vector-comparator but the overhead of
238 ;; creating a comparator might be too much.
239 (assume-type v <vector>)
240 (let1 len (vector-length v)
241 (define (pairwise= va vb)
242 (let loop ([i 0])
243 (or (= i len)
244 (and (elt= (vector-ref va i) (vector-ref vb i))
245 (loop (+ i 1))))))
246 (and (every (^w (= (vector-length w) len)) vecs)
247 (every pairwise= (cons v vecs) vecs)))]))
248
249 (define vector-fold
250 (case-lambda
251 ([proc seed v] ; fast path
252 (assume-type v <vector>)
253 (let1 len (vector-length v)
254 (let loop ([i 0] [seed seed])
255 (if (= i len) seed (loop (+ i 1) (proc seed (vector-ref v i)))))))
256 ([proc seed v . vs]
257 (let* ([vs (cons v vs)]
258 [len (fold (^[v len]
259 (assume-type v <vector>)
260 (if len (min (vector-length v) len) (vector-length v)))
261 #f vs)])
262 (let loop ([i 0] [seed seed])
263 (if (= i len)
264 seed
265 (loop (+ i 1) (apply proc seed (map (cut vector-ref <> i) vs)))))))))
266
267 (define vector-fold-right
268 (case-lambda
269 ([proc seed v] ; fast path
270 (assume-type v <vector>)
271 (let1 len (vector-length v)
272 (let loop ([i (- len 1)] [seed seed])
273 (if (= i -1) seed (loop (- i 1) (proc seed (vector-ref v i)))))))
274 ([proc seed v . vs]
275 (let* ([vs (cons v vs)]
276 [len (fold (^[v len]
277 (assume-type v <vector>)
278 (if len (min (vector-length v) len) (vector-length v)))
279 #f vs)])
280 (let loop ([i (- len 1)] [seed seed])
281 (if (= i -1)
282 seed
283 (loop (- i 1) (apply proc seed (map (cut vector-ref <> i) vs)))))))))
284
285 (define vector-count
286 (case-lambda
287 ([pred v] ; fast path
288 (vector-fold (^[c e] (if (pred e) (+ 1 c) c)) 0 v))
289 ([pred v . vs]
290 (apply vector-fold (^[c . es] (if (apply pred es) (+ 1 c) c)) 0 v vs))))
291
292 (define (vector-cumulate f seed vec)
293 (assume-type vec <vector>)
294 (let1 len (vector-length vec)
295 (rlet1 rvec (make-vector len)
296 (let loop ([i 0] [seed seed])
297 (when (< i len)
298 (let1 e (f seed (vector-ref vec i))
299 (vector-set! rvec i e)
300 (loop (+ i 1) e)))))))
301
302 (define vector-index
303 (case-lambda
304 ([pred v] ; fast path
305 (assume-type v <vector>)
306 (let1 len (vector-length v)
307 (let lp ([i 0])
308 (cond [(= i len) #f] [(pred (vector-ref v i)) i] [else (lp (+ i 1))]))))
309 ([pred v . vs]
310 (let* ([vs (cons v vs)]
311 [len (fold (^[v len]
312 (assume-type v <vector>)
313 (if len
314 (min (vector-length v) len)
315 (vector-length v)))
316 #f vs)])
317 (let lp ([i 0])
318 (cond [(= i len) #f]
319 [(apply pred (map (cut vector-ref <> i) vs)) i]
320 [else (lp (+ i 1))]))))))
321
322 (define vector-index-right
323 (case-lambda
324 ([pred v] ; fast path
325 (assume-type v <vector>)
326 (let1 len (vector-length v)
327 (let lp ([i (- len 1)])
328 (cond [(= i -1) #f] [(pred (vector-ref v i)) i] [else (lp (- i 1))]))))
329 ([pred v . vs]
330 (let* ([vs (cons v vs)]
331 [len (fold (^[v len]
332 (assume-type v <vector>)
333 (if len
334 (min (vector-length v) len)
335 (vector-length v)))
336 #f vs)])
337 (let lp ([i (- len 1)])
338 (cond [(= i -1) #f]
339 [(apply pred (map (cut vector-ref <> i) vs)) i]
340 [else (lp (- i 1))]))))))
341
342 (define (vector-skip pred v . vs)
343 (apply vector-index (complement pred) v vs))
344
345 (define (vector-skip-right pred v . vs)
346 (apply vector-index-right (complement pred) v vs))
347
348 (define (vector-binary-search vec value cmp :optional (start 0) (end -1))
349 (assume-type vec <vector>)
350 (receive (s e) (%vector-check-start+end vec start end #t)
351 (and (not (= s e))
352 (let rec ([lo s] [hi e])
353 (let* ([mid (ash (+ lo hi) -1)]
354 [r (cmp (vector-ref vec mid) value)])
355 (cond [(zero? r) mid]
356 [(= lo mid) #f]
357 [(< r 0) (rec mid hi)]
358 [else (rec lo mid)]))))))
359
360 (define vector-any
361 (case-lambda
362 ([pred v]
363 (assume-type v <vector>)
364 (let1 len (vector-length v)
365 (let loop ([i 0])
366 (if (= i len)
367 #f
368 (or (pred (vector-ref v i))
369 (loop (+ i 1)))))))
370 ([pred v . vs]
371 (let* ([vs (cons v vs)]
372 [len (fold (^[v len]
373 (assume-type v <vector>) (min (vector-length v) len))
374 +inf.0 vs)])
375 (let loop ([i 0])
376 (if (= i len)
377 #f
378 (or (apply pred (map (cut vector-ref <> i) vs))
379 (loop (+ i 1)))))))))
380
381 (define vector-every
382 (case-lambda
383 ([pred v]
384 (assume-type v <vector>)
385 (let1 len (vector-length v)
386 (let loop ([i 0] [last #t])
387 (if (= i len)
388 last
389 (and-let1 last (pred (vector-ref v i))
390 (loop (+ i 1) last))))))
391 ([pred v . vs]
392 (let* ([vs (cons v vs)]
393 [len (fold (^[v len]
394 (assume-type v <vector>) (min (vector-length v) len))
395 +inf.0 vs)])
396 (let loop ([i 0] [last #t])
397 (if (= i len)
398 last
399 (and-let1 last (apply pred (map (cut vector-ref <> i) vs))
400 (loop (+ i 1) last))))))))
401
402 (define (vector-partition pred vec)
403 (assume-type vec <vector>)
404 (let* ([len (vector-length vec)]
405 [rvec (make-vector len)])
406 (let loop ([i 0] [j 0] [fails '()])
407 (if (= i len)
408 (do ([k (- len 1) (- k 1)]
409 [fails fails (cdr fails)])
410 [(null? fails) (values rvec j)]
411 (vector-set! rvec k (car fails)))
412 (let1 elt (vector-ref vec i)
413 (if (pred elt)
414 (begin (vector-set! rvec j elt)
415 (loop (+ i 1) (+ j 1) fails))
416 (loop (+ i 1) j (cons elt fails))))))))
417
418 (define (%vector-swap! vec i j)
419 (let1 tmp (vector-ref vec i)
420 (vector-set! vec i (vector-ref vec j))
421 (vector-set! vec j tmp)))
422
423 (define (vector-swap! vec i j)
424 (assume-type vec <vector>)
425 (%ensure-mutable vec)
426 (let1 max (- (vector-length vec) 1)
427 (unless (<= 0 i max) (error "index i is out of range:" i))
428 (unless (<= 0 j max) (error "index j is out of range:" j))
429 (%vector-swap! vec i j)))
430
431 (define (%vector-reverse! vec s e)
432 (do ([i s (+ i 1)]
433 [j (- e 1) (- j 1)])
434 [(<= j i)]
435 (%vector-swap! vec i j)))
436
437 (define (vector-reverse! vec :optional (start 0) (end -1))
438 (assume-type vec <vector>)
439 (%ensure-mutable vec)
440 (receive (s e) (%vector-check-start+end vec start end #t)
441 (%vector-reverse! vec s e)))
442
443 (define (reverse-vector->list vec :optional (start 0) (end -1))
444 (assume-type vec <vector>)
445 (receive (s e) (%vector-check-start+end vec start end #t)
446 (do ([i s (+ i 1)]
447 [r '() (cons (vector-ref vec i) r)])
448 [(= i e) r]
449 )))