/*
 * $Id$
 */

package edu.jas.ufd;


import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Map;

import org.apache.log4j.Logger;

import edu.jas.arith.BigInteger;
import edu.jas.poly.AlgebraicNumber;
import edu.jas.poly.AlgebraicNumberRing;
import edu.jas.poly.ExpVector;
import edu.jas.poly.GenPolynomial;
import edu.jas.poly.GenPolynomialRing;
import edu.jas.poly.PolyUtil;
import edu.jas.structure.GcdRingElem;
import edu.jas.structure.RingElem;
import edu.jas.structure.RingFactory;
import edu.jas.structure.UnaryFunctor;
import edu.jas.util.ListUtil;


/**
 * Polynomial ufd utilities, like conversion between different representations
 * and Hensel lifting.
 * @author Heinz Kredel
 */

public class PolyUfdUtil {


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


    private static boolean debug = logger.isDebugEnabled();


    /**
     * Integral polynomial from rational function coefficients. Represent as
     * polynomial with integral polynomial coefficients by multiplication with
     * the lcm of the numerators of the rational function coefficients.
     * @param fac result polynomial factory.
     * @param A polynomial with rational function coefficients to be converted.
     * @return polynomial with integral polynomial coefficients.
     */
    public static > GenPolynomial> integralFromQuotientCoefficients(
                    GenPolynomialRing> fac, GenPolynomial> A) {
        GenPolynomial> B = fac.getZERO().copy();
        if (A == null || A.isZERO()) {
            return B;
        }
        GenPolynomial c = null;
        GenPolynomial d;
        GenPolynomial x;
        GreatestCommonDivisor ufd = new GreatestCommonDivisorSubres();
        int s = 0;
        // lcm of denominators
        for (Quotient y : A.getMap().values()) {
            x = y.den;
            // c = lcm(c,x)
            if (c == null) {
                c = x;
                s = x.signum();
            } else {
                d = ufd.gcd(c, x);
                c = c.multiply(x.divide(d));
            }
        }
        if (s < 0) {
            c = c.negate();
        }
        for (Map.Entry> y : A.getMap().entrySet()) {
            ExpVector e = y.getKey();
            Quotient a = y.getValue();
            // p = n*(c/d)
            GenPolynomial b = c.divide(a.den);
            GenPolynomial p = a.num.multiply(b);
            //B = B.sum( p, e ); // inefficient
            B.doPutToMap(e, p);
        }
        return B;
    }


    /**
     * Integral polynomial from rational function coefficients. Represent as
     * polynomial with integral polynomial coefficients by multiplication with
     * the lcm of the numerators of the rational function coefficients.
     * @param fac result polynomial factory.
     * @param L list of polynomial with rational function coefficients to be
     *            converted.
     * @return list of polynomials with integral polynomial coefficients.
     */
    public static > List>> integralFromQuotientCoefficients(
                    GenPolynomialRing> fac, Collection>> L) {
        if (L == null) {
            return null;
        }
        List>> list = new ArrayList>>(L.size());
        for (GenPolynomial> p : L) {
            list.add(integralFromQuotientCoefficients(fac, p));
        }
        return list;
    }


    /**
     * Rational function from integral polynomial coefficients. Represent as
     * polynomial with type Quotient coefficients.
     * @param fac result polynomial factory.
     * @param A polynomial with integral polynomial coefficients to be
     *            converted.
     * @return polynomial with type Quotient coefficients.
     */
    public static > GenPolynomial> quotientFromIntegralCoefficients(
                    GenPolynomialRing> fac, GenPolynomial> A) {
        GenPolynomial> B = fac.getZERO().copy();
        if (A == null || A.isZERO()) {
            return B;
        }
        RingFactory> cfac = fac.coFac;
        QuotientRing qfac = (QuotientRing) cfac;
        for (Map.Entry> y : A.getMap().entrySet()) {
            ExpVector e = y.getKey();
            GenPolynomial a = y.getValue();
            Quotient p = new Quotient(qfac, a); // can not be zero
            if (!p.isZERO()) {
                //B = B.sum( p, e ); // inefficient
                B.doPutToMap(e, p);
            }
        }
        return B;
    }


