3 ;;;; Copyright (C) 1995 Free Software Foundation, Inc.
5 ;;;; This program is free software; you can redistribute it and/or modify
6 ;;;; it under the terms of the GNU General Public License as published by
7 ;;;; the Free Software Foundation; either version 2, or (at your option)
8 ;;;; any later version.
10 ;;;; This program is distributed in the hope that it will be useful,
11 ;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
12 ;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 ;;;; GNU General Public License for more details.
15 ;;;; You should have received a copy of the GNU General Public License
16 ;;;; along with this software; see the file COPYING. If not, write to
17 ;;;; the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
18 ;;;; Boston, MA 02111-1307 USA
21 (define-module (ice-9 q))
24 ;;; Q: Based on the interface to
26 ;;; "queue.scm" Queues/Stacks for Scheme
27 ;;; Written by Andrew Wilcox (awilcox@astro.psu.edu) on April 1, 1992.
33 ;;; A list is just a bunch of cons pairs that follows some constrains,
34 ;;; right? Association lists are the same. Hash tables are just
35 ;;; vectors and association lists. You can print them, read them,
36 ;;; write them as constants, pun them off as other data structures
37 ;;; etc. This is good. This is lisp. These structures are fast and
38 ;;; compact and easy to manipulate arbitrarily because of their
39 ;;; simple, regular structure and non-disjointedness (associations
40 ;;; being lists and so forth).
42 ;;; So I figured, queues should be the same -- just a "subtype" of cons-pair
43 ;;; structures in general.
45 ;;; A queue is a cons pair:
46 ;;; ( <the-q> . <last-pair> )
48 ;;; <the-q> is a list of things in the q. New elements go at the end
51 ;;; <last-pair> is #f if the q is empty, and otherwise is the last
54 ;;; q's print nicely, but alas, they do not read well because the
55 ;;; eq?-ness of <last-pair> and (last-pair <the-q>) is lost by read.
57 ;;; All the functions that aren't explicitly defined to return
58 ;;; something else (a queue element; a boolean value) return the queue
65 ;;; recomputes and resets the <last-pair> component of a queue.
67 (define-public (sync-q! q)
68 (set-cdr! q (if (pair? (car q)) (last-pair (car q))
75 (define-public (make-q) (cons '() #f))
78 ;;; Return true if obj is a Q.
79 ;;; An object is a queue if it is equal? to '(() . #f)
80 ;;; or it is a pair P with (list? (car P))
81 ;;; and (eq? (cdr P) (last-pair (car P))).
83 (define-public (q? obj)
86 (eq? (cdr obj) (last-pair (car obj)))
87 (and (null? (car obj))
92 (define-public (q-empty? obj) (null? (car obj)))
95 ;;; Throw a q-empty exception if Q is empty.
96 (define-public (q-empty-check q) (if (q-empty? q) (throw 'q-empty q)))
99 ;;; Return the first element of Q.
100 (define-public (q-front q) (q-empty-check q) (caar q))
103 ;;; Return the last element of Q.
104 (define-public (q-rear q) (q-empty-check q) (cadr q))
107 ;;; Remove all occurences of obj from Q.
108 (define-public (q-remove! q obj)
109 (set-car! q (delq! obj (car q)))
113 ;;; Add obj to the front of Q
114 (define-public (q-push! q obj)
115 (let ((h (cons obj (car q))))
117 (or (cdr q) (set-cdr! q h)))
121 ;;; Add obj to the rear of Q
122 (define-public (enq! q obj)
123 (let ((h (cons obj '())))
126 (set-cdr! (cdr q) h))
131 ;;; Take the front of Q and return it.
132 (define-public (q-pop! q)
142 ;;; Take the front of Q and return it.
143 (define-public deq! q-pop!)
146 ;;; Return the number of enqueued elements.
148 (define-public (q-length q) (length (car q)))