158ac74be94b33911d024bf86b98152b05254180
[chickadee.git] / chickadee / queue.scm
1 ;;; Chickadee Game Toolkit
2 ;;; Copyright © 2017 David Thompson <davet@gnu.org>
3 ;;;
4 ;;; Chickadee is free software: you can redistribute it and/or modify
5 ;;; it under the terms of the GNU General Public License as published
6 ;;; by the Free Software Foundation, either version 3 of the License,
7 ;;; or (at your option) any later version.
8 ;;;
9 ;;; Chickadee is distributed in the hope that it will be useful, but
10 ;;; WITHOUT ANY WARRANTY; without even the implied warranty of
11 ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 ;;; General Public License for more details.
13 ;;;
14 ;;; You should have received a copy of the GNU General Public License
15 ;;; along with this program. If not, see
16 ;;; <http://www.gnu.org/licenses/>.
17
18 (define-module (chickadee queue)
19 #:use-module (ice-9 format)
20 #:use-module (srfi srfi-9)
21 #:use-module (srfi srfi-9 gnu)
22 #:use-module (chickadee array-list)
23 #:export (make-queue
24 queue?
25 queue-empty?
26 enqueue!
27 dequeue!))
28
29 (define-record-type <queue>
30 (%make-queue input output)
31 queue?
32 (input queue-input)
33 (output queue-output))
34
35 (define (display-queue q port)
36 (format port "#<queue length: ~d>"
37 (+ (array-list-size (queue-input q))
38 (array-list-size (queue-output q)))))
39
40 (set-record-type-printer! <queue> display-queue)
41
42 (define (make-queue)
43 "Return a new, empty queue."
44 (%make-queue (make-array-list) (make-array-list)))
45
46 (define (queue-empty? q)
47 "Return #t if Q is empty."
48 (and (array-list-empty? (queue-input q))
49 (array-list-empty? (queue-output q))))
50
51 (define (enqueue! q item)
52 "Add ITEM to Q."
53 (array-list-push! (queue-input q) item))
54
55 (define (dequeue! q)
56 "Remove the first element of Q."
57 (and (not (queue-empty? q))
58 (let ((input (queue-input q))
59 (output (queue-output q)))
60 (when (array-list-empty? output)
61 (let loop ()
62 (unless (array-list-empty? input)
63 (array-list-push! output (array-list-pop! input))
64 (loop))))
65 (array-list-pop! output))))