/*
 * $Id$
 */

package edu.jas.gb;


import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

import org.apache.log4j.Logger;

import edu.jas.poly.ExpVector;
import edu.jas.poly.GenPolynomial;
import edu.jas.poly.GenSolvablePolynomial;
import edu.jas.poly.GenSolvablePolynomialRing;
import edu.jas.poly.PolynomialList;
import edu.jas.structure.RingElem;


/**
 * Solvable Groebner bases sequential algorithms. Implements common left, right
 * and twosided Groebner bases and left, right and twosided GB tests.
 * @param  coefficient type
 * @author Heinz Kredel.
 */

public class SolvableGroebnerBaseSeq> extends SolvableGroebnerBaseAbstract {


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


    private final boolean debug = logger.isDebugEnabled();


    /**
     * Constructor.
     */
    public SolvableGroebnerBaseSeq() {
        super();
    }


    /**
     * Constructor.
     * @param sred Solvable reduction engine
     * @param pl pair selection strategy
     */
    public SolvableGroebnerBaseSeq(SolvableReduction sred, PairList pl) {
        super(sred, pl);
    }


    /**
     * Left Groebner base using pairlist class.
     * @param modv number of module variables.
     * @param F solvable polynomial list.
     * @return leftGB(F) a left Groebner base of F.
     */
    @SuppressWarnings("unchecked")
    public List> leftGB(int modv, List> F) {
        List> G = new ArrayList>();
        PairList pairlist = null;
        int l = F.size();
        //  ListIterator it = F.listIterator();
        for (GenSolvablePolynomial p : F) {
            //  p = (SolvablePolynomial) it.next();
            if (p.length() > 0) {
                p = (GenSolvablePolynomial) p.monic();
                if (p.isONE()) {
                    G.clear();
                    G.add(p);
                    return G; // since no threads are activated
                }
                G.add(p);
                if (pairlist == null) {
                    //pairlist = new OrderedPairlist( modv, p.ring );
                    pairlist = strategy.create(modv, p.ring);
                }
                // putOne not required
                pairlist.put(p);
            } else {
                l--;
            }
        }
        if (l <= 1) {
            return G; // since no threads are activated
        }

        GenSolvablePolynomial pi, pj, S, H;
        Pair pair;
        while (pairlist.hasNext()) {
            pair = pairlist.removeNext();
            if (pair == null) {
                continue;
            }
            pi = (GenSolvablePolynomial) pair.pi;
            pj = (GenSolvablePolynomial) pair.pj;
            if (debug) {
                logger.info("pi    = " + pi);
                logger.info("pj    = " + pj);
            }

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

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

            H = (GenSolvablePolynomial) H.monic();
            if (H.isONE()) {
                G.clear();
                G.add(H);
                return G; // since no threads are activated
            }
            if (debug) {
                logger.info("H = " + H);
            }
            if (H.length() > 0) {
                l++;
                G.add(H);
                pairlist.put(H);
            }
        }
        logger.debug("#sequential list = " + G.size());
        G = leftMinimalGB(G);
        logger.info("" + pairlist);
        return G;
    }


