source: branches/f4grobner/fast-add.lisp@ 4430

;; Getter/setter of leading coefficient
(defun lc (x) (term-coeff (car x)))
(defun (setf lc) (new-value x) (setf (term-coeff (car x)) new-value))

(defun fast-add-helper (p q)
  "It assumes that p and q are non-zero polynomials, i.e. non-empty lists of terms."
  (multiple-value-bind 
        (greater-p equal-p)
      (funcall order-fn (car p) (car q))
    (cond
      (greater-p 
       (fast-add-helper (cdr p) q))
      (equal-p
       (let ((s (funcall add-fn (lc p) (lc q))))
         (cond 
           ((universal-zerop s)
            (setf p (cdr p))
            )
           (t 
            (setf (lc p) s)
            (fast-add-helper (cdr p) (cdr q)))))
       (setf q (cdr q))
       )
      (t                                
       (fast-add-helper (cdr q) p)))))

(defun fast-add (p q order-fn add-fn &aux r)
  "Add two polynomials, P and Q, represented as lists of terms.
The operation is destructive to both polynomials, as the terms
of both lists are combined into the result. The operation does not
create any new instance of TERM."
  (cond ((endp p) q)
        ((endp q) p)
        (t (fast-add-helper p q))))