/*
 * $Id$
 */

package edu.jas.gbmod;


import java.io.Serializable;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

import org.apache.log4j.Logger;

import edu.jas.gb.ExtendedGB;
import edu.jas.gb.GroebnerBase;
import edu.jas.gb.Reduction;
import edu.jas.gb.ReductionSeq;
import edu.jas.gbufd.GBFactory;
import edu.jas.poly.ExpVector;
import edu.jas.poly.GenPolynomial;
import edu.jas.poly.GenPolynomialRing;
import edu.jas.poly.ModuleList;
import edu.jas.poly.PolynomialList;
import edu.jas.structure.GcdRingElem;
import edu.jas.structure.RingElem;
import edu.jas.vector.BasicLinAlg;
import edu.jas.vector.GenVector;
import edu.jas.vector.GenVectorModul;


/**
 * SyzygyAbstract class. Implements Syzygy computations and tests.
 * @param  coefficient type
 * @author Heinz Kredel
 */

public class SyzygyAbstract> implements Syzygy {


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


    private final boolean debug = logger.isDebugEnabled();


    /**
     * Reduction engine.
     */
    protected Reduction red;


    /**
     * Linear algebra engine.
     */
    protected BasicLinAlg> blas;


    /**
     * Constructor.
     */
    public SyzygyAbstract() {
        red = new ReductionSeq();
        blas = new BasicLinAlg>();
        //gb = new GroebnerBaseSeqPairSeq();
        //gb = new GroebnerBaseSeq();
        //gb = GBFactory. getImplementation(); 
    }


    /**
     * Syzygy module from Groebner base. F must be a Groebner base.
     * @param F a Groebner base.
     * @return syz(F), a basis for the module of syzygies for F.
     */
    public List>> zeroRelations(List> F) {
        return zeroRelations(0, F);
    }


    /**
     * Syzygy module from Groebner base. F must be a Groebner base.
     * @param modv number of module variables.
     * @param F a Groebner base.
     * @return syz(F), a basis for the module of syzygies for F.
     */
    public List>> zeroRelations(int modv, List> F) {
        List>> Z = new ArrayList>>();
        if (F == null) {
            return Z;
        }
        GenVectorModul> mfac = null;
        int i = 0;
        while (mfac == null && i < F.size()) {
            GenPolynomial p = F.get(i);
            if (p != null) {
                mfac = new GenVectorModul>(p.ring, F.size());
            }
        }
        if (mfac == null) {
            return Z;
        }
        GenVector> v = mfac.fromList(F);
        //System.out.println("F = " + F + " v = " + v);
        return zeroRelations(modv, v);
    }


    /**
     * Syzygy module from Groebner base. v must be a Groebner base.
     * @param modv number of module variables.
     * @param v a Groebner base.
     * @return syz(v), a basis for the module of syzygies for v.
     */
    public List>> zeroRelations(int modv, GenVector> v) {

        List>> Z = new ArrayList>>();

        GenVectorModul> mfac = v.modul;
        List> F = v.val;
        GenVector> S = mfac.getZERO();
        GenPolynomial pi, pj, s, h;
        //zero = mfac.coFac.getZERO();
        for (int i = 0; i < F.size(); i++) {
            pi = F.get(i);
            for (int j = i + 1; j < F.size(); j++) {
                pj = F.get(j);
                //logger.info("p"+i+", p"+j+" = " + pi + ", " +pj);

                if (!red.moduleCriterion(modv, pi, pj)) {
                    continue;
                }
                // if ( ! red.criterion4( pi, pj ) ) { continue; }
                List> row = S.copy().val;

                s = red.SPolynomial(row, i, pi, j, pj);
                if (s.isZERO()) {
                    Z.add(row);
                    continue;
                }

                h = red.normalform(row, F, s);
                if (!h.isZERO()) {
                    throw new RuntimeException("Syzygy no GB");
                }
                if (debug) {
                    logger.info("row = " + row.size());
                }
                Z.add(row);
            }
        }
        return Z;
    }


