/*
 * $Id$
 */

package edu.jas.ufd;


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

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;


/**
 * Abstract squarefree decomposition class.
 * @author Heinz Kredel
 */

public abstract class SquarefreeAbstract> implements Squarefree {


    /**
     * GCD engine for respective base coefficients.
     */
    protected final GreatestCommonDivisorAbstract engine;


    /**
     * Constructor.
     */
    public SquarefreeAbstract(GreatestCommonDivisorAbstract engine) {
        this.engine = engine;
    }


    /**
     * GenPolynomial polynomial greatest squarefree divisor.
     * @param P GenPolynomial.
     * @return squarefree(pp(P)).
     */
    public abstract GenPolynomial baseSquarefreePart(GenPolynomial P);


    /**
     * 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.
     */
    public abstract SortedMap, Long> baseSquarefreeFactors(GenPolynomial A);


    /**
     * GenPolynomial recursive polynomial greatest squarefree divisor.
     * @param P recursive univariate GenPolynomial.
     * @return squarefree(pp(P)).
     */
    public abstract GenPolynomial> recursiveUnivariateSquarefreePart(
                    GenPolynomial> P);


    /**
     * 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.
     */
    public abstract SortedMap>, Long> recursiveUnivariateSquarefreeFactors(
                    GenPolynomial> P);


    /**
     * GenPolynomial greatest squarefree divisor.
     * @param P GenPolynomial.
     * @return squarefree(P) a primitive respectively monic polynomial.
     */
    public abstract GenPolynomial squarefreePart(GenPolynomial P);


    /**
     * GenPolynomial test if is squarefree.
     * @param P GenPolynomial.
     * @return true if P is squarefree, else false.
     */
    public boolean isSquarefree(GenPolynomial P) {
        GenPolynomial S = squarefreePart(P);
        GenPolynomial Ps = P;
        if (P.ring.coFac.isField()) {
            Ps = Ps.monic();
        } else {
            Ps = engine.basePrimitivePart(Ps);
        }
        boolean f = Ps.equals(S);
        //if (!f) {
            //System.out.println("\nisSquarefree: " + f);
            //System.out.println("S  = " + S);
            //System.out.println("P  = " + P);
        //}
        return f;
    }


    /**
     * GenPolynomial list test if squarefree.
     * @param L list of GenPolynomial.
     * @return true if each P in L is squarefree, else false.
     */
    public boolean isSquarefree(List> L) {
        if (L == null || L.isEmpty()) {
            return true;
        }
        for (GenPolynomial P : L) {
            if (!isSquarefree(P)) {
                return false;
            }
        }
        return true;
    }


    /**
     * Recursive GenPolynomial test if is squarefree.
     * @param P recursive univariate GenPolynomial.
     * @return true if P is squarefree, else false.
     */
    public boolean isRecursiveSquarefree(GenPolynomial> P) {
        GenPolynomial> S = recursiveUnivariateSquarefreePart(P);
        boolean f = P.equals(S);
        if (!f) {
            System.out.println("\nisSquarefree: " + f);
            System.out.println("S = " + S);
            System.out.println("P = " + P);
        }
        return f;
    }


    /**
     * 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.
     */
    public abstract SortedMap, Long> squarefreeFactors(GenPolynomial P);


    /**
     * GenPolynomial squarefree and co-prime list.
     * @param A list of GenPolynomials.
     * @return B with gcd(b,c) = 1 for all b != c in B and for all non-constant
     *         a in A there exists b in B with b|a and each b in B is
     *         squarefree. B does not contain zero or constant polynomials.
     */
    public List> coPrimeSquarefree(List> A) {
        if (A == null || A.isEmpty()) {
            return A;
        }
        List> S = new ArrayList>();
        for (GenPolynomial g : A) {
            SortedMap, Long> sm = squarefreeFactors(g);
            S.addAll(sm.keySet());
        }
        List> B = engine.coPrime(S);
        return B;
    }


    /**
     * GenPolynomial squarefree and co-prime list.
     * @param a polynomial.
     * @param P squarefree co-prime list of GenPolynomials.
     * @return B with gcd(b,c) = 1 for all b != c in B and for non-constant a
     *         there exists b in P with b|a. B does not contain zero or constant
     *         polynomials.
     */
    public List> coPrimeSquarefree(GenPolynomial a, List> P) {
        if (a == null || a.isZERO() || a.isConstant()) {
            return P;
        }
        SortedMap, Long> sm = squarefreeFactors(a);
        List> B = P;
        for (GenPolynomial f : sm.keySet()) {
            B = engine.coPrime(f, B);
        }
        return B;
    }


