| 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))) |