package maths;

import java.util.Vector;

import java.util.regex.Pattern;

import java.math.BigDecimal;

import java.math.MathContext;

import java.math.BigInteger;

import java.math.RoundingMode;

public class PolyBasic {

private static int MAXSTR = 100;

final private static double ZERO = 10E-6;

private static PolyBasic basic = new PolyBasic();

public static PolyBasic getInstance() {

return basic;

}

private TMono pp_plus(TMono p1, TMono p2, boolean es) {

if (p1 == null) return p2;

if (p2 == null) return p1;

TMono poly = null;

if (p1.x < p2.x || (p1.x == p2.x && p1.deg < p2.deg)) {

TMono t = p1;

p1 = p2;

p2 = t;

}

poly = p1;

if (p1.x > p2.x)// ||(p1.x == p2.x && p1.deg > p2.deg)) append to the last one.

{

while (p1.next != null && p1.deg != 0) p1 = p1.next;

if (p1.deg != 0) {

p1.next = new TMono();

p1.next.x = p1.x;

p1 = p1.next;

p1.coef = p2;

p1.next = null;

} else {

p1.coef = pp_plus(p1.coef, p2, true);

p1.next = null;

}

if (p1.coef == null) {

if (poly == p1)

poly = null;

else {

TMono t = poly;

while (t != null && t.next != p1)

t = t.next;

t.next = null;

}

}

} else {

if (p1.deg > p2.deg) {

p1.next = pp_plus(p1.next, p2, false);

} else if (Int(p1)) {

long v = p1.val + p2.val;

if (v == 0) return null;

p1.val = v;

} else { //p1.deg == p2.deg

p1.coef = pp_plus(p1.coef, p2.coef, true);

p1.next = pp_plus(p1.next, p2.next, false);

if (p1.coef == null) {

if (poly == p1)

poly = poly.next;

else {

TMono t = poly;

while (t != null && t.next != p1)

t = t.next;

t.next = p1.next;

}

}

}

}

if (poly != null && poly.coef == null && poly.deg != 0)

poly = poly.next;

if (es == true && poly != null && poly.deg == 0 && poly.x != 0)

poly = poly.coef;

return (poly);

}

private TMono pp_minus(TMono p1, TMono p2) {

TMono m = pp_plus(p1, cp_times(-1, p2), true);

return m;

}

private TMono cp_times(long c, TMono p1) {

if (p1 == null || c == 0) return null;

if (c == 1) return p1;

if (Int(p1)) {

p1.val = p1.val * c;

return p1;

}

TMono m = p1;

while (m != null) {

m.coef = cp_times(c, m.coef);

// if (m.deg == 0)

// m = m.coef;

// else

m = m.next;

// m.next = cp_times(c, p1.next);

}

return p1;

}

private TMono pp_times(TMono p1, TMono p2) //(m X n)

{

if (p1 == null || p2 == null) return null;

TMono tp = null;

if (Int(p2))

return cp_times(p2.val, p1);

if (Int(p1))

return cp_times(p1.val, p2);

if (p1.x > p2.x) {

tp = p1;

p1 = p2;

p2 = tp;

}

TMono poly = null;

while (p1 != null) {

tp = p1;

p1 = p1.next;

tp.next = null;

TMono tt;

if (p1 != null)

tt = mp_times(tp, p_copy(p2));

else {

if (tp.deg == 0 && tp.x != 0)

tp = tp.coef;

tt = mp_times(tp, p2);

}

while (tt != null && tt.deg == 0 && tt.x != 0)

tt = tt.coef;

while (tt != null && tt.x != 0 && tt.coef == null)

tt = tt.next;

poly = pp_plus(poly, tt, true);

}

return (poly);

}

private TMono mp_times(TMono p1, TMono p2) // p1.x <= p2.x

{

TMono poly = p2;

if (p1 == null || p2 == null) return null;

if (Int(p1)) return cp_times(p1.val, p2);

if (p1.x == p2.x) {

while (p2 != null) {

p2.deg += p1.deg;

if (p2.next != null)

p2.coef = pp_times(p_copy(p1.coef), p2.coef);

else

p2.coef = pp_times(p1.coef, p2.coef);

p2 = p2.next;

}

} else if (p1.x < p2.x) {

while (p2 != null) {

if (p2.next != null)

p2.coef = pp_times(p_copy(p1), p2.coef);

else

p2.coef = pp_times(p1, p2.coef);

p2 = p2.next;

}

} else {

System.out.println("Error,must p1.x < p2.x");

}

return (poly);

}

public boolean check_zero(TMono m) {

if (m == null) return false;

if (m.x == 0 && m.val == 0) return true;

while (m != null) {

if (check_zero(m.coef))

return true;

m = m.next;

}

return false;

}

public TMono rmz(TMono poly) {

// if (poly == null || poly.x == 0) return poly;

// check_zero(poly);

// TMono m1, m2;

// m1 = poly;

// m2 = null;

// while (m1 != null) {

// if (m1.x == 0) {

// } else if (m1.coef != null)

// m2 = m1;

// else {

// if (m1 == poly)

// poly = poly.next;

// else m2.next = m1.next;

// }

// m1 = m1.next;

// }

return poly;

}

public int deg(TMono p, int x) {

if (p.x == x) return p.deg;

if (p.x > x) {

int d1 = deg(p.coef, x);

int d2 = deg(p.next, x);

return d1 > d2 ? d1 : d2;

}

return 0;

}

public TMono reduce(TMono m, param[] p) {

if (m == null)

return null;

int x = m.x;

int d = m.deg;

m = p_copy(m);

int n = 0;

for (; n < p.length; n++) {

param pm = p[n];

if (pm != null && pm.xindex >= x)

break;

}

n--;

for (int i = n; i >= 0; i--) {

param pm = p[i];

if (pm != null && pm.m != null)

m = prem(m, p_copy(pm.m));

}

return m;

}

public TMono prem(TMono p1, TMono p2) {

TMono m = p_copy(p1.coef);

TMono n = p_copy(p2.coef);

TMono result = null;

if (p1.x == p2.x)

result = prem1(p1, p2);

else

result = prem3(p1, p2);

coefgcd(result);

factor1(result);

result = factor_remove(result, m);

result = factor_remove(result, n);

return result;

}

private int degree(TMono m, int x) {

if (m == null || m.x < x)

return 0;

while (m.x > x)

m = m.coef;

if (m != null && m.x == x)

return m.deg;

return 0;

}

private TMono prem3(TMono p1, TMono p2) { // p1.x > p2.x.

if (p2 == null)

return p1;

int x = p2.x;

if (x == 0)

return p1;

TMono[] mm = new TMono[2];

getm2(p1, x, p2.deg, mm);

while (mm[0] != null && mm[1] != null) {

int d1 = degree(mm[0], x);

int d2 = degree(p2, x);

if (p1 != null) {

if (d1 >= d2) {

int dd = d1 - d2;

TMono tp;

if (dd > 0) {

tp = pth(x, 1, dd);

tp = pp_times(tp, p_copy(p2));

} else

tp = p_copy(p2);

TMono l1 = ptimes(p_copy(mm[0].coef), mm[1]);

TMono t1 = pp_times(p1, p_copy(tp.coef));

TMono t2 = pp_times(l1, tp);

boolean r = false;

if (r) {

print(t1);

print(t2);

}

p1 = pp_minus(t1, t2);

coefgcd(p1);

if (p1 == null || p1.x < x) break;

}

}

if (p1 == null || p1.x < x) break;

mm[0] = mm[1] = null;

boolean r = false;

getm2(p1, x, p2.deg, mm);

if (check_zero(p1)) {

print(p1);

print(p2);

print(mm[0]);

print(mm[1]);

}

}

coefgcd(p1);

return p1;

}

private void getm2(TMono p, int x, int deg, TMono[] mm) {

if (p == null || p.x < x)

return;

if (p.x > x) {

while (p != null) {

getm2(p.coef, x, deg, mm);

if (mm[0] != null) {

TMono m = pth(p.x, 1, p.deg);

mm[1] = ptimes(mm[1], m);

return;

}

p = p.next;

}

} else if (p.deg >= deg) {

mm[0] = p;

mm[1] = pth(0, 1, 0);

return;

}

}

private TMono prem1(TMono p1, TMono p2) {

if (p1 == null)

return null;

TMono result = null;

if (p1.x < p2.x)

result = p1;

else if (p1.x > p2.x) {

result = p1;

while (p1 != null) {

TMono m1 = prem1(p1.coef, (p2));

p1.coef = m1;

p1 = p1.next;

}

} else if (p1.x == p2.x) {

if (p1.deg < p2.deg) {

TMono t = p1;

p1 = p_copy(p2);

p2 = t;

} else p2 = p_copy(p2);

if (p1.deg >= p2.deg) {

int x = p2.x;

while (p1 != null && p1.x >= x) {

int d1 = deg(p1);

int d2 = deg(p2);

if (d1 < d2) {

TMono m = p1;

p1 = p2;

p2 = m;

int t = d1;

d1 = d2;

d2 = t;

}

if (d1 >= d2) {

int dd = d1 - d2;

TMono tp;

if (dd > 0) {

tp = pth(x, 1, dd);

tp = pp_times(tp, p_copy(p2));

} else

tp = p_copy(p2);

p1 = pp_minus(pp_times(p1.next, tp.coef), pp_times(p1.coef, tp.next));

coefgcd(p1);

if (p1 == null) break;

}

}

result = p1;

}

}

while (result != null && result.x != 0 && result.coef == null)

result = result.next;

while (result != null && result.deg == 0 && result.x != 0)

result = result.coef;

// print(result);

return result;

}

public void div_factor1(TMono m, int x, int n) {

if (x > m.x) return;

if (x == m.x) {

while (m != null && m.deg != 0) {

m.deg -= n;

if (m.deg < 0) {

int k = 0;

}

m = m.next;

}

} else {

while (m != null) {

TMono mx = m.coef;

if (mx != null && mx.x != 0 && mx.deg != 0) {

div_factor1(mx, x, n);

if (mx.deg == 0)

m.coef = mx.coef;

}

m = m.next;

if (m != null && m.x == 0)

m = m.coef;

}

}

}

public void factor2(TMono m1) {

TMono m = this.get_factor2(m1);

if (m == null)

return;

while (m != null) {

if (m.x != 0) {

this.div_factor1(m1, m.x, m.deg);

}

m = m.coef;

}

}

public TMono get_factor2(TMono m) {

if (m == null)

return null;

TMono mx = null;

TMono m1 = m;

long n = 0;

while (m != null) {

if (m.x != 0)

n = factor_contain(m.x, m.deg, m1);

if (n != 0) {

if (mx == null)

mx = new TMono(m.x, 1, (int) n);

else

mx = this.pp_times(mx, new TMono(m.x, 1, (int) n));

}

m = m.coef;

}

return mx;

}

public void factor1(TMono m1) {

TMono m = this.get_factor1(m1);

if (m == null)

return;

while (m != null) {

if (m.x != 0) {

this.div_factor1(m1, m.x, m.deg);

}

m = m.coef;

}

}

public TMono get_factor1(TMono m) {

if (m == null)

return null;

TMono mx = null;

TMono m1 = m;

m = m.coef;

long n = 0;

while (m != null) {

if (m.x != 0)

n = factor_contain(m.x, m.deg, m1);

if (n != 0) {

if (mx == null)

mx = new TMono(m.x, 1, (int) n);

else

mx = this.pp_times(mx, new TMono(m.x, 1, (int) n));

}

m = m.coef;

}

return mx;

}

private long factor_contain(long x, long n, TMono m) {

if (m == null)

return n;

if (x > m.x) {

return 0;

} else if (x == m.x) {

while (m.next != null)

m = m.next;

if (m.x == 0 && m.coef != null)

return 0;

else if (m.deg == 0 && m.coef == null)

return n;

else

return Math.min(m.deg, n);

} else if (x < m.x) {

while (m != null) {

long t = factor_contain(x, n, m.coef);

if (t == 0)

return 0;

else if (t < n)

n = t;

m = m.next;

}

}

return n;

}

public TMono factor_remove(TMono p1, TMono p2) { // p1 ,p2 be destryoed.

if (p1 == null || p2 == null || plength(p1) > 1000)

return p1;

if (p1.x == p2.x)

return p1;

if (plength(p2) <= 1)

return p1;

if (Int(p1) || Int(p2)) return p1;

coefgcd(p2);

factor1(p1);

factor1(p2);

if (prem3(p_copy(p1), p2) == null) {

System.out.println("p1 can be factored.");

print(p1);

print(p2);

TMono tp2 = p_copy(p2);

TMono tp = p_copy(p1);

TMono m = div((p1), (p2));

TMono rm = this.pdif(tp, ptimes(tp2, p_copy(m)));

if (rm != null) {

print(rm);

}

print(m);

return m;

}

return p1;

}

TMono div(TMono m, TMono d) {

if (m == null || d == null)

return m;

if (m.x < d.x)

return null;

if (m.x == d.x && m.deg < d.deg)

return null;

if (m.x == 0 && d.x == 0) {

long n = m.val / d.val;

return pth(0, (int) n, 0);

}

TMono result = null;

if (m.x > d.x) {

result = null;

while (m != null) {

TMono t = div(m.coef, d);

if (m.deg != 0)

t = ptimes(t, pth(m.x, 1, m.deg));

result = padd(result, t);

m = m.next;

}

} else // m.x == d.x;

{

int x = m.x;

while (m != null) {

int dd = m.deg - d.deg;

if (dd < 0)

return null;

TMono m1 = div(m.coef, d.coef);

if (m1 == null)

return null; //failed.

m1 = ptimes(m1, pth(x, 1, dd));

result = padd(result, p_copy(m1));

TMono mx = d.next;

if (mx.x != 0 && mx.deg == 0)

mx = mx.coef;

m = pdif(m.next, ptimes((m1), p_copy(d.next)));

}

}

while (result != null && result.x != 0 && result.coef == null)

result = result.next;

while (result != null && result.deg == 0 && result.x != 0)

result = result.coef;

return result;

}

TMono p_copy(TMono p) {

if (p == null) return null;

TMono p1 = new TMono();

p1.x = p.x;

p1.deg = p.deg;

p1.val = p.val;

p1.coef = p_copy(p.coef);

p1.next = p_copy(p.next);

return p1;

}

private int pp_compare(TMono p1, TMono p2) {

if (p1.x < p2.x || (p1.x == p2.x && p1.deg < p2.deg))

return -1;

if (p1.x > p2.x || (p1.x == p2.x && p1.deg > p2.deg))

return 1;

return 0;

}

private boolean Int(TMono p) {

if (p == null)

return false;

if (p.x == 0)

return true;

if (p.deg == 0)

return Int(p.coef);

return false;

}

public void print(TMono p) {

if (p == null)

return;

int v = this.lv(p);

int d = this.deg(p);

System.out.print(plength(p) + " x" + v + "^" + d + " :");

p_print(p, false, true);

System.out.print("\n");

}

private void p_print(TMono p, boolean ce, boolean first) { // coefficent ? print "+" of first ?

if (p == null) return;

if (p.next == null) ce = false;

if (ce) {

if (first)

System.out.print("(");

else

System.out.print(" + (");

m_print(p, true);

p = p.next;

while (p != null) {

m_print(p, false);

p = p.next;

}

System.out.print(")");

} else if (!first) {

while (p != null) {

m_print(p, false);

p = p.next;

}

} else {

m_print(p, true);

p = p.next;

while (p != null) {

m_print(p, false);

p = p.next;

}

}

}

private void m_print(TMono p, boolean first) {

if (p.x == 0) {

if (first != true) {

if (p.val > 0)

System.out.print(" + ");

else

System.out.print(" - ");

long t = Math.abs(p.val);

if (t != 1)

System.out.print(t);

} else {

if (p.val != 1)

System.out.print(p.val);

}

} else if (p.deg == 0)

p_print(p.coef, false, first);

else {

p_print(p.coef, true, first);

if (p.coef == null)

System.out.print("0");

if (p.deg != 1)

System.out.print("x" + p.x + "^" + p.deg);

else

System.out.print("x" + p.x);

}

}

public TMono pth(int x, int c, int d) {

return new TMono(x, c, d);

}

public int deg(TMono p) {

if (p == null) {

int k = 0;

}

return p.deg;

}

public int lv(TMono p) {

if (p == null) return 0;

return p.x;

}

public TMono pzero() {

return null;

}

public int plength(TMono m) {

if (m == null) return 0;

if (Int(m))

return 1;

else {

return plength(m.coef) + plength(m.next);

}

}

boolean pzerom(TMono m) {

if (m == null)

return true;

return (!pzerop(m.coef) && m.next == null);

}

public boolean pzerop(TMono m) {

if (m == null) return true;

if (Int(m))

return m.val == 0;

return pzerop(m.coef) && pzerop(m.next);

}

TPoly addpoly(TMono t, TPoly p) {

TPoly poly = new TPoly();

poly.setNext(p);

poly.setPoly(t);

return poly;

}

TPoly addPolytoList(TPoly pl, TPoly pp) {

if (pl == null) return pp;

while (pl != null) {

pp = ppush(pl.getPoly(), pp);

pl = pl.getNext();

}

return pp;

}

public TPoly ppush(TMono t, TPoly pp) {

int vra = this.lv(t);

TPoly poly = new TPoly();

poly.setNext(null);

poly.setPoly(t);

if (pp == null)

return poly;

TPoly former = null;

TPoly p = pp;

if (t == null)

return pp;

while (p != null) {

int lee = this.lv(p.getPoly());

if (lee > vra) {

former = p;

p = p.getNext();

} else

break;

}

if (p == null || this.lv(p.getPoly()) < vra) {

poly.setNext(p);

if (former == null)

return poly;

else {

former.setNext(poly);

return pp;

}

}

//else ==

while (p != null) {

if (pp_compare(p.getPoly(), poly.getPoly()) < 0) {

if (former == null) {

poly.setNext(p);

return poly;

} else {

former.setNext(poly);

poly.setNext(p);

return pp;

}

} else {

former = p;

p = p.getNext();

}

}

if (former == null) {

poly.setNext(p);

return poly;

}

former.setNext(poly);

return pp;

}

double calpoly(TMono m, param[] p) {

if (m == null || p == null)

return 0.0;

if (Int(m))

return (double) m.val;

double r = 0.0;

while (m != null) {

double v = calpoly(m.coef, p);

int id = m.x - 1;

if (id < 0 || id >= p.length || p[m.x - 1] == null) return 0.0;

r += Math.pow(p[m.x - 1].value, m.deg) * v;

m = m.next;

}

return r;

}

public double[] calculv(TMono mm, param[] p) {

int x, d;

double[] result = null;

x = lv(mm);

d = deg(mm, x);

if (d == 1) {

double val = calpoly(mm.coef, p);

if (ZERO(val))

return new double[0];

result = new double[1];

double v1 = calpoly(mm.next, p);

val = (-1) * v1 / val;

result[0] = val;

return result;

} else if (d == 2) {

TMono a1 = mm.coef;

TMono b1;

mm = mm.next;

if (mm != null && deg(mm) == 1) {

b1 = mm.coef;

mm = mm.next;

} else

b1 = null;

TMono b2;

if (mm != null && deg(mm) == 0)

b2 = mm.coef;

else

b2 = null;

double aa = calpoly(a1, p);

double bb1 = calpoly(b1, p);

double bb2 = calpoly(b2, p);

if (ZERO(aa))

return new double[0];

return poly_solve_quadratic(aa, bb1, bb2);

} else if (d == 3 || d == 4) {

TMono a1, b1, c1, d1, e1;

a1 = b1 = c1 = d1 = e1 = null;

while (mm != null) {

switch (deg(mm)) {

case 0:

d1 = mm.coef;

break;

case 1:

c1 = mm.coef;

break;

case 2:

b1 = mm.coef;

break;

case 3:

a1 = mm.coef;

break;

case 4:

e1 = mm.coef;

break;

default:

return null;

}

mm = mm.next;

}

double aa = calpoly(a1, p);

double bb = calpoly(b1, p);

double cc = calpoly(c1, p);

double dd = calpoly(d1, p);

double ee = calpoly(e1, p);

double[] r = null;

// if (ee == 0 && aa == 0)

// r = poly_solve_quadratic(1, cc / bb, dd / bb);

if (d == 3 && aa != 0.0)

r = poly_solve_cubic(1, bb / aa, cc / aa, dd / aa);

else if (d == 4 && ee != 0)

r = poly_solve_quartic(aa / ee, bb / ee, cc / ee, dd / ee);

return r;

}

return null;

}

public double[] calculv_2v(TMono mm, param[] p) {

if (mm.next != null)

return this.calculv(mm.next.coef, p);

else

return null;

}

public double[] calculate_online(TMono mm, param[] p, int dx, int dy) {

if (mm.deg != 1 && mm.x != dy) return null;

double a = calpoly(mm.coef, p);

double c = 0.0;

double b = 0.0;

if (mm.deg != 1 && mm.x != dx) return null;

if (mm.next != null) {

TMono m1 = mm.next.coef;

if (m1.x != dx)

return null;

b = calpoly(m1.coef, p);

if (m1.next != null) {

m1 = m1.next.coef;

c = calpoly(m1, p);

}

} else

return null;

double md = b * b + a * a;

double x = p[dx - 1].value;

double y = p[dy - 1].value;

if (Math.abs(md) < ZERO)

return null;

double[] result = new double[2];

result[0] = (a * a * x - a * b * y - b * c) / md;

result[1] = (b * b * y - a * b * x - a * c) / md;

return result;

}

public double[] calculate_oncr(TMono mm, param[] p, int dx, int dy) {

if (mm.deg != 2 && mm.x != dy) return null;