    /**
     * Solvable Extended Groebner base using critical pair class.
     * @param modv module variable number.
     * @param F solvable polynomial list.
     * @return a container for an extended left Groebner base of F.
     */
    @SuppressWarnings("unchecked")
    public SolvableExtendedGB extLeftGB(int modv, List> F) {

        List> G = new ArrayList>();
        List>> F2G = new ArrayList>>();
        List>> G2F = new ArrayList>>();
        PairList pairlist = null;
        boolean oneInGB = false;
        int len = F.size();

        List> row = null;
        List> rows = null;
        List> rowh = null;
        GenSolvablePolynomialRing ring = null;
        GenSolvablePolynomial H;
        GenSolvablePolynomial p;

        int nzlen = 0;
        for (GenSolvablePolynomial f : F) {
            if (f.length() > 0) {
                nzlen++;
            }
            if (ring == null) {
                ring = f.ring;
            }
        }
        GenSolvablePolynomial mone = ring.getONE(); //.negate();
        int k = 0;
        ListIterator> it = F.listIterator();
        while (it.hasNext()) {
            p = it.next();
            if (p.length() > 0) {
                row = new ArrayList>(nzlen);
                for (int j = 0; j < nzlen; j++) {
                    row.add(null);
                }
                //C c = p.leadingBaseCoefficient();
                //c = c.inverse();
                //p = p.multiply( c );
                row.set(k, mone); //.multiply(c) );
                k++;
                if (p.isUnit()) {
                    G.clear();
                    G.add(p);
                    G2F.clear();
                    G2F.add(row);
                    oneInGB = true;
                    break;
                }
                G.add(p);
                G2F.add(row);
                if (pairlist == null) {
                    //pairlist = new CriticalPairList( modv, p.ring );
                    pairlist = strategy.create(modv, p.ring);
                }
                // putOne not required
                pairlist.put(p);
            } else {
                len--;
            }
        }
        SolvableExtendedGB exgb;
        if (len <= 1 || oneInGB) {
            // adjust F2G
            for (GenSolvablePolynomial f : F) {
                row = new ArrayList>(G.size());
                for (int j = 0; j < G.size(); j++) {
                    row.add(null);
                }
                H = sred.leftNormalform(row, G, f);
                if (!H.isZERO()) {
                    logger.error("nonzero H = " + H);
                }
                F2G.add(row);
            }
            exgb = new SolvableExtendedGB(F, G, F2G, G2F);
            //System.out.println("exgb 1 = " + exgb);
            return exgb;
        }

        Pair pair;
        int i, j;
        GenSolvablePolynomial pi;
        GenSolvablePolynomial pj;
        GenSolvablePolynomial S;
        GenSolvablePolynomial x;
        GenSolvablePolynomial y;
        //GenPolynomial z;
        while (pairlist.hasNext() && !oneInGB) {
            pair = pairlist.removeNext();
            if (pair == null) {
                //pairlist.update(); // ?
                continue;
            }
            i = pair.i;
            j = pair.j;
            pi = (GenSolvablePolynomial) pair.pi;
            pj = (GenSolvablePolynomial) pair.pj;
            if (debug) {
                logger.info("i, pi    = " + i + ", " + pi);
                logger.info("j, pj    = " + j + ", " + pj);
            }

            rows = new ArrayList>(G.size());
            for (int m = 0; m < G.size(); m++) {
                rows.add(null);
            }
            S = sred.leftSPolynomial(rows, i, pi, j, pj);
            if (debug) {
                logger.debug("is reduction S = " + sred.isLeftReductionNF(rows, G, ring.getZERO(), S));
            }
            if (S.isZERO()) {
                pair.setZero();
                //pairlist.update( pair, S );
                // do not add to G2F
                continue;
            }
            if (debug) {
                logger.debug("ht(S) = " + S.leadingExpVector());
            }

            rowh = new ArrayList>(G.size());
            for (int m = 0; m < G.size(); m++) {
                rowh.add(null);
            }
            H = sred.leftNormalform(rowh, G, S);
            if (debug) {
                //System.out.println("H = " + H);
                logger.debug("is reduction H = " + sred.isLeftReductionNF(rowh, G, S, H));
            }
            if (H.isZERO()) {
                pair.setZero();
                //pairlist.update( pair, H );
                // do not add to G2F
                continue;
            }
            if (debug) {
                logger.debug("ht(H) = " + H.leadingExpVector());
            }

            row = new ArrayList>(G.size() + 1);
            for (int m = 0; m < G.size(); m++) {
                x = rows.get(m);
                if (x != null) {
                    //System.out.println("ms = " + m + " " + x);
                    x = (GenSolvablePolynomial) x.negate();
                }
                y = rowh.get(m);
                if (y != null) {
                    y = (GenSolvablePolynomial) y.negate();
                    //System.out.println("mh = " + m + " " + y);
                }
                if (x == null) {
                    x = y;
                } else {
                    x = (GenSolvablePolynomial) x.sum(y);
                }
                //System.out.println("mx = " + m + " " + x);
                row.add(x);
            }
            if (debug) {
                logger.debug("is reduction 0+sum(row,G) == H : "
                                + sred.isLeftReductionNF(row, G, H, ring.getZERO()));
            }
            row.add(null);


            //  H = H.monic();
            C c = H.leadingBaseCoefficient();
            c = c.inverse();
            H = H.multiply(c);
            // 1*c*row, leads to wrong method dispatch:
            row = PolynomialList. castToSolvableList(blas.scalarProduct(mone.multiply(c),
                            PolynomialList. castToList(row)));
            row.set(G.size(), mone);
            if (H.isONE()) {
                // pairlist.record( pair, H );
                // G.clear(); 
                G.add(H);
                G2F.add(row);
                oneInGB = true;
                break;
            }
            if (debug) {
                logger.debug("H = " + H);
            }
            G.add(H);
            //pairlist.update( pair, H );
            pairlist.put(H);
            G2F.add(row);
        }
        if (debug) {
            exgb = new SolvableExtendedGB(F, G, F2G, G2F);
            logger.info("exgb unnorm = " + exgb);
        }
        G2F = normalizeMatrix(F.size(), G2F);
        if (debug) {
            exgb = new SolvableExtendedGB(F, G, F2G, G2F);
            logger.info("exgb nonmin = " + exgb);
            boolean t2 = isLeftReductionMatrix(exgb);
            logger.debug("exgb t2 = " + t2);
        }
        exgb = minimalSolvableExtendedGB(F.size(), G, G2F);
        G = exgb.G;
        G2F = exgb.G2F;
        logger.debug("#sequential list = " + G.size());
        logger.info("" + pairlist);
        // setup matrices F and F2G
        for (GenSolvablePolynomial f : F) {
            row = new ArrayList>(G.size());
            for (int m = 0; m < G.size(); m++) {
                row.add(null);
            }
            H = sred.leftNormalform(row, G, f);
            if (!H.isZERO()) {
                logger.error("nonzero H = " + H);
            }
            F2G.add(row);
        }
        return new SolvableExtendedGB(F, G, F2G, G2F);
    }


