"""Tests for dense recursive polynomials' basic tools. """

from sympy.polys.densebasic import (
    dup_LC, dmp_LC,
    dup_TC, dmp_TC,
    dmp_ground_LC, dmp_ground_TC,
    dmp_true_LT,
    dup_degree, dmp_degree,
    dmp_degree_in, dmp_degree_list,
    dup_strip, dmp_strip,
    dmp_validate,
    dup_reverse,
    dup_copy, dmp_copy,
    dup_normal, dmp_normal,
    dup_convert, dmp_convert,
    dup_nth, dmp_nth, dmp_ground_nth,
    dmp_zero_p, dmp_zero,
    dmp_one_p, dmp_one,
    dmp_ground_p, dmp_ground,
    dmp_negative_p, dmp_positive_p,
    dmp_zeros, dmp_grounds,
    dup_from_dict, dup_from_raw_dict,
    dup_to_dict, dup_to_raw_dict,
    dmp_from_dict, dmp_to_dict,
    dmp_swap, dmp_permute,
    dmp_nest, dmp_raise,
    dup_deflate, dmp_deflate,
    dup_multi_deflate, dmp_multi_deflate,
    dup_inflate, dmp_inflate,
    dmp_exclude, dmp_include,
    dmp_inject, dmp_eject,
    dup_terms_gcd, dmp_terms_gcd,
    dmp_list_terms, dmp_apply_pairs,
)

from sympy.polys.specialpolys import (
    f_0, f_1, f_2, f_3, f_4, f_5, f_6
)

from sympy.polys.polyclasses import (
    DUP, DMP
)

from sympy.polys.algebratools import ZZ, QQ

from sympy.utilities.pytest import raises

def test_dup_LC():
    assert dup_LC([], ZZ) == 0
    assert dup_LC([2,3,4,5], ZZ) == 2

def test_dup_TC():
    assert dup_TC([], ZZ) == 0
    assert dup_TC([2,3,4,5], ZZ) == 5

def test_dmp_LC():
    assert dmp_LC([[]], ZZ) == []
    assert dmp_LC([[2,3,4],[5]], ZZ) == [2,3,4]
    assert dmp_LC([[[]]], ZZ) == [[]]
    assert dmp_LC([[[2],[3,4]],[[5]]], ZZ) == [[2],[3,4]]

def test_dmp_TC():
    assert dmp_TC([[]], ZZ) == []
    assert dmp_TC([[2,3,4],[5]], ZZ) == [5]
    assert dmp_TC([[[]]], ZZ) == [[]]
    assert dmp_TC([[[2],[3,4]],[[5]]], ZZ) == [[5]]

def test_dmp_ground_LC():
    assert dmp_ground_LC([[]], 1, ZZ) == 0
    assert dmp_ground_LC([[2,3,4],[5]], 1, ZZ) == 2
    assert dmp_ground_LC([[[]]], 2, ZZ) == 0
    assert dmp_ground_LC([[[2],[3,4]],[[5]]], 2, ZZ) == 2

def test_dmp_ground_TC():
    assert dmp_ground_TC([[]], 1, ZZ) == 0
    assert dmp_ground_TC([[2,3,4],[5]], 1, ZZ) == 5
    assert dmp_ground_TC([[[]]], 2, ZZ) == 0
    assert dmp_ground_TC([[[2],[3,4]],[[5]]], 2, ZZ) == 5

def test_dmp_true_LT():
    assert dmp_true_LT([[]], 1, ZZ) == ((0, 0), 0)
    assert dmp_true_LT([[7]], 1, ZZ) == ((0, 0), 7)

    assert dmp_true_LT([[1,0]], 1, ZZ) == ((0, 1), 1)
    assert dmp_true_LT([[1],[]], 1, ZZ) == ((1, 0), 1)
    assert dmp_true_LT([[1,0],[]], 1, ZZ) == ((1, 1), 1)

def test_dup_degree():
    assert dup_degree([]) == -1
    assert dup_degree([1]) == 0
    assert dup_degree([1,0]) == 1
    assert dup_degree([1,0,0,0,1]) == 4

def test_dmp_degree():
    assert dmp_degree([[]], 1) == -1
    assert dmp_degree([[[]]], 2) == -1

    assert dmp_degree([[1]], 1) == 0
    assert dmp_degree([[2],[1]], 1) == 1

