/*
 * $Id$
 */

package edu.jas.application;


import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.apache.log4j.Logger;

import edu.jas.arith.Rational;
import edu.jas.poly.Complex;
import edu.jas.poly.ComplexRing;
import edu.jas.poly.GenPolynomial;
import edu.jas.poly.GenPolynomialRing;
import edu.jas.poly.PolyUtil;
import edu.jas.poly.TermOrder;
import edu.jas.root.Interval;
import edu.jas.root.RealRootTuple;
import edu.jas.structure.GcdRingElem;
import edu.jas.structure.RingFactory;
import edu.jas.ufd.SquarefreeAbstract;
import edu.jas.ufd.SquarefreeFactory;


/**
 * Roots factory.
 * @author Heinz Kredel
 */
public class RootFactory {


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


    private static boolean debug = logger.isDebugEnabled();


    /**
     * Is complex algebraic number a root of a polynomial.
     * @param f univariate polynomial.
     * @param r complex algebraic number.
     * @return true, if f(r) == 0, else false;
     */
    public static  & Rational> boolean isRootRealCoeff(GenPolynomial f,
                    Complex> r) {
        RingFactory cfac = f.ring.coFac;
        ComplexRing ccfac = new ComplexRing(cfac);
        GenPolynomialRing> facc = new GenPolynomialRing>(ccfac, f.ring);
        GenPolynomial> fc = PolyUtil. complexFromAny(facc, f);
        return isRoot(fc, r);
    }


    /**
     * Is complex algebraic number a root of a polynomial.
     * @param f univariate polynomial.
     * @param r complex algebraic number.
     * @return true, if f(r) == 0, else false;
     */
    public static  & Rational> boolean isRoot(GenPolynomial> f,
                    Complex> r) {
        ComplexRing> cr = r.factory();
        GenPolynomialRing>> cfac = new GenPolynomialRing>>(
                        cr, f.factory());
        GenPolynomial>> p;
        p = PolyUtilApp. convertToComplexRealCoefficients(cfac, f);
        // test algebraic part
        Complex> a = PolyUtil.>> evaluateMain(cr, p, r);
        boolean t = a.isZERO();
        if (!t) {
            logger.info("f(r) = " + a + ", f = " + f + ", r  = " + r);
            return t;
        }
        // test approximation, not working
        RealAlgebraicRing rring = (RealAlgebraicRing) cr.ring;
        RealRootTuple rroot = rring.getRoot();
        List> rlist = rroot.tuple;
        //System.out.println("rlist = " + rlist);
        Interval vr = rlist.get(0).ring.getRoot();
        Interval vi = rlist.get(1).ring.getRoot();
        ComplexRing ccfac = new ComplexRing((RingFactory) vr.left.factory());
        Complex sw = new Complex(ccfac, vr.left, vi.left);
        Complex ne = new Complex(ccfac, vr.right, vi.right);
        Complex epsw = PolyUtil.> evaluateMain(ccfac, f, sw);
        Complex epne = PolyUtil.> evaluateMain(ccfac, f, ne);
        int rootre = (epsw.getRe().signum() * epne.getRe().signum());
        int rootim = (epsw.getIm().signum() * epne.getIm().signum());
        t = (rootre <= 0 && rootim <= 0);
        //logger.info("p(root): p = " + f + ", r = " + r.getRe() + " i " + r.getIm());
        //logger.info("r = " + new BigDecimal(r.getRe().magnitude()) + " i " + new BigDecimal(r.getIm().magnitude()));
        //logger.info("vr = " + vr + ", vi = " + vi);
        //logger.info("sw   = " + sw   + ", ne   = " + ne);
        //logger.info("root(re) = " + rootre + ", root(im) = " + rootim);
        //logger.info("epsw   = " + new BigDecimal(epsw.getRe().getRational()) + " i " + new BigDecimal(epsw.getIm().getRational()));
        //logger.info("epne   = " + new BigDecimal(epne.getRe().getRational()) + " i " + new BigDecimal(epne.getIm().getRational()));
        return true;
    }


    /**
     * Is complex algebraic number a root of a polynomial.
     * @param f univariate polynomial.
     * @param R list of complex algebraic numbers.
     * @return true, if f(r) == 0 for all r in R, else false;
     */
    public static  & Rational> boolean isRoot(GenPolynomial> f,
                    List>> R) {
        for (Complex> r : R) {
            boolean t = isRoot(f, r);
            if (!t) {
                return false;
            }
        }
        return true;
    }


    /**
     * Complex algebraic number roots.
     * @param f univariate polynomial.
     * @return a list of different complex algebraic numbers, with f(c) == 0 for
     *         c in roots.
     */
    public static  & Rational> List>> complexAlgebraicNumbersComplex(
                    GenPolynomial> f) {
        GenPolynomialRing> pfac = f.factory();
        if (pfac.nvar != 1) {
            throw new IllegalArgumentException("only for univariate polynomials");
        }
        ComplexRing cfac = (ComplexRing) pfac.coFac;
        SquarefreeAbstract> engine = SquarefreeFactory.> getImplementation(cfac);
        Map>, Long> F = engine.squarefreeFactors(f.monic());
        Set>> S = F.keySet();
        //System.out.println("S = " + S);
        List>> list = new ArrayList>>();
        for (GenPolynomial> sp : S) {
            if (sp.isConstant() || sp.isZERO()) {
                continue;
            }
            List>> ls = RootFactory. complexAlgebraicNumbersSquarefree(sp);
            long m = F.get(sp);
            for (long i = 0L; i < m; i++) {
                list.addAll(ls);
            }
        }
        return list;
    }


