"""Test sparse polynomials. """
import pickle
import pytest
from functools import reduce
from operator import add, mul

from sympy.polys.domains import ZZ_I
from sympy.polys.rings import ring, xring, sring, PolyRing, PolyElement, vring, ninf
from sympy.polys.fields import field, FracField
from sympy.polys.domains import ZZ, QQ, RR, FF, EX
from sympy.polys.orderings import lex, grlex
from sympy.polys.polyerrors import GeneratorsError, \
    ExactQuotientFailed, MultivariatePolynomialError, CoercionFailed

from sympy.testing.pytest import raises
from sympy.core import Symbol, symbols
from sympy.core.singleton import S
from sympy.core.numbers import pi, I
from sympy.functions.elementary.exponential import exp
from sympy.functions.elementary.miscellaneous import sqrt


def test_PolyRing___init__():
    x, y, z, t = map(Symbol, "xyzt")

    assert len(PolyRing("x,y,z", ZZ, lex).gens) == 3
    assert len(PolyRing(x, ZZ, lex).gens) == 1
    assert len(PolyRing(("x", "y", "z"), ZZ, lex).gens) == 3
    assert len(PolyRing((x, y, z), ZZ, lex).gens) == 3
    assert len(PolyRing("", ZZ, lex).gens) == 0
    assert len(PolyRing([], ZZ, lex).gens) == 0

    raises(GeneratorsError, lambda: PolyRing(0, ZZ, lex))

    assert PolyRing("x", ZZ[t], lex).domain == ZZ[t]
    assert PolyRing("x", 'ZZ[t]', lex).domain == ZZ[t]
    assert PolyRing("x", PolyRing("t", ZZ, lex), lex).domain == ZZ[t]

    raises(GeneratorsError, lambda: PolyRing("x", PolyRing("x", ZZ, lex), lex))

    _lex = Symbol("lex")
    assert PolyRing("x", ZZ, lex).order == lex
    assert PolyRing("x", ZZ, _lex).order == lex
    assert PolyRing("x", ZZ, 'lex').order == lex

    R1 = PolyRing("x,y", ZZ, lex)
    R2 = PolyRing("x,y", ZZ, lex)
    R3 = PolyRing("x,y,z", ZZ, lex)

    assert R1.x == R1.gens[0]
    assert R1.y == R1.gens[1]
    assert R1.x == R2.x
    assert R1.y == R2.y
    assert R1.x != R3.x
    assert R1.y != R3.y


@pytest.mark.xfail
def test_PolyRing_pickle():
    R, x, y = ring("x,y", ZZ, lex)

    dumped = pickle.dumps(R)
    loaded = pickle.loads(dumped)

    assert loaded == R


def test_PolyRing___hash__():
    R, x, y, z = ring("x,y,z", QQ)
    assert hash(R)


def test_PolyRing___eq__():
    assert ring("x,y,z", QQ)[0] == ring("x,y,z", QQ)[0]
    assert ring("x,y,z", QQ)[0] != ring("x,y,z", ZZ)[0]
    assert ring("x,y,z", ZZ)[0] != ring("x,y,z", QQ)[0]
    assert ring("x,y,z", QQ)[0] != ring("x,y", QQ)[0]
    assert ring("x,y", QQ)[0] != ring("x,y,z", QQ)[0]


def test_PolyRing_ring_new():
    R, x, y, z = ring("x,y,z", QQ)

    assert R.ring_new(7) == R(7)
    assert R.ring_new(7*x*y*z) == 7*x*y*z

    f = x**2 + 2*x*y + 3*x + 4*z**2 + 5*z + 6

    assert R.ring_new([[[1]], [[2], [3]], [[4, 5, 6]]]) == f
    assert R.ring_new({(2, 0, 0): 1, (1, 1, 0): 2, (1, 0, 0): 3, (0, 0, 2): 4, (0, 0, 1): 5, (0, 0, 0): 6}) == f
    assert R.ring_new([((2, 0, 0), 1), ((1, 1, 0), 2), ((1, 0, 0), 3), ((0, 0, 2), 4), ((0, 0, 1), 5), ((0, 0, 0), 6)]) == f

    R, = ring("", QQ)
    assert R.ring_new([((), 7)]) == R(7)

    R1 = PolyRing('x', ZZ, lex)
    R2 = PolyRing('y', QQ, lex)
    raises(NotImplementedError, lambda: R1.ring_new(R2.ground_new(1))) # Conversion not implemented

    R = PolyRing('x,y', ZZ, lex)
    raises(NotImplementedError, lambda: R.ring_new("x**2 + y + 1")) # Parsing not implemented

    R = PolyRing('x,y', ZZ, lex)
    x, y = symbols('x y')
    expr = x**2 + 2*y + 3
    poly = R.ring_new(expr)
    assert isinstance(poly, PolyElement)
    assert poly.ring == R


def test_PolyRing_drop():
    R, x,y,z = ring("x,y,z", ZZ)

    assert R.drop(x) == PolyRing("y,z", ZZ, lex)
    assert R.drop(y) == PolyRing("x,z", ZZ, lex)
    assert R.drop(z) == PolyRing("x,y", ZZ, lex)

    assert R.drop(0) == PolyRing("y,z", ZZ, lex)
    assert R.drop(0).drop(0) == PolyRing("z", ZZ, lex)
    assert R.drop(0).drop(0).drop(0) == ZZ

    assert R.drop(1) == PolyRing("x,z", ZZ, lex)

    assert R.drop(2) == PolyRing("x,y", ZZ, lex)
    assert R.drop(2).drop(1) == PolyRing("x", ZZ, lex)
    assert R.drop(2).drop(1).drop(0) == ZZ

    raises(ValueError, lambda: R.drop(3))
    raises(ValueError, lambda: R.drop(x).drop(y))


def test_PolyRing___getitem__():
    R, x,y,z = ring("x,y,z", ZZ)

    assert R[0:] == PolyRing("x,y,z", ZZ, lex)
    assert R[1:] == PolyRing("y,z", ZZ, lex)
    assert R[2:] == PolyRing("z", ZZ, lex)
    assert R[3:] == ZZ


def test_PolyRing_is_():
    R = PolyRing("x", QQ, lex)

    assert R.is_univariate is True
    assert R.is_multivariate is False

    R = PolyRing("x,y,z", QQ, lex)

    assert R.is_univariate is False
    assert R.is_multivariate is True

    R = PolyRing("", QQ, lex)

    assert R.is_univariate is False
    assert R.is_multivariate is False


def test_PolyRing_add():
    R, x = ring("x", ZZ)
    F = [ x**2 + 2*i + 3 for i in range(4) ]

    assert R.add(F) == reduce(add, F) == 4*x**2 + 24

    R, = ring("", ZZ)

    assert R.add([2, 5, 7]) == 14


def test_PolyRing_mul():
    R, x = ring("x", ZZ)
    F = [ x**2 + 2*i + 3 for i in range(4) ]

    assert R.mul(F) == reduce(mul, F) == x**8 + 24*x**6 + 206*x**4 + 744*x**2 + 945

    R, = ring("", ZZ)

    assert R.mul([2, 3, 5]) == 30


def test_PolyRing_symmetric_poly():
    R, x, y, z, t = ring("x,y,z,t", ZZ)

    raises(ValueError, lambda: R.symmetric_poly(-1))
    raises(ValueError, lambda: R.symmetric_poly(5))

    assert R.symmetric_poly(0) == R.one
    assert R.symmetric_poly(1) == x + y + z + t
    assert R.symmetric_poly(2) == x*y + x*z + x*t + y*z + y*t + z*t
    assert R.symmetric_poly(3) == x*y*z + x*y*t + x*z*t + y*z*t
    assert R.symmetric_poly(4) == x*y*z*t


def test_PolyRing_compose():

    R1 = PolyRing('x,y', ZZ, lex)
    R2 = PolyRing('z,w', ZZ, lex)

    composed = R1.compose(R2)
    assert len(composed.symbols) == 4
    symbol_names = {str(s) for s in composed.symbols}
    assert symbol_names == {'w', 'x', 'y', 'z'}

    composed = R1.compose(R1)
    assert composed == R1

    R1 = PolyRing('x,y', ZZ, lex)
    R2 = PolyRing('y,z', ZZ, lex)

    composed = R1.compose(R2)
    assert len(composed.symbols) == 3


def test_PolyRing_to_field():

    R = PolyRing('x,y', ZZ, lex)
    F = R.to_field()

    assert (F.domain == ZZ and
            F.symbols == R.symbols and
            F.order == R.order and
            F.gens == R.gens)

    assert isinstance(F, FracField)


def test_PolyRing_from_dict():

    R = PolyRing('x,y', ZZ, lex)
    poly_dict = {(1, 0): 2, (0, 1): 3, (0, 0): 1}

    poly = R.from_dict(poly_dict)
    assert isinstance(poly, PolyElement)
    assert poly.ring == R

    raises(TypeError, lambda: R.from_dict([1, 2, 3]))

    ring = PolyRing('x', ZZ, lex)
    poly_dict = {(1,): 2, (0,): 1}
    poly = ring.from_dict(poly_dict, orig_domain=QQ)
    assert isinstance(poly, PolyElement)


def test_PolyRing_index():
    R = PolyRing('x,y', ZZ, lex)
    assert R.index(None) == 0

    empty_ring = PolyRing([], ZZ, lex)
    assert empty_ring.index(None) == -1

    ring = PolyRing('x,y,z', ZZ, lex)
    assert ring.index(0) == 0
    assert ring.index(1) == 1
    assert ring.index(2) == 2

    raises(ValueError, lambda: ring.index(-1)) # negative generator indices not allowed

    R = PolyRing('x,y,z', ZZ, lex)
    x, y, z = ring.gens

    assert R.index(x) == 0
    assert R.index(y) == 1
    assert R.index(z) == 2

    raises(ValueError, lambda: R.index(3.14))
    raises(ValueError, lambda: R.index([1, 2, 3]))

    five = R(5)
    raises(ValueError, lambda: R.index(five))

    w = Symbol('w')
    raises(ValueError, lambda: R.index(w))
    raises(ValueError, lambda: R.index("u"))
    raises(ValueError, lambda: R.index("x"))

    R1 = PolyRing(symbols('x,y'), ZZ, lex)
    R2 = PolyRing(symbols('z,w'), ZZ, lex)
    z = R2.gens[0]

    raises(ValueError, lambda: R1.index(z))


def test_PolyRing_add_gens():
    R = PolyRing('x,y', ZZ, lex)
    new_symbols = symbols('z,w')

    extended_ring = R.add_gens(new_symbols)
    symbol_names = {str(s) for s in extended_ring.symbols}

    assert symbol_names == {'w', 'x', 'y', 'z'}


def test_PolyRing_drop_to_ground():
    R = PolyRing('x,y,z', ZZ, lex)
    x, y, z = R.gens

    reduced_ring = R.drop_to_ground(x, z)
    assert len(reduced_ring.symbols) == 1
    assert str(reduced_ring.symbols[0]) == 'y'

    reduced_ring = R.drop_to_ground(0, 2)
    assert len(reduced_ring.symbols) == 1
    assert str(reduced_ring.symbols[0]) == 'y'

    result = R.drop_to_ground(x, y, z)
    assert result is R


