"""Tests for square-free decomposition algorithms and related tools. """

from sympy.polys.rings import ring
from sympy.polys.domains import FF, ZZ, QQ
from sympy.polys.polyclasses import DMP
from sympy.polys.specialpolys import f_polys

from sympy.utilities.pytest import raises

f_0, f_1, f_2, f_3, f_4, f_5, f_6 = f_polys()

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

    assert R.dup_sqf_part(0) == 0
    assert R.dup_sqf_p(0) is True

    assert R.dup_sqf_part(7) == 1
    assert R.dup_sqf_p(7) is True

    assert R.dup_sqf_part(2*x + 2) == x + 1
    assert R.dup_sqf_p(2*x + 2) is True

    assert R.dup_sqf_part(x**3 + x + 1) == x**3 + x + 1
    assert R.dup_sqf_p(x**3 + x + 1) is True

    assert R.dup_sqf_part(-x**3 + x + 1) == x**3 - x - 1
    assert R.dup_sqf_p(-x**3 + x + 1) is True

    assert R.dup_sqf_part(2*x**3 + 3*x**2) == 2*x**2 + 3*x
    assert R.dup_sqf_p(2*x**3 + 3*x**2) is False

    assert R.dup_sqf_part(-2*x**3 + 3*x**2) == 2*x**2 - 3*x
    assert R.dup_sqf_p(-2*x**3 + 3*x**2) is False

    assert R.dup_sqf_list(0) == (0, [])
    assert R.dup_sqf_list(1) == (1, [])

    assert R.dup_sqf_list(x) == (1, [(x, 1)])
    assert R.dup_sqf_list(2*x**2) == (2, [(x, 2)])
    assert R.dup_sqf_list(3*x**3) == (3, [(x, 3)])

    assert R.dup_sqf_list(-x**5 + x**4 + x - 1) == \
        (-1, [(x**3 + x**2 + x + 1, 1), (x - 1, 2)])
    assert R.dup_sqf_list(x**8 + 6*x**6 + 12*x**4 + 8*x**2) == \
        ( 1, [(x, 2), (x**2 + 2, 3)])

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

    R, x = ring("x", QQ)
    assert R.dup_sqf_list(2*x**2 + 4*x + 2) == (2, [(x + 1, 2)])

    R, x = ring("x", FF(2))
    assert R.dup_sqf_list(x**2 + 1) == (1, [(x + 1, 2)])

    R, x = ring("x", FF(3))
    assert R.dup_sqf_list(x**10 + 2*x**7 + 2*x**4 + x) == \
        (1, [(x, 1),
             (x + 1, 3),
             (x + 2, 6)])

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

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

    assert R1.dup_sqf_part(f) == f
    assert R2.dup_sqf_part(g) == y + 1

    assert R1.dup_sqf_p(f) is True
    assert R2.dup_sqf_p(g) is False

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

    A = x**4 - 3*x**2 + 6
    D = x**6 - 5*x**4 + 5*x**2 + 4

    f, g = D, R.dmp_sub(A, R.dmp_mul(R.dmp_diff(D, 1), y))
    res = R.dmp_resultant(f, g)
    h = (4*y**2 + 1).drop(x)

    assert R.drop(x).dup_sqf_list(res) == (45796, [(h, 3)])

    R, x = ring("x", ZZ["t"])
    assert R.dup_sqf_list_include(DMP([1, 0, 0, 0], ZZ)*x**2) == \
        [(DMP([1, 0, 0, 0], ZZ), 1), (DMP([1], ZZ)*x, 2)]


