;; 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 ())))
; Dieses Modul enthält eine Implementierung von Warteschlangen

(provide queue-of make-queue empty-queue? front-queue
         delete-queue! insert-queue!)

; Benutze veränderbare Listen zur Implementierung der Warteschlange
(require "mlist.rkt")

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

(define queue-of
  (lambda (sig)
    (qu-of sig 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))

; Konstruktor für eine neue leere Warteschlage
(: make-queue (-> (queue-of %a)))
(define make-queue
  (lambda () (make-qu empty empty)))

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

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

; Mutator: Einfügen eines Elementes am Ende der 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))))))

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