Debian Codegraph @

lib/data/range.scm

raw
1 ;;;
2 ;;; data.range - Range objects
3 ;;;
4 ;;; Copyright (c) 2021-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 ;; Superset of SRFI-196
35
36 (define-module data.range
37 (use gauche.sequence)
38 (use scheme.list)
39 (use scheme.division)
40 (use srfi.42)
41 (export
42 ;; we expose only the root classes (not the subclasses; they're
43 ;; internal details)
44 <range-meta> <range>
45
46 ;; Constructors
47 range numeric-range iota-range vector-range string-range
48 uvector-range bitvector/bool-range bitvector/int-range
49 range-append range-reverse
50
51 ;; Predicates
52 range? range=?
53
54 ;; Accessors
55 range-length range-ref range-first range-last
56
57 ;; Iteration
58 range-split-at subrange range-segment
59 range-take range-take-right
60 range-drop range-drop-right
61 range-count range-any
62 range-every range-map range-map->list range-map->vector
63 range-for-each range-filter-map range-filter-map->list
64 range-filter range-filter->list range-remove range-remove->list
65 range-fold range-fold-right
66
67 ;; Searching
68 range-index range-index-right
69 range-take-while range-take-while-right
70 range-drop-while range-drop-while-right
71
72 ;; Conversion
73 range->list range->vector range->string
74 vector->range range->generator))
75 (select-module data.range)
76
77 ;; The classes <range> and <flat-range> are private. Users must use
78 ;; SRFI-196 API.
79
80 ;; In Gauche, a range is a sequence whose element may be computed from
81 ;; the index.
82 (define-class <range-meta> (<class>) ())
83
84 (define-class <range> (<sequence>)
85 ((length :init-keyword :length)
86 (indexer :init-keyword :indexer)) ; obj, integer -> element
87 :metaclass <range-meta>)
88
89 (define-method write-object ((r <range>) port)
90 (format port "#<range (~d)>" (~ r'length)))
91
92 ;; special case, where indexer is simply a indexed reference from a sequence
93 ;; raw-indexer, storage and offset must be given at initialization; indexer
94 ;; is computed based on the initialized value. Changing them later will have
95 ;; no effect.
96 (define-class <flat-range> (<range>)
97 ((raw-indexer :init-keyword :raw-indexer :init-value ref)
98 (storage :init-keyword :storage)
99 (offset :init-keyword :offset :init-value 0)))
100
101 (define-method initialize ((r <flat-range>) initargs)
102 (next-method)
103 (let ([raw-indexer (~ r'raw-indexer)]
104 [offset (~ r'offset)]
105 [storage (~ r'storage)]
106 [length (~ r'length)])
107 (set! (~ r'indexer)
108 (^[o i]
109 (assume (and (exact-integer? i)
110 (<=:< 0 i length))
111 "Index out of range:" i)
112 (raw-indexer storage (+ offset i))))))
113
114 ;; appended ranges.
115 ;; ranges slot contains #((offset . subrange) ...)
116 (define (%appended-range-index range i)
117 (assume (exact-integer? i) "Range index must be an exact integer:" i)
118 (assume (<=:< 0 i (~ range'length)) "Range index out of range:" i)
119 (let* ([vec (~ range'ranges)]
120 [len (vector-length vec)])
121 (define (call-indexer p i)
122 ((~ (cdr p)'indexer) (cdr p) (- i (car p))))
123 (let loop ([lo 0] [hi len] [k (ash len -1)])
124 (let1 p (vector-ref vec k)
125 (cond [(= k lo) (call-indexer p i)]
126 [(> (car p) i) (loop lo k (+ lo (ash (- k lo) -1)))]
127 [else (loop k hi (+ k (ash (- hi k) -1)))])))))
128
129 (define-class <appended-range> (<range>)
130 ((indexer :init-value %appended-range-index)
131 (ranges :init-keyword :ranges)))
132
133 ;; take a section of a range.
134 ;; Use subrange to construct this type of instance. The constructor
135 ;; tries to "flatten" nested subranges.
136 ;; If the reverse? flag is true, the indexing is reversed.
137 (define (%subrange-index range i)
138 ((~ range'range'indexer) (~ range'range) (+ i (~ range'offset))))
139 (define (%subrange-index-reverse range i)
140 ((~ range'range'indexer) (~ range'range)
141 (+ (- (~ range'length) i 1) (~ range'offset))))
142
143 (define-class <subrange> (<range>)
144 ((indexer :init-value %subrange-index :init-keyword :indexer)
145 (range :init-keyword :range)
146 (offset :init-keyword :offset)))
147
148 (define (%subrange-reversed? subrange)
149 (eq? (~ subrange'indexer) %subrange-index-reverse))
150
151 ;;;
152 ;;; Constructors
153 ;;;
154
155 (define (range length indexer)
156 (assume (and (exact-integer? length) (>= length 0))
157 "Range length must be exact nonnnegative integer:" length)
158 (make <range> :length length :indexer (^[_ i] (indexer i))))
159
160 (define (numeric-range start end :optional (step 1))
161 (make <range>
162 :length (max 0 (ceiling->exact (/ (- end start) step)))
163 :indexer (^[_ i] (+ start (* i step)))))
164
165 (define (iota-range length :optional (start 0) (step 1))
166 (make <range>
167 :length length
168 :indexer (^[_ i] (+ start (* i step)))))
169
170 ;; optional arguments are Gauche-specific
171 (define (vector-range vec :optional (start 0) (end (vector-length vec)))
172 (assume-type vec <vector>)
173 (assume (<= 0 start end (vector-length vec))
174 "Start or end index is inconsistent:" start end)
175 (make <flat-range>
176 :length (- end start)
177 :raw-indexer vector-ref
178 :storage vec
179 :offset start))
180
181 ;; optional arguments are Gauche-specific
182 (define (string-range str :optional (start 0) (end (string-length str)))
183 (assume-type str <string>)
184 (assume (<= 0 start end (string-length str))
185 "Start or end index is inconsistent:" start end)
186 (make <flat-range>
187 :length (- end start)
188 :indexer string-ref
189 :storage (string-build-index! str)
190 :offset start))
191
192 ;; Gauche extension
193 (define (uvector-range uvec :optional (start 0) (end (uvector-length uvec)))
194 (assume-type uvec <uvector>)
195 (assume (<= 0 start end (uvector-length uvec))
196 "Start or end index is inconsistent:" start end)
197 (make <flat-range>
198 :length (- end start)
199 :raw-indexer uvector-ref
200 :storage uvec
201 :offset start))
202
203 ;; Gauche extension
204 (define (bitvector/bool-range bvec
205 :optional (start 0) (end (bitvector-length bvec)))
206 (assume-type bvec <bitvector>)
207 (assume (<= 0 start end (bitvector-length bvec))
208 "Start or end index is inconsistent:" start end)
209 (make <flat-range>
210 :length (- end start)
211 :raw-indexer bitvector-ref/bool
212 :storage bvec
213 :offset start))
214
215 ;; Gauche extension
216 (define (bitvector/int-range bvec
217 :optional (start 0) (end (bitvector-length bvec)))
218 (assume-type bvec <bitvector>)
219 (assume (<= 0 start end (bitvector-length bvec))
220 "Start or end index is inconsistent:" start end)
221 (make <flat-range>
222 :length (- end start)
223 :raw-indexer bitvector-ref/int
224 :storage bvec
225 :offset start))
226
227 (define (range-append . ranges)
228 (receive (off&ranges total)
229 (map-accum (^[range total]
230 (values (cons total range)
231 (+ total (range-length range))))
232 0 ranges)
233 (make <appended-range>
234 :length total
235 :ranges (list->vector off&ranges))))
236
237 (define (range-reverse rg :optional (start 0) (end (range-length rg)))
238 (assume-type rg <range>)
239 (assume (<= 0 start end (range-length rg))
240 "Start or end index is inconsistent:" start end)
241 (if (is-a? rg <subrange>)
242 (if (%subrange-reversed? rg)
243 (make <subrange>
244 :length (- end start)
245 :range (~ rg'range)
246 :offset (+ start (~ rg'offset)))
247 (make <subrange>
248 :indexer %subrange-index-reverse
249 :length (- end start)
250 :range (~ rg'range)
251 :offset (+ start (~ rg'offset))))
252 (make <subrange>
253 :indexer %subrange-index-reverse
254 :range rg
255 :length (- end start)
256 :offset start)))
257
258 ;;;
259 ;;; Predicates
260 ;;;
261
262 (define (range? x) (is-a? x <range>))
263
264 (define (range=? elt= . ranges)
265 (or (null? ranges)
266 (and (assume (range? (car ranges)) "Range required, but got:" (car ranges))
267 (null? (cdr ranges)))
268 (let1 len (range-length (car ranges))
269 (every?-ec (: r (cdr ranges))
270 (and (= len (range-length r))
271 (every?-ec (: i len)
272 (elt= (range-ref (car ranges) i)
273 (range-ref r i))))))))
274
275 ;;;
276 ;;; Accessors
277 ;;;
278
279 (define (range-length range)
280 (assume (range? range) "Range required, but got:" range)
281 (~ range'length))
282
283 ;; The optional fallback is Gauche extension
284 (define (range-ref range n :optional fallback)
285 (assume (range? range))
286 (cond [(<=:< 0 n (range-length range)) ((~ range'indexer) range n)]
287 [(undefined? fallback) (error "Index out of range:" n)]
288 [else fallback]))
289
290 (define (range-first range :optional fallback)
291 (if (zero? (range-length range))
292 (if (undefined? fallback)
293 (error "range is empty:" range)
294 fallback)
295 (range-ref range 0)))
296 (define (range-last range :optional fallback)
297 (let1 len (range-length range)
298 (if (zero? len)
299 (if (undefined? fallback)
300 (error "range is empty:" range)
301 fallback)
302 (range-ref range (- len 1)))))
303
304 ;;;
305 ;;; Iteration
306 ;;;
307
308 (define (range-split-at range index)
309 (assume-type range <range>)
310 (assume (<= 0 index (range-length range)))
311 (values (subrange range 0 index)
312 (subrange range index (range-length range))))
313
314 (define (subrange range start end)
315 (assume-type range <range>)
316 (assume (<= start end (range-length range))
317 "Subrange start/end index out of original range:"
318 range start end)
319 (if (is-a? range <subrange>)
320 ;; We flatten the range
321 (make <subrange>
322 :length (- end start)
323 :range (~ range'range) ; use inner range
324 :offset (+ (~ range'offset) start))
325 (make <subrange>
326 :length (- end start)
327 :range range
328 :offset start)))
329
330 (define (range-segment range length)
331 (let* ([total-length (range-length range)]
332 [n (ceiling-quotient total-length length)])
333 (map (^i (subrange range
334 (* i length)
335 (min (* (+ i 1) length) total-length)))
336 (liota n))))
337
338 (define (range-take range index)
339 (subrange range 0 index))
340 (define (range-take-right range index)
341 (subrange range (- (range-length range) index) (range-length range)))
342
343 (define (range-drop range index)
344 (subrange range index (range-length range)))
345 (define (range-drop-right range index)
346 (subrange range 0 (- (range-length range) index)))
347
348 (define (range-count pred range1 . ranges)
349 (if (null? ranges)
350 (range-fold (^[cnt val] (if (pred val) (+ cnt 1) cnt)) 0 range1)
351 (apply range-fold (^[cnt . vals] (if (apply pred vals) (+ cnt 1) cnt))
352 0 range1 ranges)))
353
354 (define (range-any pred range1 . ranges)
355 (if (null? ranges)
356 (let1 g (range->generator range1)
357 (let loop ([v (g)])
358 (cond [(eof-object? v) #f]
359 [(pred v)]
360 [else (loop (g))])))
361 (let1 gs (cons (range->generator range1)
362 (map range->generator ranges))
363 (let loop ([vs (map (^g (g)) gs)])
364 (cond [(any eof-object? vs) #f]
365 [(apply pred vs)]
366 [else (loop (map (^g (g)) gs))])))))
367
368 (define (range-every pred range1 . ranges)
369 (if (null? ranges)
370 (let1 g (range->generator range1)
371 (let loop ([v (g)] [last #t])
372 (cond [(eof-object? v) last]
373 [(pred v) => (cut loop (g) <>)]
374 [else #f])))
375 (let1 gs (cons (range->generator range1)
376 (map range->generator ranges))
377 (let loop ([vs (map (^g (g)) gs)] [last #t])
378 (cond [(any eof-object? vs) last]
379 [(apply pred vs) => (cut loop (map (^g (g)) gs) <>)]
380 [else #f])))))
381
382 (define (range-map proc range1 . ranges)
383 (vector-range (apply range-map->vector proc range1 ranges)))
384
385 (define (range-map->list proc range1 . ranges)
386 (if (null? ranges)
387 (range-fold-right (^[r v] (cons (proc v) r)) '() range1)
388 (apply range-fold-right (^[r . vs] (cons (apply proc vs) r)) '()
389 range1 ranges)))
390 (define (range-map->vector proc range1 . ranges)
391 (if (null? ranges)
392 (rlet1 vec (make-vector (range-length range1))
393 (do-ec (: k (range-length range1))
394 (vector-set! vec k (proc (range-ref range1 k)))))
395 (let* ([ranges (cons range1 ranges)]
396 [vec (make-vector (apply min (map range-length ranges)))])
397 (do-ec (: k (vector-length vec))
398 (vector-set! vec k (apply proc (map (cut range-ref <> k) ranges))))
399 vec)))
400
401 (define (range-for-each proc range1 . ranges)
402 (if (null? ranges)
403 (range-fold (^[_ v] (proc v)) #f range1)
404 (apply range-fold (^[_ . vs] (apply proc vs)) #f range1 ranges)))
405
406 (define (range-filter-map proc range1 . ranges)
407 ($ vector-range $ list->vector
408 $ apply range-filter-map->list proc range1 ranges))
409
410 (define (range-filter-map->list proc range1 . ranges)
411 (if (null? ranges)
412 (range-fold-right (^[r e] (if-let1 v (proc e)
413 (cons v r)
414 r))
415 '() range1)
416 (apply range-fold-right
417 (^[r . es] (if-let1 v (apply proc es)
418 (cons v r)
419 r))
420 '() range1 ranges)))
421
422 (define (range-filter pred range)
423 ($ vector-range $ list->vector $ range-filter->list pred range))
424 (define (range-filter->list pred range)
425 (range-fold-right (^[r e] (if (pred e) (cons e r) r)) '() range))
426
427 (define (range-remove pred range)
428 ($ vector-range $ list->vector $ range-remove->list pred range))
429 (define (range-remove->list pred range)
430 (range-fold-right (^[r e] (if (pred e) r (cons e r))) '() range))
431
432 ;; kons is invoked with the same order of vector-fold (state first)
433 (define (range-fold kons knil range1 . ranges)
434 (if (null? ranges)
435 (fold (^[i seed] (kons seed (range-ref range1 i)))
436 knil
437 (liota (range-length range1)))
438 (let1 len (fold (^[r m] (min m (range-length r)))
439 (range-length range1)
440 ranges)
441 (fold (^[i seed] (apply kons seed
442 (range-ref range1 i)
443 (map (^r (range-ref r i)) ranges)))
444 knil
445 (liota len)))))
446
447 (define (range-fold-right kons knil range1 . ranges)
448 (if (null? ranges)
449 (fold (^[i seed] (kons seed (range-ref range1 i)))
450 knil
451 (liota (range-length range1) (- (range-length range1) 1) -1))
452 (let1 len (fold (^[r m] (min m (range-length r)))
453 (range-length range1)
454 ranges)
455 (fold (^[i seed] (apply kons seed
456 (range-ref range1 i)
457 (map (^r (range-ref r i)) ranges)))
458 knil
459 (liota len (- len 1) -1)))))
460
461 ;;;
462 ;;; Searching
463 ;;;
464
465 (define (range-index pred range1 . ranges)
466 (if (null? ranges)
467 (let1 len (range-length range1)
468 (let loop ([i 0])
469 (cond [(= i len) #f]
470 [(pred (range-ref range1 i)) i]
471 [else (loop (+ i 1))])))
472 (let1 len (apply min (range-length range1) (map range-length ranges))
473 (let loop ([i 0])
474 (cond [(= i len) #f]
475 [(apply pred (range-ref range1 i)
476 (map (cut range-ref <> i) ranges)) i]
477 [else (loop (+ i 1))])))))
478
479 (define (range-index-right pred range1 . ranges)
480 (if (null? ranges)
481 (let1 len (range-length range1)
482 (let loop ([i (- len 1)])
483 (cond [(= i 0) #f]
484 [(pred (range-ref range1 i)) i]
485 [else (loop (- i 1))])))
486 (let1 len (apply min (range-length range1) (map range-length ranges))
487 (let loop ([i (- len 1)])
488 (cond [(= i 0) #f]
489 [(apply pred (range-ref range1 i)
490 (map (cut range-ref <> i) ranges)) i]
491 [else (loop (- i 1))])))))
492
493 (define (range-take-while pred r)
494 (let1 len (range-length r)
495 (let loop ([i 0])
496 (if (= i len)
497 r
498 (let1 e (range-ref r i)
499 (if (pred e)
500 (loop (+ i 1))
501 (subrange r 0 i)))))))
502
503 (define (range-take-while-right pred r)
504 (let1 len (range-length r)
505 (let loop ([i (- len 1)])
506 (if (= i 0)
507 r
508 (let1 e (range-ref r i)
509 (if (pred e)
510 (loop (- i 1))
511 (subrange r (+ i 1) len)))))))
512
513 (define (range-drop-while pred r)
514 (let1 len (range-length r)
515 (let loop ([i 0])
516 (if (= i len)
517 (range 0 (constantly #f))
518 (let1 e (range-ref r i)
519 (if (pred e)
520 (loop (+ i 1))
521 (subrange r i len)))))))
522
523 (define (range-drop-while-right pred r)
524 (let1 len (range-length r)
525 (let loop ([i (- len 1)])
526 (if (= i 0)
527 (range 0 (constantly #f))
528 (let1 e (range-ref r i)
529 (if (pred e)
530 (loop (- i 1))
531 (subrange r 0 (+ i 1))))))))
532
533 ;;;
534 ;;; Conversion
535 ;;;
536
537 (define (range->list range)
538 (assume-type range <range>)
539 (list-ec (: i (range-length range))
540 (range-ref range i)))
541
542 (define (range->vector range)
543 (assume-type range <range>)
544 ;; We might be able to return the internal storage directly if range is
545 ;; <flat-range> on a vector, since "it is an error" to mutate the return
546 ;; value; but there would be no check if the caller conforms it. Until
547 ;; we see the case that such optimization is effective, we just build
548 ;; a new vector.
549 (vector-ec (: i (range-length range))
550 (range-ref range i)))
551
552 (define (range->string range)
553 (assume-type range <range>)
554 (if (and (is-a? range <flat-range>)
555 (string? (~ range'storage)))
556 (substring (~ range'storage)
557 (~ range'offset)
558 (+ (~ range'offset) (~ range'length)))
559 (string-ec (: i (range-length range))
560 (range-ref range i))))
561
562 ;; optional arguments are Gauche-specific
563 (define (vector->range vec :optional (start 0) (end (vector-length vec)))
564 (vector-range (vector-copy vec start end)))
565
566 ;; optional arguments are Gauche-specific
567 (define (range->generator range :optional (start 0) (end (range-length range)))
568 (define i start)
569 (^[] (if (>= i end)
570 (eof-object)
571 (begin0 (range-ref range i) (inc! i)))))
572
573 ;;;
574 ;;; Sequence protocol
575 ;;;
576
577 (define-method referencer ((r <range>)) (~ r'indexer))
578
579 (define-method call-with-iterator ((r <range>) proc
580 :key (start 0)
581 (end (range-length r))
582 :allow-other-keys)
583 (let ([i start])
584 (proc (^[] (>= i end))
585 (^[] (begin0 (range-ref r i) (inc! i))))))
586
587 (define-method call-with-reverse-iterator ((r <range>) proc
588 :key (start 0)
589 (end (range-length r))
590 :allow-other-keys)
591 (let ([i (- end 1)])
592 (proc (^[] (< i start)
593 (^[] (begin0 (range-ref r i) (dec! i)))))))
594
595 (define-method call-with-builder ((c <range-meta>) proc :key (size #f))
596 (if (integer? size)
597 (let ([buf (make-vector size #f)]
598 [i 0])
599 (proc (^v (vector-set! buf i v) (inc! i))
600 (^[] (vector-range buf))))
601 (let ([vs '()])
602 (proc (^v (push! vs v))
603 (^[] (vector-range (reverse-list->vector vs)))))))
604
605 (define-method size-of ((r <range>)) (range-length r))
606
607 ;; some shortcuts
608 (define-method subseq ((r <range>) s e) (subrange r s e))
609 (define-method subseq ((r <range>) s) (subrange r s (range-length r)))
610 (define-method coerce-to ((r <range-meta>) (v <vector>)) (vector-range v))
611 (define-method coerce-to ((r <range-meta>) (v <string>)) (string-range v))