/*
 * $Id$
 */

package edu.jas.fd;


import org.apache.log4j.Logger;

import edu.jas.poly.GenPolynomial;
import edu.jas.poly.GenSolvablePolynomial;
import edu.jas.poly.PolyUtil;
import edu.jas.structure.GcdRingElem;


/**
 * (Non-unique) factorization domain greatest common divisor common algorithms
 * with monic polynomial remainder sequence.
 * If C is a field, then the monic PRS (on coefficients) is computed otherwise
 * no simplifications in the reduction are made.
 * @param  coefficient type
 * @author Heinz Kredel
 */

public class GreatestCommonDivisorSimple> extends GreatestCommonDivisorAbstract {


    private static final Logger logger = Logger.getLogger(GreatestCommonDivisorSimple.class);


    private final boolean debug = true; //logger.isDebugEnabled();


    /**
     * Univariate GenSolvablePolynomial greatest common divisor. Uses
     * pseudoRemainder for remainder.
     * @param P univariate GenSolvablePolynomial.
     * @param S univariate GenSolvablePolynomial.
     * @return gcd(P,S).
     */
    @Override
    public GenSolvablePolynomial baseGcd(GenSolvablePolynomial P, GenSolvablePolynomial S) {
        if (S == null || S.isZERO()) {
            return P;
        }
        if (P == null || P.isZERO()) {
            return S;
        }
        if (P.ring.nvar > 1) {
            throw new IllegalArgumentException(this.getClass().getName() + " no univariate polynomial");
        }
        boolean field = P.ring.coFac.isField();
        long e = P.degree(0);
        long f = S.degree(0);
        GenSolvablePolynomial q;
        GenSolvablePolynomial r;
        if (f > e) {
            r = P;
            q = S;
            long g = f;
            f = e;
            e = g;
        } else {
            q = P;
            r = S;
        }
        if (debug) {
            logger.debug("degrees: e = " + e + ", f = " + f);
        }
        C c;
        if (field) {
            r = r.monic();
            q = q.monic();
            c = P.ring.getONECoefficient();
        } else {
            r = (GenSolvablePolynomial) r.abs();
            q = (GenSolvablePolynomial) q.abs();
            C a = baseContent(r);
            C b = baseContent(q);
            c = gcd(a, b); // indirection
            r = divide(r, a); // indirection
            q = divide(q, b); // indirection
        }
        if (r.isONE()) {
            return r.multiply(c);
        }
        if (q.isONE()) {
            return q.multiply(c);
        }
        GenSolvablePolynomial x;
        //System.out.println("q = " + q);
        //System.out.println("r = " + r);
        while (!r.isZERO()) {
            x = FDUtil. baseSparsePseudoRemainder(q, r);
            q = r;
            if (field) {
                r = x.monic();
            } else {
                r = x;
            }
            //System.out.println("q = " + q);
            //System.out.println("r = " + r);
        }
        q = basePrimitivePart(q);
        return (GenSolvablePolynomial) (q.multiply(c)).abs();
    }


    /**
     * Univariate GenSolvablePolynomial recursive greatest comon divisor. Uses
     * pseudoRemainder for remainder.
     * @param P univariate recursive GenSolvablePolynomial.
     * @param S univariate recursive GenSolvablePolynomial.
     * @return gcd(P,S).
     */
    @Override
    public GenSolvablePolynomial> recursiveUnivariateGcd(
                    GenSolvablePolynomial> P, GenSolvablePolynomial> S) {
        if (S == null || S.isZERO()) {
            return P;
        }
        if (P == null || P.isZERO()) {
            return S;
        }
        if (P.ring.nvar > 1) {
            throw new IllegalArgumentException("no univariate polynomial");
        }
        boolean field = P.leadingBaseCoefficient().ring.coFac.isField();
        long e = P.degree(0);
        long f = S.degree(0);
        GenSolvablePolynomial> q;
        GenSolvablePolynomial> r;
        if (f > e) {
            r = P;
            q = S;
            long g = f;
            f = e;
            e = g;
        } else {
            q = P;
            r = S;
        }
        if (debug) {
            logger.debug("degrees: e = " + e + ", f = " + f);
        }
        if (field) {
            r = PolyUtil. monic(r);
            q = PolyUtil. monic(q);
        } else {
            r = (GenSolvablePolynomial>) r.abs();
            q = (GenSolvablePolynomial>) q.abs();
        }
        GenSolvablePolynomial a = recursiveContent(r);
        GenSolvablePolynomial b = recursiveContent(q);
        logger.info("recCont a = " + a); // + ", r = " + r);
        logger.info("recCont b = " + b); // + ", q = " + q);

        GenSolvablePolynomial c = gcd(a, b); // go to recursion
        logger.info("Gcd(contents) c = " + c);
        r = FDUtil. recursiveDivide(r, a);
        q = FDUtil. recursiveDivide(q, b);
        if (r.isONE()) {
            return r.multiply(c);
        }
        if (q.isONE()) {
            return q.multiply(c);
        }
        GenSolvablePolynomial> x;
        if (debug) {
            logger.debug("r.ring = " + r.ring.toScript());
        }
        while (!r.isZERO()) { //&& r.degree()>0
            if (debug) {
                logger.info("deg(q) = " + q.degree() + ", deg(r) = " + r.degree());
            }
            x = FDUtil. recursiveSparsePseudoRemainder(q, r);
            q = r;
            if (field) {
                r = PolyUtil. monic(x);
            } else {
                r = x;
            }
        }
        q = recursivePrimitivePart(q);
        if (debug) {
            //logger.info("var = " + P.ring.varsToString() + ", gcd(pp) = " + q);
            logger.info("gcd(pp) = " + q + ", ring = " + P.ring.toScript());
        }
        q = (GenSolvablePolynomial>) q.abs().multiply(c);
        return q;
    }

}