    /**
     * Twosided Groebner base using pairlist class.
     * @param modv number of module variables.
     * @param Fp solvable polynomial list.
     * @return tsGB(Fp) a twosided Groebner base of Fp.
     */
    @SuppressWarnings("unchecked")
    public List> twosidedGB(int modv, List> Fp) {
        if (Fp == null || Fp.size() == 0) { // 0 not 1
            return new ArrayList>();
        }
        GenSolvablePolynomialRing fac = Fp.get(0).ring; // assert != null
        //List> X = generateUnivar( modv, Fp );
        List> X = fac.univariateList(modv);
        //System.out.println("X univ = " + X);
        List> F = new ArrayList>(Fp.size() * (1 + X.size()));
        F.addAll(Fp);
        GenSolvablePolynomial p, x, q;
        for (int i = 0; i < Fp.size(); i++) {
            p = Fp.get(i);
            for (int j = 0; j < X.size(); j++) {
                x = X.get(j);
                q = p.multiply(x);
                q = sred.leftNormalform(F, q);
                if (!q.isZERO()) {
                    F.add(q);
                }
            }
        }
        //System.out.println("F generated = " + F);
        List> G = new ArrayList>();
        PairList pairlist = null;
        int l = F.size();
        ListIterator> it = F.listIterator();
        while (it.hasNext()) {
            p = it.next();
            if (p.length() > 0) {
                p = (GenSolvablePolynomial) p.monic();
                if (p.isONE()) {
                    G.clear();
                    G.add(p);
                    return G; // since no threads are activated
                }
                G.add(p);
                if (pairlist == null) {
                    // pairlist = new OrderedPairlist( modv, p.ring );
                    pairlist = strategy.create(modv, p.ring);
                    if ( ! p.ring.coFac.isField() ) {
                        //throw new IllegalArgumentException("coefficients not from a field");
                        logger.warn("coefficients not from a field " + p.ring.coFac);
                    }
                }
                // putOne not required
                pairlist.put(p);
            } else {
                l--;
            }
        }
        //System.out.println("G to check = " + G);
        if (l <= 1) { // 1 ok
            return G; // since no threads are activated
        }

        Pair pair;
        GenSolvablePolynomial pi, pj, S, H;
        while (pairlist.hasNext()) {
            pair = pairlist.removeNext();
            if (pair == null) {
                continue;
            }

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

            S = sred.leftSPolynomial(pi, pj);
            if (S.isZERO()) {
                pair.setZero();
                continue;
            }
            if (debug) {
                logger.debug("ht(S) = " + S.leadingExpVector());
            }

            H = sred.leftNormalform(G, S);
            if (H.isZERO()) {
                pair.setZero();
                continue;
            }
            if (debug) {
                logger.debug("ht(H) = " + H.leadingExpVector());
            }

            H = (GenSolvablePolynomial) H.monic();
            if (H.isONE()) {
                G.clear();
                G.add(H);
                return G; // since no threads are activated
            }
            if (debug) {
                logger.debug("H = " + H);
            }
            if (H.length() > 0) {
                l++;
                G.add(H);
                pairlist.put(H);
                for (int j = 0; j < X.size(); j++) {
                    l++;
                    x = X.get(j);
                    p = H.multiply(x);
                    p = sred.leftNormalform(G, p);
                    if (!p.isZERO()) {
                        p = (GenSolvablePolynomial) p.monic();
                        if (p.isONE()) {
                            G.clear();
                            G.add(p);
                            return G; // since no threads are activated
                        }
                        G.add(p);
                        pairlist.put(p);
                    }
                }
            }
        }
        logger.debug("#sequential list = " + G.size());
        G = leftMinimalGB(G);
        logger.info("" + pairlist);
        return G;
    }


    /**
     * 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;
            GenSolvablePolynomial 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()) { // a*row + nrow, leads to wrong method dispatch
                        List> yrow = blas.scalarProduct(a,
                                        PolynomialList. castToList(row));
                        yrow = blas.vectorAdd(yrow, PolynomialList. castToList(nrow));
                        xrow = PolynomialList. castToSolvableList(yrow);
                        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;
    }


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


    /**
     * Minimal solvable extended groebner basis.
     * @param Gp a left Groebner base.
     * @param M a left reduction matrix, is modified.
     * @return a (partially) reduced left Groebner base of Gp in a container.
     */
    public SolvableExtendedGB minimalSolvableExtendedGB(int flen, List> Gp,
                    List>> M) {
        if (Gp == null) {
            return null; //new SolvableExtendedGB(null,Gp,null,M);
        }
        if (Gp.size() <= 1) {
            return new SolvableExtendedGB(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;

        GenSolvablePolynomial a;
        ExpVector e;
        ExpVector f;
        GenSolvablePolynomial 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 SolvableExtendedGB(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 = sred.leftNormalform( row, temp, a );
               //System.out.println("row after  = " + row);
            }
            F.add( a );
            k++;
        }
        // does Mf need renormalization?
        */
        return new SolvableExtendedGB(null, F, null, Mf);
    }

}