    /**
     * Rational function from integral polynomial coefficients. Represent as
     * polynomial with type Quotient coefficients.
     * @param fac result polynomial factory.
     * @param L list of polynomials with integral polynomial coefficients to be
     *            converted.
     * @return list of polynomials with type Quotient coefficients.
     */
    public static > List>> quotientFromIntegralCoefficients(
                    GenPolynomialRing> fac, Collection>> L) {
        if (L == null) {
            return null;
        }
        List>> list = new ArrayList>>(L.size());
        for (GenPolynomial> p : L) {
            list.add(quotientFromIntegralCoefficients(fac, p));
        }
        return list;
    }


    /**
     * From BigInteger coefficients. Represent as polynomial with type
     * GenPolynomial<C> coefficients, e.g. ModInteger or BigRational.
     * @param fac result polynomial factory.
     * @param A polynomial with GenPolynomial<BigInteger> coefficients to
     *            be converted.
     * @return polynomial with type GenPolynomial<C> coefficients.
     */
    public static > GenPolynomial> fromIntegerCoefficients(
                    GenPolynomialRing> fac, GenPolynomial> A) {
        GenPolynomial> B = fac.getZERO().copy();
        if (A == null || A.isZERO()) {
            return B;
        }
        RingFactory> cfac = fac.coFac;
        GenPolynomialRing rfac = (GenPolynomialRing) cfac;
        for (Map.Entry> y : A.getMap().entrySet()) {
            ExpVector e = y.getKey();
            GenPolynomial a = y.getValue();
            GenPolynomial p = PolyUtil. fromIntegerCoefficients(rfac, a);
            if (!p.isZERO()) {
                //B = B.sum( p, e ); // inefficient
                B.doPutToMap(e, p);
            }
        }
        return B;
    }


    /**
     * From BigInteger coefficients. Represent as polynomial with type
     * GenPolynomial<C> coefficients, e.g. ModInteger or BigRational.
     * @param fac result polynomial factory.
     * @param L polynomial list with GenPolynomial<BigInteger>
     *            coefficients to be converted.
     * @return polynomial list with polynomials with type GenPolynomial<C>
     *         coefficients.
     */
    public static > List>> fromIntegerCoefficients(
                    GenPolynomialRing> fac, List>> L) {
        List>> K = null;
        if (L == null) {
            return K;
        }
        K = new ArrayList>>(L.size());
        if (L.size() == 0) {
            return K;
        }
        for (GenPolynomial> a : L) {
            GenPolynomial> b = fromIntegerCoefficients(fac, a);
            K.add(b);
        }
        return K;
    }


    /**
     * Introduce lower variable. Represent as polynomial with type
     * GenPolynomial<C> coefficients.
     * @param rfac result polynomial factory.
     * @param A polynomial to be extended.
     * @return polynomial with type GenPolynomial<C> coefficients.
     */
    public static > GenPolynomial> introduceLowerVariable(
                    GenPolynomialRing> rfac, GenPolynomial A) {
        if (A == null || rfac == null) {
            return null;
        }
        GenPolynomial> Pc = rfac.getONE().multiply(A);
        if (Pc.isZERO()) {
            return Pc;
        }
        Pc = PolyUtil. switchVariables(Pc);
        return Pc;
    }


    /**
     * From AlgebraicNumber coefficients. Represent as polynomial with type
     * GenPolynomial<C> coefficients, e.g. ModInteger or BigRational.
     * @param rfac result polynomial factory.
     * @param A polynomial with AlgebraicNumber coefficients to be converted.
     * @param k for (y-k x) substitution.
     * @return polynomial with type GenPolynomial<C> coefficients.
     */
    public static > GenPolynomial> substituteFromAlgebraicCoefficients(
                    GenPolynomialRing> rfac, GenPolynomial> A, long k) {
        if (A == null || rfac == null) {
            return null;
        }
        if (A.isZERO()) {
            return rfac.getZERO();
        }
        // setup x - k alpha
        GenPolynomialRing> apfac = A.ring;
        GenPolynomial> x = apfac.univariate(0);
        AlgebraicNumberRing afac = (AlgebraicNumberRing) A.ring.coFac;
        AlgebraicNumber alpha = afac.getGenerator();
        AlgebraicNumber ka = afac.fromInteger(k);
        GenPolynomial> s = x.subtract(ka.multiply(alpha)); // x - k alpha
        if (debug) {
            logger.info("x - k alpha: " + s);
        }
        // substitute, convert and switch
        GenPolynomial> B = PolyUtil.> substituteMain(A, s);
        GenPolynomial> Pc = PolyUtil. fromAlgebraicCoefficients(rfac, B); // Q[alpha][x]
        Pc = PolyUtil. switchVariables(Pc); // Q[x][alpha]
        return Pc;
    }