def test_dmp_degree_in():
    assert dmp_degree_in([[[]]], 0, 2) == -1
    assert dmp_degree_in([[[]]], 1, 2) == -1
    assert dmp_degree_in([[[]]], 2, 2) == -1

    assert dmp_degree_in([[[1]]], 0, 2) == 0
    assert dmp_degree_in([[[1]]], 1, 2) == 0
    assert dmp_degree_in([[[1]]], 2, 2) == 0

    assert dmp_degree_in(f_4, 0, 2) == 9
    assert dmp_degree_in(f_4, 1, 2) == 12
    assert dmp_degree_in(f_4, 2, 2) == 8

    assert dmp_degree_in(f_6, 0, 2) == 4
    assert dmp_degree_in(f_6, 1, 2) == 4
    assert dmp_degree_in(f_6, 2, 2) == 6
    assert dmp_degree_in(f_6, 3, 3) == 3

    raises(IndexError, "dmp_degree_in([[1]], -5, 1)")

def test_dmp_degree_list():
    assert dmp_degree_list([[[[ ]]]], 3) == (-1,-1,-1,-1)
    assert dmp_degree_list([[[[1]]]], 3) == ( 0, 0, 0, 0)

    assert dmp_degree_list(f_0, 2) == (2, 2, 2)
    assert dmp_degree_list(f_1, 2) == (3, 3, 3)
    assert dmp_degree_list(f_2, 2) == (5, 3, 3)
    assert dmp_degree_list(f_3, 2) == (5, 4, 7)
    assert dmp_degree_list(f_4, 2) == (9, 12, 8)
    assert dmp_degree_list(f_5, 2) == (3, 3, 3)
    assert dmp_degree_list(f_6, 3) == (4, 4, 6, 3)

def test_dup_strip():
    assert dup_strip([]) == []
    assert dup_strip([0]) == []
    assert dup_strip([0,0,0]) == []

    assert dup_strip([1]) == [1]
    assert dup_strip([0,1]) == [1]
    assert dup_strip([0,0,0,1]) == [1]

    assert dup_strip([1,2,0]) == [1,2,0]
    assert dup_strip([0,1,2,0]) == [1,2,0]
    assert dup_strip([0,0,0,1,2,0]) == [1,2,0]

def test_dmp_strip():
    assert dmp_strip([0,1,0], 0) == [1,0]

    assert dmp_strip([[]], 1) == [[]]
    assert dmp_strip([[], []], 1) == [[]]
    assert dmp_strip([[], [], []], 1) == [[]]

    assert dmp_strip([[[]]], 2) == [[[]]]
    assert dmp_strip([[[]], [[]]], 2) == [[[]]]
    assert dmp_strip([[[]], [[]], [[]]], 2) == [[[]]]

    assert dmp_strip([[[1]]], 2) == [[[1]]]
    assert dmp_strip([[[]], [[1]]], 2) == [[[1]]]
    assert dmp_strip([[[]], [[1]], [[]]], 2) == [[[1]], [[]]]

def test_dmp_validate():
    assert dmp_validate([]) == ([], 0)
    assert dmp_validate([0,0,0,1,0]) == ([1,0], 0)

    assert dmp_validate([[[]]]) == ([[[]]], 2)
    assert dmp_validate([[0],[],[0],[1],[0]]) == ([[1],[]], 1)

    raises(ValueError, 'dmp_validate([[0],0,[0],[1],[0]])')

def test_dup_reverse():
    assert dup_reverse([1,2,0,3]) == [3,0,2,1]
    assert dup_reverse([1,2,3,0]) == [3,2,1]

def test_dup_copy():
    f = [ZZ(1),ZZ(0),ZZ(2)]
    g = dup_copy(f)

    g[0], g[2] = ZZ(7), ZZ(0)

    assert f != g

def test_dmp_copy():
    f = [[ZZ(1)],[ZZ(2),ZZ(0)]]
    g = dmp_copy(f, 1)

    g[0][0], g[1][1] = ZZ(7), ZZ(1)

    assert f != g

def test_dup_normal():
    assert dup_normal([0,0,2,1,0,11,0], ZZ) == \
        [ZZ(2),ZZ(1),ZZ(0),ZZ(11),ZZ(0)]

def test_dmp_normal():
    assert dmp_normal([[0],[],[0,2,1],[0],[11],[]], 1, ZZ) == \
        [[ZZ(2),ZZ(1)],[],[ZZ(11)],[]]

