
(in-package :cl-util)

;; Largely based on https://rosettacode.org/wiki/Queue/Definition#Common_Lisp
(defstruct (queue (:constructor %make-queue))
  (items '() :type list)
  (tail '() :type list))
 
(defun make-queue ()
  "Returns an empty queue."
  (%make-queue))
 
(defun queue-empty-p (queue)
  "Returns true if the queue is empty."
  (endp (queue-items queue)))
 
(defun enqueue (item queue)
  "Enqueue item in queue. Returns the queue."
  (prog1 queue
    (if (queue-empty-p queue)
      (setf (queue-items queue) (list item)
            (queue-tail queue) (queue-items queue))
      (setf (cdr (queue-tail queue)) (list item)
            (queue-tail queue) (cdr (queue-tail queue))))))
 
(defun dequeue (queue)
  "Dequeues an item from queue. Signals an error if queue is empty."
  (if (queue-empty-p queue)
    (error "Cannot dequeue from empty queue.")
    (pop (queue-items queue))))

(defun queue-peek (queue)
  "Peeks into the first item of the queue."
  (if (queue-empty-p queue)
    (error "Cannot peek into an empty queue.")
    (car (queue-items queue))))

