(defun CreatePolynomial ()
    "Creates a new empty polynomial."
    ())

(defun ReadPolynomial1 ()
    "Reads a polynomial from standard-in and returns it as a sorted list."
    ())

(defun ReadPolynomial2 (pl)
    "Reads a polynomial from the list pl and returns it as a sorted list."
    (if (null pl)
        (CreatePolynomial)
        (let ((a (first pl)) (b (second pl)))
            (AddPolynomial (list (list a b)) (ReadPolynomial2 (rest (rest pl)))))))

(defun WritePolynomial (p)
    "Readably outputs the polynomial p."
    (if (not (equal 0 (list-length p)))
        (progn
            (WritePolynomial (rest p))
            (if (not (equal 0 (list-length (rest p))))
                (if (< 0 (first (first p)))
                    (format t " + ")
                    (format t " - ")))
            (if (equal 0 (second (first p)))
                (format t "~a" (abs (first (first p))))
                (format t "~ax^~a" (abs (first (first p))) (second (first p)))))))

(defun AddPolynomial (p1 p2)
    "Computes and returns p1 + p2."
    (ReducePolynomial (concatenate 'list p1 p2)))

(defun SubPolynomial (p1 p2)
    (ReducePolynomial (SubPolynomialHelper p1 p2)))

(defun SubPolynomialHelper (p1 p2)
    "Computes and returns p1 - p2."
    (if (null p2)
        p1
        (SubPolynomial (concatenate 'list (list (list (- 0 (first (first p2))) (second (first p2)))) p1) (rest p2))))

(defun MultPolynomial (p1 p2)
    "Computes and returns p1 * p2."
    (ReducePolynomial (Cartesian p1 p2)))

(defun Cartesian (n m)
    ""
    (if (or (null n) (null m))
        ()
        (concatenate 'list (Distribute (first n) m) (Cartesian (rest n) m))))

(defun Distribute (n m)
    ""
    (if (null m)
        ()
        (concatenate 'list (list (MultiplyTerm n (first m))) (Distribute n (rest m)))))

(defun MultiplyTerm (n m)
    ""
    (list (* (first n) (first m)) (+ (second n) (second m))))

(defun EvalPolynomial (p a)
    "Evaluates the polynomial p at the point a."
    (if (null p)
        0
        (+ (EvalPolynomial (rest p) a) (* (first (first p)) (expt a (second (first p)))))))

;; Helper Functions

(defun ReducePolynomial (p)
    ""
    (ReduceZeroCoefficients (ReduceDuplicateExponents (sort p #'Compare))))

(defun ReduceDuplicateExponents (p)
    ""
    (if (null (rest p))
        p
        (if (equal (second (first p)) (second (second p)))
            (ReduceDuplicateExponents (concatenate 'list (list (list (+ (first (first p)) (first (second p))) (second (first p)))) (rest (rest p))))
            (concatenate 'list (list (first p)) (ReduceDuplicateExponents (rest p))))))

(defun ReduceZeroCoefficients (p)
    ""
    (if (null p)
        p
        (if (equal 0 (first (first p)))
            (ReduceZeroCoefficients (rest p))
            (concatenate 'list (list (first p)) (ReduceZeroCoefficients (rest p))))))

(defun Compare (t1 t2)
    ""
    (< (second t1) (second t2)))

;; Testing

;(print (ReadPolynomial2 '(99 0 17 200 3 150 8 200 0 0)))
;(write-line "")

(let (
    (polyA (ReadPolynomial2 '(1 2 3 1 5 0)))
    (polyB (ReadPolynomial2 '(2 2 5 1 2 0))))

    (WritePolynomial polyA)
    (write-line "")
    (WritePolynomial polyB)
    (write-line "")
    ;(WritePolynomial (AddPolynomial polyA polyB))
    ;(write-line "")
    ;(WritePolynomial (SubPolynomial polyA polyB))
    ;(write-line "")
    (WritePolynomial (MultPolynomial polyA polyB))
    (write-line ""))

;; Prototyping