blob: af13ebbed58448f2308ef7df4bc2a1daaf04bbd1 (
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
73
74
|
;;; Chickadee Game Toolkit
;;; Copyright © 2017, 2018 David Thompson <dthompson2@worcester.edu>
;;;
;;; Chickadee is free software: you can redistribute it and/or modify
;;; it under the terms of the GNU General Public License as published
;;; by the Free Software Foundation, either version 3 of the License,
;;; or (at your option) any later version.
;;;
;;; Chickadee is distributed in the hope that it will be useful, but
;;; WITHOUT ANY WARRANTY; without even the implied warranty of
;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
;;; General Public License for more details.
;;;
;;; You should have received a copy of the GNU General Public License
;;; along with this program. If not, see
;;; <http://www.gnu.org/licenses/>.
(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)))
|
