Debian Codegraph @

lib/scheme/list-queue.scm

raw
1 ;;;
2 ;;; scheme.list-queue - Queues based on lists (R7RS Red)
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 ;; Originally SRFI-117
35
36 ;; Implemented on top of data.queue in Gauche
37
38 (define-module scheme.list-queue
39 (use data.queue)
40 (export make-list-queue list-queue list-queue-copy
41 list-queue-unfold list-queue-unfold-right
42 list-queue? list-queue-empty?
43 list-queue-front list-queue-back
44 list-queue-list list-queue-first-last
45 list-queue-add-front! list-queue-add-back!
46 list-queue-remove-front! list-queue-remove-back!
47 list-queue-remove-all!
48 list-queue-set-list!
49 list-queue-append list-queue-append!
50 list-queue-concatenate
51 list-queue-map list-queue-map! list-queue-for-each))
52 (select-module scheme.list-queue)
53
54 (define (make-list-queue lis :optional last)
55 (if (pair? last)
56 (rlet1 q (make-queue) ; needs to satisfy O(1) restriction
57 ((with-module data.queue %queue-set-content!) q lis last))
58 (list->queue lis)))
59
60 (define (list-queue . elts) (list->queue elts))
61
62 (define (list-queue-copy q) (copy-queue q))
63
64 (define (list-queue-unfold stop? mapper successor seed
65 :optional (q (make-queue)))
66 (let loop ((seed seed) (elts '()))
67 (if (stop? seed)
68 (dolist [e elts] (queue-push! q e))
69 (loop (successor seed) (cons (mapper seed) elts))))
70 q)
71
72 (define (list-queue-unfold-right stop? mapper successor seed
73 :optional (q (make-queue)))
74 (let loop ((seed seed) (elts '()))
75 (if (stop? seed)
76 (dolist [e elts] (enqueue! q e))
77 (loop (successor seed) (cons (mapper seed) elts))))
78 q)
79
80 (define (list-queue? q) (queue? q))
81 (define (list-queue-empty? q) (queue-empty? q))
82 (define (list-queue-front q) (queue-front q))
83 (define (list-queue-back q) (queue-rear q))
84 (define (list-queue-list q) (queue-internal-list q))
85
86 ;; This also returns internal structure.
87 (define (list-queue-first-last q)
88 (when (mtqueue? q)
89 (error "Can't get internal pairs of <mtqueue>:" q))
90 (values ((with-module data.queue %qhead) q)
91 ((with-module data.queue %qtail) q)))
92
93 (define (list-queue-add-front! q elt) (queue-push! q elt))
94 (define (list-queue-add-back! q elt ) (enqueue! q elt))
95 (define (list-queue-remove-front! q) (dequeue! q))
96 (define (list-queue-remove-back! q)
97 ;; it's ok to be O(n), so we take gratuitously inefficient path
98 (let loop ([n (queue-length q)]
99 [elts (dequeue-all! q)])
100 (if (= n 1)
101 (car elts)
102 (begin (enqueue! q (car elts))
103 (loop (- n 1) (cdr elts))))))
104
105 (define (list-queue-remove-all! q) (dequeue-all! q))
106
107 (define (list-queue-set-list! q lis :optional last)
108 (let1 last (last-pair lis)
109 ((with-module data.queue %queue-set-content!) q lis last)
110 q))
111
112 (define (list-queue-append . qs)
113 (list-queue-concatenate qs))
114
115 (define (list-queue-append! . qs)
116 (let loop ([qs qs]
117 [head '()]
118 [tail '()])
119 (if (null? qs)
120 (make-list-queue head tail)
121 (receive (hd tl) (list-queue-first-last (car qs))
122 ;; we purge the original queues, so that the mutation of internal
123 ;; cells won't confuse them.
124 (dequeue-all! (car qs))
125 (cond [(null? hd) (loop (cdr qs) head tail)]
126 [(pair? tail)
127 (begin (set-cdr! tail hd) (loop (cdr qs) head tl))]
128 [else (loop (cdr qs) hd tl)])))))
129
130 (define (list-queue-concatenate qs)
131 (list->queue (concatenate (map list-queue-list qs))))
132
133 (define (list-queue-map proc q)
134 (list->queue (map proc (queue->list q))))
135
136 (define (list-queue-map! proc q)
137 (let1 xs (map proc (queue->list q))
138 ((with-module data.queue %queue-set-content!) q xs #f)
139 q))
140
141 (define (list-queue-for-each proc q)
142 (for-each proc (queue->list q)))