/*
 * $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.AlgebraicNumber;
import edu.jas.poly.AlgebraicNumberRing;
import edu.jas.poly.GenPolynomial;
import edu.jas.poly.GenPolynomialRing;
import edu.jas.poly.PolyUtil;
import edu.jas.structure.GcdRingElem;
import edu.jas.structure.Power;
import edu.jas.structure.RingFactory;


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

public abstract class SquarefreeFieldCharP> extends SquarefreeAbstract {


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


    private final boolean debug = logger.isDebugEnabled();


    /*
     * Squarefree engine for characteristic p base coefficients.
     */
    //protected final SquarefreeAbstract rengine;


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


    /**
     * Factory for a algebraic extension of a finite field of characteristic p
     * coefficients. If coFac is an algebraic extension, then
     * aCoFac is equal to coFac, else
     * aCoFac is null.
     */
    protected final AlgebraicNumberRing aCoFac;


    /**
     * Factory for a transcendental extension of a finite field of
     * characteristic p coefficients. If coFac is an transcendental
     * extension, then qCoFac is equal to coFac, else
     * qCoFac is null.
     */
    protected final QuotientRing qCoFac;


    /**
     * Constructor.
     */
    @SuppressWarnings("unchecked")
    public SquarefreeFieldCharP(RingFactory fac) {
        super(GCDFactory. getProxy(fac));
        if (!fac.isField()) {
            //throw new IllegalArgumentException("fac must be a field");
            logger.warn("fac should be a field: " + fac.toScript());
        }
        if (fac.characteristic().signum() == 0) {
            throw new IllegalArgumentException("characterisic(fac) must be non-zero");
        }
        coFac = fac;
        Object oFac = coFac;
        if (oFac instanceof AlgebraicNumberRing) {
            aCoFac = (AlgebraicNumberRing) oFac; //  is not correct
            //rengine = (SquarefreeAbstract) SquarefreeFactory.getImplementation(aCoFac.ring);
            qCoFac = null;
        } else {
            aCoFac = null;
            if (oFac instanceof QuotientRing) {
                qCoFac = (QuotientRing) oFac; //  is not correct
                //rengine = (SquarefreeAbstract) SquarefreeFactory.getImplementation(qCoFac.ring);
            } else {
                qCoFac = null;
                //rengine = null; //(SquarefreeAbstract) SquarefreeFactory.getImplementation(oFac);
            }
        }
    }


    /**
     * 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");
        }
        // just for the moment:
        GenPolynomial s = pfac.getONE();
        SortedMap, Long> factors = baseSquarefreeFactors(P);
        logger.info("sqfPart,factors = " + factors);
        for (GenPolynomial sp : factors.keySet()) {
            s = s.multiply(sp);
        }
        return s.monic();
    }


    /**
     * 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;
        }
        GenPolynomialRing pfac = A.ring;
        if (A.isConstant()) {
            C coeff = A.leadingBaseCoefficient();
            //System.out.println("coeff = " + coeff + " @ " + coeff.factory());
            SortedMap rfactors = squarefreeFactors(coeff);
            //System.out.println("rfactors,const = " + rfactors);
            if (rfactors != null && rfactors.size() > 0) {
                for (Map.Entry me : rfactors.entrySet()) {
                    C c = me.getKey();
                    if (!c.isONE()) {
                        GenPolynomial cr = pfac.getONE().multiply(c);
                        Long rk = me.getValue(); // rfactors.get(c);
                        sfactors.put(cr, rk);
                    }
                }
            } else {
                sfactors.put(A, 1L);
            }
            return sfactors;
        }
        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);
            SortedMap rfactors = squarefreeFactors(ldbcf);
            //System.out.println("rfactors,ldbcf = " + rfactors);
            if (rfactors != null && rfactors.size() > 0) {
                for (Map.Entry me : rfactors.entrySet()) {
                    C c = me.getKey();
                    if (!c.isONE()) {
                        GenPolynomial cr = pfac.getONE().multiply(c);
                        Long rk = me.getValue(); //rfactors.get(c);
                        sfactors.put(cr, rk);
                    }
                }
            } else {
                GenPolynomial f1 = pfac.getONE().multiply(ldbcf);
                //System.out.println("gcda sqf f1 = " + f1);
                sfactors.put(f1, 1L);
            }
            ldbcf = pfac.coFac.getONE();
        }
        GenPolynomial T0 = A;
        long e = 1L;
        GenPolynomial Tp;
        GenPolynomial T = null;
        GenPolynomial V = null;
        long k = 0L;
        long mp = 0L;
        boolean init = true;
        while (true) {
            //System.out.println("T0 = " + T0);
            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);
                //System.out.println("const(iV)  = " + V.isConstant());
                k = 0L;
                mp = 0L;
                init = false;
            }
            if (V.isConstant()) {
                mp = pfac.characteristic().longValue(); // assert != 0
                //T0 = PolyUtil. baseModRoot(T,mp);
                T0 = baseRootCharacteristic(T);
                logger.info("char root: T0 = " + T0 + ", T = " + T);
                if (T0 == null) {
                    //break;
                    T0 = pfac.getZERO();
                }
                e = e * mp;
                init = true;
                continue;
            }
            k++;
            if (mp != 0L && k % mp == 0L) {
                T = PolyUtil. basePseudoDivide(T, V);
                System.out.println("k = " + k);
                //System.out.println("T = " + T);
                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, (e * k));
            }
        }
        //      look, a stupid error:
        //         if ( !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);
        //         }
        logger.info("exit char root: T0 = " + T0 + ", T = " + T);
        return 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");
        }
        // just for the moment:
        GenPolynomial> s = pfac.getONE();

        SortedMap>, Long> factors = recursiveUnivariateSquarefreeFactors(P);
        if (logger.isInfoEnabled()) {
            logger.info("sqfPart,factors = " + factors);
        }
        for (GenPolynomial> sp : factors.keySet()) {
            s = s.multiply(sp);
        }
        return PolyUtil. monic(s);
    }


    /**
     * 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();
            if (debug) {
                logger.debug("new ldbcf: " + ldbcf);
            }
        }
        // factors of content
        GenPolynomial Pc = engine.recursiveContent(P);
        if (logger.isInfoEnabled()) {
            logger.info("Pc = " + Pc);
        }
        Pc = Pc.monic();
        if (!Pc.isONE()) {
            P = PolyUtil. coefficientPseudoDivide(P, Pc);
        }
        SortedMap, Long> rsf = squarefreeFactors(Pc);
        if (logger.isInfoEnabled()) {
            logger.info("rsf = " + 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;
        long e = 1L;
        GenPolynomial> Tp;
        GenPolynomial> T = null;
        GenPolynomial> V = null;
        long k = 0L;
        long mp = 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;
                mp = 0L;
                init = false;
            }
            if (V.isConstant()) {
                mp = pfac.characteristic().longValue(); // assert != 0
                //T0 = PolyUtil. recursiveModRoot(T,mp);
                T0 = recursiveUnivariateRootCharacteristic(T);
                logger.info("char root: T0r = " + T0 + ", Tr = " + T);
                if (T0 == null) {
                    //break;
                    T0 = pfac.getZERO();
                }
                e = e * mp;
                init = true;
                //continue;
            }
            k++;
            if (mp != 0L && k % mp == 0L) {
                T = PolyUtil. recursivePseudoDivide(T, V);
                System.out.println("k = " + k);
                //System.out.println("T = " + T);
                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()) {
                z = PolyUtil. monic(z);
                logger.info("z,put = " + z);
                sfactors.put(z, (e * k));
            }
        }
        logger.info("exit char root: T0 = " + T0 + ", T = " + T);
        if (sfactors.size() == 0) {
            sfactors.put(pfac.getONE(), 1L);
        }
        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);
        }
        // just for the moment:
        GenPolynomial s = pfac.getONE();
        SortedMap, Long> factors = squarefreeFactors(P);
        if (logger.isInfoEnabled()) {
            logger.info("sqfPart,factors = " + factors);
        }
        for (GenPolynomial sp : factors.keySet()) {
            if (sp.isConstant()) {
                continue;
            }
            s = s.multiply(sp);
        }
        return s.monic();
    }


    /**
     * 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 baseSquarefreeFactors(P);
        }
        SortedMap, Long> sfactors = new TreeMap, Long>();
        if (P.isZERO()) {
            return 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);
        }
        return sfactors;
    }


    /**
     * Coefficient squarefree factorization.
     * @param coeff 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 coeff) {
        if (coeff == null) {
            return null;
        }
        SortedMap factors = new TreeMap();
        RingFactory cfac = (RingFactory) coeff.factory();
        if (aCoFac != null) {
            AlgebraicNumber an = (AlgebraicNumber) (Object) coeff;
            if (cfac.isFinite()) {
                SquarefreeFiniteFieldCharP reng = (SquarefreeFiniteFieldCharP) SquarefreeFactory
                                .getImplementation(cfac);
                SortedMap rfactors = reng.rootCharacteristic(coeff); // ??
                logger.info("rfactors,finite = " + rfactors);
                factors.putAll(rfactors);
                //return factors;
            } else {
                SquarefreeInfiniteAlgebraicFieldCharP reng = (SquarefreeInfiniteAlgebraicFieldCharP) SquarefreeFactory
                                .getImplementation(cfac);
                SortedMap, Long> rfactors = reng.squarefreeFactors(an);
                logger.info("rfactors,infinite,algeb = " + rfactors);
                for (Map.Entry, Long> me : rfactors.entrySet()) {
                    AlgebraicNumber c = me.getKey();
                    if (!c.isONE()) {
                        C cr = (C) (Object) c;
                        Long rk = me.getValue(); // rfactors.get(c);
                        factors.put(cr, rk);
                    }
                }
            }
        } else if (qCoFac != null) {
            Quotient q = (Quotient) (Object) coeff;
            SquarefreeInfiniteFieldCharP reng = (SquarefreeInfiniteFieldCharP) SquarefreeFactory
                            .getImplementation(cfac);
            SortedMap, Long> rfactors = reng.squarefreeFactors(q);
            logger.info("rfactors,infinite = " + rfactors);
            for (Map.Entry, Long> me : rfactors.entrySet()) {
                Quotient c = me.getKey();
                if (!c.isONE()) {
                    C cr = (C) (Object) c;
                    Long rk = me.getValue(); //rfactors.get(c);
                    factors.put(cr, rk);
                }
            }
        } else if (cfac.isFinite()) {
            SquarefreeFiniteFieldCharP reng = (SquarefreeFiniteFieldCharP) SquarefreeFactory
                            .getImplementation(cfac);
            SortedMap rfactors = reng.rootCharacteristic(coeff); // ??
            logger.info("rfactors,finite = " + rfactors);
            factors.putAll(rfactors);
            //return factors;
        } else {
            logger.warn("case " + cfac + " not implemented");
        }
        return factors;
    }


    /* --------- char-th roots --------------------- */


    /**
     * GenPolynomial char-th root univariate polynomial.
     * @param P GenPolynomial.
     * @return char-th_rootOf(P), or null if no char-th root.
     */
    public abstract GenPolynomial baseRootCharacteristic(GenPolynomial P);


    /**
     * GenPolynomial char-th root univariate polynomial with polynomial
     * coefficients.
     * @param P recursive univariate GenPolynomial.
     * @return char-th_rootOf(P), or null if P is no char-th root.
     */
    public abstract GenPolynomial> recursiveUnivariateRootCharacteristic(
                    GenPolynomial> P);


    /**
     * Polynomial is char-th root.
     * @param P polynomial.
     * @param F = [p_1 -> e_1, ..., p_k -> e_k].
     * @return true if P = prod_{i=1,...,k} p_i**(e_i*p), else false.
     */
    public boolean isCharRoot(GenPolynomial P, SortedMap, Long> F) {
        if (P == null || F == null) {
            throw new IllegalArgumentException("P and F may not be null");
        }
        if (P.isZERO() && F.size() == 0) {
            return true;
        }
        GenPolynomial t = P.ring.getONE();
        long p = P.ring.characteristic().longValue();
        for (Map.Entry, Long> me : F.entrySet()) {
            GenPolynomial f = me.getKey();
            Long E = me.getValue(); //F.get(f);
            long e = E.longValue();
            GenPolynomial g = Power.> positivePower(f, e);
            if (!f.isConstant()) {
                g = Power.> positivePower(g, p);
            }
            t = t.multiply(g);
        }
        boolean f = P.equals(t) || P.equals(t.negate());
        if (!f) {
            System.out.println("\nfactorization(map): " + f);
            System.out.println("P = " + P);
            System.out.println("t = " + t);
            P = P.monic();
            t = t.monic();
            f = P.equals(t) || P.equals(t.negate());
            if (f) {
                return f;
            }
            System.out.println("\nfactorization(map): " + f);
            System.out.println("P = " + P);
            System.out.println("t = " + t);
        }
        return f;
    }


    /**
     * Recursive polynomial is char-th root.
     * @param P recursive polynomial.
     * @param F = [p_1 -> e_1, ..., p_k -> e_k].
     * @return true if P = prod_{i=1,...,k} p_i**(e_i*p), else false.
     */
    public boolean isRecursiveCharRoot(GenPolynomial> P,
                    SortedMap>, Long> F) {
        if (P == null || F == null) {
            throw new IllegalArgumentException("P and F may not be null");
        }
        if (P.isZERO() && F.size() == 0) {
            return true;
        }
        GenPolynomial> t = P.ring.getONE();
        long p = P.ring.characteristic().longValue();
        for (Map.Entry>, Long> me : F.entrySet()) {
            GenPolynomial> f = me.getKey();
            Long E = me.getValue(); //F.get(f);
            long e = E.longValue();
            GenPolynomial> g = Power.>> positivePower(f, e);
            if (!f.isConstant()) {
                g = Power.>> positivePower(g, p);
            }
            t = t.multiply(g);
        }
        boolean f = P.equals(t) || P.equals(t.negate());
        if (!f) {
            System.out.println("\nfactorization(map): " + f);
            System.out.println("P = " + P);
            System.out.println("t = " + t);
            P = P.monic();
            t = t.monic();
            f = P.equals(t) || P.equals(t.negate());
            if (f) {
                return f;
            }
            System.out.println("\nfactorization(map): " + f);
            System.out.println("P = " + P);
            System.out.println("t = " + t);
        }
        return f;
    }


    /**
     * Recursive polynomial is char-th root.
     * @param P recursive polynomial.
     * @param r = recursive polynomial.
     * @return true if P = r**p, else false.
     */
    public boolean isRecursiveCharRoot(GenPolynomial> P, GenPolynomial> r) {
        if (P == null || r == null) {
            throw new IllegalArgumentException("P and r may not be null");
        }
        if (P.isZERO() && r.isZERO()) {
            return true;
        }
        long p = P.ring.characteristic().longValue();
        GenPolynomial> t = Power.>> positivePower(r, p);

        boolean f = P.equals(t) || P.equals(t.negate());
        if (!f) {
            System.out.println("\nisCharRoot: " + f);
            System.out.println("P = " + P);
            System.out.println("t = " + t);
            P = P.monic();
            t = t.monic();
            f = P.equals(t) || P.equals(t.negate());
            if (f) {
                return f;
            }
            System.out.println("\nisCharRoot: " + f);
            System.out.println("P = " + P);
            System.out.println("t = " + t);
        }
        return f;
    }

}