Debian Codegraph @

lib/data/ideque.scm

raw
1 ;;;
2 ;;; data.ideque - immutable double-ended queue
3 ;;;
4 ;;; Copyright (c) 2015-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 ;; This implements banker's deque
35 ;; as described in Chris Okasaki's Purely Functional Data Structures.
36 ;; It provides amortized O(1) operation.
37 ;; The API is adapted to SRFI-134
38
39 (define-module data.ideque
40 (use gauche.record)
41 (use gauche.generator)
42 (use gauche.lazy)
43 (use util.match)
44 (use scheme.list)
45 (export <ideque>
46 make-ideque ideque ideque? ideque-empty? ideque=
47 ideque-unfold ideque-unfold-right ideque-tabulate
48 list->ideque ideque->list ideque-reverse
49 generator->ideque ideque->generator
50 ideque-ref
51 ideque-front ideque-add-front ideque-remove-front
52 ideque-back ideque-add-back ideque-remove-back
53 ideque-take ideque-take-right ideque-drop ideque-drop-right
54 ideque-split-at
55 ideque-length ideque-append ideque-count ideque-zip
56 ideque-map ideque-for-each ideque-for-each-right
57 ideque-fold ideque-fold-right
58 ideque-filter-map ideque-append-map
59 ideque-filter ideque-remove ideque-partition
60 ideque-find ideque-find-right
61 ideque-take-while ideque-take-while-right
62 ideque-drop-while ideque-drop-while-right
63 ideque-span ideque-break
64 ideque-any ideque-every))
65 (select-module data.ideque)
66
67 (define-record-type <ideque> %make-dq ideque?
68 (lenf dq-lenf) ; length of front chain
69 (f dq-f) ; front chain
70 (lenr dq-lenr) ; length of rear chain
71 (r dq-r)) ; rear chain
72
73 ;; We use a singleton for empty deque
74 (define-constant *empty* (%make-dq 0 '() 0 '()))
75
76 ;;
77 ;; Constructors
78 ;;
79
80 ;; API
81 (define (make-ideque n :optional (init #f))
82 (let* ([lenf (quotient n 2)]
83 [lenr (- n lenf)])
84 (%make-dq lenf (make-list lenf init)
85 lenr (make-list lenr init))))
86
87 ;; API [SRFI-134]
88 (define (ideque . args) (list->ideque args))
89
90 ;; API [SRFI-134]
91 (define (ideque-unfold p f g seed)
92 (list->ideque (unfold p f g seed)))
93
94 ;; API [SRFI-134]
95 (define (ideque-unfold-right p f g seed)
96 (list->ideque (unfold-right p f g seed)))
97 ;; alternatively:
98 ;; (ideque-reverse (list->ideque (unfold p f g seed)))
99
100 ;; API [SRFI-134]
101 (define (ideque-tabulate size init)
102 (let ([lenf (quotient size 2)]
103 [lenr (quotient (+ size 1) 2)])
104 (%make-dq lenf (list-tabulate lenf init)
105 lenr (unfold (cut = <> lenr)
106 (^n (init (- size n 1)))
107 (cut + <> 1)
108 0))))
109
110 (define-constant C 3)
111
112 (define (check lenf f lenr r)
113 (cond [(> lenf (+ (* lenr C) 1))
114 (let* ([i (quotient (+ lenf lenr) 2)]
115 [j (- (+ lenf lenr) i)]
116 [f. (take f i)]
117 [r. (lappend r (reverse (drop f i)))])
118 (%make-dq i f. j r.))]
119 [(> lenr (+ (* lenf C) 1))
120 (let* ([j (quotient (+ lenf lenr) 2)]
121 [i (- (+ lenf lenr) j)]
122 [r. (take r j)]
123 [f. (lappend f (reverse (drop r j)))])
124 (%make-dq i f. j r.))]
125 [else (%make-dq lenf f lenr r)]))
126
127 ;;
128 ;; Basic operations
129 ;;
130
131 ;; API [SRFI-134]
132 (define (ideque-empty? dq)
133 (and (zero? (dq-lenf dq))
134 (zero? (dq-lenr dq))))
135
136 ;; API [SRFI-134]
137 (define (ideque-add-front dq x)
138 (check (+ (dq-lenf dq) 1) (cons x (dq-f dq)) (dq-lenr dq) (dq-r dq)))
139
140 ;; API [SRFI-134]
141 (define (ideque-front dq)
142 (if (zero? (dq-lenf dq))
143 (if (zero? (dq-lenr dq))
144 (error "Empty deque:" dq)
145 (car (dq-r dq)))
146 (car (dq-f dq))))
147
148 ;; API [SRFI-134]
149 (define (ideque-remove-front dq)
150 (if (zero? (dq-lenf dq))
151 (if (zero? (dq-lenr dq))
152 (error "Empty deque:" dq)
153 *empty*)
154 (check (- (dq-lenf dq) 1) (cdr (dq-f dq)) (dq-lenr dq) (dq-r dq))))
155
156 ;; API [SRFI-134]
157 (define (ideque-add-back dq x)
158 (check (dq-lenf dq) (dq-f dq) (+ (dq-lenr dq) 1) (cons x (dq-r dq))))
159
160 ;; API [SRFI-134]
161 (define (ideque-back dq)
162 (if (zero? (dq-lenr dq))
163 (if (zero? (dq-lenf dq))
164 (error "Empty deque:" dq)
165 (car (dq-f dq)))
166 (car (dq-r dq))))
167
168 ;; API [SRFI-134]
169 (define (ideque-remove-back dq)
170 (if (zero? (dq-lenr dq))
171 (if (zero? (dq-lenf dq))
172 (error "Empty deque:" dq)
173 *empty*)
174 (check (dq-lenf dq) (dq-f dq) (- (dq-lenr dq) 1) (cdr (dq-r dq)))))
175
176 ;; API [SRFI-134]
177 (define (ideque-reverse dq)
178 (if (ideque-empty? dq)
179 *empty*
180 (%make-dq (dq-lenr dq) (dq-r dq) (dq-lenf dq) (dq-f dq))))
181
182 ;;
183 ;; Other operations
184 ;;
185
186 ;; API [SRFI-134]
187 (define ideque=
188 (case-lambda
189 [(elt=) #t]
190 [(elt= ideque) (assume-type ideque <ideque>) #t]
191 [(elt= dq1 dq2)
192 ;; we optimize two-arg case
193 (assume-type dq1 <ideque>)
194 (assume-type dq2 <ideque>)
195 (or (eq? dq1 dq2)
196 (let ([len1 (+ (dq-lenf dq1) (dq-lenr dq1))]
197 [len2 (+ (dq-lenf dq2) (dq-lenr dq2))])
198 (and (= len1 len2)
199 (receive (x t1 t2) (list-prefix= elt= (dq-f dq1) (dq-f dq2))
200 (and x
201 (receive (y r1 r2) (list-prefix= elt= (dq-r dq1) (dq-r dq2))
202 (and y
203 (if (null? t1)
204 (list= elt= t2 (reverse r1))
205 (list= elt= t1 (reverse r2))))))))))]
206 [(elt= . dqs)
207 (apply list= elt= (map ideque->list dqs))]))
208
209 ;; Compare two lists up to whichever shorter one.
210 ;; Returns the compare result and the tails of uncompared lists.
211 (define (list-prefix= elt= a b)
212 (let loop ([a a] [b b])
213 (cond [(or (null? a) (null? b)) (values #t a b)]
214 [(elt= (car a) (car b)) (loop (cdr a) (cdr b))]
215 [else (values #f a b)])))
216
217 ;; API [SRFI-134]
218 (define (ideque-ref dq n)
219 (let1 len (+ (dq-lenf dq) (dq-lenr dq))
220 (cond [(or (< n 0) (>= n len)) (error "Index out of range:" n)]
221 [(< n (dq-lenf dq)) (list-ref (dq-f dq) n)]
222 [else (list-ref (dq-r dq) (- len n 1))])))
223
224 (define (%ideque-take dq n) ; n is within the range
225 (match-let1 ($ <ideque> lenf f lenr r) dq
226 (if (<= n lenf)
227 (check n (take f n) 0 '())
228 (let1 lenr. (- n lenf)
229 (check lenf f lenr. (take-right r lenr.))))))
230
231 (define (%ideque-drop dq n) ; n is within the range
232 (match-let1 ($ <ideque> lenf f lenr r) dq
233 (if (<= n lenf)
234 (check (- lenf n) (drop f n) lenr r)
235 (let1 lenr. (- lenr (- n lenf))
236 (check 0 '() lenr. (take r lenr.))))))
237
238 (define (%check-length dq n)
239 (unless (<= 0 n (ideque-length dq))
240 (error "argument is out of range:" n)))
241
242 ;; API [SRFI-134]
243 (define (ideque-take dq n)
244 (%check-length dq n)
245 (%ideque-take dq n))
246
247 ;; API [SRFI-134]
248 (define (ideque-take-right dq n)
249 (%check-length dq n)
250 (%ideque-drop dq (- (ideque-length dq) n)))
251
252 ;; API [SRFI-134]
253 (define (ideque-drop dq n)
254 (%check-length dq n)
255 (%ideque-drop dq n))
256
257 ;; API [SRFI-134]
258 (define (ideque-drop-right dq n)
259 (%check-length dq n)
260 (%ideque-take dq (- (ideque-length dq) n)))
261
262 ;; API [SRFI-134]
263 (define (ideque-split-at dq n)
264 (%check-length dq n)
265 (values (%ideque-take dq n)
266 (%ideque-drop dq n)))
267
268 ;; API [SRFI-134]
269 (define (ideque-length dq) (+ (dq-lenf dq) (dq-lenr dq)))
270
271 ;; API [SRFI-134]
272 (define (ideque-append . dqs)
273 ;; We could save some list copying by carefully split dqs into front and
274 ;; read group and append separately, but for now we don't bother...
275 (list->ideque (concatenate (map ideque->list dqs))))
276
277 ;; API [SRFI-134]
278 (define ideque-count
279 (case-lambda
280 [(pred dq) (+ (count pred (dq-f dq)) (count pred (dq-r dq)))]
281 [(pred . dqs) (apply count pred (map ideque->list dqs))]))
282
283 ;; API [SRFI-134]
284 (define (ideque-zip dq . dqs)
285 (apply ideque-map list dq dqs))
286
287 ;; API [SRFI-134]
288 (define ideque-map
289 (case-lambda
290 [(proc dq) (%make-dq (dq-lenf dq) (map proc (dq-f dq))
291 (dq-lenr dq) (map proc (dq-r dq)))]
292 [(proc . dqs) (list->ideque (apply map proc (map ideque->list dqs)))]))
293
294 ;; API [SRFI-134]
295 (define ideque-filter-map
296 (case-lambda
297 [(proc dq) (let ([f (filter-map proc (dq-f dq))]
298 [r (filter-map proc (dq-r dq))])
299 (check (length f) f (length r) r))]
300 [(proc . dqs)
301 (list->ideque (apply filter-map proc (map ideque->list dqs)))]))
302
303 ;; API [SRFI-134]
304 (define ideque-for-each
305 (case-lambda
306 [(proc dq) (for-each proc (dq-f dq)) (for-each proc (reverse (dq-r dq)))]
307 [(proc . dqs) (apply for-each proc (map ideque->list dqs))]))
308
309 ;; API [SRFI-134]
310 (define ideque-for-each-right
311 (case-lambda
312 [(proc dq) (for-each proc (dq-r dq)) (for-each proc (reverse (dq-f dq)))]
313 [(proc . dqs)
314 (apply for-each proc (map (lambda (dq)
315 (ideque->list (ideque-reverse dq)))
316 dqs))]))
317
318 ;; API [SRFI-134]
319 (define ideque-fold
320 (case-lambda
321 [(proc knil dq) (fold proc (fold proc knil (dq-f dq)) (reverse (dq-r dq)))]
322 [(proc knil . dqs) (apply fold proc knil (map ideque->list dqs))]))
323
324 ;; API [SRFI-134]
325 (define ideque-fold-right
326 (case-lambda
327 [(proc knil dq)
328 (fold-right proc (fold-right proc knil (reverse (dq-r dq))) (dq-f dq))]
329 [(proc knil . dqs)
330 (apply fold-right proc knil (map ideque->list dqs))]))
331
332 ;; API [SRFI-134]
333 (define (ideque-append-map proc . dqs)
334 ;; can be cleverer, but for now...
335 (list->ideque (apply append-map proc (map ideque->list dqs))))
336
337 (define (%ideque-filter-remove op pred dq)
338 (let ([f (op pred (dq-f dq))]
339 [r (op pred (dq-r dq))])
340 (check (length f) f (length r) r)))
341
342 ;; API [SRFI-134]
343 (define (ideque-filter pred dq) (%ideque-filter-remove filter pred dq))
344 (define (ideque-remove pred dq) (%ideque-filter-remove remove pred dq))
345
346 ;; API [SRFI-134]
347 (define (ideque-partition pred dq)
348 (receive (f1 f2) (partition pred (dq-f dq))
349 (receive (r1 r2) (partition pred (dq-r dq))
350 (values (check (length f1) f1 (length r1) r1)
351 (check (length f2) f2 (length r2) r2)))))
352
353 (define *not-found* (cons #f #f)) ; unique value
354
355 (define (%search pred seq1 seq2 failure)
356 ;; we could write seek as CPS, but we employ *not-found* instead to avoid
357 ;; closure allocation
358 (define (seek pred s)
359 (cond [(null? s) *not-found*]
360 [(pred (car s)) (car s)]
361 [else (seek pred (cdr s))]))
362 (let1 r (seek pred seq1)
363 (if (not (eq? r *not-found*))
364 r
365 (let1 r (seek pred (reverse seq2))
366 (if (not (eq? r *not-found*))
367 r
368 (failure))))))
369
370 ;; API [SRFI-134]
371 (define (ideque-find pred dq :optional (failure (^[] #f)))
372 (%search pred (dq-f dq) (dq-r dq) failure))
373
374 ;; API [SRFI-134]
375 (define (ideque-find-right pred dq :optional (failure (^[] #f)))
376 (%search pred (dq-r dq) (dq-f dq) failure))
377
378 ;; API [SRFI-134]
379 (define (ideque-take-while pred dq)
380 (receive (hd tl) (span pred (dq-f dq))
381 (if (null? tl)
382 (receive (hd. tl.) (span pred (reverse (dq-r dq)))
383 (check (dq-lenf dq) (dq-f dq) (length hd.) (reverse hd.)))
384 (check (length hd) hd 0 '()))))
385
386 ;; API [SRFI-134]
387 (define (ideque-take-while-right pred dq)
388 (ideque-reverse (ideque-take-while pred (ideque-reverse dq))))
389
390 ;; API [SRFI-134]
391 (define (ideque-drop-while pred dq)
392 (receive (hd tl) (span pred (dq-f dq))
393 (if (null? tl)
394 (receive (hd. tl.) (span pred (reverse (dq-r dq)))
395 (check (length tl.) tl. 0 '()))
396 (check (length tl) tl (dq-lenr dq) (dq-r dq)))))
397
398 ;; API [SRFI-134]
399 (define (ideque-drop-while-right pred dq)
400 (ideque-reverse (ideque-drop-while pred (ideque-reverse dq))))
401
402 (define (%idq-span-break op pred dq)
403 (receive (head tail) (op pred (dq-f dq))
404 (if (null? tail)
405 (receive (head. tail.) (op pred (reverse (dq-r dq)))
406 (values (check (length head) head (length head.) (reverse head.))
407 (check (length tail.) tail. 0 '())))
408 (values (check (length head) head 0 '())
409 (check (length tail) tail (dq-lenr dq) (dq-r dq))))))
410
411 ;; API [SRFI-134]
412 (define (ideque-span pred dq) (%idq-span-break span pred dq))
413 (define (ideque-break pred dq) (%idq-span-break break pred dq))
414
415 ;; API [SRFI-134]
416 (define ideque-any
417 (case-lambda
418 [(pred dq) (if (null? (dq-r dq))
419 (any pred (dq-f dq))
420 (or (any pred (dq-f dq)) (any pred (reverse (dq-r dq)))))]
421 [(pred . dqs) (apply any pred (map ideque->list dqs))]))
422
423 ;; API [SRFI-134]
424 (define ideque-every
425 (case-lambda
426 [(pred dq) (if (null? (dq-r dq))
427 (every pred (dq-f dq))
428 (and (every pred (dq-f dq)) (every pred (reverse (dq-r dq)))))]
429 [(pred . dqs) (apply every pred (map ideque->list dqs))]))
430
431 ;; API [SRFI-134]
432 (define (ideque->list dq) (append (dq-f dq) (reverse (dq-r dq))))
433
434 ;; API [SRFI-134]
435 (define (list->ideque lis) (check (length lis) lis 0 '()))
436
437 ;; API [SRFI-134]
438 (define (ideque->generator dq)
439 (^[] (if (ideque-empty? dq)
440 (eof-object)
441 (rlet1 v (ideque-front dq)
442 (set! dq (ideque-remove-front dq))))))
443
444 ;; API [SRFI-134]
445 (define (generator->ideque gen)
446 (list->ideque (generator->list gen)))