def test_PolyRing_to_ground():

    R1 =  PolyRing("x", ZZ, lex)
    R2 = PolyRing("y", R1, lex)

    R = R2.to_ground()
    assert R == PolyRing("y", ZZ, lex)

    raises(ValueError, lambda: R1.to_ground()) # ZZ is not composite


def test_sring():
    x, y, z, t = symbols("x,y,z,t")
    R = PolyRing("x,y,z", ZZ, lex)
    assert sring(x + 2*y + 3*z) == (R, R.x + 2*R.y + 3*R.z)

    R = PolyRing("x,y,z", QQ, lex)
    assert sring(x + 2*y + z/3) == (R, R.x + 2*R.y + R.z/3)
    assert sring([x, 2*y, z/3]) == (R, [R.x, 2*R.y, R.z/3])

    Rt = PolyRing("t", ZZ, lex)
    R = PolyRing("x,y,z", Rt, lex)
    assert sring(x + 2*t*y + 3*t**2*z, x, y, z) == (R, R.x + 2*Rt.t*R.y + 3*Rt.t**2*R.z)

    Rt = PolyRing("t", QQ, lex)
    R = PolyRing("x,y,z", Rt, lex)
    assert sring(x + t*y/2 + t**2*z/3, x, y, z) == (R, R.x + Rt.t*R.y/2 + Rt.t**2*R.z/3)

    Rt = FracField("t", ZZ, lex)
    R = PolyRing("x,y,z", Rt, lex)
    assert sring(x + 2*y/t + t**2*z/3, x, y, z) == (R, R.x + 2*R.y/Rt.t + Rt.t**2*R.z/3)

    r = sqrt(2) - sqrt(3)
    R, a = sring(r, extension=True)
    assert R.domain == QQ.algebraic_field(sqrt(2) + sqrt(3))
    assert R.gens == ()
    assert a == R.domain.from_sympy(r)


def test_vring():

    R = PolyRing("x,y,z", ZZ, lex)
    Vr = vring("x,y,z", ZZ, lex)

    assert Vr == R
    assert len(Vr.symbols) == 3
    assert Vr.domain.is_ZZ
    assert Vr.order == lex


def test_PolyElement___hash__():
    R, x, y, z = ring("x,y,z", QQ)
    assert hash(x*y*z)


@pytest.mark.xfail(reason="Pickling fails due to PolyRing.__getstate__ implementation")
def test_PolyElement_pickle():
    R, x, y = ring("x,y", QQ, lex)
    poly = x**2 + 2*x*y + 3

    dumped = pickle.dumps(poly)
    loaded = pickle.loads(dumped)

    assert loaded == poly


def test_PolyElement___eq__():
    R, x, y = ring("x,y", ZZ, lex)

    assert ((x*y + 5*x*y) == 6) == False
    assert ((x*y + 5*x*y) == 6*x*y) == True
    assert (6 == (x*y + 5*x*y)) == False
    assert (6*x*y == (x*y + 5*x*y)) == True

    assert ((x*y - x*y) == 0) == True
    assert (0 == (x*y - x*y)) == True

    assert ((x*y - x*y) == 1) == False
    assert (1 == (x*y - x*y)) == False

    assert ((x*y - x*y) == 1) == False
    assert (1 == (x*y - x*y)) == False

    assert ((x*y + 5*x*y) != 6) == True
    assert ((x*y + 5*x*y) != 6*x*y) == False
    assert (6 != (x*y + 5*x*y)) == True
    assert (6*x*y != (x*y + 5*x*y)) == False

    assert ((x*y - x*y) != 0) == False
    assert (0 != (x*y - x*y)) == False

    assert ((x*y - x*y) != 1) == True
    assert (1 != (x*y - x*y)) == True

    assert R.one == QQ(1, 1) == R.one
    assert R.one == 1 == R.one

    poly = x**2 + 2*y - 1
    assert poly == +poly # also tests __pos__

    Rt, t = ring("t", ZZ)
    R, x, y = ring("x,y", Rt)

    assert (t**3*x/x == t**3) == True
    assert (t**3*x/x == t**4) == False


def test_PolyElement__lt_le_gt_ge__():
    R, x, y = ring("x,y", ZZ)
    _, a = ring("a", QQ)

    assert R(1) < x < x**2 < x**3
    assert R(1) <= x <= x**2 <= x**3

    assert x**3 > x**2 > x > R(1)
    assert x**3 >= x**2 >= x >= R(1)

    raises(TypeError, lambda: x > a)


def test_PolyElement__str__():
    x, y = symbols('x, y')

    for dom in [ZZ, QQ, ZZ[x], ZZ[x,y], ZZ[x][y]]:
        R, t = ring('t', dom)
        assert str(2*t**2 + 1) == '2*t**2 + 1'

    for dom in [EX, EX[x]]:
        R, t = ring('t', dom)
        assert str(2*t**2 + 1) == 'EX(2)*t**2 + EX(1)'

    R, x = ring("x", ZZ)
    assert str(R.zero) == "0"
    assert str(R({(0,): -3})) == "-3"

    R, x = ring("x", QQ)
    half = QQ(1, 2)
    f = R({(half,): 1})
    s = str(f)
    assert s == "x**(1/2)"


def test_PolyElement_copy():
    R, x, y, z = ring("x,y,z", ZZ)

    f = x*y + 3*z
    g = f.copy()

    assert f == g
    g[(1, 1, 1)] = 7
    assert f != g


def test_PolyElement_as_expr():
    R, x, y, z = ring("x,y,z", ZZ)
    f = 3*x**2*y - x*y*z + 7*z**3 + 1

    X, Y, Z = R.symbols
    g = 3*X**2*Y - X*Y*Z + 7*Z**3 + 1

    assert f != g
    assert f.as_expr() == g

    U, V, W = symbols("u,v,w")
    g = 3*U**2*V - U*V*W + 7*W**3 + 1

    assert f != g
    assert f.as_expr(U, V, W) == g

    raises(ValueError, lambda: f.as_expr(X))

    R, = ring("", ZZ)
    assert R(3).as_expr() == 3


def test_PolyElement_from_expr():
    x, y, z = symbols("x,y,z")
    R, X, Y, Z = ring((x, y, z), ZZ)

    f = R.from_expr(1)
    assert f == 1 and R.is_element(f)

    f = R.from_expr(x)
    assert f == X and R.is_element(f)

    f = R.from_expr(x*y*z)
    assert f == X*Y*Z and R.is_element(f)

    f = R.from_expr(x*y*z + x*y + x)
    assert f == X*Y*Z + X*Y + X and R.is_element(f)

    f = R.from_expr(x**3*y*z + x**2*y**7 + 1)
    assert f == X**3*Y*Z + X**2*Y**7 + 1 and R.is_element(f)

    r, F = sring([exp(2)])
    f = r.from_expr(exp(2))
    assert f == F[0] and r.is_element(f)

    raises(ValueError, lambda: R.from_expr(1/x))
    raises(ValueError, lambda: R.from_expr(2**x))
    raises(ValueError, lambda: R.from_expr(7*x + sqrt(2)))

    R, = ring("", ZZ)
    f = R.from_expr(1)
    assert f == 1 and R.is_element(f)


def test_PolyElement_degree():
    R, x,y,z = ring("x,y,z", ZZ)

    assert ninf == float('-inf')

    assert R(0).degree() is ninf
    assert R(1).degree() == 0
    assert (x + 1).degree() == 1
    assert (2*y**3 + z).degree() == 0
    assert (x*y**3 + z).degree() == 1
    assert (x**5*y**3 + z).degree() == 5

    assert R(0).degree(x) is ninf
    assert R(1).degree(x) == 0
    assert (x + 1).degree(x) == 1
    assert (2*y**3 + z).degree(x) == 0
    assert (x*y**3 + z).degree(x) == 1
    assert (7*x**5*y**3 + z).degree(x) == 5

    assert R(0).degree(y) is ninf
    assert R(1).degree(y) == 0
    assert (x + 1).degree(y) == 0
    assert (2*y**3 + z).degree(y) == 3
    assert (x*y**3 + z).degree(y) == 3
    assert (7*x**5*y**3 + z).degree(y) == 3

    assert R(0).degree(z) is ninf
    assert R(1).degree(z) == 0
    assert (x + 1).degree(z) == 0
    assert (2*y**3 + z).degree(z) == 1
    assert (x*y**3 + z).degree(z) == 1
    assert (7*x**5*y**3 + z).degree(z) == 1

    R, = ring("", ZZ)
    assert R(0).degree() is ninf
    assert R(1).degree() == 0


def test_PolyElement_tail_degree():
    R, x,y,z = ring("x,y,z", ZZ)

    assert R(0).tail_degree() is ninf
    assert R(1).tail_degree() == 0
    assert (x + 1).tail_degree() == 0
    assert (2*y**3 + x**3*z).tail_degree() == 0
    assert (x*y**3 + x**3*z).tail_degree() == 1
    assert (x**5*y**3 + x**3*z).tail_degree() == 3

    assert R(0).tail_degree(x) is ninf
    assert R(1).tail_degree(x) == 0
    assert (x + 1).tail_degree(x) == 0
    assert (2*y**3 + x**3*z).tail_degree(x) == 0
    assert (x*y**3 + x**3*z).tail_degree(x) == 1
    assert (7*x**5*y**3 + x**3*z).tail_degree(x) == 3

    assert R(0).tail_degree(y) is ninf
    assert R(1).tail_degree(y) == 0
    assert (x + 1).tail_degree(y) == 0
    assert (2*y**3 + x**3*z).tail_degree(y) == 0
    assert (x*y**3 + x**3*z).tail_degree(y) == 0
    assert (7*x**5*y**3 + x**3*z).tail_degree(y) == 0

    assert R(0).tail_degree(z) is ninf
    assert R(1).tail_degree(z) == 0
    assert (x + 1).tail_degree(z) == 0
    assert (2*y**3 + x**3*z).tail_degree(z) == 0
    assert (x*y**3 + x**3*z).tail_degree(z) == 0
    assert (7*x**5*y**3 + x**3*z).tail_degree(z) == 0

    R, = ring("", ZZ)
    assert R(0).tail_degree() is ninf
    assert R(1).tail_degree() == 0


def test_PolyElement_degrees():
    R, x,y,z = ring("x,y,z", ZZ)

    assert R(0).degrees() == (ninf, ninf, ninf)
    assert R(1).degrees() == (0, 0, 0)
    assert (x**2*y + x**3*z**2).degrees() == (3, 1, 2)


def test_PolyElement_tail_degrees():
    R, x,y,z = ring("x,y,z", ZZ)

    assert R(0).tail_degrees() == (ninf, ninf, ninf)
    assert R(1).tail_degrees() == (0, 0, 0)
    assert (x**2*y + x**3*z**2).tail_degrees() == (2, 0, 0)


def test_PolyElement_coeff():
    R, x, y, z = ring("x,y,z", ZZ, lex)
    f = 3*x**2*y - x*y*z + 7*z**3 + 23

    assert f.coeff(1) == 23
    raises(ValueError, lambda: f.coeff(3))

    assert f.coeff(x) == 0
    assert f.coeff(y) == 0
    assert f.coeff(z) == 0

    assert f.coeff(x**2*y) == 3
    assert f.coeff(x*y*z) == -1
    assert f.coeff(z**3) == 7

    raises(ValueError, lambda: f.coeff(3*x**2*y))
    raises(ValueError, lambda: f.coeff(-x*y*z))
    raises(ValueError, lambda: f.coeff(7*z**3))

    R, = ring("", ZZ)
    assert R(3).coeff(1) == 3