def test_dup_convert():
    K0, K1 = ZZ['x'], ZZ

    f = [DMP([1], ZZ),DMP([2], ZZ),DMP([], ZZ),DMP([3], ZZ)]

    assert dup_convert(f, K0, K1) == \
        [ZZ(1),ZZ(2),ZZ(0),ZZ(3)]

def test_dmp_convert():
    K0, K1 = ZZ['x'], ZZ

    f = [[DMP([1], ZZ)],[DMP([2], ZZ)],[],[DMP([3], ZZ)]]

    assert dmp_convert(f, 1, K0, K1) == \
        [[ZZ(1)],[ZZ(2)],[],[ZZ(3)]]

def test_dup_nth():
    assert dup_nth([1,2,3], 0, ZZ) == 3
    assert dup_nth([1,2,3], 1, ZZ) == 2
    assert dup_nth([1,2,3], 2, ZZ) == 1

    assert dup_nth([1,2,3], 9, ZZ) == 0

    raises(IndexError, 'dup_nth([3,4,5], -1, ZZ)')

def test_dmp_nth():
    assert dmp_nth([[1],[2],[3]], 0, 1, ZZ) == [3]
    assert dmp_nth([[1],[2],[3]], 1, 1, ZZ) == [2]
    assert dmp_nth([[1],[2],[3]], 2, 1, ZZ) == [1]

    assert dmp_nth([[1],[2],[3]], 9, 1, ZZ) == []

    raises(IndexError, 'dmp_nth([[3],[4],[5]], -1, 1, ZZ)')

def test_dmp_ground_nth():
    assert dmp_ground_nth([[1],[2],[3]], (0,0), 1, ZZ) == 3
    assert dmp_ground_nth([[1],[2],[3]], (1,0), 1, ZZ) == 2
    assert dmp_ground_nth([[1],[2],[3]], (2,0), 1, ZZ) == 1

    assert dmp_ground_nth([[1],[2],[3]], (2,1), 1, ZZ) == 0
    assert dmp_ground_nth([[1],[2],[3]], (3,0), 1, ZZ) == 0

    raises(IndexError, 'dmp_ground_nth([[3],[4],[5]], (2,-1), 1, ZZ)')

def test_dmp_zero_p():
    assert dmp_zero_p([], 0) == True
    assert dmp_zero_p([[]], 1) == True

    assert dmp_zero_p([[[]]], 2) == True
    assert dmp_zero_p([[[1]]], 2) == False

def test_dmp_zero():
    assert dmp_zero(0) == []
    assert dmp_zero(2) == [[[]]]

def test_dmp_one_p():
    assert dmp_one_p([1], 0, ZZ) == True
    assert dmp_one_p([[1]], 1, ZZ) == True
    assert dmp_one_p([[[1]]], 2, ZZ) == True
    assert dmp_one_p([[[12]]], 2, ZZ) == False

def test_dmp_one():
    assert dmp_one(0, ZZ) == [ZZ(1)]
    assert dmp_one(2, ZZ) == [[[ZZ(1)]]]

def test_dmp_ground_p():
    assert dmp_ground_p([], 0, 0) == True
    assert dmp_ground_p([[]], 0, 1) == True
    assert dmp_ground_p([[]], 1, 1) == False

    assert dmp_ground_p([[ZZ(1)]], 1, 1) == True
    assert dmp_ground_p([[[ZZ(2)]]], 2, 2) == True

    assert dmp_ground_p([[[ZZ(2)]]], 3, 2) == False
    assert dmp_ground_p([[[ZZ(3)], []]], 3, 2) == False

    assert dmp_ground_p([], None, 0) == True
    assert dmp_ground_p([[]], None, 1) == True

    assert dmp_ground_p([ZZ(1)], None, 0) == True
    assert dmp_ground_p([[[ZZ(1)]]], None, 2) == True

    assert dmp_ground_p([[[ZZ(3)], []]], None, 2) == False

def test_dmp_ground():
    assert dmp_ground(ZZ(0), 2) == [[[]]]

    assert dmp_ground(ZZ(7),-1) == ZZ(7)
    assert dmp_ground(ZZ(7), 0) == [ZZ(7)]
    assert dmp_ground(ZZ(7), 2) == [[[ZZ(7)]]]