    /**
     * Syzygy module from module Groebner base. M must be a module Groebner
     * base.
     * @param M a module Groebner base.
     * @return syz(M), a basis for the module of syzygies for M.
     */
    public ModuleList zeroRelations(ModuleList M) {
        ModuleList N = M;
        if (M == null || M.list == null) {
            return N;
        }
        if (M.rows == 0 || M.cols == 0) {
            return N;
        }
        GenPolynomial zero = M.ring.getZERO();
        //System.out.println("zero = " + zero);

        //ModuleList Np = null;
        PolynomialList F = M.getPolynomialList();
        int modv = M.cols; // > 0  
        //System.out.println("modv = " + modv);
        List>> G = zeroRelations(modv, F.list);
        //if (G == null) {
        //    return N;
        //}
        List>> Z = new ArrayList>>();
        for (int i = 0; i < G.size(); i++) {
            //F = new PolynomialList(F.ring,(List)G.get(i));
            List> Gi = G.get(i);
            List> Zi = new ArrayList>();
            // System.out.println("\nG("+i+") = " + G.get(i));
            for (int j = 0; j < Gi.size(); j++) {
                //System.out.println("\nG("+i+","+j+") = " + Gi.get(j));
                GenPolynomial p = Gi.get(j);
                if (p != null) {
                    Map> r = p.contract(M.ring);
                    int s = 0;
                    for (GenPolynomial vi : r.values()) {
                        Zi.add(vi);
                        s++;
                    }
                    if (s == 0) {
                        Zi.add(zero);
                    } else if (s > 1) { // will not happen
                        System.out.println("p = " + p);
                        System.out.println("map(" + i + "," + j + ") = " + r + ", size = " + r.size());
                        throw new RuntimeException("Map.size() > 1 = " + r.size());
                    }
                }
            }
            //System.out.println("\nZ("+i+") = " + Zi);
            Z.add(Zi);
        }
        N = new ModuleList(M.ring, Z);
        //System.out.println("\n\nN = " + N);
        return N;
    }


    /**
     * Test if sysygy.
     * @param Z list of sysygies.
     * @param F a polynomial list.
     * @return true, if Z is a list of syzygies for F, else false.
     */

    public boolean isZeroRelation(List>> Z, List> F) {
        for (List> row : Z) {
            GenPolynomial p = blas.scalarProduct(row, F);
            if (p == null) {
                continue;
            }
            if (!p.isZERO()) {
                logger.info("is not ZeroRelation = " + p.toString(p.ring.getVars()));
                logger.info("row = " + row);
                //logger.info("F = " + F);
                return false;
            }
        }
        return true;
    }


    /**
     * Test if sysygy of modules.
     * @param Z list of sysygies.
     * @param F a module list.
     * @return true, if Z is a list of syzygies for F, else false.
     */

    public boolean isZeroRelation(ModuleList Z, ModuleList F) {
        if (Z == null || Z.list == null) {
            return true;
        }
        for (List> row : Z.list) {
            List> zr = blas.leftScalarProduct(row, F.list);
            if (!blas.isZero(zr)) {
                logger.info("is not ZeroRelation (" + zr.size() + ") = " + zr);
                return false;
            }
        }
        return true;
    }


    /**
     * Resolution of a module. Only with direct GBs.
     * @param M a module list of a Groebner basis.
     * @return a resolution of M.
     */
    public List> resolution(ModuleList M) {
        List> R = new ArrayList>();
        ModuleList MM = M;
        ModuleList GM;
        ModuleList Z;
        ModGroebnerBase mbb = new ModGroebnerBaseAbstract(M.ring.coFac);
        while (true) {
            GM = mbb.GB(MM);
            Z = zeroRelations(GM);
            R.add(new ResPart(MM, GM, Z));
            if (Z == null || Z.list == null || Z.list.size() == 0) {
                break;
            }
            MM = Z;
        }
        return R;
    }


    /**
     * Resolution of a polynomial list. Only with direct GBs.
     * @param F a polynomial list of a Groebner basis.
     * @return a resolution of F.
     */
    @SuppressWarnings("unchecked")
    public List // |ResPolPart>
      resolution(PolynomialList F) {
        List>> Z;
        ModuleList Zm;
        List> G;
        PolynomialList Gl;

        GroebnerBase gb = GBFactory.getImplementation(F.ring.coFac);
        G = gb.GB(F.list);
        Z = zeroRelations(G);
        Gl = new PolynomialList(F.ring, G);
        Zm = new ModuleList(F.ring, Z);

        List R = resolution(Zm); //// |ResPolPart>
        R.add(0, new ResPolPart(F, Gl, Zm));
        return R;
    }


    /**
     * Resolution of a polynomial list.
     * @param F a polynomial list of an arbitrary basis.
     * @return a resolution of F.
     */
    @SuppressWarnings("unchecked")
    public List // |ResPolPart>
      resolutionArbitrary(PolynomialList F) {
        List>> Z;
        ModuleList Zm;
        //List> G;
        PolynomialList Gl = null;

        //G = (new GroebnerBaseSeq()).GB( F.list );
        Z = zeroRelationsArbitrary(F.list);
        //Gl = new PolynomialList(F.ring, F.list);
        Zm = new ModuleList(F.ring, Z);

        List R = resolutionArbitrary(Zm); //// |ResPolPart>
        R.add(0, new ResPolPart(F, Gl, Zm));
        return R;
    }