    /**
     * Test if list of GenPolynomials is squarefree and co-prime.
     * @param B list of GenPolynomials.
     * @return true, if for all b != c in B gcd(b,c) = 1 and each b in B is
     *         squarefree, else false.
     */
    public boolean isCoPrimeSquarefree(List> B) {
        if (B == null || B.isEmpty()) {
            return true;
        }
        if (!engine.isCoPrime(B)) {
            return false;
        }
        return isSquarefree(B);
    }


    /**
     * Normalize factorization. p'_i > 0 for i > 1 and p'_1 != 1 if k >
     * 1.
     * @param F = [p_1->e_1;, ..., p_k->e_k].
     * @return F' = [p'_1->e_1, ..., p'_k->e_k].
     */
    public SortedMap, Long> normalizeFactorization(SortedMap, Long> F) {
        if (F == null || F.size() <= 1) {
            return F;
        }
        List> Fp = new ArrayList>(F.keySet());
        GenPolynomial f0 = Fp.get(0);
        if (f0.ring.characteristic().signum() != 0) { // only ordered coefficients
            return F;
        }
        long e0 = F.get(f0);
        SortedMap, Long> Sp = new TreeMap, Long>();
        for (int i = 1; i < Fp.size(); i++) {
            GenPolynomial fi = Fp.get(i);
            long ei = F.get(fi);
            if (fi.signum() < 0) {
                //System.out.println("e0 = " + e0 + ", f0 = " + f0);
                //System.out.println("ei = " + ei + ", fi = " + fi);
                fi = fi.negate();
                if (ei % 2 != 0) { // && e0 % 2 != 0
                    f0 = f0.negate();
                }
            }
            Sp.put(fi, ei);
        }
        if (!f0.isONE()) {
            Sp.put(f0, e0);
        }
        return Sp;
    }


    /**
     * GenPolynomial is (squarefree) factorization.
     * @param P GenPolynomial.
     * @param F = [p_1,...,p_k].
     * @return true if P = prod_{i=1,...,r} p_i, else false.
     */
    public boolean isFactorization(GenPolynomial P, List> F) {
        if (P == null || F == null) {
            throw new IllegalArgumentException("P and F may not be null");
        }
        GenPolynomial t = P.ring.getONE();
        for (GenPolynomial f : F) {
            t = t.multiply(f);
        }
        boolean f = P.equals(t) || P.equals(t.negate());
        if (!f) {
            System.out.println("\nfactorization(list): " + f);
            System.out.println("F = " + F);
            System.out.println("P = " + P);
            System.out.println("t = " + t);
        }
        return f;
    }


    /**
     * Count number of factors in a (squarefree) factorization.
     * @param F = [p_1 -> e_1, ..., p_k -> e_k].
     * @return sum_{i=1,...,k} e_i.
     */
    public long factorCount(SortedMap, Long> F) {
        if (F == null || F.isEmpty()) {
            return 0L;
        }
        long f = 0L;
        for (Long e : F.values()) {
            f += e;
        }
        return f;
    }