def test_dmp_zeros():
    assert dmp_zeros(4, 0, ZZ) == [[], [], [], []]

    assert dmp_zeros(0, 2, ZZ) == []
    assert dmp_zeros(1, 2, ZZ) == [[[[]]]]
    assert dmp_zeros(2, 2, ZZ) == [[[[]]], [[[]]]]
    assert dmp_zeros(3, 2, ZZ) == [[[[]]], [[[]]], [[[]]]]

    assert dmp_zeros(3, -1, ZZ) == [0, 0, 0]

def test_dmp_grounds():
    assert dmp_grounds(ZZ(7), 0, 2) == []

    assert dmp_grounds(ZZ(7), 1, 2) == [[[[7]]]]
    assert dmp_grounds(ZZ(7), 2, 2) == [[[[7]]], [[[7]]]]
    assert dmp_grounds(ZZ(7), 3, 2) == [[[[7]]], [[[7]]], [[[7]]]]

    assert dmp_grounds(ZZ(7), 3, -1) == [7, 7, 7]

def test_dmp_negative_p():
    assert dmp_negative_p([[[]]], 2, ZZ) == False
    assert dmp_negative_p([[[1], [2]]], 2, ZZ) == False
    assert dmp_negative_p([[[-1], [2]]], 2, ZZ) == True

def test_dmp_positive_p():
    assert dmp_positive_p([[[]]], 2, ZZ) == False
    assert dmp_positive_p([[[1], [2]]], 2, ZZ) == True
    assert dmp_positive_p([[[-1], [2]]], 2, ZZ) == False

def test_dup_from_to_dict():
    assert dup_from_raw_dict({}, ZZ) == []
    assert dup_from_dict({}, ZZ) == []

    assert dup_to_raw_dict([]) == {}
    assert dup_to_dict([]) == {}

    f = [3,0,0,2,0,0,0,0,8]
    g = {8: 3, 5: 2, 0: 8}
    h = {(8,): 3, (5,): 2, (0,): 8}

    assert dup_from_raw_dict(g, ZZ) == f
    assert dup_from_dict(h, ZZ) == f

    assert dup_to_raw_dict(f) == g
    assert dup_to_dict(f) == h

    K = ZZ['x','y']

    f = [K([[3]]),K([[]]),K([[2]]),K([[]]),K([[]]),K([[8]])]
    g = {5: K([[3]]), 3: K([[2]]), 0: K([[8]])}
    h = {(5,): K([[3]]), (3,): K([[2]]), (0,): K([[8]])}

    assert dup_from_raw_dict(g, K) == f
    assert dup_from_dict(h, K) == f

    assert dup_to_raw_dict(f) == g
    assert dup_to_dict(f) == h

def test_dmp_from_to_dict():
    assert dmp_from_dict({}, 1, ZZ) == [[]]
    assert dmp_to_dict([[]], 1) == {}

    f = [[3],[],[],[2],[],[],[],[],[8]]
    g = {(8,0): 3, (5,0): 2, (0,0): 8}

    assert dmp_from_dict(g, 1, ZZ) == f
    assert dmp_to_dict(f, 1) == g

def test_dmp_swap():
    f = dmp_normal([[1,0,0],[],[1,0],[],[1]], 1, ZZ)
    g = dmp_normal([[1,0,0,0,0],[1,0,0],[1]], 1, ZZ)

    assert dmp_swap(f, 1, 1, 1, ZZ) == f

    assert dmp_swap(f, 0, 1, 1, ZZ) == g
    assert dmp_swap(g, 0, 1, 1, ZZ) == f

    raises(IndexError, "dmp_swap(f, -1, -7, 1, ZZ)")

def test_dmp_permute():
    f = dmp_normal([[1,0,0],[],[1,0],[],[1]], 1, ZZ)
    g = dmp_normal([[1,0,0,0,0],[1,0,0],[1]], 1, ZZ)

    assert dmp_permute(f, [0, 1], 1, ZZ) == f
    assert dmp_permute(g, [0, 1], 1, ZZ) == g

    assert dmp_permute(f, [1, 0], 1, ZZ) == g
    assert dmp_permute(g, [1, 0], 1, ZZ) == f

def test_dmp_nest():
    assert dmp_nest(ZZ(1), 2, ZZ) == [[[1]]]

    assert dmp_nest([[1]], 0, ZZ) == [[1]]
    assert dmp_nest([[1]], 1, ZZ) == [[[1]]]
    assert dmp_nest([[1]], 2, ZZ) == [[[[1]]]]

