/*
 * $Id$
 */

package edu.jas.ufd;


import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;

import org.apache.log4j.Logger;

import edu.jas.poly.GenPolynomial;
import edu.jas.poly.GenPolynomialRing;
import edu.jas.poly.PolyUtil;
import edu.jas.structure.GcdRingElem;
import edu.jas.structure.RingFactory;


/**
 * Squarefree decomposition for coefficient fields of characteristic 0.
 * @author Heinz Kredel
 */

public class SquarefreeFieldChar0> extends SquarefreeAbstract {


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


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


    /**
     * Factory for field of characteristic 0 coefficients.
     */
    protected final RingFactory coFac;


    /**
     * Constructor.
     */
    public SquarefreeFieldChar0(RingFactory fac) {
        super(GCDFactory. getProxy(fac));
        if (!fac.isField()) {
            throw new IllegalArgumentException("fac must be a field");
        }
        if (fac.characteristic().signum() != 0) {
            throw new IllegalArgumentException("characterisic(fac) must be zero");
        }
        coFac = fac;
    }


    /**
     * Get the String representation.
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        return getClass().getName() + " with " + engine + " over " + coFac;
    }


    /**
     * GenPolynomial polynomial greatest squarefree divisor.
     * @param P GenPolynomial.
     * @return squarefree(pp(P)).
     */
    @Override
    public GenPolynomial baseSquarefreePart(GenPolynomial P) {
        if (P == null || P.isZERO()) {
            return P;
        }
        GenPolynomialRing pfac = P.ring;
        if (pfac.nvar > 1) {
            throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials");
        }
        GenPolynomial pp = P.monic();
        if (pp.isConstant()) {
            return pp;
        }
        GenPolynomial d = PolyUtil. baseDeriviative(pp);
        d = d.monic();
        //System.out.println("d = " + d);
        GenPolynomial g = engine.baseGcd(pp, d);
        g = g.monic();
        GenPolynomial q = PolyUtil. basePseudoDivide(pp, g);
        q = q.monic();
        return q;
    }


    /**
     * GenPolynomial test if is squarefree.
     * @param P GenPolynomial.
     * @return true if P is squarefree, else false.
     */
    public boolean isBaseSquarefree(GenPolynomial P) {
        if (P == null || P.isZERO()) {
            return true;
        }
        GenPolynomialRing pfac = P.ring;
        if (pfac.nvar > 1) {
            throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials");
        }
        GenPolynomial pp = P.monic();
        if (pp.isConstant()) {
            return true;
        }
        GenPolynomial d = PolyUtil. baseDeriviative(pp);
        d = d.monic();
        //System.out.println("d = " + d);
        GenPolynomial g = engine.baseGcd(pp, d);
        g = g.monic();
        return g.isONE();
    }