    /**
     * Convert to AlgebraicNumber coefficients. Represent as polynomial with
     * AlgebraicNumber coefficients, C is e.g. ModInteger or BigRational.
     * @param pfac result polynomial factory.
     * @param A polynomial with GenPolynomial<BigInteger> coefficients to
     *            be converted.
     * @param k for (y-k x) substitution.
     * @return polynomial with AlgebraicNumber<C> coefficients.
     */
    public static > GenPolynomial> substituteConvertToAlgebraicCoefficients(
                    GenPolynomialRing> pfac, GenPolynomial A, long k) {
        if (A == null || pfac == null) {
            return null;
        }
        if (A.isZERO()) {
            return pfac.getZERO();
        }
        // convert to Q(alpha)[x]
        GenPolynomial> B = PolyUtil. convertToAlgebraicCoefficients(pfac, A);
        // setup x .+. k alpha for back substitution
        GenPolynomial> x = pfac.univariate(0);
        AlgebraicNumberRing afac = (AlgebraicNumberRing) pfac.coFac;
        AlgebraicNumber alpha = afac.getGenerator();
        AlgebraicNumber ka = afac.fromInteger(k);
        GenPolynomial> s = x.sum(ka.multiply(alpha)); // x + k alpha
        // substitute
        GenPolynomial> N = PolyUtil.> substituteMain(B, s);
        return N;
    }


    /**
     * Norm of a polynomial with AlgebraicNumber coefficients.
     * @param A polynomial from GenPolynomial<AlgebraicNumber<C>>.
     * @param k for (y - k x) substitution.
     * @return norm(A) = res_x(A(x,y),m(x)) in GenPolynomialRing<C>.
     */
    public static > GenPolynomial norm(GenPolynomial> A, long k) {
        if (A == null) {
            return null;
        }
        GenPolynomialRing> pfac = A.ring; // Q(alpha)[x]
        if (pfac.nvar > 1) {
            throw new IllegalArgumentException("only for univariate polynomials");
        }
        AlgebraicNumberRing afac = (AlgebraicNumberRing) pfac.coFac;
        GenPolynomial agen = afac.modul;
        GenPolynomialRing cfac = afac.ring;
        if (A.isZERO()) {
            return cfac.getZERO();
        }
        AlgebraicNumber ldcf = A.leadingBaseCoefficient();
        if (!ldcf.isONE()) {
            A = A.monic();
        }
        GenPolynomialRing> rfac = new GenPolynomialRing>(cfac, pfac);

        // transform minimal polynomial to bi-variate polynomial
        GenPolynomial> Ac = PolyUfdUtil. introduceLowerVariable(rfac, agen);
        //System.out.println("Ac = " + Ac.toScript());

        // transform to bi-variate polynomial, 
        // switching varaible sequence from Q[alpha][x] to Q[X][alpha]
        GenPolynomial> Pc = PolyUfdUtil. substituteFromAlgebraicCoefficients(rfac, A, k);
        Pc = PolyUtil. monic(Pc);
        //System.out.println("Pc = " + Pc.toScript());

        GreatestCommonDivisorSubres engine = new GreatestCommonDivisorSubres( /*cfac.coFac*/);
        // = (GreatestCommonDivisorAbstract)GCDFactory.getImplementation( cfac.coFac );

        GenPolynomial> Rc = engine.recursiveUnivariateResultant(Pc, Ac);
        //System.out.println("Rc = " + Rc.toScript());
        GenPolynomial res = Rc.leadingBaseCoefficient();
        res = res.monic();
        return res;
    }


    /**
     * Norm of a polynomial with AlgebraicNumber coefficients.
     * @param A polynomial from GenPolynomial<AlgebraicNumber<C>>.
     * @return norm(A) = resultant_x( A(x,y), m(x) ) in K[y].
     */
    public static > GenPolynomial norm(GenPolynomial> A) {
        return norm(A, 0L);
    }


    /**
     * Ensure that the field property is determined. Checks if modul is
     * irreducible and modifies the algebraic number ring.
     * @param afac algebraic number ring.
     */
    public static > void ensureFieldProperty(AlgebraicNumberRing afac) {
        if (afac.getField() != -1) {
            return;
        }
        if (!afac.ring.coFac.isField()) {
            afac.setField(false);
            return;
        }
        Factorization mf = FactorFactory. getImplementation(afac.ring);
        if (mf.isIrreducible(afac.modul)) {
            afac.setField(true);
        } else {
            afac.setField(false);
        }
    }


