;;;-*- Mode: Lisp; Package: UTILS -*-

(in-package :utils)

(export '(queue-contents make-queue enqueue dequeue  pop-queue front
          empty-queue-p queue-nconc push-queue))

;;;; Queues (from Norwig):

(proclaim '(inline queue-contents make-queue enqueue dequeue
                   front empty-queue-p queue-nconc))


;;; A queue is a (last . contents) pair

(defun queue-contents (q) (cdr q))

;(enqueue 2 (enqueue 1 (make-queue)))

(defun make-queue (&key initial-contents)
  "Build a new queue, with initial-contents as elements. Initial-contents
is going to be changed!"
  (let ((q (cons nil initial-contents)))
    (setf (car q) (last q))
    q))

#|
(defun make-queue ()
  "Build a new queue, with no elements."
  (let ((q (cons nil nil)))
    (setf (car q) q)))
|#

(defun enqueue (item q)
  "Insert item at the end of the queue."
  (setf (car q)
        (setf (rest (car q))
              (cons item nil)))
  q)

(defun dequeue (q)
  "Remove an item from the front of the queue."
  (pop (cdr q))
  (if (null (cdr q)) (setf (car q) q))
  q)

(defun pop-queue (q)
  "Remove an item from the front of the queue."
  (prog1
    (pop (cdr q))
    (if (null (cdr q)) (setf (car q) q))))

(defun front (q) (first (queue-contents q)))

(defun empty-queue-p (q) (null (queue-contents q)))

(defun queue-nconc (q list)
  "Add the elements of LIST to the end of the queue."
  (setf (car q)
        (last (setf (rest (car q)) list))))

; not very queue-like, but serves its purpose. (pm)
(defun push-queue (item q)
  (if (empty-queue-p q)
    (enqueue item q)
    (setf (cdr q)  (push item (cdr q))))
  q)