    /**
     * Resolution of a module.
     * @param M a module list of an arbitrary basis.
     * @return a resolution of M.
     */
    public List> resolutionArbitrary(ModuleList M) {
        List> R = new ArrayList>();
        ModuleList MM = M;
        ModuleList GM = null;
        ModuleList Z;
        //ModGroebnerBase mbb = new ModGroebnerBaseAbstract(M.ring.coFac);
        while (true) {
            //GM = mbb.GB(MM);
            Z = zeroRelationsArbitrary(MM);
            R.add(new ResPart(MM, GM, Z));
            if (Z == null || Z.list == null || Z.list.size() == 0) {
                break;
            }
            MM = Z;
        }
        return R;
    }


    /**
     * Syzygy module from arbitrary base.
     * @param F a polynomial list.
     * @return syz(F), a basis for the module of syzygies for F.
     */
    public List>> zeroRelationsArbitrary(List> F) {
        return zeroRelationsArbitrary(0, F);
    }


    /**
     * Syzygy module from arbitrary base.
     * @param modv number of module variables.
     * @param F a polynomial list.
     * @return syz(F), a basis for the module of syzygies for F.
     */
    public List>> zeroRelationsArbitrary(int modv, List> F) {
        if (F == null) {
            return new ArrayList>>();
            //return zeroRelations(modv, F);
        }
        if (F.size() <= 1) {
            return zeroRelations(modv, F);
        }
        GroebnerBase gb = GBFactory.getImplementation(F.get(0).ring.coFac);
        final int lenf = F.size();
        ExtendedGB exgb = gb.extGB(F);
        if (debug) {
            logger.debug("exgb = " + exgb);
            if (!gb.isReductionMatrix(exgb)) {
                logger.error("is reduction matrix ? false");
            }
        }
        List> G = exgb.G;
        List>> G2F = exgb.G2F;
        List>> F2G = exgb.F2G;

        List>> sg = zeroRelations(modv, G);
        GenPolynomialRing ring = G.get(0).ring;
        ModuleList S = new ModuleList(ring, sg);
        if (debug) {
            logger.debug("syz = " + S);
            if (!isZeroRelation(sg, G)) {
                logger.error("is syzygy ? false");
            }
        }
        List>> sf;
        sf = new ArrayList>>(sg.size());
        //List> row;
        for (List> r : sg) {
            Iterator> it = r.iterator();
            Iterator>> jt = G2F.iterator();

            List> rf;
            rf = new ArrayList>(lenf);
            for (int m = 0; m < lenf; m++) {
                rf.add(ring.getZERO());
            }
            while (it.hasNext() && jt.hasNext()) {
                GenPolynomial si = it.next();
                List> ai = jt.next();
                //System.out.println("si = " + si);
                //System.out.println("ai = " + ai);
                if (si == null || ai == null) {
                    continue;
                }
                List> pi = blas.scalarProduct(si, ai);
                //System.out.println("pi = " + pi);
                rf = blas.vectorAdd(rf, pi);
            }
            if (it.hasNext() || jt.hasNext()) {
                logger.error("zeroRelationsArbitrary wrong sizes");
            }
            //System.out.println("\nrf = " + rf + "\n");
            sf.add(rf);
        }
        List>> M;
        M = new ArrayList>>(lenf);
        for (List> r : F2G) {
            Iterator> it = r.iterator();
            Iterator>> jt = G2F.iterator();

            List> rf;
            rf = new ArrayList>(lenf);
            for (int m = 0; m < lenf; m++) {
                rf.add(ring.getZERO());
            }
            while (it.hasNext() && jt.hasNext()) {
                GenPolynomial si = it.next();
                List> ai = jt.next();
                //System.out.println("si = " + si);
                //System.out.println("ai = " + ai);
                if (si == null || ai == null) {
                    continue;
                }
                List> pi = blas.scalarProduct(ai, si);
                //System.out.println("pi = " + pi);
                rf = blas.vectorAdd(rf, pi);
            }
            if (it.hasNext() || jt.hasNext()) {
                logger.error("zeroRelationsArbitrary wrong sizes");
            }
            //System.out.println("\nMg Mf = " + rf + "\n");
            M.add(rf);
        }
        //ModuleList ML = new ModuleList( ring, M );
        //System.out.println("syz ML = " + ML);
        // debug only:
        /* not true in general
        List> F2 = new ArrayList>( F.size() );
        for ( List> rr: M ) {
            GenPolynomial rrg = blas.scalarProduct( F, rr );
            F2.add( rrg );
        }
        PolynomialList pF = new PolynomialList( ring, F );
        PolynomialList pF2 = new PolynomialList( ring, F2 );
        if ( ! pF.equals( pF2 ) ) {
           logger.error("is FAB = F ? false");
        }
        */
        int sflen = sf.size();
        List>> M2;
        M2 = new ArrayList>>(lenf);
        int i = 0;
        for (List> ri : M) {
            List> r2i;
            r2i = new ArrayList>(ri.size());
            int j = 0;
            for (GenPolynomial rij : ri) {
                GenPolynomial p = null;
                if (i == j) {
                    p = ring.getONE().subtract(rij);
                } else {
                    if (rij != null) {
                        p = rij.negate();
                    }
                }
                r2i.add(p);
                j++;
            }
            M2.add(r2i);
            if (!blas.isZero(r2i)) {
                sf.add(r2i);
            }
            i++;
        }
        if (debug) {
            ModuleList M2L = new ModuleList(ring, M2);
            logger.debug("syz M2L = " + M2L);
            ModuleList SF = new ModuleList(ring, sf);
            logger.debug("syz sf = " + SF);
            logger.debug("#syz " + sflen + ", " + sf.size());
            if (!isZeroRelation(sf, F)) {
                logger.error("is syz sf ? false");
            }
        }
        return sf;
    }