def test_PolyElement_LC():
    R, x, y = ring("x,y", QQ, lex)
    assert R(0).LC == QQ(0)
    assert (QQ(1,2)*x).LC == QQ(1, 2)
    assert (QQ(1,4)*x*y + QQ(1,2)*x).LC == QQ(1, 4)


def test_PolyElement_LM():
    R, x, y = ring("x,y", QQ, lex)
    assert R(0).LM == (0, 0)
    assert (QQ(1,2)*x).LM == (1, 0)
    assert (QQ(1,4)*x*y + QQ(1,2)*x).LM == (1, 1)


def test_PolyElement_LT():
    R, x, y = ring("x,y", QQ, lex)
    assert R(0).LT == ((0, 0), QQ(0))
    assert (QQ(1,2)*x).LT == ((1, 0), QQ(1, 2))
    assert (QQ(1,4)*x*y + QQ(1,2)*x).LT == ((1, 1), QQ(1, 4))

    R, = ring("", ZZ)
    assert R(0).LT == ((), 0)
    assert R(1).LT == ((), 1)


def test_PolyElement_leading_monom():
    R, x, y = ring("x,y", QQ, lex)
    assert R(0).leading_monom() == 0
    assert (QQ(1,2)*x).leading_monom() == x
    assert (QQ(1,4)*x*y + QQ(1,2)*x).leading_monom() == x*y


def test_PolyElement_leading_term():
    R, x, y = ring("x,y", QQ, lex)
    assert R(0).leading_term() == 0
    assert (QQ(1,2)*x).leading_term() == QQ(1,2)*x
    assert (QQ(1,4)*x*y + QQ(1,2)*x).leading_term() == QQ(1,4)*x*y


def test_PolyElement_terms():
    R, x,y,z = ring("x,y,z", QQ)
    terms = (x**2/3 + y**3/4 + z**4/5).terms()
    assert terms == [((2,0,0), QQ(1,3)), ((0,3,0), QQ(1,4)), ((0,0,4), QQ(1,5))]

    R, x,y = ring("x,y", ZZ, lex)
    f = x*y**7 + 2*x**2*y**3

    assert f.terms() == f.terms(lex) == f.terms('lex') == [((2, 3), 2), ((1, 7), 1)]
    assert f.terms(grlex) == f.terms('grlex') == [((1, 7), 1), ((2, 3), 2)]

    R, x,y = ring("x,y", ZZ, grlex)
    f = x*y**7 + 2*x**2*y**3

    assert f.terms() == f.terms(grlex) == f.terms('grlex') == [((1, 7), 1), ((2, 3), 2)]
    assert f.terms(lex) == f.terms('lex') == [((2, 3), 2), ((1, 7), 1)]

    R, = ring("", ZZ)
    assert R(3).terms() == [((), 3)]


def test_PolyElement_monoms():
    R, x,y,z = ring("x,y,z", QQ)
    monoms = (x**2/3 + y**3/4 + z**4/5).monoms()
    assert monoms == [(2,0,0), (0,3,0), (0,0,4)]

    R, x,y = ring("x,y", ZZ, lex)
    f = x*y**7 + 2*x**2*y**3

    assert f.monoms() == f.monoms(lex) == f.monoms('lex') == [(2, 3), (1, 7)]
    assert f.monoms(grlex) == f.monoms('grlex') == [(1, 7), (2, 3)]

    R, x,y = ring("x,y", ZZ, grlex)
    f = x*y**7 + 2*x**2*y**3

    assert f.monoms() == f.monoms(grlex) == f.monoms('grlex') == [(1, 7), (2, 3)]
    assert f.monoms(lex) == f.monoms('lex') == [(2, 3), (1, 7)]


def test_PolyElement_coeffs():
    R, x,y,z = ring("x,y,z", QQ)
    coeffs = (x**2/3 + y**3/4 + z**4/5).coeffs()
    assert coeffs == [QQ(1,3), QQ(1,4), QQ(1,5)]

    R, x,y = ring("x,y", ZZ, lex)
    f = x*y**7 + 2*x**2*y**3

    assert f.coeffs() == f.coeffs(lex) == f.coeffs('lex') == [2, 1]
    assert f.coeffs(grlex) == f.coeffs('grlex') == [1, 2]

    R, x,y = ring("x,y", ZZ, grlex)
    f = x*y**7 + 2*x**2*y**3

    assert f.coeffs() == f.coeffs(grlex) == f.coeffs('grlex') == [1, 2]
    assert f.coeffs(lex) == f.coeffs('lex') == [2, 1]


def test_PolyElement___add__():
    Rt, t = ring("t", ZZ)
    Ruv, u,v = ring("u,v", ZZ)
    Rxyz, x,y,z = ring("x,y,z", Ruv)

    assert dict(x + 3*y) == {(1, 0, 0): 1, (0, 1, 0): 3}

    assert dict(u + x) == dict(x + u) == {(1, 0, 0): 1, (0, 0, 0): u}
    assert dict(u + x*y) == dict(x*y + u) == {(1, 1, 0): 1, (0, 0, 0): u}
    assert dict(u + x*y + z) == dict(x*y + z + u) == {(1, 1, 0): 1, (0, 0, 1): 1, (0, 0, 0): u}

    assert dict(u*x + x) == dict(x + u*x) == {(1, 0, 0): u + 1}
    assert dict(u*x + x*y) == dict(x*y + u*x) == {(1, 1, 0): 1, (1, 0, 0): u}
    assert dict(u*x + x*y + z) == dict(x*y + z + u*x) == {(1, 1, 0): 1, (0, 0, 1): 1, (1, 0, 0): u}

    assert dict(0 + t) == {(1,): 1}

    raises(TypeError, lambda: t + x)
    raises(TypeError, lambda: x + t)
    raises(TypeError, lambda: t + u)
    raises(TypeError, lambda: u + t)

    Fuv, u,v = field("u,v", ZZ)
    Rxyz, x,y,z = ring("x,y,z", Fuv)

    assert dict(u + x) == dict(x + u) == {(1, 0, 0): 1, (0, 0, 0): u}

    Rxyz, x,y,z = ring("x,y,z", EX)

    assert dict(EX(pi) + x*y*z) == dict(x*y*z + EX(pi)) == {(1, 1, 1): EX(1), (0, 0, 0): EX(pi)}

    raises(TypeError, lambda: t + QQ(1, 2))
    raises(TypeError, lambda: QQ(1, 2) + t)

    R, x = ring("x", ZZ)
    R1, a = ring("a", R)

    assert x + a == R1.domain.convert(x) + a
    assert (x + a).ring == R1
    assert a + x == a + R1.domain.convert(x)
    assert (a + x).ring == R1


def test_PolyElement___sub__():
    Rt, t = ring("t", ZZ)
    Ruv, u,v = ring("u,v", ZZ)
    Rxyz, x,y,z = ring("x,y,z", Ruv)

    assert dict(x - 3*y) == {(1, 0, 0): 1, (0, 1, 0): -3}

    assert dict(-u + x) == dict(x - u) == {(1, 0, 0): 1, (0, 0, 0): -u}
    assert dict(-u + x*y) == dict(x*y - u) == {(1, 1, 0): 1, (0, 0, 0): -u}
    assert dict(-u + x*y + z) == dict(x*y + z - u) == {(1, 1, 0): 1, (0, 0, 1): 1, (0, 0, 0): -u}

    assert dict(-u*x + x) == dict(x - u*x) == {(1, 0, 0): -u + 1}
    assert dict(-u*x + x*y) == dict(x*y - u*x) == {(1, 1, 0): 1, (1, 0, 0): -u}
    assert dict(-u*x + x*y + z) == dict(x*y + z - u*x) == {(1, 1, 0): 1, (0, 0, 1): 1, (1, 0, 0): -u}

    raises(TypeError, lambda: t - x)
    raises(TypeError, lambda: x - t)
    raises(TypeError, lambda: t - u)
    raises(TypeError, lambda: u - t)

    Fuv, u,v = field("u,v", ZZ)
    Rxyz, x,y,z = ring("x,y,z", Fuv)

    assert dict(-u + x) == dict(x - u) == {(1, 0, 0): 1, (0, 0, 0): -u}

    Rxyz, x,y,z = ring("x,y,z", EX)

    assert dict(-EX(pi) + x*y*z) == dict(x*y*z - EX(pi)) == {(1, 1, 1): EX(1), (0, 0, 0): -EX(pi)}

    Rb, x = ring('x', ZZ, lex)
    Rn, y = ring('y', Rb, lex)

    pb = x + 1
    pn = y + 1

    result = pb - pn
    assert result.ring == Rn and isinstance(result, PolyElement)

    raises(TypeError, lambda: t - QQ(1, 2))
    raises(TypeError, lambda: QQ(1, 2) - t)

    R, x = ring("x", ZZ)
    R1, a = ring("a", R)

    assert x - a == R1.domain.convert(x) - a
    assert (x - a).ring == R1
    assert a - x == a - R1.domain.convert(x)
    assert (a - x).ring == R1


def test_PolyElement___mul__():
    Rt, t = ring("t", ZZ)
    Ruv, u,v = ring("u,v", ZZ)
    Rxyz, x,y,z = ring("x,y,z", Ruv)

    assert dict(u*x) == dict(x*u) == {(1, 0, 0): u}

    assert dict(2*u*x + z) == dict(x*2*u + z) == {(1, 0, 0): 2*u, (0, 0, 1): 1}
    assert dict(u*2*x + z) == dict(2*x*u + z) == {(1, 0, 0): 2*u, (0, 0, 1): 1}
    assert dict(2*u*x + z) == dict(x*2*u + z) == {(1, 0, 0): 2*u, (0, 0, 1): 1}
    assert dict(u*x*2 + z) == dict(x*u*2 + z) == {(1, 0, 0): 2*u, (0, 0, 1): 1}

    assert dict(2*u*x*y + z) == dict(x*y*2*u + z) == {(1, 1, 0): 2*u, (0, 0, 1): 1}
    assert dict(u*2*x*y + z) == dict(2*x*y*u + z) == {(1, 1, 0): 2*u, (0, 0, 1): 1}
    assert dict(2*u*x*y + z) == dict(x*y*2*u + z) == {(1, 1, 0): 2*u, (0, 0, 1): 1}
    assert dict(u*x*y*2 + z) == dict(x*y*u*2 + z) == {(1, 1, 0): 2*u, (0, 0, 1): 1}

    assert dict(2*u*y*x + z) == dict(y*x*2*u + z) == {(1, 1, 0): 2*u, (0, 0, 1): 1}
    assert dict(u*2*y*x + z) == dict(2*y*x*u + z) == {(1, 1, 0): 2*u, (0, 0, 1): 1}
    assert dict(2*u*y*x + z) == dict(y*x*2*u + z) == {(1, 1, 0): 2*u, (0, 0, 1): 1}
    assert dict(u*y*x*2 + z) == dict(y*x*u*2 + z) == {(1, 1, 0): 2*u, (0, 0, 1): 1}

    assert dict(3*u*(x + y) + z) == dict((x + y)*3*u + z) == {(1, 0, 0): 3*u, (0, 1, 0): 3*u, (0, 0, 1): 1}

    raises(TypeError, lambda: t*x + z)
    raises(TypeError, lambda: x*t + z)
    raises(TypeError, lambda: t*u + z)
    raises(TypeError, lambda: u*t + z)

    Fuv, u,v = field("u,v", ZZ)
    Rxyz, x,y,z = ring("x,y,z", Fuv)

    assert dict(u*x) == dict(x*u) == {(1, 0, 0): u}

    Rxyz, x,y,z = ring("x,y,z", EX)

    assert dict(EX(pi)*x*y*z) == dict(x*y*z*EX(pi)) == {(1, 1, 1): EX(pi)}

    raises(TypeError, lambda: t * QQ(1, 2))
    raises(TypeError, lambda: QQ(1, 2) * t)

    R, x = ring("x", ZZ)
    r, a = ring("a", ZZ)
    assert x.__rmul__(a) is NotImplemented

    _, x, y = ring("x,y", ZZ)
    p = x + y
    raises(TypeError, lambda: (1/2)*p)

    R, x = ring("x", ZZ)
    R1, a = ring("a", R)

    assert x*a == R1.domain.convert(x) * a
    assert (x*a).ring == R1
    assert a*x == a * R1.domain.convert(x)
    assert (a*x).ring == R1


