/*
 * $Id$
 */

package edu.jas.gb;


import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

import org.apache.log4j.Logger;

import edu.jas.poly.ExpVector;
import edu.jas.poly.GenPolynomial;
import edu.jas.poly.GenPolynomialRing;
import edu.jas.poly.PolyUtil;
import edu.jas.poly.PolynomialList;
import edu.jas.poly.TermOrder;
import edu.jas.structure.RingElem;
import edu.jas.structure.RingFactory;
import edu.jas.vector.BasicLinAlg;


/**
 * Groebner Bases abstract class. Implements common Groebner bases and GB test
 * methods.
 * @param  coefficient type
 * @author Heinz Kredel
 * 
 * @see edu.jas.application.GBAlgorithmBuilder
 * @see edu.jas.gbufd.GBFactory
 */

public abstract class GroebnerBaseAbstract> implements GroebnerBase {


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


    private final boolean debug = logger.isDebugEnabled();


    /**
     * Reduction engine.
     */
    public final Reduction red;


    /**
     * Strategy for pair selection.
     */
    public final PairList strategy;


    /**
     * linear algebra engine.
     */
    public final BasicLinAlg> blas;


    /**
     * Constructor.
     */
    public GroebnerBaseAbstract() {
        this(new ReductionSeq());
    }


    /**
     * Constructor.
     * @param red Reduction engine
     */
    public GroebnerBaseAbstract(Reduction red) {
        this(red, new OrderedPairlist());
    }


    /**
     * Constructor.
     * @param pl pair selection strategy
     */
    public GroebnerBaseAbstract(PairList pl) {
        this(new ReductionSeq(), pl);
    }


    /**
     * Constructor.
     * @param red Reduction engine
     * @param pl pair selection strategy
     */
    public GroebnerBaseAbstract(Reduction red, PairList pl) {
        if (red == null) {
            red = new ReductionSeq();
        }
        this.red = red;
        if (pl == null) {
            pl = new OrderedPairlist();
        }
        this.strategy = pl;
        blas = new BasicLinAlg>();
    }


    /**
     * Get the String representation with GB engines.
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        return this.getClass().getSimpleName();
    }


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


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


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


    /**
     * Groebner base test.
     * @param modv module variable number.
     * @param F polynomial list.
     * @param b true for simple test, false for GB test.
     * @return true, if F is a Groebner base, else false.
     */
    public boolean isGB(int modv, List> F, boolean b) {
        if (b) {
            return isGBsimple(modv, F);
        }
        return isGBidem(modv, F);
    }


    /**
     * Groebner base simple test.
     * @param modv module variable number.
     * @param F polynomial list.
     * @return true, if F is a Groebner base, else false.
     */
    public boolean isGBsimple(int modv, List> F) {
        if (F == null || F.isEmpty()) {
            return true;
        }
        GenPolynomial pi, pj, s, h;
        ExpVector ei, ej, eij;
        for (int i = 0; i < F.size(); i++) {
            pi = F.get(i);
            ei = pi.leadingExpVector();
            for (int j = i + 1; j < F.size(); j++) {
                pj = F.get(j);
                ej = pj.leadingExpVector();
                if (!red.moduleCriterion(modv, ei, ej)) {
                    continue;
                }
                eij = ei.lcm(ej);
                if (!red.criterion4(ei, ej, eij)) {
                    continue;
                }
                if (!criterion3(i, j, eij, F)) {
                    continue;
                }
                s = red.SPolynomial(pi, pj);
                if (s.isZERO()) {
                    continue;
                }
                //System.out.println("i, j = " + i + ", " + j); 
                h = red.normalform(F, s);
                if (!h.isZERO()) {
                    logger.info("no GB: pi = " + pi + ", pj = " + pj);
                    logger.info("s  = " + s + ", h = " + h);
                    return false;
                }
            }
        }
        return true;
    }


    /**
     * GB criterium 3.
     * @return true if the S-polynomial(i,j) is required.
     */
    boolean criterion3(int i, int j, ExpVector eij, List> P) {
        assert i < j;
        //for ( int k = 0; k < P.size(); k++ ) {
        // not of much use
        for (int k = 0; k < i; k++) {
            GenPolynomial A = P.get(k);
            ExpVector ek = A.leadingExpVector();
            if (eij.multipleOf(ek)) {
                return false;
            }
        }
        return true;
    }


