; hw3.lisp
; CS 381 homework 3
; Jacob Lundberg

; MY-MERGE merges two pre-sorted lists in #'< order.
; Tolerates non-list args because that made MERGE-LEVEL easier.
(defun MY-MERGE (list1 list2)
  (cond ((null list1) list2)  ; end of list1
        ((null list2) list1)  ; end of list2
        ((not (listp list1)) (MY-MERGE (cons list1 nil) list2))
        ((not (listp list2)) (MY-MERGE list1 (cons list2 nil)))
        ((< (car list2) (car list1))  ; insert list2[0] here
           (cons (car list2) (MY-MERGE list1 (cdr list2))))
        (T (cons (car list1) (MY-MERGE (cdr list1) list2)))
  )
)

; MERGE-LEVEL is needed by MERGE-SORT to merge a level of a list.
(defun MERGE-LEVEL (list1)
  (cond ((null list1) nil)  ; no list
        ((null (cdr list1)) list1)  ; end of list
        (T (cons (MY-MERGE (car list1) (car (cdr list1)))
                 (MERGE-LEVEL (cddr list1))))  ; recurse
  )
)

; MERGE-SORT uses MY-MERGE to merge sort a list.
(defun MERGE-SORT (list1)
  (cond ((null list1) nil)  ; no list
        ((null (cdr list1)) (car list1))  ; single-element
        (T (MERGE-SORT (MERGE-LEVEL list1)))  ; recurse
  )
)

; MY-REVERSE reverses the order of the elements in a list.
(defun MY-REVERSE (list1)
  (cond ((null list1) nil)  ; no list
        ((null (cdr list1)) (cons (car list1) nil))  ; single element
        (T `(,@(MY-REVERSE (cdr list1)) ,(car list1)))  ; recurse
  )
)

; BINTREE-SEARCH searches a binary tree.
(defun BINTREE-SEARCH (leaf1 tree1)
  (cond ((null tree1) nil)  ; empty tree or no match
        ((eql (car tree1) leaf1) T)  ; found a match
        ((> (car tree1) leaf1) (BINTREE-SEARCH leaf1 (car (cdr tree1))))  ; left subtree
        (T (BINTREE-SEARCH leaf1 (car (cddr tree1))))  ; right subtree
  )
)