    /**
     * GenPolynomial polynomial squarefree factorization.
     * @param A GenPolynomial.
     * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} p_i^{e_i}
     *         and p_i squarefree.
     */
    @Override
    public SortedMap, Long> baseSquarefreeFactors(GenPolynomial A) {
        SortedMap, Long> sfactors = new TreeMap, Long>();
        if (A == null || A.isZERO()) {
            return sfactors;
        }
        if (A.isConstant()) {
            sfactors.put(A, 1L);
            return sfactors;
        }
        GenPolynomialRing pfac = A.ring;
        if (pfac.nvar > 1) {
            throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials");
        }
        C ldbcf = A.leadingBaseCoefficient();
        if (!ldbcf.isONE()) {
            A = A.divide(ldbcf);
            GenPolynomial f1 = pfac.getONE().multiply(ldbcf);
            //System.out.println("gcda sqf f1 = " + f1);
            sfactors.put(f1, 1L);
            ldbcf = pfac.coFac.getONE();
        }
        GenPolynomial T0 = A;
        GenPolynomial Tp;
        GenPolynomial T = null;
        GenPolynomial V = null;
        long k = 0L;
        boolean init = true;
        while (true) {
            if (init) {
                if (T0.isConstant() || T0.isZERO()) {
                    break;
                }
                Tp = PolyUtil. baseDeriviative(T0);
                T = engine.baseGcd(T0, Tp);
                T = T.monic();
                V = PolyUtil. basePseudoDivide(T0, T);
                //System.out.println("iT0 = " + T0);
                //System.out.println("iTp = " + Tp);
                //System.out.println("iT  = " + T);
                //System.out.println("iV  = " + V);
                k = 0L;
                init = false;
            }
            if (V.isConstant()) {
                break;
            }
            k++;
            GenPolynomial W = engine.baseGcd(T, V);
            W = W.monic();
            GenPolynomial z = PolyUtil. basePseudoDivide(V, W);
            //System.out.println("W = " + W);
            //System.out.println("z = " + z);
            V = W;
            T = PolyUtil. basePseudoDivide(T, V);
            //System.out.println("V = " + V);
            //System.out.println("T = " + T);
            if (z.degree(0) > 0) {
                if (ldbcf.isONE() && !z.leadingBaseCoefficient().isONE()) {
                    z = z.monic();
                    logger.info("z,monic = " + z);
                }
                sfactors.put(z, k);
            }
        }
        //      look, a stupid error:
        //         if ( pfac.coFac.isField() && !ldbcf.isONE() ) {
        //             GenPolynomial f1 = sfactors.firstKey();
        //             long e1 = sfactors.remove(f1);
        //             System.out.println("gcda sqf c = " + c);
        //             f1 = f1.multiply(c);
        //             //System.out.println("gcda sqf f1e = " + f1);
        //             sfactors.put(f1,e1);
        //         }
        return normalizeFactorization(sfactors);
    }


    /**
     * GenPolynomial recursive univariate polynomial greatest squarefree
     * divisor.
     * @param P recursive univariate GenPolynomial.
     * @return squarefree(pp(P)).
     */
    @Override
    public GenPolynomial> recursiveUnivariateSquarefreePart(GenPolynomial> P) {
        if (P == null || P.isZERO()) {
            return P;
        }
        GenPolynomialRing> pfac = P.ring;
        if (pfac.nvar > 1) {
            throw new IllegalArgumentException(this.getClass().getName()
                            + " only for multivariate polynomials");
        }
        // squarefree content
        GenPolynomial> pp = P;
        GenPolynomial Pc = engine.recursiveContent(P);
        Pc = Pc.monic();
        if (!Pc.isONE()) {
            pp = PolyUtil. coefficientPseudoDivide(pp, Pc);
            //System.out.println("pp,sqp = " + pp);
            //GenPolynomial Pr = squarefreePart(Pc);
            //Pr = Pr.monic();
            //System.out.println("Pr,sqp = " + Pr);
        }
        if (pp.leadingExpVector().getVal(0) < 1) {
            //System.out.println("pp = " + pp);
            //System.out.println("Pc = " + Pc);
            return pp.multiply(Pc);
        }
        GenPolynomial> d = PolyUtil. recursiveDeriviative(pp);
        //System.out.println("d = " + d);
        GenPolynomial> g = engine.recursiveUnivariateGcd(pp, d);
        //System.out.println("g,rec = " + g);
        g = PolyUtil. monic(g);
        GenPolynomial> q = PolyUtil. recursivePseudoDivide(pp, g);
        q = PolyUtil. monic(q);
        return q.multiply(Pc);
    }


    /**
     * GenPolynomial test if is squarefree.
     * @param P GenPolynomial.
     * @return true if P is squarefree, else false.
     */
    public boolean isRecursiveUnivariateSquarefree(GenPolynomial> P) {
        if (P == null || P.isZERO()) {
            return true;
        }
        GenPolynomialRing> pfac = P.ring;
        if (pfac.nvar > 1) {
            throw new IllegalArgumentException(this.getClass().getName()
                            + " only for multivariate polynomials");
        }
        // squarefree content
        GenPolynomial> pp = P;
        GenPolynomial Pc = engine.recursiveContent(P);
        if (logger.isInfoEnabled()) {
            logger.info("recursiveContent = " + Pc);
        }
        if (!isSquarefree(Pc)) {
            return false;
        }
        Pc = Pc.monic();
        if (!Pc.isONE()) {
            pp = PolyUtil. coefficientPseudoDivide(pp, Pc);
            //System.out.println("pp,sqp = " + pp);
        }
        if (pp.leadingExpVector().getVal(0) <= 1) {
            //System.out.println("pp = " + pp);
            //System.out.println("Pc = " + Pc);
            return true;
        }
        GenPolynomial> d = PolyUtil. recursiveDeriviative(pp);
        //System.out.println("d = " + d);
        GenPolynomial> g = engine.recursiveUnivariateGcd(pp, d);
        if (logger.isInfoEnabled()) {
            logger.info("gcd = " + g);
        }
        //System.out.println("g,rec = " + g);
        g = PolyUtil. monic(g);
        return g.isONE();
    }