    /**
     * Groebner base idempotence test.
     * @param modv module variable number.
     * @param F polynomial list.
     * @return true, if F is equal to GB(F), else false.
     */
    public boolean isGBidem(int modv, List> F) {
        if (F == null || F.isEmpty()) {
            return true;
        }
        GenPolynomialRing pring = F.get(0).ring;
        List> G = GB(modv, F);
        PolynomialList Fp = new PolynomialList(pring, F);
        PolynomialList Gp = new PolynomialList(pring, G);
        return Fp.compareTo(Gp) == 0;
    }


    /**
     * Common zero test.
     * @param F polynomial list.
     * @return -1, 0 or 1 if dimension(ideal(F)) &eq; -1, 0 or ≥ 1.
     */
    public int commonZeroTest(List> F) {
        if (F == null || F.isEmpty()) {
            return 1;
        }
        GenPolynomialRing pfac = F.get(0).ring;
        if (pfac.nvar <= 0) {
            return -1;
        }
        //int uht = 0;
        Set v = new HashSet(); // for non reduced GBs
        for (GenPolynomial p : F) {
            if (p.isZERO()) {
                continue;
            }
            if (p.isConstant()) { // for non-monic lists
                return -1;
            }
            ExpVector e = p.leadingExpVector();
            if (e == null) {
                continue;
            }
            int[] u = e.dependencyOnVariables();
            if (u == null) {
                continue;
            }
            if (u.length == 1) {
                //uht++;
                v.add(u[0]);
            }
        }
        if (pfac.nvar == v.size()) {
            return 0;
        }
        return 1;
    }


    /**
     * Groebner base using pairlist class.
     * @param F polynomial list.
     * @return GB(F) a Groebner base of F.
     */
    public List> GB(List> F) {
        return GB(0, F);
    }


    /**
     * Extended Groebner base using critical pair class.
     * @param F polynomial list.
     * @return a container for a Groebner base G of F together with
     *         back-and-forth transformations.
     */
    public ExtendedGB extGB(List> F) {
        return extGB(0, F);
    }


    /**
     * Extended Groebner base using critical pair class.
     * @param modv module variable number.
     * @param F polynomial list.
     * @return a container for a Groebner base G of F together with
     *         back-and-forth transformations.
     */
    public ExtendedGB extGB(int modv, List> F) {
        throw new UnsupportedOperationException("extGB not implemented in " + this.getClass().getSimpleName());
    }