    /**
     * Kronecker substitution. Substitute x_i by x**d**(i-1) to construct a
     * univariate polynomial.
     * @param A polynomial to be converted.
     * @return a univariate polynomial.
     */
    public static > GenPolynomial substituteKronecker(GenPolynomial A) {
        if (A == null) {
            return A;
        }
        long d = A.degree() + 1L;
        return substituteKronecker(A, d);
    }


    /**
     * Kronecker substitution. Substitute x_i by x**d**(i-1) to construct a
     * univariate polynomial.
     * @param A polynomial to be converted.
     * @return a univariate polynomial.
     */
    public static > GenPolynomial substituteKronecker(GenPolynomial A, long d) {
        if (A == null) {
            return A;
        }
        RingFactory cfac = A.ring.coFac;
        GenPolynomialRing ufac = new GenPolynomialRing(cfac, 1);
        GenPolynomial B = ufac.getZERO().copy();
        if (A.isZERO()) {
            return B;
        }
        for (Map.Entry y : A.getMap().entrySet()) {
            ExpVector e = y.getKey();
            C a = y.getValue();
            long f = 0L;
            long h = 1L;
            for (int i = 0; i < e.length(); i++) {
                long j = e.getVal(i) * h;
                f += j;
                h *= d;
            }
            ExpVector g = ExpVector.create(1, 0, f);
            B.doPutToMap(g, a);
        }
        return B;
    }


    /**
     * Kronecker substitution. Substitute x_i by x**d**(i-1) to construct a
     * univariate polynomials.
     * @param A list of polynomials to be converted.
     * @return a list of univariate polynomials.
     */
    public static > List> substituteKronecker(
                    List> A, int d) {
        if (A == null || A.get(0) == null) {
            return null;
        }
        return ListUtil., GenPolynomial> map(A, new SubstKronecker(d));
    }


    /**
     * Kronecker back substitution. Substitute x**d**(i-1) to x_i to construct a
     * multivariate polynomial.
     * @param A polynomial to be converted.
     * @param fac result polynomial factory.
     * @return a multivariate polynomial.
     */
    public static > GenPolynomial backSubstituteKronecker(
                    GenPolynomialRing fac, GenPolynomial A, long d) {
        if (A == null) {
            return A;
        }
        if (fac == null) {
            throw new IllegalArgumentException("null factory not allowed ");
        }
        int n = fac.nvar;
        GenPolynomial B = fac.getZERO().copy();
        if (A.isZERO()) {
            return B;
        }
        for (Map.Entry y : A.getMap().entrySet()) {
            ExpVector e = y.getKey();
            C a = y.getValue();
            long f = e.getVal(0);
            ExpVector g = ExpVector.create(n);
            for (int i = 0; i < n; i++) {
                long j = f % d;
                f /= d;
                g = g.subst(i, j);
            }
            B.doPutToMap(g, a);
        }
        return B;
    }


    /**
     * Kronecker back substitution. Substitute x**d**(i-1) to x_i to construct a
     * multivariate polynomials.
     * @param A list of polynomials to be converted.
     * @param fac result polynomial factory.
     * @return a list of multivariate polynomials.
     */
    public static > List> backSubstituteKronecker(
                    GenPolynomialRing fac, List> A, long d) {
        return ListUtil., GenPolynomial> map(A, new BackSubstKronecker(fac, d));
    }

}


/**
 * Kronecker substitutuion functor.
 */
class SubstKronecker> implements UnaryFunctor, GenPolynomial> {


    final long d;


    public SubstKronecker(long d) {
        this.d = d;
    }


    public GenPolynomial eval(GenPolynomial c) {
        if (c == null) {
            return null;
        }
        return PolyUfdUtil. substituteKronecker(c, d);
    }
}


/**
 * Kronecker back substitutuion functor.
 */
class BackSubstKronecker> implements
                UnaryFunctor, GenPolynomial> {


    final long d;


    final GenPolynomialRing fac;


    public BackSubstKronecker(GenPolynomialRing fac, long d) {
        this.d = d;
        this.fac = fac;
    }


    public GenPolynomial eval(GenPolynomial c) {
        if (c == null) {
            return null;
        }
        return PolyUfdUtil. backSubstituteKronecker(fac, c, d);
    }
}