;; 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)
; - einer 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 ist eins der folgenden:
; - ein Codeblatt
; - ein Codeknoten
(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))

; Konstruktion eines Codebaums aus zwei Teilcodebä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)))

; Gewichtung eines Baums
(: weight (tree -> natural))
(define weight
  (lambda (tree)
    (cond ((leaf? tree) (leaf-weight tree))
          ((node? tree) (node-weight tree)))))

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

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Decodieren von Nachrichten:

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

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

; Decodieren mit einem aktuellen Ast des Huffman-Baums
(: 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 (restbits tree next-branch)
    (cond ((leaf? next-branch) (cons (leaf-symbol next-branch)
                                     (decode-1 restbits tree tree)))
          ((node? next-branch) (decode-1 restbits 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 gegebener Liste
; von Symbol/Häufigkeitspaaren: nacheinander geordnet eingefügen
(: 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))))))
  

; Ein Beispiel für die Konstruktion einer initialen Menge von Teilbäumen aus
; einer Liste von Symbol/Häufigkeitspaaren:
(: abcdTrees (list-of tree))
(define abcdTrees
  (make-leaf-set (list (make-leaf "A" 8)
                       (make-leaf "B" 3)
                       (make-leaf "C" 1)
                       (make-leaf "D" 1))))