def test_dmp_raise():
    assert dmp_raise([], 2, 0, ZZ) == [[[]]]
    assert dmp_raise([[1]], 0, 1, ZZ) == [[1]]

    assert dmp_raise([[1,2,3], [], [2,3]], 2, 1, ZZ) == \
        [[[[1]],[[2]],[[3]]], [[[]]], [[[2]],[[3]]]]

def test_dup_deflate():
    assert dup_deflate([], ZZ) == (1, [])
    assert dup_deflate([2], ZZ) == (1, [2])
    assert dup_deflate([1,2,3], ZZ) == (1, [1,2,3])
    assert dup_deflate([1,0,2,0,3], ZZ) == (2, [1,2,3])

    assert dup_deflate(dup_from_raw_dict({7:1,1:1}, ZZ), ZZ) == \
        (1, [1, 0, 0, 0, 0, 0, 1, 0])
    assert dup_deflate(dup_from_raw_dict({7:1,0:1}, ZZ), ZZ) == \
        (7, [1, 1])
    assert dup_deflate(dup_from_raw_dict({7:1,3:1}, ZZ), ZZ) == \
        (1, [1, 0, 0, 0, 1, 0, 0, 0])

    assert dup_deflate(dup_from_raw_dict({7:1,4:1}, ZZ), ZZ) == \
        (1, [1, 0, 0, 1, 0, 0, 0, 0])
    assert dup_deflate(dup_from_raw_dict({8:1,4:1}, ZZ), ZZ) == \
        (4, [1, 1, 0])

    assert dup_deflate(dup_from_raw_dict({8:1}, ZZ), ZZ) == \
        (8, [1, 0])
    assert dup_deflate(dup_from_raw_dict({7:1}, ZZ), ZZ) == \
        (7, [1, 0])
    assert dup_deflate(dup_from_raw_dict({1:1}, ZZ), ZZ) == \
        (1, [1, 0])

def test_dmp_deflate():
    assert dmp_deflate([[]], 1, ZZ) == ((1, 1), [[]])
    assert dmp_deflate([[2]], 1, ZZ) == ((1, 1), [[2]])

    f = [[1, 0, 0], [], [1, 0], [], [1]]

    assert dmp_deflate(f, 1, ZZ) == ((2, 1), [[1, 0, 0], [1, 0], [1]])

def test_dup_multi_deflate():
    assert dup_multi_deflate(([2],), ZZ) == (1, ([2],))
    assert dup_multi_deflate(([], []), ZZ) == (1, ([], []))

    assert dup_multi_deflate(([1,2,3],), ZZ) == (1, ([1,2,3],))
    assert dup_multi_deflate(([1,0,2,0,3],), ZZ) == (2, ([1,2,3],))

    assert dup_multi_deflate(([1,0,2,0,3], [2,0,0]), ZZ) == \
        (2, ([1,2,3], [2,0]))
    assert dup_multi_deflate(([1,0,2,0,3], [2,1,0]), ZZ) == \
        (1, ([1,0,2,0,3], [2,1,0]))

def test_dmp_multi_deflate():
    assert dmp_multi_deflate(([[]],), 1, ZZ) == \
        ((1, 1), ([[]],))
    assert dmp_multi_deflate(([[]], [[]]), 1, ZZ) == \
        ((1, 1), ([[]], [[]]))

    assert dmp_multi_deflate(([[1]], [[]]), 1, ZZ) == \
        ((1, 1), ([[1]], [[]]))
    assert dmp_multi_deflate(([[1]], [[2]]), 1, ZZ) == \
        ((1, 1), ([[1]], [[2]]))
    assert dmp_multi_deflate(([[1]], [[2,0]]), 1, ZZ) == \
        ((1, 1), ([[1]], [[2, 0]]))

    assert dmp_multi_deflate(([[2,0]], [[2,0]]), 1, ZZ) == \
        ((1, 1), ([[2, 0]], [[2, 0]]))

    assert dmp_multi_deflate(([[2]], [[2,0,0]]), 1, ZZ) == ((1, 2), ([[2]], [[2, 0]]))
    assert dmp_multi_deflate(([[2,0,0]], [[2,0,0]]), 1, ZZ) == ((1, 2), ([[2, 0]], [[2, 0]]))

    assert dmp_multi_deflate(([2,0,0], [1,0,4,0,1]), 0, ZZ) == \