    /**
     * Minimal ordered Groebner basis.
     * @param Gp a Groebner base.
     * @return a reduced Groebner base of Gp.
     */
    public List> minimalGB(List> Gp) {
        if (Gp == null || Gp.size() <= 1) {
            return Gp;
        }
        // remove zero polynomials
        List> G = new ArrayList>(Gp.size());
        for (GenPolynomial a : Gp) {
            if (a != null && !a.isZERO()) { // always true in GB()
                // already positive a = a.abs();
                G.add(a);
            }
        }
        if (G.size() <= 1) {
            return G;
        }
        // remove top reducible polynomials
        GenPolynomial a;
        List> F;
        F = new ArrayList>(G.size());
        while (G.size() > 0) {
            a = G.remove(0);
            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
                // drop polynomial 
                if (debug) {
                    System.out.println("dropped " + a);
                    List> ff;
                    ff = new ArrayList>(G);
                    ff.addAll(F);
                    a = red.normalform(ff, a);
                    if (!a.isZERO()) {
                        System.out.println("error, nf(a) " + a);
                    }
                }
            } else {
                F.add(a);
            }
        }
        G = F;
        if (G.size() <= 1) {
            return G;
        }
        // reduce remaining polynomials
        Collections.reverse(G); // important for lex GB
        int len = G.size();
        if (debug) {
            System.out.println("#G " + len);
            for (GenPolynomial aa : G) {
                System.out.println("aa = " + aa.length() + ", lt = " + aa.getMap().keySet());
            }
        }
        int i = 0;
        while (i < len) {
            a = G.remove(0);
            if (debug) {
                System.out.println("doing " + a.length() + ", lt = " + a.leadingExpVector());
            }
            a = red.normalform(G, a);
            G.add(a); // adds as last
            i++;
        }
        return G;
    }


    /**
     * Test for minimal ordered Groebner basis.
     * @param Gp an ideal base.
     * @return true, if Gp is a reduced minimal Groebner base.
     */
    public boolean isMinimalGB(List> Gp) {
        if (Gp == null || Gp.size() == 0) {
            return true;
        }
        // test for zero polynomials
        for (GenPolynomial a : Gp) {
            if (a == null || a.isZERO()) {
                if (debug) {
                    logger.debug("zero polynomial " + a);
                }
                return false;
            }
        }
        // test for top reducible polynomials
        List> G = new ArrayList>(Gp);
        List> F = new ArrayList>(G.size());
        while (G.size() > 0) {
            GenPolynomial a = G.remove(0);
            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
                if (debug) {
                    logger.debug("top reducible polynomial " + a);
                }
                return false;
            } else {
                F.add(a);
            }
        }
        G = F;
        if (G.size() <= 1) {
            return true;
        }
        // test reducibility of polynomials
        int len = G.size();
        int i = 0;
        while (i < len) {
            GenPolynomial a = G.remove(0);
            if (!red.isNormalform(G, a)) {
                if (debug) {
                    logger.debug("reducible polynomial " + a);
                }
                return false;
            }
            G.add(a); // re-adds as last
            i++;
        }
        return true;
    }


    /**
     * Test if reduction matrix.
     * @param exgb an ExtendedGB container.
     * @return true, if exgb contains a reduction matrix, else false.
     */
    public boolean isReductionMatrix(ExtendedGB exgb) {
        if (exgb == null) {
            return true;
        }
        return isReductionMatrix(exgb.F, exgb.G, exgb.F2G, exgb.G2F);
    }


    /**
     * Test if reduction matrix.
     * @param F a polynomial list.
     * @param G a Groebner base.
     * @param Mf a possible reduction matrix.
     * @param Mg a possible reduction matrix.
     * @return true, if Mg and Mf are reduction matrices, else false.
     */
    public boolean isReductionMatrix(List> F, List> G,
                    List>> Mf, List>> Mg) {
        // no more check G and Mg: G * Mg[i] == 0
        // check F and Mg: F * Mg[i] == G[i]
        int k = 0;
        for (List> row : Mg) {
            boolean t = red.isReductionNF(row, F, G.get(k), null);
            if (!t) {
                logger.error("F isReductionMatrix s, k = " + F.size() + ", " + k);
                return false;
            }
            k++;
        }
        // check G and Mf: G * Mf[i] == F[i]
        k = 0;
        for (List> row : Mf) {
            boolean t = red.isReductionNF(row, G, F.get(k), null);
            if (!t) {
                logger.error("G isReductionMatrix s, k = " + G.size() + ", " + k);
                return false;
            }
            k++;
        }
        return true;
    }


    /**
     * Normalize M. Make all rows the same size and make certain column elements
     * zero.
     * @param M a reduction matrix.
     * @return normalized M.
     */
    public List>> normalizeMatrix(int flen, List>> M) {
        if (M == null) {
            return M;
        }
        if (M.size() == 0) {
            return M;
        }
        List>> N = new ArrayList>>();
        List>> K = new ArrayList>>();
        int len = M.get(M.size() - 1).size(); // longest row
        // pad / extend rows
        for (List> row : M) {
            List> nrow = new ArrayList>(row);
            for (int i = row.size(); i < len; i++) {
                nrow.add(null);
            }
            N.add(nrow);
        }
        // System.out.println("norm N fill = " + N);
        // make zero columns
        int k = flen;
        for (int i = 0; i < N.size(); i++) { // 0
            List> row = N.get(i);
            if (debug) {
                logger.info("row = " + row);
            }
            K.add(row);
            if (i < flen) { // skip identity part
                continue;
            }
            List> xrow;
            GenPolynomial a;
            //System.out.println("norm i = " + i);
            for (int j = i + 1; j < N.size(); j++) {
                List> nrow = N.get(j);
                //System.out.println("nrow j = " +j + ", " + nrow);
                if (k < nrow.size()) { // always true
                    a = nrow.get(k);
                    //System.out.println("k, a = " + k + ", " + a);
                    if (a != null && !a.isZERO()) {
                        xrow = blas.scalarProduct(a, row);
                        xrow = blas.vectorAdd(xrow, nrow);
                        //System.out.println("xrow = " + xrow);
                        N.set(j, xrow);
                    }
                }
            }
            k++;
        }
        //System.out.println("norm K reduc = " + K);
        // truncate 
        N.clear();
        for (List> row : K) {
            List> tr = new ArrayList>();
            for (int i = 0; i < flen; i++) {
                tr.add(row.get(i));
            }
            N.add(tr);
        }
        K = N;
        //System.out.println("norm K trunc = " + K);
        return K;
    }


    /**
     * Minimal extended groebner basis.
     * @param Gp a Groebner base.
     * @param M a reduction matrix, is modified.
     * @return a (partially) reduced Groebner base of Gp in a container.
     */
    public ExtendedGB minimalExtendedGB(int flen, List> Gp, List>> M) {
        if (Gp == null) {
            return null; //new ExtendedGB(null,Gp,null,M);
        }
        if (Gp.size() <= 1) {
            return new ExtendedGB(null, Gp, null, M);
        }
        List> G;
        List> F;
        G = new ArrayList>(Gp);
        F = new ArrayList>(Gp.size());

        List>> Mg;
        List>> Mf;
        Mg = new ArrayList>>(M.size());
        Mf = new ArrayList>>(M.size());
        List> row;
        for (List> r : M) {
            // must be copied also
            row = new ArrayList>(r);
            Mg.add(row);
        }
        row = null;

        GenPolynomial a;
        ExpVector e;
        ExpVector f;
        GenPolynomial p;
        boolean mt;
        ListIterator> it;
        ArrayList ix = new ArrayList();
        ArrayList jx = new ArrayList();
        int k = 0;
        //System.out.println("flen, Gp, M = " + flen + ", " + Gp.size() + ", " + M.size() );
        while (G.size() > 0) {
            a = G.remove(0);
            e = a.leadingExpVector();

            it = G.listIterator();
            mt = false;
            while (it.hasNext() && !mt) {
                p = it.next();
                f = p.leadingExpVector();
                mt = e.multipleOf(f);
            }
            it = F.listIterator();
            while (it.hasNext() && !mt) {
                p = it.next();
                f = p.leadingExpVector();
                mt = e.multipleOf(f);
            }
            //System.out.println("k, mt = " + k + ", " + mt);
            if (!mt) {
                F.add(a);
                ix.add(k);
            } else { // drop polynomial and corresponding row and column
                // F.add( a.ring.getZERO() );
                jx.add(k);
            }
            k++;
        }
        if (debug) {
            logger.debug("ix, #M, jx = " + ix + ", " + Mg.size() + ", " + jx);
        }
        int fix = -1; // copied polys
        // copy Mg to Mf as indicated by ix
        for (int i = 0; i < ix.size(); i++) {
            int u = ix.get(i);
            if (u >= flen && fix == -1) {
                fix = Mf.size();
            }
            //System.out.println("copy u, fix = " + u + ", " + fix);
            if (u >= 0) {
                row = Mg.get(u);
                Mf.add(row);
            }
        }
        if (F.size() <= 1 || fix == -1) {
            return new ExtendedGB(null, F, null, Mf);
        }
        // must return, since extended normalform has not correct order of polys
        /*
        G = F;
        F = new ArrayList>( G.size() );
        List> temp;
        k = 0;
        final int len = G.size();
        while ( G.size() > 0 ) {
            a = G.remove(0);
            if ( k >= fix ) { // dont touch copied polys
               row = Mf.get( k );
               //System.out.println("doing k = " + k + ", " + a);
               // must keep order, but removed polys missing
               temp = new ArrayList>( len );
               temp.addAll( F );
               temp.add( a.ring.getZERO() ); // ??
               temp.addAll( G );
               //System.out.println("row before = " + row);
               a = red.normalform( row, temp, a );
               //System.out.println("row after  = " + row);
            }
            F.add( a );
            k++;
        }
        // does Mf need renormalization?
        */
        return new ExtendedGB(null, F, null, Mf);
    }


    /**
     * Univariate head term degrees.
     * @param A list of polynomials.
     * @return a list of the degrees of univariate head terms.
     */
    public List univariateDegrees(List> A) {
        List ud = new ArrayList();
        if (A == null || A.size() == 0) {
            return ud;
        }
        GenPolynomialRing pfac = A.get(0).ring;
        if (pfac.nvar <= 0) {
            return ud;
        }
        //int uht = 0;
        Map v = new TreeMap(); // for non reduced GBs
        for (GenPolynomial p : A) {
            ExpVector e = p.leadingExpVector();
            if (e == null) {
                continue;
            }
            int[] u = e.dependencyOnVariables();
            if (u == null) {
                continue;
            }
            if (u.length == 1) {
                //uht++;
                Long d = v.get(u[0]);
                if (d == null) {
                    v.put(u[0], e.getVal(u[0]));
                }
            }
        }
        for (int i = 0; i < pfac.nvar; i++) {
            Long d = v.get(i);
            ud.add(d);
        }
        //Collections.reverse(ud);
        return ud;
    }


    /**
     * Construct univariate polynomial of minimal degree in variable i of a zero
     * dimensional ideal(G).
     * @param i variable index.
     * @param G list of polynomials, a monic reduced Gröbner base of a zero
     *            dimensional ideal.
     * @return univariate polynomial of minimal degree in variable i in ideal(G)
     */
    public GenPolynomial constructUnivariate(int i, List> G) {
        if (G == null || G.size() == 0) {
            throw new IllegalArgumentException("G may not be null or empty");
        }
        List ud = univariateDegrees(G);
        if (ud.size() <= i) {
            //logger.info("univ pol, ud = " + ud);
            throw new IllegalArgumentException("ideal(G) not zero dimensional " + ud);
        }
        int ll = 0;
        Long di = ud.get(i);
        if (di != null) {
            ll = (int) (long) di;
        } else {
            throw new IllegalArgumentException("ideal(G) not zero dimensional");
        }
        long vsdim = 1;
        for (Long d : ud) {
            if (d != null) {
                vsdim *= d;
            }
        }
        logger.info("univariate construction, deg = " + ll + ", vsdim = " + vsdim);
        GenPolynomialRing pfac = G.get(0).ring;
        RingFactory cfac = pfac.coFac;
        String var = pfac.getVars()[pfac.nvar - 1 - i];
        GenPolynomialRing ufac = new GenPolynomialRing(cfac, 1, new TermOrder(TermOrder.INVLEX),
                        new String[] { var });

        GenPolynomialRing cpfac = new GenPolynomialRing(cfac, ll, new TermOrder(TermOrder.INVLEX));
        GenPolynomialRing> rfac = new GenPolynomialRing>(cpfac, pfac);
        GenPolynomial> P = rfac.getZERO();
        for (int k = 0; k < ll; k++) {
            GenPolynomial> Pp = rfac.univariate(i, k);
            GenPolynomial cp = cpfac.univariate(cpfac.nvar - 1 - k);
            Pp = Pp.multiply(cp);
            P = P.sum(Pp);
        }
        if (debug) {
            logger.info("univariate construction, P = " + P);
            logger.info("univariate construction, deg_*(G) = " + ud);
            //throw new RuntimeException("check");
        }
        GenPolynomial X;
        GenPolynomial XP;
        // solve system of linear equations for the coefficients of the univariate polynomial
        List> ls;
        int z = -1;
        do {
            //System.out.println("ll  = " + ll);
            GenPolynomial> Pp = rfac.univariate(i, ll);
            GenPolynomial cp = cpfac.univariate(cpfac.nvar - 1 - ll);
            Pp = Pp.multiply(cp);
            P = P.sum(Pp);
            X = pfac.univariate(i, ll);
            XP = red.normalform(G, X);
            //System.out.println("XP = " + XP);
            GenPolynomial> XPp = PolyUtil. toRecursive(rfac, XP);
            GenPolynomial> XPs = XPp.sum(P);
            ls = new ArrayList>(XPs.getMap().values());
            //System.out.println("ls,1 = " + ls);
            ls = red.irreducibleSet(ls);
            z = commonZeroTest(ls);
            if (z != 0) {
                ll++;
                if (ll > vsdim) {
                    logger.info("univariate construction, P = " + P);
                    logger.info("univariate construction, nf(P) = " + XP);
                    logger.info("G = " + G);
                    throw new ArithmeticException(
                                    "univariate polynomial degree greater than vector space dimansion");
                }
                cpfac = cpfac.extend(1);
                rfac = new GenPolynomialRing>(cpfac, pfac);
                P = PolyUtil. extendCoefficients(rfac, P, 0, 0L);
                XPp = PolyUtil. extendCoefficients(rfac, XPp, 0, 1L);
                P = P.sum(XPp);
            }
        } while (z != 0); // && ll <= 5 && !XP.isZERO()
        // construct result polynomial
        GenPolynomial pol = ufac.univariate(0, ll);
        for (GenPolynomial pc : ls) {
            ExpVector e = pc.leadingExpVector();
            if (e == null) {
                continue;
            }
            int[] v = e.dependencyOnVariables();
            if (v == null || v.length == 0) {
                continue;
            }
            int vi = v[0];
            C tc = pc.trailingBaseCoefficient();
            tc = tc.negate();
            GenPolynomial pi = ufac.univariate(0, ll - 1 - vi);
            pi = pi.multiply(tc);
            pol = pol.sum(pi);
        }
        if (logger.isInfoEnabled()) {
            logger.info("univariate construction, pol = " + pol);
        }
        return pol;
    }


    /**
     * Cleanup and terminate ThreadPool.
     */
    public void terminate() {
        logger.info("terminate not implemented");
        //throw new RuntimeException("get a stack trace");
    }


    /**
     * Cancel ThreadPool.
     */
    public int cancel() {
        logger.info("cancel not implemented");
        return 0;
    }

}