#lang sicp


;;(define (element-of-set? x set)
;;  (cond ((null? set) false)
;;        ((equal? x (car set)) true)
;;        (else (element-of-set? x (cdr set)))))

;;(define (adjoin-set x set)
;;  (if (element-of-set? x set)
;;      set
;;      (cons x set)))

;;(define (intersection-set set1 set2)
;;  (cond ((or (null? set1) (null? set2)) '())
;;        ((element-of-set? (car set1) set2)
;;         (cons (car set1)
;;               (intersection-set (cdr set1) set2)))
;;        (else (intersection-set (cdr set1) set2))))


;;(define (union-set set1 set2)
;;  (cond ((null? set1) set2)
;;        ((null? set2) set1)
;;        ((not (element-of-set? (car set1) set2))
;;         (cons (car set1) (union-set (cdr set1) set2)))
;;        (else (union-set (cdr set1) set2))))

;; With duplicates

;;(define (adjoin-set x set) (cons x set))

;;(define (union-set set1 set2) (append set1 set2))

;; Efficiency is dependent on the number duplicates in the underlying list
;; This increases with each operation.  For smaller numbers of duplicates
;; adjoin and union should be much cheaper than the no-duplicate versions.

;; ORDERED

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((= x (car set)) true)
        ((< x (car set)) false)
        (else (element-of-set? x (cdr set)))))

(define (intersection-set set1 set2)
  (if (or (null? set1) (null? set2))
      '()
      (let ((x1 (car set1)) (x2 (car set2)))
        (cond ((= x1 x2)
               (cons x1
                     (intersection-set (cdr set1)
                                       (cdr set2))))
              ((< x1 x2)
               (intersection-set (cdr set1) set2))
              ((< x2 x1)
               (intersection-set set1 (cdr set2)))))))

(define (adjoin-set x set)
  (cond ((null? set) (list x))
        ((equal? x (car set)) set)
        ((< x (car set)) (cons x set))
        (else (adjoin-set x (cdr set)))))

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        (else
         (let ((x1 (car set1))
               (x2 (car set2)))
          (cond ((= x1 x2) (cons x1 (union-set (cdr set1) (cdr set2))))
                ((< x1 x2) (cons x1 (union-set (cdr set1) set2)))
                (else (cons x2 (union-set set1 (cdr set2)))))))))