    /**
     * GenPolynomial recursive univariate polynomial squarefree factorization.
     * @param P recursive univariate GenPolynomial.
     * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} p_i^{e_i}
     *         and p_i squarefree.
     */
    @Override
    public SortedMap>, Long> recursiveUnivariateSquarefreeFactors(
                    GenPolynomial> P) {
        SortedMap>, Long> sfactors = new TreeMap>, Long>();
        if (P == null || P.isZERO()) {
            return sfactors;
        }
        GenPolynomialRing> pfac = P.ring;
        if (pfac.nvar > 1) {
            // recursiveContent not possible by return type
            throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials");
        }
        // if base coefficient ring is a field, make monic
        GenPolynomialRing cfac = (GenPolynomialRing) pfac.coFac;
        C ldbcf = P.leadingBaseCoefficient().leadingBaseCoefficient();
        if (!ldbcf.isONE()) {
            GenPolynomial lc = cfac.getONE().multiply(ldbcf);
            GenPolynomial> pl = pfac.getONE().multiply(lc);
            sfactors.put(pl, 1L);
            C li = ldbcf.inverse();
            //System.out.println("li = " + li);
            P = P.multiply(cfac.getONE().multiply(li));
            //System.out.println("P,monic = " + P);
            ldbcf = P.leadingBaseCoefficient().leadingBaseCoefficient();
        }
        // factors of content
        GenPolynomial Pc = engine.recursiveContent(P);
        if (logger.isInfoEnabled()) {
            logger.info("recursiveContent = " + Pc);
        }
        Pc = Pc.monic();
        if (!Pc.isONE()) {
            P = PolyUtil. coefficientPseudoDivide(P, Pc);
        }
        SortedMap, Long> rsf = squarefreeFactors(Pc);
        if (logger.isInfoEnabled()) {
            logger.info("squarefreeFactors = " + rsf);
        }
        // add factors of content
        for (Map.Entry, Long> me : rsf.entrySet()) {
            GenPolynomial c = me.getKey();
            if (!c.isONE()) {
                GenPolynomial> cr = pfac.getONE().multiply(c);
                Long rk = me.getValue(); // rsf.get(c);
                sfactors.put(cr, rk);
            }
        }

        // factors of recursive polynomial
        GenPolynomial> T0 = P;
        GenPolynomial> Tp;
        GenPolynomial> T = null;
        GenPolynomial> V = null;
        long k = 0L;
        boolean init = true;
        while (true) {
            if (init) {
                if (T0.isConstant() || T0.isZERO()) {
                    break;
                }
                Tp = PolyUtil. recursiveDeriviative(T0);
                T = engine.recursiveUnivariateGcd(T0, Tp);
                T = PolyUtil. monic(T);
                V = PolyUtil. recursivePseudoDivide(T0, T);
                //System.out.println("iT0 = " + T0);
                //System.out.println("iTp = " + Tp);
                //System.out.println("iT = " + T);
                //System.out.println("iV = " + V);
                k = 0L;
                init = false;
            }
            if (V.isConstant()) {
                break;
            }
            k++;
            GenPolynomial> W = engine.recursiveUnivariateGcd(T, V);
            W = PolyUtil. monic(W);
            GenPolynomial> z = PolyUtil. recursivePseudoDivide(V, W);
            //System.out.println("W = " + W);
            //System.out.println("z = " + z);
            V = W;
            T = PolyUtil. recursivePseudoDivide(T, V);
            //System.out.println("V = " + V);
            //System.out.println("T = " + T);
            //was: if ( z.degree(0) > 0 ) {
            if (!z.isONE() && !z.isZERO()) {
                if (ldbcf.isONE()) {
                    z = PolyUtil. monic(z);
                    logger.info("z,monic = " + z);
                }
                sfactors.put(z, k);
            }
        }
        return sfactors;
    }


