ice-9/q.scm

   1 ;;;; q.scm --- Queues
   2 ;;;;
   3 ;;;;    Copyright (C) 1995, 2001, 2004, 2006 Free Software Foundation, Inc.
   4 ;;;;
   5 ;;;; This library is free software; you can redistribute it and/or
   6 ;;;; modify it under the terms of the GNU Lesser General Public
   7 ;;;; License as published by the Free Software Foundation; either
   8 ;;;; version 2.1 of the License, or (at your option) any later version.
   9 ;;;;
  10 ;;;; This library 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 GNU
  13 ;;;; Lesser General Public License for more details.
  14 ;;;;
  15 ;;;; You should have received a copy of the GNU Lesser General Public
  16 ;;;; License along with this library; if not, write to the Free Software
  17 ;;;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  18 ;;;;
  19
  20 ;;; Commentary:
  21
  22 ;;; Q: Based on the interface to
  23 ;;;
  24 ;;; "queue.scm"  Queues/Stacks for Scheme
  25 ;;;  Written by Andrew Wilcox (awilcox@astro.psu.edu) on April 1, 1992.
  26
  27 ;;; {Q}
  28 ;;;
  29 ;;; A list is just a bunch of cons pairs that follows some constrains,
  30 ;;; right?  Association lists are the same.  Hash tables are just
  31 ;;; vectors and association lists.  You can print them, read them,
  32 ;;; write them as constants, pun them off as other data structures
  33 ;;; etc. This is good.  This is lisp.  These structures are fast and
  34 ;;; compact and easy to manipulate arbitrarily because of their
  35 ;;; simple, regular structure and non-disjointedness (associations
  36 ;;; being lists and so forth).
  37 ;;;
  38 ;;; So I figured, queues should be the same -- just a "subtype" of cons-pair
  39 ;;; structures in general.
  40 ;;;
  41 ;;; A queue is a cons pair:
  42 ;;;             ( <the-q> . <last-pair> )
  43 ;;;
  44 ;;; <the-q> is a list of things in the q.  New elements go at the end
  45 ;;; of that list.
  46 ;;;
  47 ;;; <last-pair> is #f if the q is empty, and otherwise is the last
  48 ;;; pair of <the-q>.
  49 ;;;
  50 ;;; q's print nicely, but alas, they do not read well because the
  51 ;;; eq?-ness of <last-pair> and (last-pair <the-q>) is lost by read.
  52 ;;;
  53 ;;; All the functions that aren't explicitly defined to return
  54 ;;; something else (a queue element; a boolean value) return the queue
  55 ;;; object itself.
  56
  57 ;;; Code:
  58
  59 (define-module (ice-9 q)
  60   :export (sync-q! make-q q? q-empty? q-empty-check q-front q-rear
  61            q-remove! q-push! enq! q-pop! deq! q-length))
  62
  63 ;;; sync-q!
  64 ;;;   The procedure
  65 ;;;
  66 ;;;             (sync-q! q)
  67 ;;;
  68 ;;;   recomputes and resets the <last-pair> component of a queue.
  69 ;;;
  70 (define (sync-q! q)
  71   (set-cdr! q (if (pair? (car q)) (last-pair (car q))
  72                   #f))
  73   q)
  74
  75 ;;; make-q
  76 ;;;  return a new q.
  77 ;;;
  78 (define (make-q) (cons '() #f))
  79
  80 ;;; q? obj
  81 ;;;   Return true if obj is a Q.
  82 ;;;   An object is a queue if it is equal? to '(() . #f)
  83 ;;;   or it is a pair P with (list? (car P))
  84 ;;;                      and (eq? (cdr P) (last-pair (car P))).
  85 ;;;
  86 (define (q? obj)
  87   (and (pair? obj)
  88        (if (pair? (car obj))
  89            (eq? (cdr obj) (last-pair (car obj)))
  90            (and (null? (car obj))
  91                 (not (cdr obj))))))
  92
  93 ;;; q-empty? obj
  94 ;;;
  95 (define (q-empty? obj) (null? (car obj)))
  96
  97 ;;; q-empty-check q
  98 ;;;  Throw a q-empty exception if Q is empty.
  99 (define (q-empty-check q) (if (q-empty? q) (throw 'q-empty q)))
 100
 101 ;;; q-front q
 102 ;;;  Return the first element of Q.
 103 (define (q-front q) (q-empty-check q) (caar q))
 104
 105 ;;; q-rear q
 106 ;;;  Return the last element of Q.
 107 (define (q-rear q) (q-empty-check q) (cadr q))
 108
 109 ;;; q-remove! q obj
 110 ;;;  Remove all occurences of obj from Q.
 111 (define (q-remove! q obj)
 112   (set-car! q (delq! obj (car q)))
 113   (sync-q! q))
 114
 115 ;;; q-push! q obj
 116 ;;;  Add obj to the front of Q
 117 (define (q-push! q obj)
 118   (let ((h (cons obj (car q))))
 119     (set-car! q h)
 120     (or (cdr q) (set-cdr! q h)))
 121   q)
 122
 123 ;;; enq! q obj
 124 ;;;  Add obj to the rear of Q
 125 (define (enq! q obj)
 126   (let ((h (cons obj '())))
 127     (if (null? (car q))
 128         (set-car! q h)
 129         (set-cdr! (cdr q) h))
 130     (set-cdr! q h))
 131   q)
 132
 133 ;;; q-pop! q
 134 ;;;  Take the front of Q and return it.
 135 (define (q-pop! q)
 136   (q-empty-check q)
 137   (let ((it (caar q))
 138         (next (cdar q)))
 139     (if (null? next)
 140         (set-cdr! q #f))
 141     (set-car! q next)
 142     it))
 143
 144 ;;; deq! q
 145 ;;;  Take the front of Q and return it.
 146 (define deq! q-pop!)
 147
 148 ;;; q-length q
 149 ;;;  Return the number of enqueued elements.
 150 ;;;
 151 (define (q-length q) (length (car q)))
 152
 153 ;;; q.scm ends here