blob: c866ce882d3ccc2242e72de31b720caa8184e6e1 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
;;; Chickadee Game Toolkit
;;; Copyright © 2017, 2018 David Thompson <dthompson2@worcester.edu>
;;;
;;; Licensed under the Apache License, Version 2.0 (the "License");
;;; you may not use this file except in compliance with the License.
;;; You may obtain a copy of the License at
;;;
;;; http://www.apache.org/licenses/LICENSE-2.0
;;;
;;; Unless required by applicable law or agreed to in writing, software
;;; distributed under the License is distributed on an "AS IS" BASIS,
;;; WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
;;; See the License for the specific language governing permissions and
;;; limitations under the License.
(define-module (chickadee data queue)
#:use-module (ice-9 format)
#:use-module (srfi srfi-9)
#:use-module (srfi srfi-9 gnu)
#:use-module (chickadee data array-list)
#:export (make-queue
queue?
queue-length
queue-empty?
enqueue!
dequeue!
queue-clear!))
(define-record-type <queue>
(%make-queue input output)
queue?
(input queue-input)
(output queue-output))
(define (display-queue q port)
(format port "#<queue length: ~d>" (queue-length q)))
(set-record-type-printer! <queue> display-queue)
(define (make-queue)
"Return a new, empty queue."
(%make-queue (make-array-list) (make-array-list)))
(define (queue-length q)
"Return the number of elements in Q."
(+ (array-list-size (queue-input q))
(array-list-size (queue-output q))))
(define (queue-empty? q)
"Return #t if Q is empty."
(zero? (queue-length q)))
(define (enqueue! q item)
"Add ITEM to Q."
(array-list-push! (queue-input q) item))
(define (dequeue! q)
"Remove the first element of Q."
(and (not (queue-empty? q))
(let ((input (queue-input q))
(output (queue-output q)))
(when (array-list-empty? output)
(let loop ()
(unless (array-list-empty? input)
(array-list-push! output (array-list-pop! input))
(loop))))
(array-list-pop! output))))
(define (queue-clear! q)
"Remove all items from Q."
(array-list-clear! (queue-input q))
(array-list-clear! (queue-output q)))
|