;---------------------------------------------------------;
;                  Konstruktoren                          ;
;---------------------------------------------------------;

(define (konstr-blatt symbol wichtung)
  (list 'blatt symbol wichtung))

(define (konstr-code-baum links rechts)
  (list links 
        rechts
        (append (symbole links) (symbole rechts))
        (+ (wichtung links) (wichtung rechts))))

;---------------------------------------------------------;
;                  Selektoren                             ;
;---------------------------------------------------------;

(define (symbol-blatt x) (cadr x))

(define (wichtung-blatt x) (caddr x))

(define (linker-ast baum) (car baum))
(define (rechter-ast baum) (cadr baum))

(define (symbole baum)
  (if (blatt? baum)
      (list (symbol-blatt baum))
      (caddr baum)))

(define (wichtung baum)
  (if (blatt? baum)
      (wichtung-blatt baum)
      (cadddr baum)))

;---------------------------------------------------------;
;                  Praedikate                             ;
;---------------------------------------------------------;

(define (blatt? objekt)
  (eq? (car objekt) 'blatt))


;---------------------------------------------------------;
(define (hinzufuegen-menge x menge)
  (cond ((null? menge) (list x))
        ((< (wichtung x) (wichtung (car menge)))
         (cons x menge))
        (else (cons (car  menge)
                    (hinzufuegen-menge x (cdr menge))))))

(define (decodiere bits baum)
  (decodiere-1 bits baum baum))

(define (decodiere-1 bits baum aktueller-ast)
  (if (null? bits)
      '()
      (let ((naechster-ast
             (waehle-ast (car bits)
                         aktueller-ast)))
        (if (blatt? naechster-ast)
            (cons (symbol-blatt naechster-ast)
                  (decodiere-1 (cdr bits)
                               baum
                               baum))
            (decodiere-1 (cdr bits)
                         baum
                         naechster-ast)))))

(define (waehle-ast bit ast)
  (cond ((= bit 0) (linker-ast ast))
        ((= bit 1) (rechter-ast ast))
        (else (error "Falsches Bit -- WAEHLE-AST"))))


(define (konstr-blatt-menge paare)
  (if (null? paare)
      '()
      (let ((paar (car paare)))
        (hinzufuegen-menge
         (konstr-blatt (car paar)
                       (cadr paar))
         (konstr-blatt-menge (cdr paare))))))