def test_PolyElement___truediv__():
    R, x,y,z = ring("x,y,z", ZZ)

    assert (2*x**2 - 4)/2 == x**2 - 2
    assert (2*x**2 - 3)/2 == x**2

    assert (x**2 - 1).quo(x) == x
    assert (x**2 - x).quo(x) == x - 1

    raises(ExactQuotientFailed, lambda: (x**2 - 1)/x)
    assert (x**2 - x)/x == x - 1
    raises(ExactQuotientFailed, lambda: (x**2 - 1)/(2*x))

    assert (x**2 - 1).quo(2*x) == 0
    assert (x**2 - x)/(x - 1) == (x**2 - x).quo(x - 1) == x

    raises(TypeError, lambda: x / QQ(1, 2))

    R, x,y,z = ring("x,y,z", ZZ)
    assert len((x**2/3 + y**3/4 + z**4/5).terms()) == 0

    R, x,y,z = ring("x,y,z", QQ)
    assert len((x**2/3 + y**3/4 + z**4/5).terms()) == 3

    Rt, t = ring("t", ZZ)
    Ruv, u,v = ring("u,v", ZZ)
    Rxyz, x,y,z = ring("x,y,z", Ruv)

    assert dict((u**2*x + u)/u) == {(1, 0, 0): u, (0, 0, 0): 1}
    raises(ExactQuotientFailed, lambda: u/(u**2*x + u))

    raises(TypeError, lambda: t/x)
    raises(TypeError, lambda: x/t)
    raises(TypeError, lambda: t/u)
    raises(TypeError, lambda: u/t)

    R, x = ring("x", ZZ)
    f, g = x**2 + 2*x + 3, R(0)

    raises(ZeroDivisionError, lambda: f.div(g))
    raises(ZeroDivisionError, lambda: divmod(f, g))
    raises(ZeroDivisionError, lambda: f.rem(g))
    raises(ZeroDivisionError, lambda: f % g)
    raises(ZeroDivisionError, lambda: f.quo(g))
    raises(ZeroDivisionError, lambda: f / g)
    raises(ZeroDivisionError, lambda: f.exquo(g))

    R, x, y = ring("x,y", ZZ)
    f, g = x*y + 2*x + 3, R(0)

    raises(ZeroDivisionError, lambda: f.div(g))
    raises(ZeroDivisionError, lambda: divmod(f, g))
    raises(ZeroDivisionError, lambda: f.rem(g))
    raises(ZeroDivisionError, lambda: f % g)
    raises(ZeroDivisionError, lambda: f.quo(g))
    raises(ZeroDivisionError, lambda: f / g)
    raises(ZeroDivisionError, lambda: f.exquo(g))

    R, x = ring("x", ZZ)

    f, g = x**2 + 1, 2*x - 4
    q, r = R(0), x**2 + 1

    assert f.div(g) == divmod(f, g) == (q, r)
    assert f.rem(g) == f % g == r
    assert f.quo(g) == q
    raises(ExactQuotientFailed, lambda: f / g)
    raises(ExactQuotientFailed, lambda: f.exquo(g))

    f, g = 3*x**3 + x**2 + x + 5, 5*x**2 - 3*x + 1
    q, r = R(0), f

    assert f.div(g) == divmod(f, g) == (q, r)
    assert f.rem(g) == f % g == r
    assert f.quo(g) == q
    raises(ExactQuotientFailed, lambda: f / g)
    raises(ExactQuotientFailed, lambda: f.exquo(g))

    f, g = 5*x**4 + 4*x**3 + 3*x**2 + 2*x + 1, x**2 + 2*x + 3
    q, r = 5*x**2 - 6*x, 20*x + 1

    assert f.div(g) == divmod(f, g) == (q, r)
    assert f.rem(g) == f % g == r
    assert f.quo(g) == q
    raises(ExactQuotientFailed, lambda: f / g)
    raises(ExactQuotientFailed, lambda: f.exquo(g))

    f, g = 5*x**5 + 4*x**4 + 3*x**3 + 2*x**2 + x, x**4 + 2*x**3 + 9
    q, r = 5*x - 6, 15*x**3 + 2*x**2 - 44*x + 54

    assert f.div(g) == divmod(f, g) == (q, r)
    assert f.rem(g) == f % g == r
    assert f.quo(g) == q
    raises(ExactQuotientFailed, lambda: f / g)
    raises(ExactQuotientFailed, lambda: f.exquo(g))

    R, x = ring("x", QQ)

    f, g = x**2 + 1, 2*x - 4
    q, r = x/2 + 1, R(5)

    assert f.div(g) == divmod(f, g) == (q, r)
    assert f.rem(g) == f % g == r
    assert f.quo(g) == q
    raises(ExactQuotientFailed, lambda: f / g)
    raises(ExactQuotientFailed, lambda: f.exquo(g))

    f, g = 3*x**3 + x**2 + x + 5, 5*x**2 - 3*x + 1
    q, r = QQ(3, 5)*x + QQ(14, 25), QQ(52, 25)*x + QQ(111, 25)

    assert f.div(g) == divmod(f, g) == (q, r)
    assert f.rem(g) == f % g == r
    assert f.quo(g) == q
    raises(ExactQuotientFailed, lambda: f / g)
    raises(ExactQuotientFailed, lambda: f.exquo(g))

    R, x,y = ring("x,y", ZZ)

    f, g = x**2 - y**2, x - y
    q, r = x + y, R(0)

    assert f.div(g) == divmod(f, g) == (q, r)
    assert f.rem(g) == f % g == r
    assert f.quo(g) == q
    assert f.exquo(g) == f / g == q

    f, g = x**2 + y**2, x - y
    q, r = x + y, 2*y**2

    assert f.div(g) == divmod(f, g) == (q, r)
    assert f.rem(g) == f % g == r
    assert f.quo(g) == q
    raises(ExactQuotientFailed, lambda: f / g)
    raises(ExactQuotientFailed, lambda: f.exquo(g))

    f, g = x**2 + y**2, -x + y
    q, r = -x - y, 2*y**2

    assert f.div(g) == divmod(f, g) == (q, r)
    assert f.rem(g) == f % g == r
    assert f.quo(g) == q
    raises(ExactQuotientFailed, lambda: f / g)
    raises(ExactQuotientFailed, lambda: f.exquo(g))

    f, g = x**2 + y**2, 2*x - 2*y
    q, r = R(0), f

    assert f.div(g) == divmod(f, g) == (q, r)
    assert f.rem(g) == f % g == r
    assert f.quo(g) == q
    raises(ExactQuotientFailed, lambda: f / g)
    raises(ExactQuotientFailed, lambda: f.exquo(g))

    R, x,y = ring("x,y", QQ)

    f, g = x**2 - y**2, x - y
    q, r = x + y, R(0)

    assert f.div(g) == divmod(f, g) == (q, r)
    assert f.rem(g) == f % g == r
    assert f.quo(g) == q
    assert f.exquo(g) == f / g == q

    f, g = x**2 + y**2, x - y
    q, r = x + y, 2*y**2

    assert f.div(g) == divmod(f, g) == (q, r)
    assert f.rem(g) == f % g == r
    assert f.quo(g) == q
    raises(ExactQuotientFailed, lambda: f / g)
    raises(ExactQuotientFailed, lambda: f.exquo(g))

    f, g = x**2 + y**2, -x + y
    q, r = -x - y, 2*y**2

    assert f.div(g) == divmod(f, g) == (q, r)
    assert f.rem(g) == f % g == r
    assert f.quo(g) == q
    raises(ExactQuotientFailed, lambda: f / g)
    raises(ExactQuotientFailed, lambda: f.exquo(g))

    f, g = x**2 + y**2, 2*x - 2*y
    q, r = x/2 + y/2, 2*y**2

    assert f.div(g) == divmod(f, g) == (q, r)
    assert f.rem(g) == f % g == r
    assert f.quo(g) == q
    raises(ExactQuotientFailed, lambda: f / g)
    raises(ExactQuotientFailed, lambda: f.exquo(g))

    R, x = ring("x", ZZ, lex)
    raises(TypeError, lambda: QQ(1, 2) / x)


def test_PolyElement___pow__():
    R, x = ring("x", ZZ, grlex)
    f = 2*x + 3

    assert f**0 == 1
    assert f**1 == f
    raises(ValueError, lambda: f**(-1))
    raises(TypeError, lambda: f ** (2.5))
    raises(TypeError, lambda: f ** ("2"))
    zero_poly = R.zero
    raises(ValueError, lambda: zero_poly**(0))

    assert f**2 == f._pow_generic(2) == f._pow_multinomial(2) == 4*x**2 + 12*x + 9
    assert f**3 == f._pow_generic(3) == f._pow_multinomial(3) == 8*x**3 + 36*x**2 + 54*x + 27
    assert f**4 == f._pow_generic(4) == f._pow_multinomial(4) == 16*x**4 + 96*x**3 + 216*x**2 + 216*x + 81
    assert f**5 == f._pow_generic(5) == f._pow_multinomial(5) == 32*x**5 + 240*x**4 + 720*x**3 + 1080*x**2 + 810*x + 243

    R, x,y,z = ring("x,y,z", ZZ, grlex)
    f = x**3*y - 2*x*y**2 - 3*z + 1
    g = x**6*y**2 - 4*x**4*y**3 - 6*x**3*y*z + 2*x**3*y + 4*x**2*y**4 + 12*x*y**2*z - 4*x*y**2 + 9*z**2 - 6*z + 1

    assert f**2 == f._pow_generic(2) == f._pow_multinomial(2) == g

    f = x + x ** 2 + x ** 3 + x ** 4 + x ** 5 + x ** 6
    g = (x**24 + 4*x**23 + 10*x**22 + 20*x**21 + 35*x**20 +
         56*x**19 + 80*x**18 + 104*x**17 + 125*x**16 + 140*x**15 +
         146*x**14 + 140*x**13 + 125*x**12 + 104*x**11 + 80*x**10 +
         56*x**9 + 35*x**8 + 20*x**7 + 10*x**6 + 4*x**5 + x**4)

    assert f**4 == f._pow_generic(4) == g

    R, t = ring("t", ZZ)
    f = -11200*t**4 - 2604*t**2 + 49
    g = 15735193600000000*t**16 + 14633730048000000*t**14 + 4828147466240000*t**12 \
      + 598976863027200*t**10 + 3130812416256*t**8 - 2620523775744*t**6 \
      + 92413760096*t**4 - 1225431984*t**2 + 5764801

    assert f**4 == f._pow_generic(4) == f._pow_multinomial(4) == g

    f = x + y - y
    result = f ** 2
    assert result == x**2 == f._pow_multinomial(2)


