/*
 * $Id$
 */

package edu.jas.application;


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import org.apache.log4j.Logger;

import edu.jas.gb.GroebnerBase;
import edu.jas.gbufd.GBFactory;
import edu.jas.poly.ExpVector;
import edu.jas.poly.GenPolynomial;
import edu.jas.poly.GenPolynomialRing;
import edu.jas.structure.GcdRingElem;
import edu.jas.structure.RingFactory;
import edu.jas.ufd.SquarefreeAbstract;
import edu.jas.ufd.SquarefreeFactory;


/**
 * Comprehensive Groebner Base sequential algorithm. Implements faithful
 * comprehensive Groebner bases via Groebner systems and CGB test.
 * @param  coefficient type
 * @author Heinz Kredel
 */

public class ComprehensiveGroebnerBaseSeq>
/* extends GroebnerBaseAbstract> */{


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


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


    /**
     * Squarefree for coefficient content and primitive parts.
     */
    protected final SquarefreeAbstract engine;


    /*
     * Flag if gcd engine should be used.
     */
    //private final boolean notFaithfull = false;


    /**
     * Comprehensive reduction engine.
     */
    protected final CReductionSeq cred;


    /**
     * Polynomial coefficient ring factory.
     */
    protected final RingFactory cofac;


    /**
     * Constructor.
     * @param rf base coefficient ring factory.
     */
    public ComprehensiveGroebnerBaseSeq(RingFactory rf) {
        this(new CReductionSeq(rf), rf);
    }


    /**
     * Constructor.
     * @param red C-pseudo-Reduction engine
     * @param rf base coefficient ring factory.
     */
    @SuppressWarnings("unchecked")
    public ComprehensiveGroebnerBaseSeq(CReductionSeq red, RingFactory rf) {
        // super(null); // red not possible since type of type
        cred = red;
        cofac = rf;
        // selection for C but used for R:
        //engine e = GCDFactory. getImplementation(cofac);
        engine = SquarefreeFactory. getImplementation(rf);
    }


    /**
     * Comprehensive-Groebner base test.
     * @param F polynomial list.
     * @return true, if F is a Comprehensive-Groebner base, else false.
     */
    // @Override
    public boolean isGB(List>> F) {
        return isGB(0, F);
    }


    /**
     * Comprehensive-Groebner base test.
     * @param modv module variable number.
     * @param F polynomial list.
     * @return true, if F is a Comprehensive-Groebner base, else false.
     */
    // @Override
    public boolean isGB(int modv, List>> F) {
        // return isGBcol( modv, F );
        return isGBsubst(modv, F);
    }


    /**
     * Comprehensive-Groebner base test using colored systems.
     * @param F polynomial list.
     * @return true, if F is a Comprehensive-Groebner base, else false.
     */
    // @Override
    public boolean isGBcol(List>> F) {
        return isGBcol(0, F);
    }


    /**
     * Comprehensive-Groebner base test using colored systems.
     * @param modv module variable number.
     * @param F polynomial list.
     * @return true, if F is a Comprehensive-Groebner base, else false.
     */
    // @Override
    public boolean isGBcol(int modv, List>> F) {
        if (F == null || F.size() == 0) {
            return true;
        }
        List> CS = cred.determine(F);
        return isGBsys(modv, CS);
    }


    /**
     * Comprehensive-Groebner system test.
     * @param CS list of colored systems.
     * @return true, if CS is a Comprehensive-Groebner system, else false.
     */
    // @Override
    public boolean isGBsys(List> CS) {
        return isGBsys(0, CS);
    }


    /**
     * Comprehensive-Groebner system test.
     * @param modv module variable number.
     * @param CS list of colored systems.
     * @return true, if CS is a Comprehensive-Groebner system, else false.
     */
    // @Override
    public boolean isGBsys(int modv, List> CS) {
        if (CS == null || CS.size() == 0) {
            return true;
        }
        ColorPolynomial p, q, h, hp;
        for (ColoredSystem cs : CS) {
            if (debug) {
                if (!cs.isDetermined()) {
                    System.out.println("not determined, cs = " + cs);
                    return false;
                }
                if (!cs.checkInvariant()) {
                    System.out.println("not invariant, cs = " + cs);
                    return false;
                }
            }
            Condition cond = cs.condition;
            List> S = cs.list;
            int k = S.size();
            for (int j = 0; j < k; j++) {
                p = S.get(j);
                for (int l = j + 1; l < k; l++) {
                    q = S.get(l);
                    h = cred.SPolynomial(p, q);
                    // System.out.println("spol(a,b) = " + h);
                    h = cred.normalform(cond, S, h);
                    // System.out.println("NF(spol(a,b)) = " + h);
                    if (debug) {
                        if (!cred.isNormalform(S, h)) {
                            System.out.println("not normalform, h = " + h);
                            System.out.println("cs = " + cs);
                            return false;
                        }
                    }
                    if (!h.isZERO()) {
                        hp = cond.reDetermine(h);
                        if (!hp.isZERO()) {
                            System.out.println("p = " + p);
                            System.out.println("q = " + q);
                            System.out.println("not zero:   NF(spol(p,q))  = " + h);
                            System.out.println("redetermine(NF(spol(p,q))) = " + hp);
                            System.out.println("cs = " + cs);
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }


    /**
     * Comprehensive-Groebner base test using substitution.
     * @param F polynomial list.
     * @return true, if F is a Comprehensive-Groebner base, else false.
     */
    // @Override
    public boolean isGBsubst(List>> F) {
        return isGBsubst(0, F);
    }


    /**
     * Comprehensive-Groebner base test using substitution.
     * @param modv module variable number.
     * @param F polynomial list.
     * @return true, if F is a Comprehensive-Groebner base, else false.
     */
    // @Override
    public boolean isGBsubst(int modv, List>> F) {
        if (F == null || F.size() == 0) {
            return true;
        }
        GenPolynomial> f = F.get(0); // assert non Zero
        GenPolynomialRing> cf = f.ring;

        List> CS = cred.determine(F);
        if (logger.isDebugEnabled()) {
            logger.info("determined polynomials =\n" + CS);
        }
        // substitute zero conditions into parameter coefficients and test
        for (ColoredSystem cs : CS) {
            Ideal id = cs.condition.zero;
            ResidueRing r = new ResidueRing(id);
            GenPolynomialRing> rf = new GenPolynomialRing>(r, cf);
            List>> list = PolyUtilApp. toResidue(rf, F);
            //GroebnerBase> bb = new GroebnerBasePseudoSeq>(r);
            GroebnerBase> bb = GBFactory.getImplementation(r);
            boolean t = bb.isGB(list);
            if (!t) {
                System.out.println("test condition = " + cs.condition);
                System.out.println("no GB for residue coefficients = " + list);
                return false;
            }
        }

        // substitute random ideal into parameter coefficients and test
        GenPolynomialRing ccf = (GenPolynomialRing) cf.coFac;
        int nv = ccf.nvar - 2;
        if (nv < 1) {
            nv = 1;
        }
        List> il = new ArrayList>();
        int i = 0;
        int j = 1;
        while (i < nv) {
            j++;
            GenPolynomial p = ccf.random(j + 1);
            // System.out.println("p = " + p);
            if (p.isConstant()) {
                continue;
            }
            if (p.isZERO()) {
                continue;
            }
            p = engine.squarefreePart(p);
            il.add(p);
            i++;
        }
        logger.info("random ideal = " + il);
        Ideal id = new Ideal(ccf, il);
        ResidueRing r = new ResidueRing(id);
        GenPolynomialRing> rf = new GenPolynomialRing>(r, cf);
        List>> list = PolyUtilApp. toResidue(rf, F);
        logger.info("random residue = " + r.ideal.getList());
        //GroebnerBase> bb = new GroebnerBasePseudoSeq>(r);
        GroebnerBase> bb = GBFactory.getImplementation(r);
        boolean t = bb.isGB(list);
        if (!t) {
            System.out.println("no GB for residue coefficients = " + list);
            return false;
        }
        return true;
    }


    /**
     * Comprehensive-Groebner system test.
     * @param F Groebner system.
     * @return true, if F is a Comprehensive-Groebner system, else false.
     */
    // @Override
    public boolean isGBsys(GroebnerSystem F) {
        return isGBsys(0, F.list);
    }


    /**
     * Comprehensive-Groebner base test.
     * @param F Groebner system.
     * @return true, if F is a Comprehensive-Groebner base, else false.
     */
    // @Override
    public boolean isCGB(GroebnerSystem F) {
        return isGB(F.getCGB());
    }


    /**
     * Comprehensive-Groebner system and base test.
     * @param F Groebner system.
     * @return true, if F is a Comprehensive-Groebner system and base, else
     *         false.
     */
    // @Override
    public boolean isGB(GroebnerSystem F) {
        return isGBsys(0, F.list) && isGB(F.getCGB());
    }


    /**
     * Comprehensive Groebner base system using pairlist class.
     * @param F polynomial list.
     * @return GBsys(F) a Comprehensive Groebner system of F.
     */
    // @Override
    // @SuppressWarnings("unchecked")
    public GroebnerSystem GBsys(List>> F) {
        if (F == null) {
            return null;
        }
        List> CSp = new ArrayList>();
        if (F.size() == 0) {
            return new GroebnerSystem(CSp);
        }
        // extract coefficient factory
        GenPolynomial> f = F.get(0);
        GenPolynomialRing> fac = f.ring;
        // determine polynomials
        List> CS = cred.determine(F);
        // System.out.println("CS = " + CS);
        // CS.remove(0); // empty colored system
        if (logger.isInfoEnabled()) {
            logger.info("determined polynomials =\n" + CS);
        }

        // setup pair lists
        List> CSs = new ArrayList>();
        ColoredSystem css;
        for (ColoredSystem cs : CS) {
            OrderedCPairlist pairlist = new OrderedCPairlist(fac);
            for (ColorPolynomial p : cs.list) {
                // System.out.println("p = " + p);
                pairlist.put(p);
            }
            css = new ColoredSystem(cs.condition, cs.list, pairlist);
            CSs.add(css);
        }

        // main loop
        List> CSb = new ArrayList>();
        List> ncs;
        List> CSh; //, CSbh;
        ColoredSystem cs;
        List> G;
        OrderedCPairlist pairlist;
        Condition cond;
        int si = 0;
        while (CSs.size() > 0) {
            cs = CSs.get(0); // remove(0);
            si++;
            logger.info("poped GBsys number    " + si + " with condition = " + cs.condition);
            logger.info("poped GBsys (remaining " + (CSs.size() - 1) + ") with pairlist  = " + cs.pairlist);
            if (!cs.isDetermined()) {
                cs = cs.reDetermine();
            }
            pairlist = cs.pairlist;
            G = cs.list;
            cond = cs.condition;
            // logger.info( pairlist.toString() );

            CPair pair;
            ColorPolynomial pi;
            ColorPolynomial pj;
            ColorPolynomial S;
            // GenPolynomial> H;
            ColorPolynomial H;
            while (pairlist.hasNext()) {
                pair = pairlist.removeNext();
                if (pair == null)
                    continue;

                pi = pair.pi;
                pj = pair.pj;
                if (debug) {
                    logger.info("pi    = " + pi);
                    logger.info("pj    = " + pj);
                }

                S = cred.SPolynomial(pi, pj);
                if (S.isZERO()) {
                    pair.setZero();
                    continue;
                }
                if (debug) {
                    // logger.info("ht(S) = " + S.leadingExpVector() );
                    logger.info("S = " + S);
                }

                H = cred.normalform(cond, G, S);
                if (H.isZERO()) {
                    pair.setZero();
                    continue;
                }
                if (debug) {
                    logger.info("ht(H) = " + H.leadingExpVector());
                }

                H = H.abs();
                if (debug) {
                    logger.debug("H = " + H);
                }
                logger.info("H = " + H);
                if (!H.isZERO()) {
                    //CSh = new ArrayList>();
                    ncs = determineAddPairs(cs, H);
                    if (ncs.size() == 0) {
                        continue;
                    }
                    cs = ncs.remove(0); // remove other?
                    pairlist = cs.pairlist;
                    G = cs.list;
                    cond = cs.condition;
                    logger.info("replaced main branch = " + cond);
                    logger.info("#new systems       = " + ncs.size());
                    int yi = CSs.size();
                    for (ColoredSystem x : ncs) {
                        if (!x.isDetermined()) {
                            x = x.reDetermine();
                        }
                        CSs = x.addToList(CSs);
                    }
                    logger.info("#new systems added = " + (CSs.size() - yi));
                }
            }
            // all s-pols reduce to zero in this branch
            if (!cs.isDetermined()) {
                cs = cs.reDetermine();
            }
            CSb.add(cs);
            CSs.remove(0);
            logger.info("done with = " + cs.condition);
        }
        // all branches done
        CSh = new ArrayList>();
        for (ColoredSystem x : CSb) {
            // System.out.println("G = " + x.list );
            if (!x.isDetermined()) {
                x = x.reDetermine();
            }
            cs = minimalGB(x);
            // System.out.println("min(G) = " + cs.list );
            if (!cs.isDetermined()) {
                cs = cs.reDetermine();
            }
            // cs = new ColoredSystem( x.condition, G, x.pairlist );
            CSh.add(cs);
            logger.info("#sequential done = " + x.condition);
            logger.info(x.pairlist.toString());
        }
        CSb = new ArrayList>(CSh);
        return new GroebnerSystem(CSb);
    }


    /**
     * Determine polynomial relative to a condition of a colored system and add
     * pairs.
     * @param cs a colored system.
     * @param A color polynomial.
     * @return list of colored systems, the conditions extending the condition
     *         of cs.
     */
    public List> determineAddPairs(ColoredSystem cs, ColorPolynomial A) {
        List> NCS = new ArrayList>();
        if (A == null || A.isZERO()) {
            // NCS.add( cs );
            return NCS;
        }
        List> S = cs.list;
        Condition cond = cs.condition; // .clone(); done in Condition
        // itself
        OrderedCPairlist pl = cs.pairlist;

        List> Sp;
        ColorPolynomial nz;
        ColoredSystem NS;
        // if ( A.isDetermined() ) { ... } // dont use this
        // System.out.println("to determine = " + A);
        GenPolynomial> Ap = A.getPolynomial();
        List> cd = cred.caseDistinction(cond, Ap);
        logger.info("# cases = " + cd.size());
        for (Condition cnd : cd) {
            //nz = cnd.determine(Ap);
            nz = cnd.reDetermine(A);
            if (nz.isZERO()) {
                logger.info("zero determined nz = " + nz);
                Sp = new ArrayList>(S);
                OrderedCPairlist PL = pl.copy();
                NS = new ColoredSystem(cnd, Sp, PL);
                try {
                    if (!NS.isDetermined()) {
                        NS = NS.reDetermine();
                    }
                } catch (RuntimeException e) {
                    System.out.println("Contradiction in NS_0 = " + NS);
                    //e.printStackTrace();
                    continue;
                }
                NCS = NS.addToList(NCS);
                continue;
            }
            if (S.contains(nz)) {
                System.out.println("*** S.contains(nz) ***");
                continue;
            }
            logger.info("new determined nz = " + nz);
            Sp = new ArrayList>(S);
            Sp.add(nz);
            OrderedCPairlist PL = pl.copy();
            PL.put(nz);
            NS = new ColoredSystem(cnd, Sp, PL);
            try {
                if (!NS.isDetermined()) {
                    NS = NS.reDetermine();
                }
            } catch (RuntimeException e) {
                System.out.println("Contradiction in NS = " + NS);
                //e.printStackTrace();
                continue;
            }
            NCS = NS.addToList(NCS);
        }
        // System.out.println("new determination = " + NCS);
        return NCS;
    }


    /**
     * Comprehensive Groebner base via Groebner system.
     * @param F polynomial list.
     * @return GB(F) a Comprehensive Groebner base of F.
     */
    // @Override
    // @SuppressWarnings("unchecked")
    public List>> GB(List>> F) {
        if (F == null) {
            return F;
        }
        // compute Groebner system
        GroebnerSystem gs = GBsys(F);
        // System.out.println("\n\nGBsys = " + gs);
        return gs.getCGB();
    }


    /**
     * Minimal ordered Groebner basis.
     * @param cs colored system.
     * @return a reduced Groebner base of Gp.
     */
    // @Override
    public ColoredSystem minimalGB(ColoredSystem cs) {
        // List> Gp ) {
        if (cs == null || cs.list == null || cs.list.size() <= 1) {
            return cs;
        }
        // remove zero polynomials
        List> G = new ArrayList>(cs.list.size());
        for (ColorPolynomial a : cs.list) {
            if (a != null && !a.isZERO()) { // always true in GB()
                // already positive a = a.abs();
                G.add(a);
            }
        }
        if (G.size() <= 1) {
            return new ColoredSystem(cs.condition, G, cs.pairlist);
        }
        // System.out.println("G check " + G);
        // remove top reducible polynomials
        Condition cond = cs.condition;
        ColorPolynomial a, b;
        List> F;
        F = new ArrayList>(G.size());
        while (G.size() > 0) {
            a = G.remove(0);
            b = a;
            // System.out.println("check " + b);
            //if (false) {
            //    if (a.red.leadingBaseCoefficient().isConstant()) { // dont drop
            //        // these
            //        F.add(a);
            //        continue;
            //    }
            //}
            if (cred.isTopReducible(G, a) || cred.isTopReducible(F, a)) {
                // drop polynomial
                if (debug) {
                    // System.out.println("trying to drop " + a);
                    List> ff;
                    ff = new ArrayList>(G);
                    ff.addAll(F);
                    a = cred.normalform(cond, ff, a);
                    try {
                        a = cond.reDetermine(a);
                    } catch (RuntimeException ignored) {
                    }
                    if (!a.isZERO()) {
                        logger.error("nf(a) != 0 " + b + ", " + a);
                        F.add(b);
                    }
                }
            } else {
                F.add(a);
            }
        }
        G = F;
        if (G.size() <= 1) {
            return new ColoredSystem(cs.condition, G, cs.pairlist);
        }
        Collections.reverse(G); // important for lex GB
        // reduce remaining polynomials
        int len = G.size();
        int i = 0;
        while (i < len) {
            a = G.remove(0);
            b = a;
            ExpVector e = a.red.leadingExpVector();
            // System.out.println("reducing " + a);
            a = cred.normalform(cond, G, a); // unchanged by top reduction
            // System.out.println("reduced " + a);
            try {
                a = cond.reDetermine(a);
            } catch (RuntimeException ignored) {
            }
            ExpVector f = a.red.leadingExpVector();
            // a = ##engine.basePrimitivePart(a); //a.monic(); was not required
            // a = a.abs();
            // a = red.normalform( F, a );
            if (e.equals(f)) {
                G.add(a); // adds as last
            } else { // should not happen
                if (debug) {
                    logger.error("nf(a) not determined " + b + ", " + a);
                }
                G.add(b); // adds as last
            }
            i++;
        }
        return new ColoredSystem(cs.condition, G, cs.pairlist);
    }

}