/*
 * $Id$
 */

package edu.jas.fd;


import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;

import org.apache.log4j.Logger;

import edu.jas.gbmod.SolvableSyzygyAbstract;
import edu.jas.poly.GenPolynomial;
import edu.jas.poly.GenSolvablePolynomial;
import edu.jas.poly.GenSolvablePolynomialRing;
import edu.jas.poly.PolyUtil;
import edu.jas.poly.RecSolvablePolynomial;
import edu.jas.poly.RecSolvablePolynomialRing;
import edu.jas.structure.GcdRingElem;
import edu.jas.structure.RingFactory;
import edu.jas.ufd.GCDFactory;


/**
 * (Non-unique) factorization domain greatest common divisor common algorithms.
 * @param  coefficient type
 * @author Heinz Kredel
 */

public abstract class GreatestCommonDivisorAbstract> implements
                GreatestCommonDivisor {


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


    private final boolean debug = logger.isDebugEnabled();


    /**
     * Engine for syzygy computation.
     */
    final SolvableSyzygyAbstract syz;


    /**
     * Engine for commutative gcd computation.
     */
    //edu.jas.ufd.GreatestCommonDivisorAbstract cgcd;


    /**
     * Constructor.
     */
    public GreatestCommonDivisorAbstract() {
        syz = new SolvableSyzygyAbstract();
        //cgcd = GCDFactory. getImplementation(pfac.coFac);
    }


    /**
     * Get the String representation.
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        return getClass().getName();
    }


    /**
     * GenSolvablePolynomial base coefficient content.
     * @param P GenSolvablePolynomial.
     * @return cont(P).
     */
    public C baseContent(GenSolvablePolynomial P) {
        if (P == null) {
            throw new IllegalArgumentException("P == null");
        }
        if (P.isZERO()) {
            return P.ring.getZEROCoefficient();
        }
        C d = null;
        for (C c : P.getMap().values()) {
            if (d == null) {
                d = c;
            } else {
                d = d.gcd(c);
            }
            if (d.isONE()) {
                return d;
            }
        }
        if (d.signum() < 0) {
            d = d.negate();
        }
        return d;
    }


    /**
     * GenSolvablePolynomial base coefficient primitive part.
     * @param P GenSolvablePolynomial.
     * @return pp(P).
     */
    public GenSolvablePolynomial basePrimitivePart(GenSolvablePolynomial P) {
        if (P == null) {
            throw new IllegalArgumentException("P == null");
        }
        if (P.isZERO()) {
            return P;
        }
        C d = baseContent(P);
        if (d.isONE()) {
            return P;
        }
        GenSolvablePolynomial pp = (GenSolvablePolynomial) P.divide(d);
        if (debug) {
            GenSolvablePolynomial p = pp.multiply(d);
            if (!p.equals(P)) {
                throw new ArithmeticException("pp(p)*cont(p) != p: ");
            }
        }
        return pp;
    }


    /**
     * Univariate GenSolvablePolynomial greatest common divisor. Uses sparse
     * pseudoRemainder for remainder.
     * @param P univariate GenSolvablePolynomial.
     * @param S univariate GenSolvablePolynomial.
     * @return gcd(P,S).
     */
    public abstract GenSolvablePolynomial baseGcd(GenSolvablePolynomial P, GenSolvablePolynomial S);


    /**
     * GenSolvablePolynomial recursive content.
     * @param P recursive GenSolvablePolynomial.
     * @return cont(P).
     */
    public GenSolvablePolynomial recursiveContent(GenSolvablePolynomial> P) {
        if (P == null) {
            throw new IllegalArgumentException("P == null");
        }
        if (P.isZERO()) {
            return (GenSolvablePolynomial) P.ring.getZEROCoefficient();
        }
        GenSolvablePolynomial d = null;
        for (GenPolynomial cp : P.getMap().values()) {
            GenSolvablePolynomial c = (GenSolvablePolynomial) cp;
            if (d == null) {
                d = c;
            } else {
                d = gcd(d, c); // go to recursion
            }
            if (d.isONE()) {
                return d;
            }
        }
        return (GenSolvablePolynomial) d.abs();
    }


    /**
     * GenSolvablePolynomial recursive primitive part.
     * @param P recursive GenSolvablePolynomial.
     * @return pp(P).
     */
    public GenSolvablePolynomial> recursivePrimitivePart(
                    GenSolvablePolynomial> P) {
        if (P == null) {
            throw new IllegalArgumentException("P == null");
        }
        if (P.isZERO()) {
            return P;
        }
        GenSolvablePolynomial d = recursiveContent(P);
        if (d.isONE()) {
            return P;
        }
        if(debug) {
           logger.info("content(P) = " + d);
        }
        GenSolvablePolynomial> pp = FDUtil. recursiveDivide(P, d);
        return pp;
    }


    /**
     * GenSolvablePolynomial base recursive content.
     * @param P recursive GenSolvablePolynomial.
     * @return baseCont(P).
     */
    public C baseRecursiveContent(GenSolvablePolynomial> P) {
        if (P == null) {
            throw new IllegalArgumentException("P == null");
        }
        if (P.isZERO()) {
            GenSolvablePolynomialRing cf = (GenSolvablePolynomialRing) P.ring.coFac;
            return cf.coFac.getZERO();
        }
        C d = null;
        for (GenPolynomial cp : P.getMap().values()) {
            GenSolvablePolynomial c = (GenSolvablePolynomial) cp;
            C cc = baseContent(c);
            if (d == null) {
                d = cc;
            } else {
                d = gcd(d, cc);
            }
            if (d.isONE()) {
                return d;
            }
        }
        if (d.signum() < 0) {
            d = d.negate();
        }
        return d;
    }


    /**
     * GenSolvablePolynomial base recursive primitive part.
     * @param P recursive GenSolvablePolynomial.
     * @return basePP(P).
     */
    public GenSolvablePolynomial> baseRecursivePrimitivePart(
                    GenSolvablePolynomial> P) {
        if (P == null) {
            throw new IllegalArgumentException("P == null");
        }
        if (P.isZERO()) {
            return P;
        }
        C d = baseRecursiveContent(P);
        if (d.isONE()) {
            return P;
        }
        GenSolvablePolynomial> pp = (GenSolvablePolynomial>) PolyUtil
                        . baseRecursiveDivide(P, d);
        return pp;
    }


    /**
     * GenSolvablePolynomial recursive greatest common divisor. Uses
     * pseudoRemainder for remainder.
     * @param P recursive GenSolvablePolynomial.
     * @param S recursive GenSolvablePolynomial.
     * @return gcd(P,S).
     */
    public GenSolvablePolynomial> recursiveGcd(GenSolvablePolynomial> P,
                    GenSolvablePolynomial> S) {
        if (S == null || S.isZERO()) {
            return P;
        }
        if (P == null || P.isZERO()) {
            return S;
        }
        if (P.ring.nvar <= 1) {
            return recursiveUnivariateGcd(P, S);
        }
        // distributed polynomials gcd
        GenSolvablePolynomialRing> rfac = P.ring;
        GenSolvablePolynomialRing dfac;
        if (rfac instanceof RecSolvablePolynomialRing) {
            RecSolvablePolynomialRing rf = (RecSolvablePolynomialRing) rfac;
            dfac = RecSolvablePolynomialRing. distribute(rf);
        } else {
            GenSolvablePolynomialRing df = (GenSolvablePolynomialRing) rfac;
            dfac = df.distribute();
        }
        GenSolvablePolynomial Pd = (GenSolvablePolynomial) PolyUtil. distribute(dfac, P);
        GenSolvablePolynomial Sd = (GenSolvablePolynomial) PolyUtil. distribute(dfac, S);
        GenSolvablePolynomial Dd = gcd(Pd, Sd);
        // convert to recursive
        GenSolvablePolynomial> C 
            = (GenSolvablePolynomial>) PolyUtil. recursive(rfac, Dd);
        return C;
    }


    /**
     * Univariate GenSolvablePolynomial recursive greatest common divisor. Uses
     * pseudoRemainder for remainder.
     * @param P univariate recursive GenSolvablePolynomial.
     * @param S univariate recursive GenSolvablePolynomial.
     * @return gcd(P,S).
     */
    public abstract GenSolvablePolynomial> recursiveUnivariateGcd(
                    GenSolvablePolynomial> P, GenSolvablePolynomial> S);


    /**
     * GenSolvablePolynomial content.
     * @param P GenSolvablePolynomial.
     * @return cont(P).
     */
    public GenSolvablePolynomial content(GenSolvablePolynomial P) {
        if (P == null) {
            throw new IllegalArgumentException("P == null");
        }
        GenSolvablePolynomialRing pfac = P.ring;
        if (pfac.nvar <= 1) {
            // baseContent not possible by return type
            throw new IllegalArgumentException("use baseContent() for univariate polynomials");
        }
        GenSolvablePolynomialRing> rfac // = (RecSolvablePolynomialRing) 
            = pfac.recursive(1);

        GenSolvablePolynomial> Pr 
            = (RecSolvablePolynomial) PolyUtil. recursive(rfac, P);
        GenSolvablePolynomial D = recursiveContent(Pr);
        return D;
    }


    /**
     * GenSolvablePolynomial primitive part.
     * @param P GenSolvablePolynomial.
     * @return pp(P).
     */
    public GenSolvablePolynomial primitivePart(GenSolvablePolynomial P) {
        if (P == null) {
            throw new IllegalArgumentException("P == null");
        }
        if (P.isZERO()) {
            return P;
        }
        GenSolvablePolynomialRing pfac = P.ring;
        if (pfac.nvar <= 1) {
            return basePrimitivePart(P);
        }
        GenSolvablePolynomialRing> rfac = /*(RecSolvablePolynomialRing)*/pfac.recursive(1);

        GenSolvablePolynomial> Pr = (RecSolvablePolynomial) PolyUtil. recursive(rfac, P);
        GenSolvablePolynomial> PP = recursivePrimitivePart(Pr);

        GenSolvablePolynomial D = (GenSolvablePolynomial) PolyUtil. distribute(pfac, PP);
        return D;
    }


    /**
     * GenSolvablePolynomial division. Indirection to GenSolvablePolynomial
     * method.
     * @param a GenSolvablePolynomial.
     * @param b coefficient.
     * @return a/b.
     */
    public GenSolvablePolynomial divide(GenSolvablePolynomial a, C b) {
        if (b == null || b.isZERO()) {
            throw new IllegalArgumentException("division by zero");

        }
        if (a == null || a.isZERO()) {
            return a;
        }
        return (GenSolvablePolynomial) a.divide(b);
    }


    /**
     * Coefficient greatest common divisor. Indirection to coefficient method.
     * @param a coefficient.
     * @param b coefficient.
     * @return gcd(a,b).
     */
    public C gcd(C a, C b) {
        if (b == null || b.isZERO()) {
            return a;
        }
        if (a == null || a.isZERO()) {
            return b;
        }
        return a.gcd(b);
    }


    /**
     * GenSolvablePolynomial greatest common divisor.
     * @param P GenSolvablePolynomial.
     * @param S GenSolvablePolynomial.
     * @return gcd(P,S).
     */
    public GenSolvablePolynomial gcd(GenSolvablePolynomial P, GenSolvablePolynomial S) {
        if (S == null || S.isZERO()) {
            return P;
        }
        if (P == null || P.isZERO()) {
            return S;
        }
        GenSolvablePolynomialRing pfac = P.ring;
        if (pfac.nvar <= 1) {
            GenSolvablePolynomial T = baseGcd(P, S);
            return T;
        }
        GenSolvablePolynomialRing> rfac = /*(RecSolvablePolynomialRing)*/pfac.recursive(1);

        GenSolvablePolynomial> Pr = (RecSolvablePolynomial) PolyUtil. recursive(rfac, P);
        GenSolvablePolynomial> Sr = (RecSolvablePolynomial) PolyUtil. recursive(rfac, S);
        GenSolvablePolynomial> Dr = recursiveUnivariateGcd(Pr, Sr);
        GenSolvablePolynomial D = (GenSolvablePolynomial) PolyUtil. distribute(pfac, Dr);
        return D;
    }


    /**
     * GenSolvablePolynomial least common multiple.
     * @param P GenSolvablePolynomial.
     * @param S GenSolvablePolynomial.
     * @return lcm(P,S).
     */
    public GenSolvablePolynomial lcm(GenSolvablePolynomial P, GenSolvablePolynomial S) {
        GenSolvablePolynomial[] oc = leftOreCond(P,S);
        return oc[0].multiply(P);
        //throw new UnsupportedOperationException("lcm not implemented");
    }


    /**
     * List of GenSolvablePolynomials greatest common divisor.
     * @param A non empty list of GenSolvablePolynomials.
     * @return gcd(A_i).
     */
    public GenSolvablePolynomial gcd(List> A) {
        if (A == null || A.isEmpty()) {
            throw new IllegalArgumentException("A may not be empty");
        }
        GenSolvablePolynomial g = A.get(0);
        for (int i = 1; i < A.size(); i++) {
            GenSolvablePolynomial f = A.get(i);
            g = gcd(g, f);
        }
        return g;
    }


    /**
     * GenSolvablePolynomial co-prime list.
     * @param A list of GenSolvablePolynomials.
     * @return B with gcd(b,c) = 1 for all b != c in B and for all non-constant
     *         a in A there exists b in B with b|a. B does not contain zero or
     *         constant polynomials.
     */
    public List> coPrime(List> A) {
        if (A == null || A.isEmpty()) {
            return A;
        }
        List> B = new ArrayList>(A.size());
        // make a coprime to rest of list
        GenSolvablePolynomial a = A.get(0);
        //System.out.println("a = " + a);
        if (!a.isZERO() && !a.isConstant()) {
            for (int i = 1; i < A.size(); i++) {
                GenSolvablePolynomial b = A.get(i);
                GenSolvablePolynomial g = (GenSolvablePolynomial) gcd(a, b).abs();
                if (!g.isONE()) {
                    a = FDUtil. basePseudoQuotient(a, g);
                    b = FDUtil. basePseudoQuotient(b, g);
                    GenSolvablePolynomial gp = (GenSolvablePolynomial) gcd(a, g); //.abs();
                    while (!gp.isONE()) {
                        a = FDUtil. basePseudoQuotient(a, gp);
                        g = FDUtil. basePseudoQuotient(g, gp);
                        B.add(g); // gcd(a,g) == 1
                        g = gp;
                        gp = (GenSolvablePolynomial) gcd(a, gp); //.abs();
                    }
                    if (!g.isZERO() && !g.isConstant() /*&& !B.contains(g)*/) {
                        B.add(g); // gcd(a,g) == 1
                    }
                }
                if (!b.isZERO() && !b.isConstant()) {
                    B.add(b); // gcd(a,b) == 1
                }
            }
        } else {
            B.addAll(A.subList(1, A.size()));
        }
        // make rest coprime
        B = coPrime(B);
        //System.out.println("B = " + B);
        if (!a.isZERO() && !a.isConstant() /*&& !B.contains(a)*/) {
            a = (GenSolvablePolynomial) a.abs();
            B.add(a);
        }
        return B;
    }


    /**
     * GenSolvablePolynomial co-prime list.
     * @param A list of GenSolvablePolynomials.
     * @return B with gcd(b,c) = 1 for all b != c in B and for all non-constant
     *         a in A there exists b in B with b|a. B does not contain zero or
     *         constant polynomials.
     */
    public List> coPrimeRec(List> A) {
        if (A == null || A.isEmpty()) {
            return A;
        }
        List> B = new ArrayList>();
        // make a co-prime to rest of list
        for (GenSolvablePolynomial a : A) {
            //System.out.println("a = " + a);
            B = coPrime(a, B);
            //System.out.println("B = " + B);
        }
        return B;
    }


    /**
     * GenSolvablePolynomial co-prime list.
     * @param a GenSolvablePolynomial.
     * @param P co-prime list of GenSolvablePolynomials.
     * @return B with gcd(b,c) = 1 for all b != c in B and for non-constant a
     *         there exists b in P with b|a. B does not contain zero or constant
     *         polynomials.
     */
    public List> coPrime(GenSolvablePolynomial a, List> P) {
        if (a == null || a.isZERO() || a.isConstant()) {
            return P;
        }
        List> B = new ArrayList>(P.size() + 1);
        // make a coprime to elements of the list P
        for (int i = 0; i < P.size(); i++) {
            GenSolvablePolynomial b = P.get(i);
            GenSolvablePolynomial g = (GenSolvablePolynomial) gcd(a, b); //.abs();
            if (!g.isONE()) {
                a = FDUtil. basePseudoQuotient(a, g);
                b = FDUtil. basePseudoQuotient(b, g);
                // make g co-prime to new a, g is co-prime to c != b in P, B
                GenSolvablePolynomial gp = (GenSolvablePolynomial) gcd(a, g); //.abs();
                while (!gp.isONE()) {
                    a = FDUtil. basePseudoQuotient(a, gp);
                    g = FDUtil. basePseudoQuotient(g, gp);
                    if (!g.isZERO() && !g.isConstant() /*&& !B.contains(g)*/) {
                        B.add(g); // gcd(a,g) == 1 and gcd(g,c) == 1 for c != b in P, B
                    }
                    g = gp;
                    gp = (GenSolvablePolynomial) gcd(a, gp); //.abs();
                }
                // make new g co-prime to new b
                gp = (GenSolvablePolynomial) gcd(b, g); //.abs();
                while (!gp.isONE()) {
                    b = FDUtil. basePseudoQuotient(b, gp);
                    g = FDUtil. basePseudoQuotient(g, gp);
                    if (!g.isZERO() && !g.isConstant() /*&& !B.contains(g)*/) {
                        B.add(g); // gcd(a,g) == 1 and gcd(g,c) == 1 for c != b in P, B
                    }
                    g = gp;
                    gp = (GenSolvablePolynomial) gcd(b, gp); //.abs();
                }
                if (!g.isZERO() && !g.isConstant() /*&& !B.contains(g)*/) {
                    B.add(g); // gcd(a,g) == 1 and gcd(g,c) == 1 for c != b in P, B
                }
            }
            if (!b.isZERO() && !b.isConstant() /*&& !B.contains(b)*/) {
                B.add(b); // gcd(a,b) == 1 and gcd(b,c) == 1 for c != b in P, B
            }
        }
        if (!a.isZERO() && !a.isConstant() /*&& !B.contains(a)*/) {
            B.add(a);
        }
        return B;
    }


    /**
     * GenSolvablePolynomial test for co-prime list.
     * @param A list of GenSolvablePolynomials.
     * @return true if gcd(b,c) = 1 for all b != c in B, else false.
     */
    public boolean isCoPrime(List> A) {
        if (A == null || A.isEmpty()) {
            return true;
        }
        if (A.size() == 1) {
            return true;
        }
        for (int i = 0; i < A.size(); i++) {
            GenSolvablePolynomial a = A.get(i);
            for (int j = i + 1; j < A.size(); j++) {
                GenSolvablePolynomial b = A.get(j);
                GenSolvablePolynomial g = gcd(a, b);
                if (!g.isONE()) {
                    System.out.println("not co-prime, a: " + a);
                    System.out.println("not co-prime, b: " + b);
                    System.out.println("not co-prime, g: " + g);
                    return false;
                }
            }
        }
        return true;
    }


    /**
     * GenSolvablePolynomial test for co-prime list of given list.
     * @param A list of GenSolvablePolynomials.
     * @param P list of co-prime GenSolvablePolynomials.
     * @return true if isCoPrime(P) and for all a in A exists p in P with p | a,
     *         else false.
     */
    public boolean isCoPrime(List> P, List> A) {
        if (!isCoPrime(P)) {
            return false;
        }
        if (A == null || A.isEmpty()) {
            return true;
        }
        for (GenSolvablePolynomial q : A) {
            if (q.isZERO() || q.isConstant()) {
                continue;
            }
            boolean divides = false;
            for (GenSolvablePolynomial p : P) {
                GenSolvablePolynomial a = FDUtil. baseSparsePseudoRemainder(q, p);
                if (a.isZERO()) { // p divides q
                    divides = true;
                    break;
                }
            }
            if (!divides) {
                System.out.println("no divisor for: " + q);
                return false;
            }
        }
        return true;
    }


    /**
     * Univariate GenSolvablePolynomial extended greatest common divisor. Uses
     * sparse pseudoRemainder for remainder.
     * @param P univariate GenSolvablePolynomial.
     * @param S univariate GenSolvablePolynomial.
     * @return [ gcd(P,S), a, b ] with a*P + b*S = gcd(P,S).
     */
    @SuppressWarnings("unchecked")
    public GenSolvablePolynomial[] baseExtendedGcd(GenSolvablePolynomial P, GenSolvablePolynomial S) {
        //return P.egcd(S);
        GenSolvablePolynomial[] hegcd = baseHalfExtendedGcd(P, S);
        GenSolvablePolynomial[] ret = (GenSolvablePolynomial[]) new GenSolvablePolynomial[3];
        ret[0] = hegcd[0];
        ret[1] = hegcd[1];
        GenSolvablePolynomial x = (GenSolvablePolynomial) hegcd[0].subtract(hegcd[1].multiply(P));
        GenSolvablePolynomial[] qr = FDUtil. basePseudoQuotientRemainder(x, S);
        // assert qr[1].isZERO() 
        ret[2] = qr[0];
        return ret;
    }


    /**
     * Univariate GenSolvablePolynomial half extended greatest comon divisor.
     * Uses sparse pseudoRemainder for remainder.
     * @param S GenSolvablePolynomial.
     * @return [ gcd(P,S), a ] with a*P + b*S = gcd(P,S).
     */
    @SuppressWarnings("unchecked")
    public GenSolvablePolynomial[] baseHalfExtendedGcd(GenSolvablePolynomial P,
                    GenSolvablePolynomial S) {
        //if ( P == null ) {
        //    throw new IllegalArgumentException("null P not allowed");
        //}
        GenSolvablePolynomial[] ret = (GenSolvablePolynomial[]) new GenSolvablePolynomial[2];
        ret[0] = null;
        ret[1] = null;
        if (S == null || S.isZERO()) {
            ret[0] = P;
            ret[1] = P.ring.getONE();
            return ret;
        }
        if (P == null || P.isZERO()) {
            ret[0] = S;
            ret[1] = S.ring.getZERO();
            return ret;
        }
        if (P.ring.nvar != 1) {
            throw new IllegalArgumentException("for univariate polynomials only " + P.ring);
        }
        GenSolvablePolynomial q = P;
        GenSolvablePolynomial r = S;
        GenSolvablePolynomial c1 = P.ring.getONE().copy();
        GenSolvablePolynomial d1 = P.ring.getZERO().copy();
        while (!r.isZERO()) {
            GenSolvablePolynomial[] qr = FDUtil. basePseudoQuotientRemainder(q, r);
            //q.divideAndRemainder(r);
            q = qr[0];
            GenSolvablePolynomial x = (GenSolvablePolynomial) c1.subtract(q.multiply(d1));
            c1 = d1;
            d1 = x;
            q = r;
            r = qr[1];
        }
        // normalize ldcf(q) to 1, i.e. make monic
        C g = q.leadingBaseCoefficient();
        if (g.isUnit()) {
            C h = g.inverse();
            q = q.multiply(h);
            c1 = c1.multiply(h);
        }
        //assert ( ((c1.multiply(P)).remainder(S).equals(q) )); 
        ret[0] = q;
        ret[1] = c1;
        return ret;
    }


    /**
     * Univariate GenSolvablePolynomial greatest common divisor diophantine
     * version.
     * @param P univariate GenSolvablePolynomial.
     * @param S univariate GenSolvablePolynomial.
     * @param c univariate GenSolvablePolynomial.
     * @return [ a, b ] with a*P + b*S = c and deg(a) < deg(S).
     */
    @SuppressWarnings("unchecked")
    public GenSolvablePolynomial[] baseGcdDiophant(GenSolvablePolynomial P, GenSolvablePolynomial S,
                    GenSolvablePolynomial c) {
        GenSolvablePolynomial[] egcd = baseExtendedGcd(P, S);
        GenSolvablePolynomial g = egcd[0];
        GenSolvablePolynomial[] qr = FDUtil. basePseudoQuotientRemainder(c, g);
        if (!qr[1].isZERO()) {
            throw new ArithmeticException("not solvable, r = " + qr[1] + ", c = " + c + ", g = " + g);
        }
        GenSolvablePolynomial q = qr[0];
        GenSolvablePolynomial a = egcd[1].multiply(q);
        GenSolvablePolynomial b = egcd[2].multiply(q);
        if (!a.isZERO() && a.degree(0) >= S.degree(0)) {
            qr = FDUtil. basePseudoQuotientRemainder(a, S);
            a = qr[1];
            b = (GenSolvablePolynomial) b.sum(P.multiply(qr[0]));
        }
        GenSolvablePolynomial[] ret = (GenSolvablePolynomial[]) new GenSolvablePolynomial[2];
        ret[0] = a;
        ret[1] = b;

        if (debug) {
            GenSolvablePolynomial y = (GenSolvablePolynomial) ret[0].multiply(P)
                            .sum(ret[1].multiply(S));
            if (!y.equals(c)) {
                System.out.println("P  = " + P);
                System.out.println("S  = " + S);
                System.out.println("c  = " + c);
                System.out.println("a  = " + a);
                System.out.println("b  = " + b);
                System.out.println("y  = " + y);
                throw new ArithmeticException("not diophant, x = " + y.subtract(c));
            }
        }
        return ret;
    }


    /**
     * Coefficient left Ore condition. Generators for the left Ore condition of two 
     * coefficients. 
     * @param a coefficient.
     * @param b coefficient.
     * @return [oa, ob] = leftOreCond(a,b), with oa*a == ob*b.
     */
    public C[] leftOreCond(C a, C b) {
        if (a == null || a.isZERO() || b == null || b.isZERO()) {
            throw new IllegalArgumentException("a and b must be non zero");
        }
        C[] oc = (C[]) new GcdRingElem[2];
        if (a instanceof GenSolvablePolynomial && b instanceof GenSolvablePolynomial) {
            GenSolvablePolynomial ap = (GenSolvablePolynomial) a;
            GenSolvablePolynomial bp = (GenSolvablePolynomial) b;
            GenSolvablePolynomial[] ocp = leftOreCond(ap,bp);
            oc[0] = (C) ocp[0];
            oc[1] = (C) ocp[1];
            return oc;
        }
        RingFactory rf = (RingFactory) a.factory();
        if (a.equals(b)) {
            oc[0] = rf.getONE();
            oc[1] = rf.getONE();
            return oc;
        }
        if (rf.isCommutative()) {
            logger.info("left Ore condition on coefficients, commutative case: " + a + ", " + b);
            C gcd = a.gcd(b);
            C p = a.multiply(b);
            C lcm = p.divide(gcd);
            oc[0] = lcm.divide(a);
            oc[1] = lcm.divide(b);
            logger.info("Ore multiple: " + lcm + ", " + Arrays.toString(oc));
            return oc;
        }
        throw new UnsupportedOperationException("leftOreCond not implemented for " + rf.toScript());
        //return oc;
    }


    /** 
     * Left Ore condition. Generators for the left Ore condition of two solvable
     * polynomials.
     * @param a solvable polynomial
     * @param b solvable polynomial
     * @return [p,q] with p*a = q*b
     */
    public GenSolvablePolynomial[] leftOreCond(GenSolvablePolynomial a, GenSolvablePolynomial b) {
        if (a == null || a.isZERO() || b == null || b.isZERO()) {
            throw new IllegalArgumentException("a and b must be non zero");
        }
        GenSolvablePolynomialRing pfac = a.ring;
        GenSolvablePolynomial[] oc = (GenSolvablePolynomial[]) new GenSolvablePolynomial[2];
        if (a.equals(b)) {
            oc[0] = pfac.getONE();
            oc[1] = pfac.getONE();
            return oc;
        }
        if (pfac.isCommutative()) {
            logger.info("left Ore condition, polynomial commutative case: " + a + ", " + b);
            edu.jas.ufd.GreatestCommonDivisorAbstract cgcd = GCDFactory. getImplementation(pfac.coFac);
            GenSolvablePolynomial lcm = (GenSolvablePolynomial) cgcd.lcm(a, b);
            //oc[0] = FDUtil. basePseudoQuotient(lcm, a);
            //oc[1] = FDUtil. basePseudoQuotient(lcm, b);
            oc[0] = (GenSolvablePolynomial) PolyUtil. basePseudoDivide(lcm, a);
            oc[1] = (GenSolvablePolynomial) PolyUtil. basePseudoDivide(lcm, b);
            logger.info("Ore multiple: " + lcm + ", " + Arrays.toString(oc));
            return oc;
        }
        oc = syz.leftOreCond(a, b);
        //logger.info("Ore multiple: " + oc[0].multiply(a) + ", " + Arrays.toString(oc));
        return oc;
    }

}