    /**
     * Complex algebraic number roots.
     * @param f univariate squarefree polynomial.
     * @return a list of different complex algebraic numbers, with f(c) == 0 for
     *         c in roots.
     */
    public static  & Rational> 
      List>> complexAlgebraicNumbersSquarefree(
                   GenPolynomial> f) {
        GenPolynomialRing> pfac = f.factory();
        if (pfac.nvar != 1) {
            throw new IllegalArgumentException("only for univariate polynomials");
        }
        ComplexRing cfac = (ComplexRing) pfac.coFac;
        TermOrder to = new TermOrder(TermOrder.INVLEX);
        GenPolynomialRing> tfac = new GenPolynomialRing>(cfac, 2, to); //,vars); //tord?
        //System.out.println("tfac = " + tfac);
        GenPolynomial> t = tfac.univariate(1, 1L).sum(
                        tfac.univariate(0, 1L).multiply(cfac.getIMAG()));
        //System.out.println("t = " + t); // t = x + i y
        GenPolynomialRing rfac = new GenPolynomialRing(cfac.ring, tfac); //tord?
        //System.out.println("rfac = " + rfac);
        List>> list = new ArrayList>>();
        GenPolynomial> sp = f;
        if (sp.isConstant() || sp.isZERO()) {
            return list;
        }
        // substitute t = x + i y
        GenPolynomial> su = PolyUtil.> substituteUnivariate(sp, t);
        //System.out.println("su = " + su);
        su = su.monic();
        //System.out.println("su = " + su);
        GenPolynomial re = PolyUtil. realPartFromComplex(rfac, su);
        GenPolynomial im = PolyUtil. imaginaryPartFromComplex(rfac, su);
        if (debug) {
            logger.debug("rfac = " + rfac.toScript());
            logger.debug("t  = " + t + ", re = " + re.toScript() + ", im = " + im.toScript());
        }
        List> li = new ArrayList>(2);
        li.add(re);
        li.add(im);
        Ideal id = new Ideal(rfac, li);
        //System.out.println("id = " + id);

        List> idul = id.zeroDimRootDecomposition();

        IdealWithRealAlgebraicRoots idr;
        for (IdealWithUniv idu : idul) {
            //System.out.println("---idu = " + idu);
            idr = PolyUtilApp. realAlgebraicRoots(idu);
            //System.out.println("---idr = " + idr);
            for (List> crr : idr.ran) {
                //System.out.println("crr = " + crr);
                RealRootTuple root = new RealRootTuple(crr);
                //System.out.println("root = " + root);
                RealAlgebraicRing car = new RealAlgebraicRing(idu, root);
                //System.out.println("car = " + car);
                List> gens = car.generators();
                //System.out.println("gens = " + gens);
                int sg = gens.size();
                RealAlgebraicNumber rre = gens.get(sg - 2);
                RealAlgebraicNumber rim = gens.get(sg - 1);
                ComplexRing> cring = new ComplexRing>(car);
                Complex> crn = new Complex>(cring, rre, rim);
                //System.out.println("crn = " + crn + " in " + crn.ring);

                //boolean it;
                //int count = 0;
                //do { // refine intervals if necessary, not meaningful
                //    Interval vr = crr.get(0).ring.getRoot();
                //    Interval vi = crr.get(1).ring.getRoot();
                //    ComplexRing ccfac = new ComplexRing((RingFactory) vr.left.factory());
                //    Complex sw = new Complex(ccfac, vr.left, vi.left);
                //    Complex ne = new Complex(ccfac, vr.right, vi.right);
                //    Complex epsw = PolyUtil.> evaluateMain(ccfac, f, sw);
                //    Complex epne = PolyUtil.> evaluateMain(ccfac, f, ne);
                //    int rootre = (epsw.getRe().signum() * epne.getRe().signum());
                //    int rootim = (epsw.getIm().signum() * epne.getIm().signum());
                //    it = true || (rootre <= 0 && rootim <= 0); // TODO
                //    if (!it) {
                //        logger.info("refine intervals: vr = " + vr + ", vi = " + vi); // + ", crn = " + crn.ring);
                //        crn.getRe().ring.realRing.halfInterval();
                //        //System.out.println("crn.re = " + crn.getRe().ring.realRing);
                //        crn.getIm().ring.realRing.halfInterval();
                //        //System.out.println("crn.im = " + crn.getIm().ring.realRing);
                //        if (count++ > 2) {
                //            //throw new RuntimeException("no roots of " + f);
                //            logger.info("break in root refinement of " + crn + " in " + crn.ring);
                //            it = true;
                //        }
                //    }
                //} while (!it);
                list.add(crn);
            }
        }
        return list;
    }


    /* todo
     * Complex algebraic numbers.
     * @param f univariate polynomial.
     * @param eps rational precision.
     * @return a list of different complex algebraic numbers.
     public static  & Rational> 
     List> complexAlgebraicNumbersComplex(GenPolynomial> f, BigRational eps) {
     }
    */

}