(defun quadrado (n)
  (do ((i 0 (+ i 1))
       (j 1 (+ j 2))
       (result 0))
      ((= i (abs n)) result)
      (setf result (+ result j))
      )
  )

(defun last (lista)
  (if (null (cdr lista))
      (car lista) (last (cdr lista))
      )
  )

(defun list (a &rest b)
  (cons a b)     
)

(defun append (lista1 lista2)
  (if (null lista1)
      lista2 (cons (car lista1) (append (cdr lista1) lista2)) 
      )
  )

(defun reverse (lista)
  (if (null lista)
      lista (append (reverse (cdr lista)) (list (car lista)))
      )
  )

(defun member (item lista)
  (if (or (null lista)
	  (eq (car lista) item))
      lista (member item (cdr lista))
      )
  )

(defun adjoin (item lista)
  (if (member item lista)
      lista (cons item lista)
      )
  )
  
  
(defun union (lista1 lista2)
  (cond
   ((null lista2) lista1)
   ((member (car lista2) lista1) (union lista1 (cdr lista2)))
   (t (union (cons (car lista2) lista1) (cdr lista2)))
   )
  )

(defun union2 (lista1 lista2)
  (let ((lista lista1))
    (dolist (item lista2)
	    (setf lista (join item lista))
	    )
    lista
    )
  )

(defun intersection (lista1 lista2)
  (cond
   ((null lista2) lista2)
   ((member (car lista2) lista1)
    (cons (car lista2) (intersection lista1 (cdr lista2))))
   (t (intersection lista1 (cdr lista2)))
   )
  )
  
(defun subsetp (lista1 lista2)
  (if (null lista1)
      t (and (member  (car lista1) lista2)
	     (subsetp (cdr lista1) lista2))
      )
  )

(defun set-difference (lista1 lista2)
  (cond
   ((null lista1) lista1)
   ((member (car lista1) lista2)
    (set-difference (cdr lista1) lista2))
   (t (cons (car lista1) (set-difference (cdr lista1) lista2)))
   )
  )

(defun tail (sublista lista)
  (if (>= (length lista) (length sublista))
      (equal sublista (nthcdr (- (length lista) (length sublista)) lista))
    nil
    )
  )

(defun sublist (sublista lista)
  (cond
   ((null lista) (null sublista))
   ((tail sublista lista) t)
   (t (sublist sublista (reverse (cdr (reverse lista)))))
   )
  )

(defun sublist2 (sublista lista)
  (do ((i 0 (+ i 1))
       (j (- (length lista) (length sublista)) (- j 1))
       (result nil))
      ((or result (< j 0)) result)
      
      (when (equal sublista (nthcdr i (butlast lista j)))
	(setf result t)
	)
      )
  )

(defun butlast (lista &optional n)
  (let ((indice (if (null n) 1 n)))
    (if (null (nthcdr indice lista))
	nil (append (list (car lista)) (butlast (cdr lista) indice))
	)
    )
  )

(defun merge (lista1 lista2)
  (do ((i 0)
       (j 0)
       (result nil))
      ((= (+ (length lista1) (length lista2)) (length result)) result)
      (cond
       ((= i (length lista1))
	(setf result (append result (nthcdr j lista2))))
       ((= j (length lista2))
	(setf result (append result (nthcdr i lista1))))
       ((< (nth i lista1) (nth j lista2))
	(setf result (append result (list (nth i lista1))))
	(setf i (+ i 1)))
       (t
	(setf result (append result (list (nth j lista2))))
	(setf j (+ j 1)))
       )
      )
  )

(defun sort (lista)
  (if (null (cdr lista))
      lista
    (merge (sort (butlast lista (floor   (/ (length lista) 2))))
	   (sort (nthcdr  (ceiling (/ (length lista) 2)) lista))
	   )
    )
  )

(defun empty (arvore)
  (null arvore)
  )

(defun make-node (info)
  (list info nil nil)
  )

(defun info (arvore)
  (first arvore)
  )

(defun left (arvore)
  (second arvore)
  )

(defun right (arvore)
  (third arvore)
  )

(defun find (x arvore)
  (cond
   ((empty arvore) nil)
   ((= (info arvore) x) arvore)
   ((> (info arvore) x) (find x (left arvore) ) )
   (t                   (find x (right arvore)) )
   )
  )

(defun insert (x arvore)
  (cond
   ((empty arvore) (make-node x))
   ((= (info arvore) x) arvore)
   ((> (info arvore) x)
    (list (info arvore) (insert x (left arvore)) (right arvore)))
   (t
    (list (info arvore) (left arvore) (insert x (right arvore)) ))
   )
  )

;; LISTA 4:
;; 1 - pre-order, in-order e pos-order
;; 2 - height
;; 3 - balanced

(defun pre-order (arvore)
  (unless (empty arvore)
    (print (info arvore))
    (pre-order (left arvore))
    (pre-order (right arvore))
    )
  )

(defun in-order (arvore)
  (unless (empty arvore)
    (in-order (left arvore))
    (print (info arvore))
    (in-order (right arvore))
    )
  )

(defun pos-order (arvore)
  (unless (empty arvore)
    (pos-order (left arvore))
    (pos-order (right arvore))
    (print (info arvore))
    t
    )
  )

(defun height (arvore)
  (if (empty arvore)
      0 (+ 1 (max
	      (height (left arvore))
	      (height (right arvore)))
	   )
      )
  )

(defun balanced (arvore)
  (cond
   ((empty arvore) t)
   ((and (<= (abs (- (height (left arvore)) (height (right arvore)))) 1)
	 (balanced (left arvore))
	 (balanced (right arvore))) t)
   (t nil)
   )
  )