/*
 * $Id$
 */

package edu.jas.gb;


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

import org.apache.log4j.Logger;

import edu.jas.poly.GenWordPolynomial;
import edu.jas.structure.RingElem;


/**
 * Non-commutative Groebner Bases abstract class. Implements common Groebner
 * bases and GB test methods.
 * @param  coefficient type
 * @author Heinz Kredel
 */

public abstract class WordGroebnerBaseAbstract> implements WordGroebnerBase {


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


    private final boolean debug = logger.isDebugEnabled();


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


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


    /**
     * Constructor.
     */
    public WordGroebnerBaseAbstract() {
        this(new WordReductionSeq());
    }


    /**
     * Constructor.
     * @param red Word Reduction engine
     */
    public WordGroebnerBaseAbstract(WordReduction red) {
        this(red, new OrderedWordPairlist());
    }


    /**
     * Constructor.
     * @param red Word Reduction engine
     * @param pl Word pair selection strategy
     */
    public WordGroebnerBaseAbstract(WordReduction red, WordPairList pl) {
        this.red = red;
        this.strategy = pl;
    }


    /**
     * Word Groebner base test.
     * @param F Word polynomial list.
     * @return true, if F is a Groebner base, else false.
     */
    public boolean isGB(List> F) {
        if (F == null || F.isEmpty()) {
            return true;
        }
        for (int i = 0; i < F.size(); i++) {
            GenWordPolynomial pi = F.get(i);
            for (int j = i + 1; j < F.size(); j++) {
                GenWordPolynomial pj = F.get(j);
                List> S = red.SPolynomials(pi, pj);
                if (S.isEmpty()) {
                    continue;
                }
                for (GenWordPolynomial s : S) {
                    GenWordPolynomial 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;
    }


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


    /**
     * 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 (GenWordPolynomial 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
        GenWordPolynomial 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 (GenWordPolynomial 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.leadingWord());
            }
            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 (GenWordPolynomial 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) {
            GenWordPolynomial a = G.remove(0);
            if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) {
                if (debug) {
                    logger.debug("top reducible polynomial " + a);
                }
                return false;
            }
            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) {
            GenWordPolynomial 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;
    }


    /**
     * Cleanup and terminate ThreadPool.
     */
    public void terminate() {
        logger.info("terminate not implemented");
    }


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

}