;;; queues with amortized constant-time access to data
(module yasos-queues   
        (make-queue queue? empty? protocol size state front clear! deq! enq!)
        
(import scheme (chicken base) (chicken format)
        (except yasos object object-with-ancestors))
                 
;; interface     
(define-predicate queue?)
(define-operation (empty? obj))
(define-operation (clear! obj))
(define-operation (front obj))
(define-operation (deq! obj))
(define-operation (enq! obj x))
(define-operation (state obj))
                 
;; implementation
(define (make-queue)
  (let ((in '()) (out '()))
    (operations ()
      ((queue? self) #t)
      ((empty? self) (and (null? in) (null? out)))
      ((size self) (+ (length in) (length out)))
      ((show self . optional-arg)
       (if (null? optional-arg)
         (show self #t)
         (format (car optional-arg)
                 "#,~s~%"
                 (cons 'queue (append out (reverse in))))))
      ((state self) ; for inheritance
       (lambda () (vector in out)))
      ((front self)
       (if (and (null? in) (null? out))
         (error 'front "queue empty")
         (begin
           (when (null? out)
             (set! out (reverse in))
             (set! in '()))
           (car out))))
      ((enq! self x) (set! in (cons x in)))
      ((deq! self)
       (if (and (null? in) (null? out))
         (error 'deq! "queue empty")
         (begin
           (when (null? out)
             (set! out (reverse in))
             (set! in '()))
           (set! out (cdr out)))))
      ((clear! self) (set! in '()) (set! out '())))))

) ; module queues