;; an implementation of queues.
(module queue mzscheme
  (require (lib "unitsig.ss"))
  (provide (all-defined))

  ;; A queue must support the following operations:
  (define-signature queue^
    (
     
     ;; make-queue: () -> queue
     ;; returns an empty queue
     make-queue

     ;; empty-queue: queue -> boolean
     ;; returns #t if the queue is empty, and otherwise #f.
     empty-queue?

     ;; front-queue: queue -> element
     ;; returns the front element in the queue.
     front-queue

     ;; insert-queue!: queue -> element -> queue
     ;; adds an element into the queue, and then returns the modified queue.
     insert-queue!

     ;; delete-queue!: queue -> queue
     ;; drops the front element from the queue, and returns the modified queue.
     delete-queue!
     ))


;   (define another-queue-impl@
;     (unit/sig queue^
;         (import)

;       (define (make-queue))))

  
  
  (define queue-impl@
    (unit/sig queue^
        (import)
      
      (define (make-queue)
        (cons '() '()))

      (define (front-ptr queue)
        (car queue))

      (define (rear-ptr queue)
        (cdr queue))

      (define (set-front-ptr! queue item)
        (set-car! queue item))

      (define (set-rear-ptr! queue item)
        (set-cdr! queue item))
      

      (define (empty-queue? queue)
        (null? (front-ptr queue)))


      (define (front-queue queue)
        (if (empty-queue? queue)
            (error "FRONT called with an empty queue" queue)
            (car (front-ptr queue))))


      (define (insert-queue! queue item)
        (let ((new-pair (cons item '())))
          (cond [(empty-queue? queue)
                 (set-front-ptr! queue new-pair)
                 (set-rear-ptr! queue new-pair)
                 queue]
                
                [else
                 (set-cdr! (rear-ptr queue) new-pair)
                 (set-rear-ptr! queue new-pair)
                 queue])))


      (define (delete-queue! queue)
        (cond ((empty-queue? queue)
               (error "DELETE! called with an empty queue" queue))
              (else
               (set-front-ptr! queue (cdr (front-ptr queue)))
               queue)))


      ))

  
  ;; makes the implementation easily available.
  (define-values/invoke-unit/sig queue^ queue-impl@)
)