;; 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-vanilla-reader.ss" "deinprogramm")((modname huffman) (read-case-sensitive #f) (teachpacks ()) (deinprogramm-settings #(#f write repeating-decimal #f #t none explicit #f ())))
; Datenstrukturen für Huffman-Bäume

; Ein Codeblatt besteht aus
; - einem Symbol (string)
; - einer Gewichtung (natural)
(define-record-procedures leaf
  make-leaf
  leaf?
  (leaf-symbol leaf-weight))

(: make-leaf (string natural -> leaf))
(: leaf? (any -> boolean))
(: leaf-symbol (leaf -> string))
(: leaf-weight (leaf -> natural))

; Ein Codeknoten besteht aus
; - einer Menge von Symbolen (list-of string)
; - eine Gewichtung (natural)
; - einem linken Codebaum
; - einem rechten Codebaum
(define-record-procedures node
  make-node
  node?
  (node-symbols node-weight node-left node-right))

; Ein Codebaum (Huffman-Baum) ist eins der folgenden:
; - ein Codeblatt (leaf)
; - ein Codeknoten (node)
(define tree
  (signature
    (mixed leaf
           node)))

(: make-node ((list-of string) natural tree tree -> node))
(: node? (any -> boolean))
(: node-symbols (node -> (list-of string)))
(: node-weight (node -> natural))
(: node-left (node -> tree))
(: node-right (node -> tree))

; Konstruktor für innere Knoten aus zwei Teilbäumen
(: make-code-tree (tree tree -> node))
(define make-code-tree
  (lambda (left right)
    (make-node (append (symbols left) (symbols right))
               (+ (weight left) (weight right))
               left
               right)))

; Selektoren für Codebäume

; Symbole eines Codebaums
(: symbols (tree -> (list-of string)))
(define symbols
  (lambda (tree)
    (cond ((leaf? tree) (list (leaf-symbol tree)))
          ((node? tree) (node-symbols tree)))))

; Gewichtung eines Codebaums
(: weight (tree -> natural))
(define weight
  (lambda (tree)
     (cond ((leaf? tree) (leaf-weight tree))
           ((node? tree) (node-weight tree)))))
   
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Decodierer für Huffman-codierte Nachrichten

; Ein Bit ist 0 oder 1
(define bit (signature (one-of 0 1)))

; Decodiere eine Liste von Bits mit Hilfe des Huffman-Baums
(: decode ((list-of bit) tree -> (list-of string)))
(define decode
  (lambda (bits tree)
    (decode-1 bits tree tree)))

(: decode-1 ((list-of bit) tree tree -> (list-of string)))
(define decode-1
  (lambda (bits tree current-branch)
    (if (empty? bits)
        empty
        (decode-next-branch (rest bits) tree
                            (choose-branch (first bits) current-branch)))))

(: choose-branch (bit node -> tree))
(define choose-branch
  (lambda (bit branch)
    (cond ((= bit 0) (node-left branch))
          ((= bit 1) (node-right branch)))))

(: decode-next-branch ((list-of bit) tree tree -> (list-of string)))
(define decode-next-branch
  (lambda (bits tree next-branch)
    (cond ((leaf? next-branch) (cons (leaf-symbol next-branch)
                                     (decode-1 bits tree tree)))
          ((node? next-branch) (decode-1 bits tree next-branch)))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Konstruktion von Huffman-Bäumen

; Struktur: Liste von Codebäumen geordnet nach Gewichtungen
; Vorteil: Zugriff auf Bäume mit kleinstem Gewicht in konstanter Zeit!

; Einfügen in geordnete Menge von gewichteten Elementen
; 2. Argument: geordnete Liste von Bäumen!
(: add-weightet-set (tree (list-of tree) -> (list-of tree)))
(define add-weightet-set
  (lambda (x set)
    (cond ((empty? set) (cons x empty))
          ((< (weight x) (weight (first set))) (cons x set))
          (else (cons (first set) (add-weightet-set x (rest set)))))))

; Konstruktiere initiale Menge von Teilbäumen aus gegebenen Liste
; von Symbol/Häufigkeitspaaren: nacheinander geordnet eingefügt
(: make-leaf-set ((list-of leaf) -> (list-of tree)))
(define make-leaf-set
  (lambda (pairs)
    (if (empty? pairs)
        empty
        (add-weightet-set (first pairs) (make-leaf-set (rest pairs))))))