;; Die ersten drei Zeilen dieser Datei wurden von DrRacket eingefügt. Sie enthalten Metadaten
;; über die Sprachebene dieser Datei in einer Form, die DrRacket verarbeiten kann.
#reader(lib "DMdA-assignments-reader.ss" "deinprogramm")((modname queue) (read-case-sensitive #f) (teachpacks ()) (deinprogramm-settings #(#f write repeating-decimal #t #t none explicit #f ())))
; Die Schnittstelle von Warteschlangen:
(provide queue-of make-queue empty-queue? front-queue
         insert-queue! delete-queue!)

; Benutze veränderbare Listen
(require "mlist.rkt")

; Eine veränderbare Warteschlange besteht aus zwei Verweisen
; auf den Anfang und das Ende der eigentlichen Warteschlange
(define-record-procedures-parametric-2 qu qu-of
  make-qu
  qu?
  ((qu-begin set-qu-begin!) (qu-end set-qu-end!)))

; Signaturkonstruktor für Warteschlangen
(define queue-of
  (lambda (sig) (qu-of (mlist-of sig) (mlist-of sig))))

(: make-qu ((mlist-of %a) (mlist-of %a) -> (queue-of %a)))
(: qu? (any -> boolean))
(: qu-begin ((queue-of %a) -> (mlist-of %a)))
(: set-qu-begin! ((queue-of %a) (mlist-of %a) -> unspecific))
(: qu-end   ((queue-of %a) -> (mlist-of %a)))
(: set-qu-end! ((queue-of %a) (mlist-of %a) -> unspecific))

; Erzeuge eine leere Warteschlange
(: make-queue ( -> (queue-of any)))
(define make-queue
  (lambda () (make-qu empty empty)))

; Selektor: ist eine Warteschlange leer?
(: empty-queue? ((queue-of %a) -> boolean))
(define empty-queue?
  (lambda (q)
    (empty? (qu-begin q))))

; Selektor: erstes Element einer Warteschlange
(: front-queue ((queue-of %a) -> %a))
(define front-queue
  (lambda (q)
    (if (empty-queue? q)
        (violation "Empty queue")
        (mfirst (qu-begin q)))))

; Hinzufügen eines Elementes zu einer Warteschlange
(: insert-queue! ((queue-of %a) %a -> unspecific))
(define insert-queue!
  (lambda (q e)
    (letrec ((new-elem (mcons e empty)))
      (if (empty-queue? q)
          (begin (set-qu-begin! q new-elem)
                 (set-qu-end! q new-elem))
          (begin (set-mrest! (qu-end q) new-elem)
                 (set-qu-end! q new-elem))))))

; Entfernen des ersten Elementes der Warteschlange
(: delete-queue! ((queue-of %a) -> unspecific))
(define delete-queue!
  (lambda (q)
    (if (empty-queue? q)
        (violation "Empty queue")
        (set-qu-begin! q (mrest (qu-begin q))))))

(define q (make-queue))