set-btree.rkt

#lang racket

(provide union-set intersection-set element-of-set? adjoin-set make-set)
(require "accumulate.rkt")
(require "btree.rkt")
(require "list-tree.rkt")
(require "tree-list.rkt")

(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((= x (entry set)) #t)
        ((< x (entry set)) (element-of-set? x (left-branch set))) 
        (else (element-of-set? x (right-branch set)))))

(define (adjoin-set x set)
  (cond ((null? set) (make-tree x '() '()))
        ((= x (entry set)) set)
        ((< x (entry set)) (make-tree (entry set)
                                      (adjoin-set x (left-branch set))
                                      (right-branch set)))
        (else (make-tree (entry set)
                         (left-branch set)
                         (adjoin-set x (right-branch set))))))

(define (element-of-set-list? x set)
  (cond ((null? set) #f)
        ((= x (car set)) #t)
        ((< x (car set)) #f)
        (else (element-of-set-list? x (cdr set)))))

(define (intersection-set t1 t2)
  (define (intersection-set-list set1 set2)
    (if (or (null? set1) (null? set2))
        '()
        (let ((x1 (car set1))
              (x2 (car set2)))
          (cond ((= x1 x2) (cons x1 (intersection-set-list (cdr set1) (cdr set2))))
                ((< x1 x2) (intersection-set-list (cdr set1) set2))
                (else (intersection-set-list set1 (cdr set2)))))))
  (let ((tl1 (tree->list-2 t1))
        (tl2 (tree->list-2 t2)))
    (list->tree (intersection-set-list tl1 tl2))))

(define (union-set t1 t2)
  (define (union-set-list set1 set2)
    (cond ((null? set1) set2)
          ((null? set2) set1)
          (else (let ((x1 (car set1))
                      (x2 (car set2)))
                  (cond ((= x1 x2) (cons x1 (union-set-list (cdr set1) (cdr set2))))
                        ((< x1 x2) (cons x1 (union-set-list (cdr set1) set2)))
                        (else (cons x1 (union-set-list set1 (cdr set2)))))))))
  (let ((tl1 (tree->list-2 t1))
        (tl2 (tree->list-2 t2)))
    (list->tree (union-set-list tl1 tl2))))

(define (make-set . elements) (list->tree elements))