def test_dmp_sqf():
    R, x, y = ring("x,y", ZZ)
    assert R.dmp_sqf_part(0) == 0
    assert R.dmp_sqf_p(0) is True

    assert R.dmp_sqf_part(7) == 1
    assert R.dmp_sqf_p(7) is True

    assert R.dmp_sqf_list(3) == (3, [])
    assert R.dmp_sqf_list_include(3) == [(3, 1)]

    R, x, y, z = ring("x,y,z", ZZ)
    assert R.dmp_sqf_p(f_0) is True
    assert R.dmp_sqf_p(f_0**2) is False
    assert R.dmp_sqf_p(f_1) is True
    assert R.dmp_sqf_p(f_1**2) is False
    assert R.dmp_sqf_p(f_2) is True
    assert R.dmp_sqf_p(f_2**2) is False
    assert R.dmp_sqf_p(f_3) is True
    assert R.dmp_sqf_p(f_3**2) is False
    assert R.dmp_sqf_p(f_5) is False
    assert R.dmp_sqf_p(f_5**2) is False

    assert R.dmp_sqf_p(f_4) is True
    assert R.dmp_sqf_part(f_4) == -f_4

    assert R.dmp_sqf_part(f_5) == x + y - z

    R, x, y, z, t = ring("x,y,z,t", ZZ)
    assert R.dmp_sqf_p(f_6) is True
    assert R.dmp_sqf_part(f_6) == f_6

    R, x = ring("x", ZZ)
    f = -x**5 + x**4 + x - 1

    assert R.dmp_sqf_list(f) == (-1, [(x**3 + x**2 + x + 1, 1), (x - 1, 2)])
    assert R.dmp_sqf_list_include(f) == [(-x**3 - x**2 - x - 1, 1), (x - 1, 2)]

    R, x, y = ring("x,y", ZZ)
    f = -x**5 + x**4 + x - 1

    assert R.dmp_sqf_list(f) == (-1, [(x**3 + x**2 + x + 1, 1), (x - 1, 2)])
    assert R.dmp_sqf_list_include(f) == [(-x**3 - x**2 - x - 1, 1), (x - 1, 2)]

    f = -x**2 + 2*x - 1
    assert R.dmp_sqf_list_include(f) == [(-1, 1), (x - 1, 2)]

    R, x, y = ring("x,y", FF(2))
    raises(NotImplementedError, lambda: R.dmp_sqf_list(y**2 + 1))


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

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

    g = x**9 - 20*x**8 + 166*x**7 - 744*x**6 + 1965*x**5 - 3132*x**4 + 2948*x**3 - 1504*x**2 + 320*x
    assert R.dup_gff_list(g) == [(x**2 - 5*x + 4, 1), (x**2 - 5*x + 4, 2), (x, 3)]

    raises(ValueError, lambda: R.dup_gff_list(0))

[(10, 'sympy.polys.specialpolys.f_polys', 'f_polys', False, 'from sympy.polys.specialpolys import f_polys\n'), (13, 'sympy.polys.rings.ring', 'ring', False, 'from sympy.polys.rings import ring\n'), (50, 'sympy.polys.rings.ring', 'ring', False, 'from sympy.polys.rings import ring\n'), (62, 'sympy.polys.rings.ring', 'ring', False, 'from sympy.polys.rings import ring\n'), (74, 'sympy.polys.rings.ring', 'ring', False, 'from sympy.polys.rings import ring\n'), (85, 'sympy.polys.rings.ring', 'ring', False, 'from sympy.polys.rings import ring\n'), (91, 'sympy.polys.rings.ring', 'ring', False, 'from sympy.polys.rings import ring\n'), (101, 'sympy.polys.rings.ring', 'ring', False, 'from sympy.polys.rings import ring\n'), (118, 'sympy.polys.rings.ring', 'ring', False, 'from sympy.polys.rings import ring\n'), (122, 'sympy.polys.rings.ring', 'ring', False, 'from sympy.polys.rings import ring\n'), (128, 'sympy.polys.rings.ring', 'ring', False, 'from sympy.polys.rings import ring\n'), (142, 'sympy.polys.rings.ring', 'ring', False, 'from sympy.polys.rings import ring\n'), (53, 'sympy.polys.domains.FF', 'FF', False, 'from sympy.polys.domains import FF, ZZ, QQ\n'), (56, 'sympy.polys.domains.FF', 'FF', False, 'from sympy.polys.domains import FF, ZZ, QQ\n'), (63, 'sympy.polys.domains.FF', 'FF', False, 'from sympy.polys.domains import FF, ZZ, QQ\n'), (137, 'sympy.polys.domains.FF', 'FF', False, 'from sympy.polys.domains import FF, ZZ, QQ\n'), (86, 'sympy.polys.polyclasses.DMP', 'DMP', False, 'from sympy.polys.polyclasses import DMP\n'), (87, 'sympy.polys.polyclasses.DMP', 'DMP', False, 'from sympy.polys.polyclasses import DMP\n'), (87, 'sympy.polys.polyclasses.DMP', 'DMP', False, 'from sympy.polys.polyclasses import DMP\n')]