def test_PolyElement___divmod__():
    R1, x, y = ring("x,y", ZZ)
    R2, z = ring("z", ZZ)
    R3, a, b = ring("a,b", QQ)

    p1 = x**2 + 2*x + 1
    p2 = x + 1
    zero_poly = R1.zero

    raises(ZeroDivisionError, lambda: divmod(p1, zero_poly))

    q, r = divmod(p1, p2)
    assert q == x + 1
    assert r == R1.zero

    p3 = x**2 + 3*x + 5
    q, r = divmod(p3, p2)
    assert q == x + 2
    assert r == 3

    z_poly = z**2 + 1
    raises(TypeError, lambda: divmod(p1, z_poly))


    q, r = divmod(p1, 1)
    assert q == p1
    assert r == R1.zero

    p4 = 6*x**2 + 4*x + 2
    q, r = divmod(p4, 2)
    assert q == 3*x**2 + 2*x + 1
    assert r == R1.zero

    p5 = 5*x + 3
    q, r = divmod(p5, 2)
    assert q == 0
    assert r == x + 1

    raises(TypeError, lambda: divmod(p1, QQ(1, 2)))

    result = divmod(0, p2)
    q, r = result
    assert q == R1.zero
    assert r == R1.zero

    result = divmod(5, p2)
    q, r = result
    assert q == R1.zero
    assert r == 5

    raises(TypeError, lambda: divmod(QQ(1, 2), p2))

    Rt, t = ring("t", ZZ)
    R, x, y = ring("x,y", Rt)

    assert divmod((x + 2 * t), t) == (2, x)

    R, x, y = ring("x, y", ZZ)
    Rt, t, u = ring("t, u", R)

    assert divmod((x + y), (x * t + y * t)) == (0, x + y)


def test_PolyElement___mod__():
    R1, x, y = ring("x,y", ZZ)
    R2, z = ring("z", ZZ)

    p1 = x**2 + 2*x + 3

    raises(ZeroDivisionError, lambda: p1 % R1.zero)

    assert (x**2 + 2*x + 3) % (x + 1) == 2

    assert ((x + 1)*(x + 2)) % (x + 1) == R1.zero
    assert (x*y + x + y + 1) % (x + 1) == R1.zero # x*y + x + y + 1 = (x + 1)(y + 1)

    assert (x**2 + 2*x + 3) % 2 == x**2 + 1
    assert (x**2 + 2*x + 3) % 1 == R1.zero
    assert (7*x**2 + 5*x + 3) % 3 == x**2 - x

    raises(TypeError, lambda: (x**2 + 2*x + 3) % (z**2 + 1))
    raises(TypeError, lambda: (x**2 + 2*x + 3) % QQ(1, 2))

    assert 5 % (x + 1) == R1.domain_new(5)
    assert 0 % (x + 1) == R1.zero
    assert 10 % (x**2 + 1) == R1.domain_new(10)

    raises(TypeError, lambda: QQ(1, 2) % p1)

    Rt, t = ring("t", ZZ)
    R, x, y = ring("x,y", Rt)
    assert (x + 2*t) % t == x

    R, x, y = ring("x, y", ZZ)
    Rt, t = ring("t", R)
    assert (x + y) % (x*t + y*t) == x + y


