"""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, 36, 10, 45), 'sympy.polys.specialpolys.f_polys', 'f_polys', ({}, {}), '()', False, 'from sympy.polys.specialpolys import f_polys\n'), ((13, 11, 13, 24), 'sympy.polys.rings.ring', 'ring', ({(13, 16, 13, 19): '"""x"""', (13, 21, 13, 23): 'ZZ'}, {}), "('x', ZZ)", False, 'from sympy.polys.rings import ring\n'), ((50, 11, 50, 24), 'sympy.polys.rings.ring', 'ring', ({(50, 16, 50, 19): '"""x"""', (50, 21, 50, 23): 'QQ'}, {}), "('x', QQ)", False, 'from sympy.polys.rings import ring\n'), ((62, 12, 62, 25), 'sympy.polys.rings.ring', 'ring', ({(62, 17, 62, 20): '"""x"""', (62, 22, 62, 24): 'ZZ'}, {}), "('x', ZZ)", False, 'from sympy.polys.rings import ring\n'), ((74, 14, 74, 29), 'sympy.polys.rings.ring', 'ring', ({(74, 19, 74, 24): '"""x,y"""', (74, 26, 74, 28): 'ZZ'}, {}), "('x,y', ZZ)", False, 'from sympy.polys.rings import ring\n'), ((85, 11, 85, 29), 'sympy.polys.rings.ring', 'ring', ({(85, 16, 85, 19): '"""x"""', (85, 21, 85, 28): "ZZ['t']"}, {}), "('x', ZZ['t'])", False, 'from sympy.polys.rings import ring\n'), ((91, 14, 91, 29), 'sympy.polys.rings.ring', 'ring', ({(91, 19, 91, 24): '"""x,y"""', (91, 26, 91, 28): 'ZZ'}, {}), "('x,y', ZZ)", False, 'from sympy.polys.rings import ring\n'), ((101, 17, 101, 34), 'sympy.polys.rings.ring', 'ring', ({(101, 22, 101, 29): '"""x,y,z"""', (101, 31, 101, 33): 'ZZ'}, {}), "('x,y,z', ZZ)", False, 'from sympy.polys.rings import ring\n'), ((118, 20, 118, 39), 'sympy.polys.rings.ring', 'ring', ({(118, 25, 118, 34): '"""x,y,z,t"""', (118, 36, 118, 38): 'ZZ'}, {}), "('x,y,z,t', ZZ)", False, 'from sympy.polys.rings import ring\n'), ((122, 11, 122, 24), 'sympy.polys.rings.ring', 'ring', ({(122, 16, 122, 19): '"""x"""', (122, 21, 122, 23): 'ZZ'}, {}), "('x', ZZ)", False, 'from sympy.polys.rings import ring\n'), ((128, 14, 128, 29), 'sympy.polys.rings.ring', 'ring', ({(128, 19, 128, 24): '"""x,y"""', (128, 26, 128, 28): 'ZZ'}, {}), "('x,y', ZZ)", False, 'from sympy.polys.rings import ring\n'), ((142, 11, 142, 24), 'sympy.polys.rings.ring', 'ring', ({(142, 16, 142, 19): '"""x"""', (142, 21, 142, 23): 'ZZ'}, {}), "('x', ZZ)", False, 'from sympy.polys.rings import ring\n'), ((53, 21, 53, 26), 'sympy.polys.domains.FF', 'FF', ({(53, 24, 53, 25): '2'}, {}), '(2)', False, 'from sympy.polys.domains import FF, ZZ, QQ\n'), ((56, 21, 56, 26), 'sympy.polys.domains.FF', 'FF', ({(56, 24, 56, 25): '3'}, {}), '(3)', False, 'from sympy.polys.domains import FF, ZZ, QQ\n'), ((63, 22, 63, 27), 'sympy.polys.domains.FF', 'FF', ({(63, 25, 63, 26): '3'}, {}), '(3)', False, 'from sympy.polys.domains import FF, ZZ, QQ\n'), ((137, 26, 137, 31), 'sympy.polys.domains.FF', 'FF', ({(137, 29, 137, 30): '2'}, {}), '(2)', False, 'from sympy.polys.domains import FF, ZZ, QQ\n'), ((86, 34, 86, 55), 'sympy.polys.polyclasses.DMP', 'DMP', ({(86, 38, 86, 50): '[1, 0, 0, 0]', (86, 52, 86, 54): 'ZZ'}, {}), '([1, 0, 0, 0], ZZ)', False, 'from sympy.polys.polyclasses import DMP\n'), ((87, 10, 87, 31), 'sympy.polys.polyclasses.DMP', 'DMP', ({(87, 14, 87, 26): '[1, 0, 0, 0]', (87, 28, 87, 30): 'ZZ'}, {}), '([1, 0, 0, 0], ZZ)', False, 'from sympy.polys.polyclasses import DMP\n'), ((87, 38, 87, 50), 'sympy.polys.polyclasses.DMP', 'DMP', ({(87, 42, 87, 45): '[1]', (87, 47, 87, 49): 'ZZ'}, {}), '([1], ZZ)', False, 'from sympy.polys.polyclasses import DMP\n')]