;; not gonna bother copy-pasting the rest of the implementation.
;; ex 2.59
(defun adjoin-set (s i)
  (if (element-of-set? s i)
      s
      (cons i s)))
(defun union-set (s1 s2)
  (labels ((rec (s1 s2)
	     (if (null s1)
		 s2
		 (rec (cdr s1) (adjoin-set s2 (car s1))))))
    (rec s1 s2)))

;; ex 2.60
;; element-of-set? doesn't change I'm pretty sure.
(defun element-of-set? (s e)
  (if (null s)
      nil
      (element-of-set? (cdr s) e)))
;; adjoin becomes more efficient, as it is now an O(1) operation
(defun adjoin-set-duppy (s e)
  (cons e s))
;; union-set becomes a linear-time algorithm as it relies on adjoin-set.
;; doesn't really change in logic otherwise, though.x
(defun union-set-duppy (s1 s2)
  (labels ((rec (s1 s2)
	     (if (null s1)
		 s2
		 (rec (cdr s1) (adjoin-set s2 (car s1))))))
    (rec s1 s2)))

;; ex 2.61
;; Note: NOT tail recursive. not gonna work for too long lists.
;; though the book's given intersection-list is also not tail
;; recursive, so this is probably intended.
(defun adjoin-set-ordered (s1 i)
  (cond
    ((null s1) (cons i nil))
    ((= i (car s1)) s1)
    ((< i (car s1))
     (cons i s1))
    (t (cons (car s1) (adjoin-set-ordered (cdr s1) i)))))

;; ex 2.62
;; same with 2.61, not tail recursive
;; both could be translated fairly easily though
(defun union-set-ordered (s1 s2)
  (cond
    ((null s1) s2)
    ((null s2) s1)
    ((= (car s1) (car s2))
     (cons (car s1)
	   (union-set-ordered (cdr s1) (cdr s2))))
    ((> (car s1) (car s2))
     (cons (car s2)
	   (union-set-ordered s1 (cdr s2))))
    ((< (car s1) (car s2))
     (cons (car s1)
	   (union-set-ordered (cdr s1) s2)))
    (t (error "asd"))))

;; ex 2.63
;; a) it looks like the result should be the same.
;; tried the code, couldn't get them to give different results.
;; on the figure 2.16 trees, they all give the same results.
;; b) At first glance they might look equivalent. However,
;; the first algorithm has a hidden cost in the append operation.
;; because the fastest way to append two linked lists is an O(N)
;; operation: so eventually it becomes O(N/2 + 2N/4 + 4N/8 + ... + logN)
;; or something like that, which is O(N + logn) or O(N).
;; the second algorithm doesn't waste time with that, and is therefore
;; a flat O(logN). The second one takes less time.

;; damn, raw lisp code can be hard to read. might be a skill issue.
;; ex 2.64
;; "short" paragraph. yeah.
;; Okay, so...
;; partial-tree takes a list of elements and n.
;; in the base case, i.e. n = 0, the result is trivially just (cons nil elts)
;; otherwise, the function calculates the length of the left half of the tree,
;; recursively calls itself with that "left half". As partial-tree returns
;; the rest of the elements, we take the "right half" from this rest of the elements
;; (of course making sure to save and exclude the center element, as that is
;; the root of the tree).
;; This way, we create a tree by recursively creating the left subtree, then the right
;; subtree, then we simply combine these to create the final tree.
;; b) O(N) each element is visited exactly once.

;; ex 2.65
;; assuming the union and intersection don't have to maintain
;; balance (or that's handled by something else)
(defstruct btree elt left right)
(defun adjoin-set-tree (s i)
  (cond
    ((null s) (make-btree :elt i :left nil :right nil))
    ((= (btree-elt s) i) s)
    ((< (btree-elt s) i)
     (make-btree :elt (btree-elt s)
		 :left (btree-left s)
		 :right (adjoin-set-tree (btree-right s) i)))
    ((> (btree-elt s) i)
     (make-btree :elt (btree-elt s)
		 :left (adjoin-set-tree (btree-left s) i)
		 :right (btree-right s)))))
(defun union-set-tree (s1 s2)
  (cond
    ((null s1) s2)
    ((null s2) s1)
    (t (union-set-tree (union-set-tree (btree-left s1) (btree-right s2))
		  s     (adjoin-set-tree s2 (btree-elt s1))))))
;; yeah, okay. this looks good enough, didn't test it at all, but whatevs.