/*
 * $Id$
 */

package edu.jas.gbufd;


import java.util.List;
import java.util.Map;

import org.apache.log4j.Logger;

import edu.jas.gb.ReductionAbstract;
import edu.jas.poly.ExpVector;
import edu.jas.poly.GenPolynomial;
import edu.jas.structure.RingElem;


/**
 * Polynomial pseudo reduction sequential use algorithm. Coefficients of
 * polynomials must not be from a field, i.e. the fraction free reduction is
 * implemented. Implements normalform.
 * @param  coefficient type
 * @author Heinz Kredel
 */

public class PseudoReductionSeq> extends ReductionAbstract implements
                PseudoReduction {


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


    /**
     * Constructor.
     */
    public PseudoReductionSeq() {
    }


    /**
     * Normalform.
     * @param Ap polynomial.
     * @param Pp polynomial list.
     * @return nf(Ap) with respect to Pp.
     */
    @SuppressWarnings("unchecked")
    public GenPolynomial normalform(List> Pp, GenPolynomial Ap) {
        if (Pp == null || Pp.isEmpty()) {
            return Ap;
        }
        if (Ap == null || Ap.isZERO()) {
            return Ap;
        }
        Map.Entry m;
        GenPolynomial[] P = new GenPolynomial[0];
        synchronized (Pp) {
            P = Pp.toArray(P);
        }
        int l = P.length;
        ExpVector[] htl = new ExpVector[l];
        C[] lbc = (C[]) new RingElem[l];
        GenPolynomial[] p = new GenPolynomial[l];
        int i;
        int j = 0;
        for (i = 0; i < l; i++) {
            if (P[i] == null) {
                continue;
            }
            p[i] = P[i];
            m = p[i].leadingMonomial();
            if (m != null) {
                p[j] = p[i];
                htl[j] = m.getKey();
                lbc[j] = m.getValue();
                j++;
            }
        }
        l = j;
        ExpVector e;
        C a;
        boolean mt = false;
        GenPolynomial R = Ap.ring.getZERO().copy();

        GenPolynomial S = Ap.copy();
        while (S.length() > 0) {
            m = S.leadingMonomial();
            e = m.getKey();
            a = m.getValue();
            for (i = 0; i < l; i++) {
                mt = e.multipleOf(htl[i]);
                if (mt)
                    break;
            }
            if (!mt) {
                //logger.debug("irred");
                //R = R.sum(a, e);
                //S = S.subtract(a, e);
                R.doPutToMap(e, a);
                S.doRemoveFromMap(e, a);
                //System.out.println(" S = " + S);
            } else {
                e = e.subtract(htl[i]);
                //logger.info("red div = " + e);
                @SuppressWarnings("cast")
                C c = (C) lbc[i];
                if (a.remainder(c).isZERO()) { //c.isUnit() ) {
                    a = a.divide(c);
                    S = S.subtractMultiple(a, e, p[i]);
                } else {
                    R = R.multiply(c);
                    //S = S.multiply(c);
                    S = S.scaleSubtractMultiple(c, a, e, p[i]);
                }
                //Q = p[i].multiply(a, e);
                //S = S.subtract(Q);
            }
        }
        return R;
    }


    /**
     * Normalform.
     * @param Pp polynomial list.
     * @param Ap polynomial.
     * @return ( nf(Ap), mf ) with respect to Pp and mf as multiplication factor
     *         for Ap.
     */
    @SuppressWarnings("unchecked")
    public PseudoReductionEntry normalformFactor(List> Pp, GenPolynomial Ap) {
        if (Ap == null) {
            return null;
        }
        C mfac = Ap.ring.getONECoefficient();
        PseudoReductionEntry pf = new PseudoReductionEntry(Ap, mfac);
        if (Pp == null || Pp.isEmpty()) {
            return pf;
        }
        if (Ap.isZERO()) {
            return pf;
        }
        Map.Entry m;
        GenPolynomial[] P = new GenPolynomial[0];
        synchronized (Pp) {
            P = Pp.toArray(P);
        }
        int l = P.length;
        ExpVector[] htl = new ExpVector[l];
        C[] lbc = (C[]) new RingElem[l]; // want C[] 
        GenPolynomial[] p = new GenPolynomial[l];
        int i;
        int j = 0;
        for (i = 0; i < l; i++) {
            if (P[i] == null) {
                continue;
            }
            p[i] = P[i];
            m = p[i].leadingMonomial();
            if (m != null) {
                p[j] = p[i];
                htl[j] = m.getKey();
                lbc[j] = m.getValue();
                j++;
            }
        }
        l = j;
        ExpVector e;
        C a;
        boolean mt = false;
        GenPolynomial R = Ap.ring.getZERO().copy();

        GenPolynomial S = Ap.copy();
        while (S.length() > 0) {
            m = S.leadingMonomial();
            e = m.getKey();
            a = m.getValue();
            for (i = 0; i < l; i++) {
                mt = e.multipleOf(htl[i]);
                if (mt)
                    break;
            }
            if (!mt) {
                //logger.debug("irred");
                //R = R.sum(a, e);
                //S = S.subtract(a, e);
                R.doPutToMap(e, a);
                S.doRemoveFromMap(e, a);
                //System.out.println(" S = " + S);
            } else {
                e = e.subtract(htl[i]);
                //logger.info("red div = " + e);
                C c = lbc[i];
                if (a.remainder(c).isZERO()) { //c.isUnit() ) {
                    a = a.divide(c);
                    S = S.subtractMultiple(a, e, p[i]);
                } else {
                    mfac = mfac.multiply(c);
                    R = R.multiply(c);
                    //S = S.multiply(c);
                    S = S.scaleSubtractMultiple(c, a, e, p[i]);
                }
                //Q = p[i].multiply(a, e);
                //S = S.subtract(Q);
            }
        }
        if (logger.isInfoEnabled()) {
            logger.info("multiplicative factor = " + mfac);
        }
        pf = new PseudoReductionEntry(R, mfac);
        return pf;
    }


    /**
     * Normalform with recording. Note: Only meaningful if all divisions
     * are exact. Compute first the multiplication factor m with
     * normalform(Pp,Ap,m), then call this method with
     * normalform(row,Pp,m*Ap).
     * @param row recording matrix, is modified.
     * @param Pp a polynomial list for reduction.
     * @param Ap a polynomial.
     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
     */
    @SuppressWarnings("unchecked")
    public GenPolynomial normalform(List> row, List> Pp,
                    GenPolynomial Ap) {
        if (Pp == null || Pp.isEmpty()) {
            return Ap;
        }
        if (Ap == null || Ap.isZERO()) {
            return Ap;
        }
        GenPolynomial[] P = new GenPolynomial[0];
        synchronized (Pp) {
            P = Pp.toArray(P);
        }
        int l = P.length;
        ExpVector[] htl = new ExpVector[l];
        Object[] lbc = new Object[l]; // want C 
        GenPolynomial[] p = new GenPolynomial[l];
        Map.Entry m;
        int j = 0;
        int i;
        for (i = 0; i < l; i++) {
            p[i] = P[i];
            m = p[i].leadingMonomial();
            if (m != null) {
                p[j] = p[i];
                htl[j] = m.getKey();
                lbc[j] = m.getValue();
                j++;
            }
        }
        l = j;
        ExpVector e;
        C a;
        boolean mt = false;
        GenPolynomial zero = Ap.ring.getZERO();
        GenPolynomial R = Ap.ring.getZERO().copy();
        GenPolynomial fac = null;
        GenPolynomial S = Ap.copy();
        while (S.length() > 0) {
            m = S.leadingMonomial();
            e = m.getKey();
            a = m.getValue();
            for (i = 0; i < l; i++) {
                mt = e.multipleOf(htl[i]);
                if (mt)
                    break;
            }
            if (!mt) {
                //logger.debug("irred");
                //R = R.sum(a, e);
                //S = S.subtract(a, e);
                R.doPutToMap(e, a);
                S.doRemoveFromMap(e, a);
                // System.out.println(" S = " + S);
                //throw new RuntimeException("Syzygy no GB");
            } else {
                e = e.subtract(htl[i]);
                //logger.info("red div = " + e);
                C c = (C) lbc[i];
                if (a.remainder(c).isZERO()) { //c.isUnit() ) {
                    a = a.divide(c);
                    S = S.subtractMultiple(a, e, p[i]);
                    //System.out.print("|");
                } else {
                    //System.out.print("*");
                    R = R.multiply(c);
                    //S = S.multiply(c);
                    S = S.scaleSubtractMultiple(c, a, e, p[i]);
                }
                //Q = p[i].multiply(a, e);
                //S = S.subtract(Q);
                fac = row.get(i);
                if (fac == null) {
                    fac = zero.sum(a, e);
                } else {
                    fac = fac.sum(a, e);
                }
                row.set(i, fac);
            }
        }
        return R;
    }

}