    /**
     * GenPolynomial greatest squarefree divisor.
     * @param P GenPolynomial.
     * @return squarefree(pp(P)).
     */
    @Override
    public GenPolynomial squarefreePart(GenPolynomial P) {
        if (P == null) {
            throw new IllegalArgumentException(this.getClass().getName() + " P != null");
        }
        if (P.isZERO()) {
            return P;
        }
        GenPolynomialRing pfac = P.ring;
        if (pfac.nvar <= 1) {
            return baseSquarefreePart(P);
        }
        GenPolynomialRing cfac = pfac.contract(1);
        GenPolynomialRing> rfac = new GenPolynomialRing>(cfac, 1);

        GenPolynomial> Pr = PolyUtil. recursive(rfac, P);
        GenPolynomial Pc = engine.recursiveContent(Pr);
        Pr = PolyUtil. coefficientPseudoDivide(Pr, Pc);
        GenPolynomial Ps = squarefreePart(Pc);
        if (logger.isInfoEnabled()) {
            logger.info("content = " + Pc + ", squarefreePart = " + Ps);
        }
        GenPolynomial> PP = recursiveUnivariateSquarefreePart(Pr);
        GenPolynomial> PS = PP.multiply(Ps);
        GenPolynomial D = PolyUtil. distribute(pfac, PS);
        if (logger.isInfoEnabled()) {
            logger.info("univRec = " + Pr + ", squarefreePart = " + PP);
        }
        return D;
    }


    /**
     * GenPolynomial test if is squarefree.
     * @param P GenPolynomial.
     * @return true if P is squarefree, else false.
     */
    @Override
    public boolean isSquarefree(GenPolynomial P) {
        if (P == null) {
            throw new IllegalArgumentException(this.getClass().getName() + " P != null");
        }
        if (P.isZERO()) {
            return true;
        }
        GenPolynomialRing pfac = P.ring;
        if (pfac.nvar <= 1) {
            return isBaseSquarefree(P);
        }
        GenPolynomialRing cfac = pfac.contract(1);
        GenPolynomialRing> rfac = new GenPolynomialRing>(cfac, 1);
        GenPolynomial> Pr = PolyUtil. recursive(rfac, P);
        return isRecursiveUnivariateSquarefree(Pr);
    }


    /**
     * GenPolynomial squarefree factorization.
     * @param P GenPolynomial.
     * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} p_i^{e_i}
     *         and p_i squarefree.
     */
    @Override
    public SortedMap, Long> squarefreeFactors(GenPolynomial P) {
        if (P == null) {
            throw new IllegalArgumentException(this.getClass().getName() + " P != null");
        }
        GenPolynomialRing pfac = P.ring;
        if (pfac.nvar <= 1) {
            return normalizeFactorization(baseSquarefreeFactors(P));
        }
        SortedMap, Long> sfactors = new TreeMap, Long>();
        if (P.isZERO()) {
            return normalizeFactorization(sfactors);
        }
        GenPolynomialRing cfac = pfac.contract(1);
        GenPolynomialRing> rfac = new GenPolynomialRing>(cfac, 1);

        GenPolynomial> Pr = PolyUtil. recursive(rfac, P);
        SortedMap>, Long> PP = recursiveUnivariateSquarefreeFactors(Pr);

        for (Map.Entry>, Long> m : PP.entrySet()) {
            Long i = m.getValue();
            GenPolynomial> Dr = m.getKey();
            GenPolynomial D = PolyUtil. distribute(pfac, Dr);
            sfactors.put(D, i);
        }
        if (logger.isInfoEnabled()) {
            logger.info("squarefreeFactors(" + P + ") = " + sfactors);
        }
        return normalizeFactorization(sfactors);
    }


    /**
     * Coefficients squarefree factorization.
     * @param P coefficient.
     * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} p_i^{e_i}
     *         and p_i squarefree.
     */
    @Override
    public SortedMap squarefreeFactors(C P) {
        throw new UnsupportedOperationException("method not implemented");
    }

}