Debian Codegraph @

lib/srfi/214.scm

raw
1 ;;;
2 ;;; SRFI-214 - flexvector
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 ;; We use data.ring-buffer to implement flexvector
35 ;;
36 (define-module srfi.214
37 (use srfi.42)
38 (use data.ring-buffer)
39 (export make-flexvector flexvector
40 flexvector-unfold flexvector-unfold-right
41 flexvector-copy flexvector-reverse-copy
42 flexvector-append flexvector-concatenate
43 flexvector-append-subvectors
44
45 flexvector? flexvector-empty? flexvector=?
46
47 flexvector-ref flexvector-front flexvector-back
48 flexvector-length
49
50 flexvector-add! flexvector-add-front! flexvector-add-back!
51 flexvector-add-all! flexvector-append! flexvector-remove!
52 flexvector-remove-front! flexvector-remove-back!
53 flexvector-remove-range!
54 flexvector-clear! flexvector-set!
55 flexvector-swap! flexvector-fill! flexvector-reverse!
56 flexvector-copy! flexvector-reverse-copy!
57
58 flexvector-fold flexvector-fold-right
59 flexvector-map flexvector-map/index
60 flexvector-append-map flexvector-append-map/index
61 flexvector-filter flexvector-filter/index
62 flexvector-filter! flexvector-filter/index!
63 flexvector-for-each flexvector-for-each/index
64 flexvector-count flexvector-cumulate
65
66 flexvector-index flexvector-index-right
67 flexvector-skip flexvector-skip-right
68 flexvector-binary-search
69 flexvector-any flexvector-every flexvector-partition
70
71 flexvector->vector vector->flexvector
72 flexvector->list list->flexvector reverse-flexvector->list
73 flexvector->string string->flexvector
74 generator->flexvector))
75 (select-module srfi.214)
76
77 ;;
78 ;; Constructors
79 ;;
80 (define (make-flexvector size :optional fill)
81 (make-ring-buffer (make-vector size fill)
82 :initial-tail-index size))
83 (define (flexvector . xs)
84 (let1 v (list->vector xs)
85 (make-ring-buffer v :initial-tail-index (vector-length v))))
86
87 (define (flexvector-unfold p f g . seeds)
88 (rlet1 fv (make-ring-buffer)
89 (let loop ((seeds seeds))
90 (unless (apply p seeds)
91 (ring-buffer-add-back! fv (apply f seeds))
92 (loop (values->list (apply g seeds)))))))
93
94 (define (flexvector-unfold-right p f g . seeds)
95 (rlet1 fv (make-ring-buffer)
96 (let loop ((seeds seeds))
97 (unless (apply p seeds)
98 (ring-buffer-add-front! fv (apply f seeds))
99 (loop (values->list (apply g seeds)))))))
100
101 (define (flexvector-copy fv :optional (start 0)
102 (end (flexvector-length fv)))
103 (assume-type fv <ring-buffer>)
104 (make-ring-buffer (ring-buffer->flat-vector fv start end)
105 :initial-tail-index (- end start)))
106
107 (define (flexvector-reverse-copy fv :optional (start 0)
108 (end (flexvector-length fv)))
109 (assume-type fv <ring-buffer>)
110 ;; Can be more efficient, but for now.
111 ;; (We want to treat ring-buffer as opaque, so avoid accessing storage
112 ;; diractly).
113 (let1 vec (make-vector (- end start))
114 (dotimes [k (- end start)]
115 (vector-set! vec k (ring-buffer-ref fv (- end k 1))))
116 (make-ring-buffer vec :initial-tail-index (- end start))))
117
118 (define (flexvector-append . fvs) (flexvector-concatenate fvs))
119
120 (define (flexvector-concatenate fvs)
121 (define len (fold (^[fv s] (+ (flexvector-length fv) s)) 0 fvs))
122 (rlet1 dest (make-vector len)
123 (let loop ([fvs fvs] [k 0])
124 (if (null? fvs)
125 (make-ring-buffer dest :initial-tail-index len)
126 (begin (ring-buffer->flat-vector! dest k (car fvs))
127 (loop (cdr fvs) (+ k (flexvector-length (car fvs)))))))))
128
129 ;; flexvector-append-subvectors
130
131 ;;
132 ;; Predicates
133 ;;
134 (define (flexvector? obj) (ring-buffer? obj))
135
136 (define (flexvector-empty? obj) (ring-buffer-empty? obj))
137
138 (define flexvector=?
139 (case-lambda
140 [(elt=?) #t]
141 [(elt=? fv) (assume (flexvector? fv)) #t]
142 [(elt=? fv . fvs)
143 (let1 len (flexvetor-length fv)
144 (every (^[fv2]
145 (and (= len (flexvector-length fv2))
146 (every-ec (: i len)
147 (elt=? (flexvector-ref a i)
148 (flexvector-ref b i)))))
149 fvs))]))
150
151 ;;
152 ;; Selectors
153 ;;
154 (define (flexvector-ref fv i) (ring-buffer-ref fv i))
155 (define (flexvector-front fv) (ring-buffer-front fv))
156 (define (flexvector-back fv) (ring-buffer-back fv))
157 (define (flexvector-length fv) (ring-buffer-num-entries fv))
158
159 ;;
160 ;; Mutators
161 ;;
162
163 (define (flexvector-add! fv i . xs)
164 (ring-buffer-insert-all! fv i xs))
165 (define (flexvector-add-all! f i xs)
166 (ring-buffer-insert-all! fv i xs))
167
168 (define (flexvector-add-front! fv . xs)
169 (for-each (cut ring-buffer-add-front! fv <>) (reverse xs)))
170 (define (flexvector-add-back! fv . xs)
171 (for-each (cut ring-buffer-add-back! fv <>) xs))
172
173 ;; flexvector-append!
174 ;; flexvector-remove!
175
176 (define (flexvector-remove-front! fv) (ring-buffer-remove-front! fv))
177 (define (flexvector-remove-back! fv) (ring-buffer-remove-back! fv))
178
179 ;; flexvector-remove-range!
180
181 (define (flexvector-clear! fv) (ring-buffer-clear! fv))
182
183 (define (flexvector-set! fv i obj) (ring-buffer-set! fv i obj))
184
185 ;; flexvector-swap!
186 ;; flexvector-fill!
187 ;; flexvector-reverse!
188 ;; flexvector-copy!
189 ;; flexvector-reverse-copy!
190
191 ;;
192 ;; Iteration
193 ;;