;; 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 set-tree) (read-case-sensitive #f) (teachpacks ()) (deinprogramm-settings #(#f write repeating-decimal #f #t none explicit #f ())))
; Schnittstelle für Mengen:
(provide set empty-set add-set elem?)

; Wir betrachten hier nur Zahlenmengen mit ganzen Zahlen: set
; Implementierung hier: Mengen als geordnete Binärbäume ihrer Elemente

; Ein Knoten besteht aus:
; - einem Eintrag (integer)
; - ein linker Teilbaum
; - ein rechter Teilbaum
(define-record-procedures node
  make-node
  node?
  (node-entry node-left node-right))

; Ein Binärbaum ist eins der Folgenden:
; - ein leerer Baum (empty-list)
; - ein Baumknoten (node)
(define btree
  (signature
    (mixed empty-list
           node)))

(: make-node (integer btree btree -> node))
(: node? (any -> boolean))
(: node-entry (node -> integer))
(: node-left  (node -> btree))
(: node-right (node -> btree))

(define set (signature btree))

; Die leere Menge
(: empty-set set)
(define empty-set empty)

; Ist ein Element in einer Menge enthalten?
(: elem? (integer set -> boolean))
(define elem?
  (lambda (x s)
    (cond ((empty? s) #f)
          ((= x (node-entry s)) #t)
          ((< x (node-entry s)) (elem? x (node-left s)))
          ((> x (node-entry s)) (elem? x (node-right s))))))

; Zu einer Menge ein Element hinzufügen
(: add-set (integer set -> set))
(define add-set
  (lambda (x s)
    (cond ((empty? s) (make-node x empty empty))
          ((= x (node-entry s)) s)
          ((< x (node-entry s)) (make-node (node-entry s)
                                           (add-set x (node-left s))
                                           (node-right s)))
          ((> x (node-entry s)) (make-node (node-entry s)
                                           (node-left s)
                                           (add-set x (node-right s)))))))


(define set13 (add-set 1 (add-set 3 empty-set)))
(define set12 (add-set 2 (add-set 1 empty-set)))

; Vereinige zwei Mengen
;(: union (set set -> set))

; Bilde den Durchschnitt zweier Mengen
;(: intersect (set set -> set))