;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
;                               CQUEUE
;
;             Circular queue, implemented using a vector
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define queue (make-record-type "queue" '(size vect start end full)))
(define create-queue (record-constructor queue '(size vect start end full)))
(define (make-queue n)
  (create-queue n (make-vector n) 0 0 nil)) ; so it runs from 0 to n-1
;;;
;;; The queue is essentially composed of a circular vector. Think of a clock
;;; face. As we add to the end of the q we do so at the end, and increment
;;; q modulo size (similar to a clock, modulo 12!!). The q is empty when
;;; start and end are equal. When we take something off the q (ie. dequeue)
;;; we increment start modulo size. If on adding to the q (ie enqueue)
;;;
;;; start=end then queue is full, and we mark full to be true.
;;; If we attempt to add to q when full we have overflow, and 
;;; if we attempt to dequeue when q is empty we have underflow
;;;

(define queue? (record-predicate queue))

(define size (record-accessor queue 'size))
(define vect (record-accessor queue 'vect))
(define start  (record-accessor queue 'start))
(define end  (record-accessor queue 'end))
(define full (record-accessor queue 'full))

(define start! (record-modifier queue 'start))
(define end! (record-modifier queue 'end))
(define full! (record-modifier queue 'full))

(define (full? q)
  (full q))

(define (empty? q)
  (and (not (full? q))
       (= (start q) (end q))))

(define q (make-queue 10))
;;;
;;; Make me a queue of 10 elements
;;;

(define (enqueue e q)
  (cond ((full? q) 'overflow)
	(t (let ((v (vect q)))
	     (vector-set! v (end q) e)
	     (end! q (modulo (+ (end q) 1) (size q)))
	     (full! q (= (start q) (end q)))))))

(define (dequeue q)
  (cond ((empty? q) 'underflow)
	(t (let ((e (vector-ref (vect q) (start q))))
	     (vector-set! (vect q) (start q) #f)                ; NOTE 1.
	     (start! q (modulo (+ (start q) 1) (size q)))
	     (full! q nil)
	     e))))
;;;
;;; NOTE 1. This line can be deleted, it is
;;;         only there so that we can (show q) and see an element
;;;         has been removed from the queue (see show below)
;;;

(define (front q)
  (cond ((empty? q) 'empty)
	(t (vector-ref (vect q) (start q)))))

(define (show q)
  (format nil "start = ~S, end = ~S, q = ~S , full? ~S, empty? ~S"
	  (start q) (end q) (vect q) (full? q) (empty? q)))

(define (q->list q)
  (cond ((empty? q) '())
	(#t (let ((l '()))
	      (do ((i (modulo (- (end q) 1) (size q))
		      (modulo (- i 1) (size q))))
		  ((= i (start q)) (cons (front q) l))
		(set! l (cons (vector-ref (vect q) i) l)))))))

(define (qlength q)
  (length (q->list q)))
;;;
;;; Inefficient, but easy
;;;

(define (qlength q)
  (cond ((full q) (size q))                 
	(#t (modulo (- (end q) (start q)) (size q)))))
;;;
;;; Due to Robert Glassey
;;;