;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
;                      Compulsory Exercise 1
;
;           Complete by Wednesday the 22nd October 1997, at 12 o'clock
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; Implement a queue abstract data type (ADT)
; implement as a circular queue, using a vector of length n
; using the defines below and implement the operations
; 
; (0) (empty? q)
;     delivers t if q is empty, otherwise false
; (1) (front q)
;      delivers the first item in the q (or 'empty)
; (2) (enqueue e q)
;     Adds e to the end of the queue (or 'overflow if full)
; (3) (dequeue q)
;     Delivers the first item in the q, and removes that
;     item from the q (or 'underflow if empty)
; (4) (qlength q)
;     Delivers an integer, n, the number of items in the queue
; (5) (q->list q)
;     Delivers the contents of q as a list (scm type list)
;
; NOTE: (4) and (5) are optional
; NOTE: you will need to load the world file in scm so that
;       you get access to the record functions
; NOTE: look at function modulo
;

(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 #f)); 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 (show q)
  (format nil "start = ~S, end = ~S, q = ~S , full? ~S, empty? ~S"
	  (start q) (end q) (vect q) (full? q) (empty? q)))
;;;
;;; Use this function to show the queue, for debugging
;;;

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

;(print (show q))

;
;~~~~~~~~~~~~~~~~~~           FILL IN THE BLANKS         ~~~~~~~~~~~~~~~~~~~~~
;

(define (full? q)	
 'undefined)
;;;
;;; Is the (full q) true
;;;

(define (empty? q)
  'undefined)
;;;
;;; Is the q empty?
;;; The q is empty if start  = end and it is not full
;;;	

(define (enqueue e q)
  'undefined)
;;;
;;; When we put e on the q ....
;;; 1. If the q is full deliver 'overflow
;;; 2. q is not full, so 
;;; 2.1 put e on the end of the q
;;; 2.1.1 get the (vect q) that stores the elements of the q
;;; 2.1.2 do a vect-set! on the (end q) element
;;; 2.2 update the (end q), by incrementing modulo (size q)
;;; 2.3 if (start q) = (end q) then q is now full.
;;;

(define (dequeue q)
  'undefined)
;;;
;;; If the q is empty, deliver 'underflow ... otherwise
;;; Remove the element, e, at the start of the q
;;; update the start of the q pointer,
;;; the q is definitely NOT full!
;;; deliver e as a result.
;;;
;;; This is symmetric to enqueue above. 
;;;

(define (front q)
  'undefined)
;;;
;;; Give me the element at the front/start of the 
;;; queue ... so long as queue is not empty?
;;; NOTE: could use this in function dequeue above
;;;

(define (qlength q)
  'undefined)
;;;
;;; Just how many items are actually on the q?
;;;

(define (q->list q)
  'undefined)
;;;
;;; put all the elemnts actually on the q
;;; onto a list and deliver that as a result
;;;