    /**
     * GenPolynomial is (squarefree) factorization.
     * @param P GenPolynomial.
     * @param F = [p_1 -> e_1, ..., p_k -> e_k].
     * @return true if P = prod_{i=1,...,k} p_i**e_i, else false.
     */
    public boolean isFactorization(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();
        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);
            t = t.multiply(g);
        }
        boolean f = P.equals(t) || P.equals(t.negate());
        if (!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("F = " + F);
            System.out.println("P = " + P);
            System.out.println("t = " + t);
            //RuntimeException e = new RuntimeException("fac-map");
            //e.printStackTrace();
            //throw e;
        }
        return f;
    }


    /**
     * GenPolynomial is (squarefree) factorization.
     * @param P GenPolynomial.
     * @param F = [p_1 -> e_1, ..., p_k -> e_k].
     * @return true if P = prod_{i=1,...,k} p_i**e_i, else false.
     */
    public boolean isRecursiveFactorization(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();
        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);
            t = t.multiply(g);
        }
        boolean f = P.equals(t) || P.equals(t.negate());
        if (!f) {
            //System.out.println("P = " + P);
            //System.out.println("t = " + t);
            GenPolynomialRing cf = (GenPolynomialRing) P.ring.coFac;
            GreatestCommonDivisorAbstract engine = GCDFactory.getProxy(cf.coFac);
            GenPolynomial> Pp = engine.recursivePrimitivePart(P);
            Pp = PolyUtil. monic(Pp);
            GenPolynomial> tp = engine.recursivePrimitivePart(t);
            tp = PolyUtil. monic(tp);
            f = Pp.equals(tp) || Pp.equals(tp.negate());
            if (f) {
                return f;
            }
            System.out.println("\nfactorization(map): " + f);
            System.out.println("F  = " + F);
            System.out.println("P  = " + P);
            System.out.println("t  = " + t);
            System.out.println("Pp = " + Pp);
            System.out.println("tp = " + tp);
            //RuntimeException e = new RuntimeException("fac-map");
            //e.printStackTrace();
            //throw e;
        }
        return f;
    }


    /**
     * GenPolynomial recursive polynomial greatest squarefree divisor.
     * @param P recursive GenPolynomial.
     * @return squarefree(pp(P)).
     */
    public GenPolynomial> recursiveSquarefreePart(GenPolynomial> P) {
        if (P == null || P.isZERO()) {
            return P;
        }
        if (P.ring.nvar <= 1) {
            return recursiveUnivariateSquarefreePart(P);
        }
        // distributed polynomials squarefree part
        GenPolynomialRing> rfac = P.ring;
        RingFactory> rrfac = rfac.coFac;
        GenPolynomialRing cfac = (GenPolynomialRing) rrfac;
        GenPolynomialRing dfac = cfac.extend(rfac.nvar);
        GenPolynomial Pd = PolyUtil. distribute(dfac, P);
        GenPolynomial Dd = squarefreePart(Pd);
        // convert to recursive
        GenPolynomial> C = PolyUtil. recursive(rfac, Dd);
        return C;
    }


    /**
     * GenPolynomial recursive polynomial squarefree factorization.
     * @param P recursive GenPolynomial.
     * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k}
     *         p_i^{e_i} and p_i squarefree.
     */
    public SortedMap>, Long> recursiveSquarefreeFactors(
                    GenPolynomial> P) {
        SortedMap>, Long> factors;
        factors = new TreeMap>, Long>();
        if (P == null || P.isZERO()) {
            return factors;
        }
        if (P.ring.nvar <= 1) {
            return recursiveUnivariateSquarefreeFactors(P);
        }
        // distributed polynomials squarefree part
        GenPolynomialRing> rfac = P.ring;
        RingFactory> rrfac = rfac.coFac;
        GenPolynomialRing cfac = (GenPolynomialRing) rrfac;
        GenPolynomialRing dfac = cfac.extend(rfac.nvar);
        GenPolynomial Pd = PolyUtil. distribute(dfac, P);
        SortedMap, Long> dfacs = squarefreeFactors(Pd);
        // convert to recursive
        for (Map.Entry, Long> Dm : dfacs.entrySet()) {
            GenPolynomial Dd = Dm.getKey();
            Long e = Dm.getValue();
            GenPolynomial> C = PolyUtil. recursive(rfac, Dd);
            factors.put(C, e);
        }
        return factors;
    }


    /**
     * Univariate GenPolynomial partial fraction decomposition.
     * @param A univariate GenPolynomial.
     * @param D sorted map [d_1 -> e_1, ..., d_k -> e_k] with d_i
     *            squarefree.
     * @return [ [Ai0, Ai1,..., Aie_i], i=0,...,k ] with A/prod(D) = A0 + sum(
     *         sum ( Aij/di^j ) ) with deg(Aij) < deg(di).
     */
    public List>> basePartialFraction(GenPolynomial A,
                    SortedMap, Long> D) {
        if (D == null || A == null) {
            throw new IllegalArgumentException("null A or D not allowed");
        }
        List>> pf = new ArrayList>>(D.size() + 1);
        if (D.size() == 0) {
            return pf;
        }
        //List> fi;
        if (A.isZERO()) {
            for (Map.Entry, Long> me : D.entrySet()) {
                //GenPolynomial d = me.getKey();
                long e = me.getValue(); //D.get(d);
                int e1 = (int) e + 1;
                List> fi = new ArrayList>(e1);
                for (int i = 0; i < e1; i++) {
                    fi.add(A);
                }
                pf.add(fi);
            }
            List> fi = new ArrayList>(1);
            fi.add(A);
            pf.add(0, fi);
            return pf;
        }
        // A != 0, D != empty
        List> Dp = new ArrayList>(D.size());
        for (Map.Entry, Long> me : D.entrySet()) {
            GenPolynomial d = me.getKey();
            long e = me.getValue(); //D.get(d);
            GenPolynomial f = Power.> positivePower(d, e);
            Dp.add(f);
        }
        List> F = engine.basePartialFraction(A, Dp);
        //System.out.println("fraction list = " + F.size());
        GenPolynomial A0 = F.remove(0);
        List> fi = new ArrayList>(1);
        fi.add(A0);
        pf.add(fi);
        int i = 0;
        for (Map.Entry, Long> me : D.entrySet()) { // assume fixed sequence order
            GenPolynomial d = me.getKey();
            long e = me.getValue(); // D.get(d);
            int ei = (int) e;
            GenPolynomial gi = F.get(i); // assume fixed sequence order
            List> Fi = engine.basePartialFraction(gi, d, ei);
            pf.add(Fi);
            i++;
        }
        return pf;
    }


    /**
     * Test for Univariate GenPolynomial partial fraction decomposition.
     * @param A univariate GenPolynomial.
     * @param D sorted map [d_1 -> e_1, ..., d_k -> e_k] with d_i
     *            squarefree.
     * @param F a list of lists [ [Ai0, Ai1,..., Aie_i], i=0,...,k ]
     * @return true, if A/prod(D) = A0 + sum( sum ( Aij/di^j ) ), else false.
     */
    public boolean isBasePartialFraction(GenPolynomial A, SortedMap, Long> D,
                    List>> F) {
        if (D == null || A == null || F == null) {
            throw new IllegalArgumentException("null A, D or F not allowed");
        }
        if (D.isEmpty() && F.isEmpty()) {
            return true;
        }
        if (D.isEmpty() || F.isEmpty()) {
            return false;
        }
        List> Dp = new ArrayList>(D.size());
        for (Map.Entry, Long> me : D.entrySet()) {
            GenPolynomial d = me.getKey();
            long e = me.getValue(); // D.get(d);
            GenPolynomial f = Power.> positivePower(d, e);
            Dp.add(f);
        }
        List> fi = F.get(0);
        if (fi.size() != 1) {
            System.out.println("size(fi) != 1 " + fi);
            return false;
        }
        boolean t;
        GenPolynomial A0 = fi.get(0);
        //System.out.println("A0 = " + A0);
        List> Qp = new ArrayList>(D.size() + 1);
        Qp.add(A0);

        //         List> Fp = engine.basePartialFraction(A,Dp);
        //         System.out.println("fraction list = " + F.size());
        //         t = engine.isBasePartialFraction(A,Dp,Fp);
        //         if ( ! t ) {
        //             System.out.println("not recursion isPartFrac = " + Fp);
        //             return false;
        //         }
        //         GenPolynomial A0p = Fp.remove(0);
        //         if ( ! A0.equals(A0p) ) {
        //             System.out.println("A0 != A0p " + A0p);
        //             return false;
        //         }

        int i = 0;
        for (Map.Entry, Long> me : D.entrySet()) { // assume fixed sequence order
            GenPolynomial d = me.getKey();
            long e = me.getValue(); // D.get(d);
            int ei = (int) e;
            List> Fi = F.get(i + 1); // assume fixed sequence order

            //            GenPolynomial pi = Fp.get(i);        // assume fixed sequence order
            //             t = engine.isBasePartialFraction(pi,d,ei,Fi);
            //             if ( ! t ) {
            //                 System.out.println("not isPartFrac exp = " + pi + ", d = " + d + ", e = " + ei);
            //                 System.out.println("not isPartFrac exp = " + Fi);
            //                 return false;
            //             }

            GenPolynomial qi = engine.basePartialFractionValue(d, ei, Fi);
            Qp.add(qi);

            //             t = qi.equals(pi);
            //             if ( ! t ) {
            //                 System.out.println("not isPartFrac exp = " + pi + ", d = " + d + ", e = " + ei + ", qi = " + qi);
            //             }

            i++;
        }

        t = engine.isBasePartialFraction(A, Dp, Qp);
        if (!t) {
            System.out.println("not final isPartFrac " + Qp);
        }
        return t;
    }


    /**
     * Coefficients greatest squarefree divisor.
     * @param P coefficient.
     * @return squarefree part of P.
     */
    public C squarefreePart(C P) {
        if (P == null) {
            return null;
        }
        // just for the moment: TODO
        C s = null;
        SortedMap factors = squarefreeFactors(P);
        //logger.info("sqfPart,factors = " + factors);
        System.out.println("sqfPart,factors = " + factors);
        for (C sp : factors.keySet()) {
            if (s == null) {
                s = sp;
            } else {
                s = s.multiply(sp);
            }
        }
        return s;
    }


    /**
     * 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.
     */
    public abstract SortedMap squarefreeFactors(C P);
    /* not possible:
    {
        if (P == null) {
            return null;
        }
        SortedMap factors = new TreeMap();
        SquarefreeAbstract reng = SquarefreeFactory.getImplementation((RingFactory) P.factory());
            System.out.println("fcp,reng = " + reng);
            SortedMap rfactors = reng.squarefreeFactors(P);
            for (C c : rfactors.keySet()) {
                if (!c.isONE()) {
                    C cr = (C) (Object) c;
                    Long rk = rfactors.get(c);
                    factors.put(cr, rk);
                }
            }

        return factors;
    }
    */

}