    /**
     * Syzygy module from arbitrary module base.
     * @param M an arbitrary module base.
     * @return syz(M), a basis for the module of syzygies for M.
     */
    public ModuleList zeroRelationsArbitrary(ModuleList M) {
        ModuleList N = M;
        if (M == null || M.list == null) {
            return N;
        }
        if (M.rows == 0 || M.cols == 0) {
            return N;
        }
        GenPolynomial zero = M.ring.getZERO();
        //System.out.println("zero = " + zero);

        //ModuleList Np = null;
        PolynomialList F = M.getPolynomialList();
        int modv = M.cols; // > 0  
        //System.out.println("modv = " + modv);
        List>> G = zeroRelationsArbitrary(modv, F.list);
        //if (G == null) {
        //    return N;
        //}
        List>> Z = new ArrayList>>();
        for (int i = 0; i < G.size(); i++) {
            //F = new PolynomialList(F.ring,(List)G.get(i));
            List> Gi = G.get(i);
            List> Zi = new ArrayList>();
            // System.out.println("\nG("+i+") = " + G.get(i));
            for (int j = 0; j < Gi.size(); j++) {
                //System.out.println("\nG("+i+","+j+") = " + Gi.get(j));
                GenPolynomial p = Gi.get(j);
                if (p != null) {
                    Map> r = p.contract(M.ring);
                    int s = 0;
                    for (GenPolynomial vi : r.values()) {
                        Zi.add(vi);
                        s++;
                    }
                    if (s == 0) {
                        Zi.add(zero);
                    } else if (s > 1) { // will not happen
                        System.out.println("p = " + p);
                        System.out.println("map(" + i + "," + j + ") = " + r + ", size = " + r.size());
                        throw new RuntimeException("Map.size() > 1 = " + r.size());
                    }
                }
            }
            //System.out.println("\nZ("+i+") = " + Zi);
            Z.add(Zi);
        }
        N = new ModuleList(M.ring, Z);
        //System.out.println("\n\nN = " + N);
        return N;
    }

}


/**
 * Container for module resolution components.
 * @param  coefficient type
 */
class ResPart> implements Serializable {


    public final ModuleList module;


    public final ModuleList GB;


    public final ModuleList syzygy;


    /**
     * ResPart.
     * @param m a module list.
     * @param g a module list GB.
     * @param z a syzygy module list.
     */
    public ResPart(ModuleList m, ModuleList g, ModuleList z) {
        module = m;
        GB = g;
        syzygy = z;
    }


    /**
     * toString.
     */
    @Override
    public String toString() {
        StringBuffer s = new StringBuffer("ResPart(\n");
        s.append("module = " + module);
        s.append("\n GB = " + GB);
        s.append("\n syzygy = " + syzygy);
        s.append(")");
        return s.toString();
    }
}


/**
 * Container for polynomial resolution components.
 */
class ResPolPart> implements Serializable {


    public final PolynomialList ideal;


    public final PolynomialList GB;


    public final ModuleList syzygy;


    /**
     * ResPolPart.
     * @param m a polynomial list.
     * @param g a polynomial list GB.
     * @param z a syzygy module list.
     */
    public ResPolPart(PolynomialList m, PolynomialList g, ModuleList z) {
        ideal = m;
        GB = g;
        syzygy = z;
    }


    /**
     * toString.
     */
    @Override
    public String toString() {
        StringBuffer s = new StringBuffer("ResPolPart(\n");
        s.append("ideal = " + ideal);
        s.append("\n GB = " + GB);
        s.append("\n syzygy = " + syzygy);
        s.append(")");
        return s.toString();
    }

}