;;;
;;; Queue Maintenance Tools
;;; Based Roughly On The Descriptions In Russell & Norvig (1995)
;;;
;;; Queues are implemented here as lists with pointers to the tail cons.
;;; The head and tail pointers are bundled into a struct.
;;;
;;; DAVID NOELLE  Wed Apr 17 12:22:47 1996
;;;


;;;
;;; Package
;;;

(cl::defpackage "QUEUE"
  (:export "QUEUE"
	   "MAKE-QUEUE"
	   "COPY-QUEUE"
	   "EMPTY-QUEUE-P"
	   "REMOVE-FRONT"
	   "ENQUEUE-AT-FRONT"
	   "ENQUEUE-AT-END"))

(cl::in-package "QUEUE")


;;;
;;; Queue Structure
;;;

(defstruct (queue
	    (:constructor make-queue-given-list)
	    (:copier copy-queue-structure-only))
  (head nil :type list)
  (tail nil :type list))
  

;;; make-queue  --  Makes a queue with a copy of the list "elements" 
;;; as the initial contents.
(defun make-queue (&optional elements)
  (declare (type list elements))
  (let* ((lst (copy-list elements))
	 (q (make-queue-given-list :head lst :tail (last lst))))
    (declare (type list lst)
	     (type queue q))
    q))

;;; copy-queue  --  Makes a copy of the given queue, copying the
;;; conses in the list.
(defun copy-queue (q)
  (declare (type queue q))
  (let ((new-q (copy-queue-structure-only q)))
    (declare (type queue new-q))
    (setf (queue-head new-q) (copy-list (queue-head q)))
    (setf (queue-tail new-q) (last (queue-head new-q)))
    new-q))


;;;
;;; Queue Utilities
;;;

;;; empty-queue-p  --  Returns non-nil is the given queue is empty.
(defun empty-queue-p (q)
  (declare (type queue q))
  (null (queue-head q)))

;;; remove-front  --  Remove the front element from the given queue,
;;; and return that element.
(defun remove-front (q)
  (declare (type queue q))
  (let ((front (queue-head q)))
    (declare (type list front))
    (unless (null front)
      (when (eq front (queue-tail q))
	(setf (queue-tail q) nil))
      (setf (queue-head q) (rest front))
      (car front))))

;;; enqueue-at-front  --  Place a copy of "elements", in the given
;;; order, at the front of the given queue.  This is really treating
;;; the queue like a stack.
(defun enqueue-at-front (elements q)
  (declare (type list elements) (type queue q))
  (setf (queue-head q) (append elements (queue-head q)))
  (when (null (queue-tail q))
    (setf (queue-tail q) (last (queue-head q))))
  q)

;;; enqueue-at-end  --  Place a copy of "elements", in the given
;;; order, at the end of the given queue.
(defun enqueue-at-end (elements q)
  (declare (type list elements) (type queue q))
  (let ((new-tail (copy-list elements)))
    (declare (type list new-tail))
    (if (null (queue-head q))
      (setf (queue-head q) new-tail)
      (setf (cdr (queue-tail q)) new-tail))
    (unless (null new-tail)
      (setf (queue-tail q) (last new-tail))))
  q)