def test_PolyElement___floordiv__():
    R, x, y = ring("x,y", ZZ)

    raises(ZeroDivisionError, lambda: x // R.zero)

    assert (x + 1) // x == R(1)
    assert (5*x + 4*y) // y == R(4)

    Rt, t = ring("t", ZZ)
    R, x, y = ring("x,y", Rt)

    assert (x + 2*t) // t == R(2)
    assert x + 2*t // t == x + 2
    raises(TypeError, lambda: x // QQ(1, 2))

    R, x, y = ring("x, y", ZZ)
    Rt, t = ring("t", R)
    Ra, a = ring("a", ZZ)

    raises(ExactQuotientFailed, lambda: (x + y) // (x*t + y*t))
    raises(TypeError, lambda: (x + y) // a)

    assert R(2) // (x + 1) == R(0) == R(2)._floordiv(x + 1)
    raises(TypeError, lambda: QQ(1, 2) // (x + 1))
    assert 5 // x == R(0)


def test_PolyElement_div():
    R, x = ring("x", ZZ, grlex)

    f = x**3 - 12*x**2 - 42
    g = x - 3

    q = x**2 - 9*x - 27
    r = -123

    assert f.div([g]) == ([q], r)

    R, x = ring("x", ZZ, grlex)
    f = x**2 + 2*x + 2
    assert f.div([R(1)]) == ([f], 0)

    R, x = ring("x", QQ, grlex)
    f = x**2 + 2*x + 2
    assert f.div([R(2)]) == ([QQ(1,2)*x**2 + x + 1], 0)

    R, x,y = ring("x,y", ZZ, grlex)
    f = 4*x**2*y - 2*x*y + 4*x - 2*y + 8

    assert f.div([R(2)]) == ([2*x**2*y - x*y + 2*x - y + 4], 0)
    assert f.div([2*y]) == ([2*x**2 - x - 1], 4*x + 8)

    f = x - 1
    g = y - 1

    assert f.div([g]) == ([0], f)

    f = x*y**2 + 1
    G = [x*y + 1, y + 1]

    Q = [y, -1]
    r = 2

    assert f.div(G) == (Q, r)

    f = x**2*y + x*y**2 + y**2
    G = [x*y - 1, y**2 - 1]

    Q = [x + y, 1]
    r = x + y + 1

    assert f.div(G) == (Q, r)

    G = [y**2 - 1, x*y - 1]

    Q = [x + 1, x]
    r = 2*x + 1

    assert f.div(G) == (Q, r)

    R, = ring("", ZZ)
    assert R(3).div(R(2)) == (0, 3)

    R, = ring("", QQ)
    assert R(3).div(R(2)) == (QQ(3, 2), 0)

    R, x = ring("x", ZZ)
    f = R(0)
    g1, g2 = x + 1, x - 1
    assert f.div([g1, g2]) == ([], R(0))

    R1, x = ring("x", ZZ)
    R2, y = ring("y", ZZ)

    f, g = x**2 + 1, y + 1
    raises(ValueError, lambda: f.div([g]))


def test_PolyElement_rem():
    R, x = ring("x", ZZ, grlex)

    f = x**3 - 12*x**2 - 42
    g = x - 3
    r = -123

    assert f.rem([g]) == f.div([g])[1] == r

    R, x,y = ring("x,y", ZZ, grlex)

    f = 4*x**2*y - 2*x*y + 4*x - 2*y + 8

    assert f.rem([R(2)]) == f.div([R(2)])[1] == 0
    assert f.rem([2*y]) == f.div([2*y])[1] == 4*x + 8

    f = x - 1
    g = y - 1

    assert f.rem([g]) == f.div([g])[1] == f

    f = x*y**2 + 1
    G = [x*y + 1, y + 1]
    r = 2

    assert f.rem(G) == f.div(G)[1] == r

    f = x**2*y + x*y**2 + y**2
    G = [x*y - 1, y**2 - 1]
    r = x + y + 1

    assert f.rem(G) == f.div(G)[1] == r

    G = [y**2 - 1, x*y - 1]
    r = 2*x + 1

    assert f.rem(G) == f.div(G)[1] == r


def test_PolyElement_deflate():
    R, x = ring("x", ZZ)

    assert (2*x**2).deflate(x**4 + 4*x**2 + 1) == ((2,), [2*x, x**2 + 4*x + 1])

    R, x,y = ring("x,y", ZZ)

    assert R(0).deflate(R(0)) == ((1, 1), [0, 0])
    assert R(1).deflate(R(0)) == ((1, 1), [1, 0])
    assert R(1).deflate(R(2)) == ((1, 1), [1, 2])
    assert R(1).deflate(2*y) == ((1, 1), [1, 2*y])
    assert (2*y).deflate(2*y) == ((1, 1), [2*y, 2*y])
    assert R(2).deflate(2*y**2) == ((1, 2), [2, 2*y])
    assert (2*y**2).deflate(2*y**2) == ((1, 2), [2*y, 2*y])

    f = x**4*y**2 + x**2*y + 1
    g = x**2*y**3 + x**2*y + 1

    assert f.deflate(g) == ((2, 1), [x**2*y**2 + x*y + 1, x*y**3 + x*y + 1])


def test_PolyElement_clear_denoms():
    R, x,y = ring("x,y", QQ)

    assert R(1).clear_denoms() == (ZZ(1), 1)
    assert R(7).clear_denoms() == (ZZ(1), 7)

    assert R(QQ(7,3)).clear_denoms() == (3, 7)
    assert R(QQ(7,3)).clear_denoms() == (3, 7)

    assert (3*x**2 + x).clear_denoms() == (1, 3*x**2 + x)
    assert (x**2 + QQ(1,2)*x).clear_denoms() == (2, 2*x**2 + x)

    rQQ, x,t = ring("x,t", QQ, lex)
    rZZ, X,T = ring("x,t", ZZ, lex)

    F = [x - QQ(17824537287975195925064602467992950991718052713078834557692023531499318507213727406844943097,413954288007559433755329699713866804710749652268151059918115348815925474842910720000)*t**7
           - QQ(4882321164854282623427463828745855894130208215961904469205260756604820743234704900167747753,12936071500236232304854053116058337647210926633379720622441104650497671088840960000)*t**6
           - QQ(36398103304520066098365558157422127347455927422509913596393052633155821154626830576085097433,25872143000472464609708106232116675294421853266759441244882209300995342177681920000)*t**5
           - QQ(168108082231614049052707339295479262031324376786405372698857619250210703675982492356828810819,58212321751063045371843239022262519412449169850208742800984970927239519899784320000)*t**4
           - QQ(5694176899498574510667890423110567593477487855183144378347226247962949388653159751849449037,1617008937529529038106756639507292205901365829172465077805138081312208886105120000)*t**3
           - QQ(154482622347268833757819824809033388503591365487934245386958884099214649755244381307907779,60637835157357338929003373981523457721301218593967440417692678049207833228942000)*t**2
           - QQ(2452813096069528207645703151222478123259511586701148682951852876484544822947007791153163,2425513406294293557160134959260938308852048743758697616707707121968313329157680)*t
           - QQ(34305265428126440542854669008203683099323146152358231964773310260498715579162112959703,202126117191191129763344579938411525737670728646558134725642260164026110763140),
         t**8 + QQ(693749860237914515552,67859264524169150569)*t**7
              + QQ(27761407182086143225024,610733380717522355121)*t**6
              + QQ(7785127652157884044288,67859264524169150569)*t**5
              + QQ(36567075214771261409792,203577793572507451707)*t**4
              + QQ(36336335165196147384320,203577793572507451707)*t**3
              + QQ(7452455676042754048000,67859264524169150569)*t**2
              + QQ(2593331082514399232000,67859264524169150569)*t
              + QQ(390399197427343360000,67859264524169150569)]

    G = [3725588592068034903797967297424801242396746870413359539263038139343329273586196480000*X -
         160420835591776763325581422211936558925462474417709511019228211783493866564923546661604487873*T**7 -
         1406108495478033395547109582678806497509499966197028487131115097902188374051595011248311352864*T**6 -
         5241326875850889518164640374668786338033653548841427557880599579174438246266263602956254030352*T**5 -
         10758917262823299139373269714910672770004760114329943852726887632013485035262879510837043892416*T**4 -
         13119383576444715672578819534846747735372132018341964647712009275306635391456880068261130581248*T**3 -
         9491412317016197146080450036267011389660653495578680036574753839055748080962214787557853941760*T**2 -
         3767520915562795326943800040277726397326609797172964377014046018280260848046603967211258368000*T -
         632314652371226552085897259159210286886724229880266931574701654721512325555116066073245696000,
         610733380717522355121*T**8 +
         6243748742141230639968*T**7 +
         27761407182086143225024*T**6 +
         70066148869420956398592*T**5 +
         109701225644313784229376*T**4 +
         109009005495588442152960*T**3 +
         67072101084384786432000*T**2 +
         23339979742629593088000*T +
         3513592776846090240000]

    assert [ f.clear_denoms()[1].set_ring(rZZ) for f in F ] == G


def test_PolyElement_cofactors():
    R, x, y = ring("x,y", ZZ)

    f, g = R(0), R(0)
    assert f.cofactors(g) == (0, 0, 0)

    f, g = R(2), R(0)
    assert f.cofactors(g) == (2, 1, 0)

    f, g = R(-2), R(0)
    assert f.cofactors(g) == (2, -1, 0)

    f, g = R(0), R(-2)
    assert f.cofactors(g) == (2, 0, -1)

    f, g = R(0), 2*x + 4
    assert f.cofactors(g) == (2*x + 4, 0, 1)

    f, g = 2*x + 4, R(0)
    assert f.cofactors(g) == (2*x + 4, 1, 0)

    f, g = R(2), R(2)
    assert f.cofactors(g) == (2, 1, 1)

    f, g = R(-2), R(2)
    assert f.cofactors(g) == (2, -1, 1)

    f, g = R(2), R(-2)
    assert f.cofactors(g) == (2, 1, -1)

    f, g = R(-2), R(-2)
    assert f.cofactors(g) == (2, -1, -1)

    f, g = x**2 + 2*x + 1, R(1)
    assert f.cofactors(g) == (1, x**2 + 2*x + 1, 1)

    f, g = x**2 + 2*x + 1, R(2)
    assert f.cofactors(g) == (1, x**2 + 2*x + 1, 2)

    f, g = 2*x**2 + 4*x + 2, R(2)
    assert f.cofactors(g) == (2, x**2 + 2*x + 1, 1)

    f, g = R(2), 2*x**2 + 4*x + 2
    assert f.cofactors(g) == (2, 1, x**2 + 2*x + 1)

    f, g = 2*x**2 + 4*x + 2, x + 1
    assert f.cofactors(g) == (x + 1, 2*x + 2, 1)

    f, g = x + 1, 2*x**2 + 4*x + 2
    assert f.cofactors(g) == (x + 1, 1, 2*x + 2)

    f, g = x**2*y + x*y**2 , x*y
    assert f.cofactors(g) == (x*y, x + y, 1)

    R, x, y, z, t = ring("x,y,z,t", ZZ)

    f, g = t**2 + 2*t + 1, 2*t + 2
    assert f.cofactors(g) == (t + 1, t + 1, 2)

    f, g = z**2*t**2 + 2*z**2*t + z**2 + z*t + z, t**2 + 2*t + 1
    h, cff, cfg = t + 1, z**2*t + z**2 + z, t + 1

    assert f.cofactors(g) == (h, cff, cfg)
    assert g.cofactors(f) == (h, cfg, cff)

    R, x, y = ring("x,y", QQ)

    f = QQ(1,2)*x**2 + x + QQ(1,2)
    g = QQ(1,2)*x + QQ(1,2)

    h = x + 1

    assert f.cofactors(g) == (h, g, QQ(1,2))
    assert g.cofactors(f) == (h, QQ(1,2), g)

    R, x, y = ring("x,y", RR)

    f = 2.1*x*y**2 - 2.1*x*y + 2.1*x
    g = 2.1*x**3
    h = 1.0*x

    assert f.cofactors(g) == (h, f/h, g/h)
    assert g.cofactors(f) == (h, g/h, f/h)


def test_PolyElement_gcd():
    R, x, y = ring("x,y", QQ)

    f = QQ(1,2)*x**2 + x + QQ(1,2)
    g = QQ(1,2)*x + QQ(1,2)

    assert f.gcd(g) == x + 1

    R, x, y = ring("x,y", RR)

    f = x**2 + x*y + x
    g = x + y + 1

    d = f.gcd(g)
    assert d == g


def test_PolyElement_cancel():
    R, x, y = ring("x,y", ZZ)

    f = 2*x**3 + 4*x**2 + 2*x
    g = 3*x**2 + 3*x
    F = 2*x + 2
    G = 3

    assert f.cancel(g) == (F, G)
    assert (-f).cancel(g) == (-F, G)
    assert f.cancel(-g) == (-F, G)

    R, x, y = ring("x,y", QQ)

    f = QQ(1,2)*x**3 + x**2 + QQ(1,2)*x
    g = QQ(1,3)*x**2 + QQ(1,3)*x
    F = 3*x + 3
    G = 2

    assert f.cancel(g) == (F, G)

    assert (-f).cancel(g) == (-F, G)
    assert f.cancel(-g) == (-F, G)

    Fx, x = field("x", ZZ)
    Rt, t = ring("t", Fx)

    f = (-x**2 - 4)/4*t
    g = t**2 + (x**2 + 2)/2

    assert f.cancel(g) == ((-x**2 - 4)*t, 4*t**2 + 2*x**2 + 4)

    R, x, y = ring("x,y", ZZ_I)
    f = x + y + ZZ_I(0, 1) * y
    g = -ZZ_I(0, 1) * x ** 2 + x + y
    assert f.cancel(g) == (I*(x + y) - y, x**2 + I*(x + y)) == ((0 + 1*I)*x + (-1 + 1*I)*y, x**2 + (0 + 1*I)*x + (0 + 1*I)*y)

def test_PolyElement_max_norm():
    R, x, y = ring("x,y", ZZ)

    assert R(0).max_norm() == 0
    assert R(1).max_norm() == 1

    assert (x**3 + 4*x**2 + 2*x + 3).max_norm() == 4


def test_PolyElement_l1_norm():
    R, x, y = ring("x,y", ZZ)

    assert R(0).l1_norm() == 0
    assert R(1).l1_norm() == 1

    assert (x**3 + 4*x**2 + 2*x + 3).l1_norm() == 10


def test_PolyElement_diff():
    R, X = xring("x:11", QQ)

    f = QQ(288,5)*X[0]**8*X[1]**6*X[4]**3*X[10]**2 + 8*X[0]**2*X[2]**3*X[4]**3 +2*X[0]**2 - 2*X[1]**2

    assert f.diff(X[0]) == QQ(2304,5)*X[0]**7*X[1]**6*X[4]**3*X[10]**2 + 16*X[0]*X[2]**3*X[4]**3 + 4*X[0]
    assert f.diff(X[4]) == QQ(864,5)*X[0]**8*X[1]**6*X[4]**2*X[10]**2 + 24*X[0]**2*X[2]**3*X[4]**2
    assert f.diff(X[10]) == QQ(576,5)*X[0]**8*X[1]**6*X[4]**3*X[10]


def test_PolyElement___call__():
    R, x = ring("x", ZZ)
    f = 3*x + 1

    assert f(0) == 1
    assert f(1) == 4

    raises(ValueError, lambda: f())
    raises(ValueError, lambda: f(0, 1))

    raises(CoercionFailed, lambda: f(QQ(1,7)))

    R, x,y = ring("x,y", ZZ)
    f = 3*x + y**2 + 1

    assert f(0, 0) == 1
    assert f(1, 7) == 53

    Ry = R.drop(x)

    assert f(0) == Ry.y**2 + 1
    assert f(1) == Ry.y**2 + 4

    raises(ValueError, lambda: f())
    raises(ValueError, lambda: f(0, 1, 2))

    raises(CoercionFailed, lambda: f(1, QQ(1,7)))
    raises(CoercionFailed, lambda: f(QQ(1,7), 1))
    raises(CoercionFailed, lambda: f(QQ(1,7), QQ(1,7)))


def test_PolyElement_evaluate():
    R, x = ring("x", ZZ)
    f = x**3 + 4*x**2 + 2*x + 3

    r = f.evaluate(x, 0)
    assert r == 3 and not isinstance(r, PolyElement)

    raises(CoercionFailed, lambda: f.evaluate(x, QQ(1,7)))

    R, x, y, z = ring("x,y,z", ZZ)
    f = (x*y)**3 + 4*(x*y)**2 + 2*x*y + 3

    r = f.evaluate(x, 0)
    assert r == 3 and R.drop(x).is_element(r)
    r = f.evaluate([(x, 0), (y, 0)])
    assert r == 3 and R.drop(x, y).is_element(r)
    r = f.evaluate(y, 0)
    assert r == 3 and R.drop(y).is_element(r)
    r = f.evaluate([(y, 0), (x, 0)])
    assert r == 3 and R.drop(y, x).is_element(r)

    r = f.evaluate([(x, 0), (y, 0), (z, 0)])
    assert r == 3 and not isinstance(r, PolyElement)

    raises(ValueError, lambda: f.evaluate((x, 1), (y, 1), (z, 1), (1, 1)))

    r = f.evaluate([])
    assert r == f

    raises(CoercionFailed, lambda: f.evaluate([(x, 1), (y, QQ(1,7))]))
    raises(CoercionFailed, lambda: f.evaluate([(x, QQ(1,7)), (y, 1)]))
    raises(CoercionFailed, lambda: f.evaluate([(x, QQ(1,7)), (y, QQ(1,7))]))


def test_PolyElement_subs():
    R, x = ring("x", ZZ)
    f = x**3 + 4*x**2 + 2*x + 3

    r = f.subs(x, 0)
    assert r == 3 and R.is_element(r)

    raises(CoercionFailed, lambda: f.subs(x, QQ(1,7)))

    R, x, y, z = ring("x,y,z", ZZ)
    f = x**3 + 4*x**2 + 2*x + 3

    assert f.subs([]) == f
    r = f.subs(x, 0)
    assert r == 3 and R.is_element(r)
    r = f.subs([(x, 0), (y, 0)])
    assert r == 3 and R.is_element(r)

    assert (x*y - y).subs(x, 1) == 0

    raises(ValueError, lambda: f.subs((x, 1), (y, 1), (z, 1), (1, 1)))

    raises(CoercionFailed, lambda: f.subs([(x, 1), (y, QQ(1,7))]))
    raises(CoercionFailed, lambda: f.subs([(x, QQ(1,7)), (y, 1)]))
    raises(CoercionFailed, lambda: f.subs([(x, QQ(1,7)), (y, QQ(1,7))]))


def test_PolyElement_symmetrize():
    R, x, y = ring("x,y", ZZ)

    # Homogeneous, symmetric
    f = x**2 + y**2
    sym, rem, m = f.symmetrize()
    assert rem == 0
    assert sym.compose(m) + rem == f

    # Homogeneous, asymmetric
    f = x**2 - y**2
    sym, rem, m = f.symmetrize()
    assert rem != 0
    assert sym.compose(m) + rem == f

    # Inhomogeneous, symmetric
    f = x*y + 7
    sym, rem, m = f.symmetrize()
    assert rem == 0
    assert sym.compose(m) + rem == f

    # Inhomogeneous, asymmetric
    f = y + 7
    sym, rem, m = f.symmetrize()
    assert rem != 0
    assert sym.compose(m) + rem == f

    # Constant
    f = R.from_expr(3)
    sym, rem, m = f.symmetrize()
    assert rem == 0
    assert sym.compose(m) + rem == f

    # Constant constructed from sring
    R, f = sring(3)
    sym, rem, m = f.symmetrize()
    assert rem == 0
    assert sym.compose(m) + rem == f


def test_PolyElement_compose():
    R, x = ring("x", ZZ)
    f = x**3 + 4*x**2 + 2*x + 3

    r = f.compose(x, 0)
    assert r == 3 and R.is_element(r)

    assert f.compose(x, x) == f
    assert f.compose(x, x**2) == x**6 + 4*x**4 + 2*x**2 + 3

    raises(CoercionFailed, lambda: f.compose(x, QQ(1,7)))

    R, x, y, z = ring("x,y,z", ZZ)
    f = x**3 + 4*x**2 + 2*x + 3

    r = f.compose(x, 0)
    assert r == 3 and R.is_element(r)
    r = f.compose([(x, 0), (y, 0)])
    assert r == 3 and R.is_element(r)

    r = (x**3 + 4*x**2 + 2*x*y*z + 3).compose(x, y*z**2 - 1)
    q = (y*z**2 - 1)**3 + 4*(y*z**2 - 1)**2 + 2*(y*z**2 - 1)*y*z + 3
    assert r == q and R.is_element(r)

    r = f.compose({x: 0, y: 0})
    assert r == 3 and R.is_element(r)

    raises(ValueError, lambda: f.compose("not a pair"))


def test_PolyElement_is_():
    R, x,y,z = ring("x,y,z", QQ)

    assert (x - x).is_generator == False
    assert (x - x).is_ground == True
    assert (x - x).is_monomial == True
    assert (x - x).is_term == True

    assert (x - x + 1).is_generator == False
    assert (x - x + 1).is_ground == True
    assert (x - x + 1).is_monomial == True
    assert (x - x + 1).is_term == True

    assert x.is_generator == True
    assert x.is_ground == False
    assert x.is_monomial == True
    assert x.is_term == True

    assert (x*y).is_generator == False
    assert (x*y).is_ground == False
    assert (x*y).is_monomial == True
    assert (x*y).is_term == True

    assert (3*x).is_generator == False
    assert (3*x).is_ground == False
    assert (3*x).is_monomial == False
    assert (3*x).is_term == True

    assert (3*x + 1).is_generator == False
    assert (3*x + 1).is_ground == False
    assert (3*x + 1).is_monomial == False
    assert (3*x + 1).is_term == False

    assert R(0).is_zero is True
    assert R(1).is_zero is False

    assert R(0).is_one is False
    assert R(1).is_one is True

    assert (x - 1).is_monic is True
    assert (2*x - 1).is_monic is False

    assert R(0).is_positive is False
    assert R(1).is_positive is True
    assert (-x + 1).is_positive is False
    assert(x + 1).is_positive is True

    assert R(0).is_negative is False
    assert R(-1).is_negative is True
    assert (-x + 1).is_negative is True
    assert (x + 1).is_negative is False

    assert R(0).is_nonpositive is True
    assert R(1).is_nonpositive is False
    assert (-x + 1).is_nonpositive is True
    assert (x + 1).is_nonpositive is False

    assert (3*x + 2).is_primitive is True
    assert (4*x + 2).is_primitive is False

    assert (x + y + z + 1).is_linear is True
    assert (x*y*z + 1).is_linear is False

    assert (x*y + z + 1).is_quadratic is True
    assert (x*y*z + 1).is_quadratic is False

    assert (x - 1).is_squarefree is True
    assert ((x - 1)**2).is_squarefree is False

    assert (x**2 + x + 1).is_irreducible is True
    assert (x**2 + 2*x + 1).is_irreducible is False

    _, t = ring("t", FF(11))

    assert (7*t + 3).is_irreducible is True
    assert (7*t**2 + 3*t + 1).is_irreducible is False

    _, u = ring("u", ZZ)
    f = u**16 + u**14 - u**10 - u**8 - u**6 + u**2

    assert f.is_cyclotomic is False
    assert (f + 1).is_cyclotomic is True

    raises(MultivariatePolynomialError, lambda: x.is_cyclotomic)

    R, = ring("", ZZ)
    assert R(4).is_squarefree is True
    assert R(6).is_irreducible is True


def test_PolyElement_drop():
    R, x,y,z = ring("x,y,z", ZZ)

    assert R(1).drop(0).ring == PolyRing("y,z", ZZ, lex)
    assert R(1).drop(0).drop(0).ring == PolyRing("z", ZZ, lex)
    assert R.is_element(R(1).drop(0).drop(0).drop(0)) is False

    raises(ValueError, lambda: z.drop(0).drop(0).drop(0))
    raises(ValueError, lambda: x.drop(0))


def test_PolyElement_drop_to_ground():
    # multivariate case, drop 'y' from ZZ[x, y]
    Rxy, x, y = ring("x, y", ZZ)
    f = x*y**2 + 2*x*y + 3*x

    g = f.drop_to_ground(y)

    # new ring has only x as generator, and domain is ZZ[y]
    assert str(g.ring.symbols) == '(x,)'
    assert str(g.ring.domain.symbols) == '(y,)'
    assert str(g.ring.domain) == 'ZZ[y]'

    # drop x instead, so x goes into the domain
    g2 = f.drop_to_ground(x)
    assert str(g2.ring.symbols)== '(y,)'
    assert str(g2.ring.domain.symbols) == '(x,)'
    assert str(g2.ring.domain) == 'ZZ[x]'

    # cannot drop the only generator
    Rx, x = ring("x", ZZ)
    f = x**2 + 1
    raises(ValueError, lambda: f.drop_to_ground(x))


def test_PolyElement_coeff_wrt():
    R, x, y, z = ring("x, y, z", ZZ)

    p = 4*x**3 + 5*y**2 + 6*y**2*z + 7
    assert p.coeff_wrt(1, 2) == 6*z + 5 # using generator index
    assert p.coeff_wrt(x, 3) == 4 # using generator

    p = 2*x**4 + 3*x*y**2*z + 10*y**2 + 10*x*z**2
    assert p.coeff_wrt(x, 1) == 3*y**2*z + 10*z**2
    assert p.coeff_wrt(y, 2) == 3*x*z + 10

    p = 4*x**2 + 2*x*y + 5
    assert p.coeff_wrt(z, 1) == R(0)
    assert p.coeff_wrt(y, 2) == R(0)


def test_PolyElement_prem():
    R, x, y = ring("x, y", ZZ)

    f, g = x**2 + x*y, 2*x + 2
    assert f.prem(g) == -4*y + 4 # first generator is chosen by default if it is not given

    f, g = x**2 + 1, 2*x - 4
    assert f.prem(g) == f.prem(g, x) == 20
    assert f.prem(g, 1) == R(0)

    f, g = x*y + 2*x + 1, x + y
    assert f.prem(g) == -y**2 - 2*y + 1
    assert f.prem(g, 1) == f.prem(g, y) == -x**2 + 2*x + 1

    f, g = x + 1, x**2 + 1
    assert f.prem(g) == f and f.prem(g, x) == f

    raises(ZeroDivisionError, lambda: f.prem(R(0)))


def test_PolyElement_pdiv():
    R, x, y = ring("x,y", ZZ)

    f, g = x**4 + 5*x**3 + 7*x**2, 2*x**2 + 3
    assert f.pdiv(g) == f.pdiv(g, x) == (4*x**2 + 20*x + 22, -60*x - 66)

    f, g = x**2 - y**2, x - y
    assert f.pdiv(g) == f.pdiv(g, 0) == (x + y, 0)

    f, g = x*y + 2*x + 1, x + y
    assert f.pdiv(g) == (y + 2, -y**2 - 2*y + 1)
    assert f.pdiv(g, y) == f.pdiv(g, 1) == (x + 1, -x**2 + 2*x + 1)

    assert R(0).pdiv(g) == (0, 0)
    raises(ZeroDivisionError, lambda: f.prem(R(0)))

    raises(ZeroDivisionError, lambda: f.pdiv(R(0)))


def test_PolyElement_pquo():
    R, x, y = ring("x, y", ZZ)

    f, g = x**4 - 4*x**2*y + 4*y**2, x**2 - 2*y
    assert f.pquo(g) == f.pquo(g, x) == x**2 - 2*y
    assert f.pquo(g, y) == 4*x**2 - 8*y + 4

    f, g = x**4 - y**4, x**2 - y**2
    assert f.pquo(g) == f.pquo(g, 0) == x**2 + y**2


def test_PolyElement_pexquo():
    R, x, y = ring("x, y", ZZ)

    f, g = x**2 - y**2, x - y
    assert f.pexquo(g) == f.pexquo(g, x) == x + y
    assert f.pexquo(g, y) == f.pexquo(g, 1) == x + y + 1

    f, g = x**2 + 3*x + 6, x + 2
    raises(ExactQuotientFailed, lambda: f.pexquo(g))


def test_PolyElement_gcdex():
    _, x = ring("x", QQ)

    f, g = 2*x, x**2 - 16
    s, t, h = x/32, -QQ(1, 16), 1

    assert f.half_gcdex(g) == (s, h)
    assert f.gcdex(g) == (s, t, h)


def test_PolyElement_subresultants():
    R, x, y = ring("x, y", ZZ)

    f, g = x**2*y + x*y, x + y # degree(f, x) > degree(g, x)
    h = y**3 - y**2
    assert f.subresultants(g) == [f, g, h] # first generator is chosen default

    # generator index or generator is given
    assert f.subresultants(g, 0) ==  f.subresultants(g, x) == [f, g, h]

    assert f.subresultants(g, y) == [x**2*y + x*y, x + y, x**3 + x**2]

    f, g = 2*x - y, x**2 + 2*y + x # degree(f, x) < degree(g, x)
    assert f.subresultants(g) == [x**2 + x + 2*y, 2*x - y, y**2 + 10*y]

    f, g = R(0), y**3 - y**2 # f = 0
    assert f.subresultants(g) == [y**3 - y**2, 1]

    f, g = x**2*y + x*y, R(0) # g = 0
    assert f.subresultants(g) == [x**2*y + x*y, 1]

    f, g = R(0), R(0) # f = 0 and g = 0
    assert f.subresultants(g) == [0, 0]

    f, g = x**2 + x, x**2 + x # f and g are same polynomial
    assert f.subresultants(g) == [x**2 + x, x**2 + x]

    R, x, y = ring("x,y", ZZ)
    f1 = x**4 + x**3 + x**2 + x + 1
    g1 = x**2 + 1
    assert f1.subresultants(g1) == [x**4 + x**3 + x**2 + x + 1, x**2 + 1, -1]


def test_PolyElement_resultant():
    _, x = ring("x", ZZ)
    f, g, h = x**2 - 2*x + 1, x**2 - 1, 0

    assert f.resultant(g) == h


def test_PolyElement_discriminant():
    _, x = ring("x", ZZ)
    f, g = x**3 + 3*x**2 + 9*x - 13, -11664

    assert f.discriminant() == g

    F, a, b, c = ring("a,b,c", ZZ)
    _, x = ring("x", F)

    f, g = a*x**2 + b*x + c, b**2 - 4*a*c

    assert f.discriminant() == g


def test_PolyElement_decompose():
    _, x = ring("x", ZZ)

    f = x**12 + 20*x**10 + 150*x**8 + 500*x**6 + 625*x**4 - 2*x**3 - 10*x + 9
    g = x**4 - 2*x + 9
    h = x**3 + 5*x

    assert g.compose(x, h) == f
    assert f.decompose() == [g, h]

    _, x, y = ring("x, y", ZZ)
    f = x**2 + y

    raises(MultivariatePolynomialError, lambda: f.decompose())


def test_PolyElement_shift():
    _, x = ring("x", ZZ)
    assert (x**2 - 2*x + 1).shift(2) == x**2 + 2*x + 1
    assert (x**2 - 2*x + 1).shift_list([2]) == x**2 + 2*x + 1

    R, x, y = ring("x, y", ZZ)
    assert (x*y).shift_list([1, 2]) == (x+1)*(y+2)

    raises(MultivariatePolynomialError, lambda: (x*y).shift(1))


def test_PolyElement_sturm():
    F, t = field("t", ZZ)
    _, x = ring("x", F)

    f = 1024/(15625*t**8)*x**5 - 4096/(625*t**8)*x**4 + 32/(15625*t**4)*x**3 - 128/(625*t**4)*x**2 + F(1)/62500*x - F(1)/625

    assert f.sturm() == [
        x**3 - 100*x**2 + t**4/64*x - 25*t**4/16,
        3*x**2 - 200*x + t**4/64,
        (-t**4/96 + F(20000)/9)*x + 25*t**4/18,
        (-9*t**12 - 11520000*t**8 - 3686400000000*t**4)/(576*t**8 - 245760000*t**4 + 26214400000000),
    ]

    _, x, y = ring("x, y", ZZ)
    f = x**2 + y

    raises(MultivariatePolynomialError, lambda: f.sturm())


def test_PolyElement_gff_list():
    _, x = ring("x", ZZ)

    f = x**5 + 2*x**4 - x**3 - 2*x**2
    assert f.gff_list() == [(x, 1), (x + 2, 4)]

    f = x*(x - 1)**3*(x - 2)**2*(x - 4)**2*(x - 5)
    assert f.gff_list() == [(x**2 - 5*x + 4, 1), (x**2 - 5*x + 4, 2), (x, 3)]


def test_PolyElement_norm():
    k = QQ
    K = QQ.algebraic_field(sqrt(2))
    sqrt2 = K.unit
    _, X, Y = ring("x,y", k)
    _, x, y = ring("x,y", K)

    assert (x*y + sqrt2).norm() == X**2*Y**2 - 2


def test_PolyElement_sqf_norm():
    R, x = ring("x", QQ.algebraic_field(sqrt(3)))
    X = R.to_ground().x

    assert (x**2 - 2).sqf_norm() == ([1], x**2 - 2*sqrt(3)*x + 1, X**4 - 10*X**2 + 1)

    R, x = ring("x", QQ.algebraic_field(sqrt(2)))
    X = R.to_ground().x

    assert (x**2 - 3).sqf_norm() == ([1], x**2 - 2*sqrt(2)*x - 1, X**4 - 10*X**2 + 1)


def test_PolyElement_sqf_list():
    _, x = ring("x", ZZ)

    f = x**5 - x**3 - x**2 + 1
    g = x**3 + 2*x**2 + 2*x + 1
    h = x - 1
    p = x**4 + x**3 - x - 1

    assert f.sqf_part() == p
    assert f.sqf_list() == (1, [(g, 1), (h, 2)])


def test_issue_18894():
    items = [S(3)/16 + sqrt(3*sqrt(3) + 10)/8, S(1)/8 + 3*sqrt(3)/16, S(1)/8 + 3*sqrt(3)/16, -S(3)/16 + sqrt(3*sqrt(3) + 10)/8]
    R, a = sring(items, extension=True)
    assert R.domain == QQ.algebraic_field(sqrt(3)+sqrt(3*sqrt(3)+10))
    assert R.gens == ()
    result = []
    for item in items:
        result.append(R.domain.from_sympy(item))
    assert a == result


def test_PolyElement_factor_list():
    _, x = ring("x", ZZ)

    f = x**5 - x**3 - x**2 + 1

    u = x + 1
    v = x - 1
    w = x**2 + x + 1

    assert f.factor_list() == (1, [(u, 1), (v, 2), (w, 1)])


def test_issue_21410():
    R, x = ring('x', FF(2))
    p = x**6 + x**5 + x**4 + x**3 + 1
    assert p._pow_multinomial(4) == x**24 + x**20 + x**16 + x**12 + 1


def test_zero_polynomial_primitive():

    x = symbols('x')

    R = ZZ[x]
    zero_poly = R(0)
    cont, prim = zero_poly.primitive()
    assert cont == 0
    assert prim == zero_poly
    assert prim.is_primitive is False


def test_PolyElement_const():
    R, x = ring("x", ZZ)

    assert R(0).const() == 0
    assert (x**2 + 2*x + 1).const() == 1


def test_PolyElement_mul_monom():
    R, x, y = ring("x, y", ZZ)
    assert (2*x*y + 3*x**2).mul_monom((1, 0)) == 2*x**2*y + 3*x**3
    assert (2*x + 3).mul_monom((0, 0)) == 2*x + 3
    assert R(5).mul_monom((3, 0)) == 5*x**3
    assert R.zero.mul_monom((2, 1)) == R.zero

    R, x, y, z = ring("x, y, z", ZZ)
    assert (2*x*y + 3*z).mul_monom((1, 2, 0)) == 2*x**2*y**3 + 3*x*y**2*z


def test_PolyElement_quo_term():
    R, x, y = ring("x, y", ZZ)

    raises(ZeroDivisionError, lambda: x.quo_term(((1, 0), 0)))

    assert R(0).quo_term(((1, 0), 2)) == R.zero

    f = x**2 + 2*x + 1
    r = f.quo_term((R.zero_monom, 2))
    assert r == (x**2 + 2*x + 1).quo_ground(2)

    f = x**2*y + 2*x*y
    term = ((1, 1), 1)
    r = f.quo_term(term)
    assert r == x + 2


def test_PolyElement_almosteq():

    Rz, x, y = ring("x,y", RR)
    Rq, a, b = ring("a,b", QQ)

    poly1 = 1.0*x**2 + 2.0*x + 3.0
    poly2 = 1.000001*x**2 + 2.000001*x + 3.000001
    poly3 = 1.0*x**2 + 2.0*x + 3.0

    poly_diff_monoms = 1.0*x**3 + 2.0*x + 3.0
    assert not poly1.almosteq(poly_diff_monoms)

    poly_diff_coeffs = 1.1*x**2 + 2.0*x + 3.0
    assert not poly1.almosteq(poly_diff_coeffs)

    assert poly1.almosteq(poly3)  # identical
    assert poly1.almosteq(poly2, tolerance=1e-5)

    assert not poly1.almosteq(5.0)

    const_poly = Rq(QQ(5, 2))
    z = symbols('z')
    assert not const_poly.almosteq(z)

    assert not const_poly.almosteq(6.0)

    assert const_poly.almosteq(2.5)


def test_PolyElement_parent():
    R, x, y = ring("x, y", ZZ)
    f = x**2 + y
    D = f.parent()

    assert D == R.to_domain()
    assert D.has_assoc_Ring


@pytest.mark.xfail(reason=(
    "PolyElement constructor prevents invalid internal states, "
    "_check() is not used because of performance concerns."
))
def test_PolyElement__check():
    R, x, y = ring("x, y", ZZ)

    f = x**2 + 2*x*y + 3
    f._check()

    invalid = object.__new__(PolyElement)
    invalid.ring = R
    dict.__init__(invalid, {(1, -1): 2})  # Invalid: negative exponent

    invalid._check()


def test_PolyElement_to_dict():
    R, x, y = ring("x,y", ZZ)

    assert R(0).to_dict() == {}
    assert R(1).to_dict() == {(0, 0): 1}

    f = x**2 + 2*x*y + y**2
    g = (x + y)**2
    expected_dict = {(2, 0): 1, (1, 1): 2, (0, 2): 1}
    assert f.to_dict() == g.to_dict() == expected_dict


def test_PolyElement_lcm():
    R, x = ring("x", QQ)
    assert (x + 1).lcm(x**2 - 1) == x**2 - 1
    assert R.zero.lcm(x + 1) == 0
    assert (x + 2).lcm(x + 2) == x + 2
    assert (x + 1).lcm(x - 1) == (x - 1).lcm(x + 1)  # symmetry

    R, x = ring("x", ZZ)
    assert (2*x + 2).lcm(3*x + 3) == 6*x + 6
    assert (4*x**2 + 8*x + 4).lcm(2*x + 2) == 4*x**2 + 8*x + 4


def test_PolyElement_quo_ground():
    R, x = ring("x", ZZ)
    raises(ZeroDivisionError, lambda: x.quo_ground(0))
    assert R.zero.quo_ground(5) == R.zero
    assert (x**2 + 2*x + 3).quo_ground(1) == x**2 + 2*x + 3
    assert (x**2 + 2*x + 4).quo_ground(2) == (x**2)/2 + x + 2

    R, x = ring("x", QQ)
    assert (x**2 + 3*x + 6).quo_ground(3) == (x**2)/3 + x + 2


def test_PolyElement_imul_num():
    R, x, y = ring("x, y", ZZ)

    p = x
    assert p.imul_num(3) == 3 * x and p.imul_num(3) is not p

    p = x + y
    assert p.imul_num(0) is p and p == R.zero

    p = x + y ** 2
    p_id = id(p)
    q = p.imul_num(5)
    assert q == 5 * x + 5 * y ** 2 and q is p and id(q) == p_id


def test_PolyElement__iadd_monom():
    R, x, y = ring("x, y", ZZ)

    p = x
    result = p._iadd_monom(((1, 2), ZZ(5)))
    assert result == x + 5 * x * y ** 2 and result is not p

    p = x ** 2 + y
    result = p._iadd_monom(((3, 0), ZZ(4)))
    assert result[(3, 0)] == 4 and result is p

    p = x ** 2 + y
    assert p._iadd_monom(((2, 0), ZZ(5)))[(2, 0)] == 6

    p = x ** 2 + y
    assert (2, 0) not in p._iadd_monom(((2, 0), ZZ(-1)))
