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

(: empty-set set)
(: elem? (real set -> boolean))
(: add-set (real set -> set))
;(: union   (set set -> set))
;(: intersect (set set -> set))

; Ein Knoten besteht aus
; - einem Eintrag (real)
; - einen linken Teilbaum
; - einen rechten Teilbaum
(define-record-procedures node
  make-node node?
  (node-entry node-left node-right))


; Ein Binaerbaum ist eines der folgenden:
; - ein leerer Baum (empty-list)
; - ein Knoten (node)
(define btree
  (signature (mixed empty-list node)))

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

;Darstellung einer Menge
(define set (signature btree))

;Leere Menge
(define empty-set empty)

;Suche ein Element in einer Menge
(define elem?
  (lambda (x s)
    (cond ((empty? s) #f)
          ((= x (node-entry s)) #t)
          ((< x (node-entry s)) (elem? x (node-left s)))
          (else (elem? x (node-right s))))))

; Fuege ein Element hinzu
(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)))
          (else (make-node (node-entry s) 
                           (node-left s)
                           (add-set x (node-right s)))))))

;Die Menge mit den Elementen 1 und 2 
(define set12 (add-set 2 (add-set 1 empty-set)))

;Die Menge mit den Elementen 1 und 3 
(define set13 (add-set 3 (add-set 1 empty-set)))

(check-expect (elem? 1 set12) #t)
(check-expect (elem? 3 set12) #f)
;(check-expect (elem? 1 (intersect set12 set13)) #t)
;(check-expect (elem? 3 (intersect set12 set13)) #f)