#!/usr/bin/python2


def expand(l):
    
    return expand_help(l, [], 1)


def expand_help(l, r, s):

    """
    Basically what we want to do is walk through a list like 
    l = [(0, 2), (0, 1), (1, 2)] and turn it into something like
    r = [(-1, [(0, 2)]), (-1, [(0, 1), (1, 2)])], so there are a
    few different cases. 

    if l[0] is a list then we should expand that, if not then it must be 
    (1, [(0, 2)]) by definition of phi_b_ext.

    if l[1] is a list, expand that, then if l[2] is a list as well expand
    it and foil, otherwise multiply each element of l[1] by l[2],

    similarly, if l[2] is a list, multiply each element of l[2] by l[1],
    otherwise just multiply l[1] and l[2]
    """

    if type(l[0]) == list:
        r.extend(expand_help(l[0], [], -1*s))
    else:
        r.append((-1*s, [l[0]]))

    t = []
    if type(l[1]) == list:
        a = expand_help(l[1], [], -1*s)
        if type(l[2]) == list:
            b = expand_help(l[2], [], s)
            for i in a:
                s_a, els_a = i
                for j in b:
                    n_a = list(els_a)
                    s_b, els_b = j
                    n_a.extend(els_b)
                    t.append((s_a*s_b, n_a))
        else:
            for i in a:
                x, y = i
                y.append(l[2])
                t.append((x, y))
    else:
        if type(l[2]) == list:
            a = expand_help(l[2], [], s)
            for i in a:
                x, y = i
                if type(y) == list:
                    new_l1 = [l[1]]
                    new_l1.extend(y)
                    t.append((-1*s*x, new_l1))
                else:
                    t.append((-1*s*x, [l[1], y]))
        else:
            t.append((-1*s, [l[1]]))
            t[-1][1].append(l[2])

    r.extend(t)
    return r

def test_expand():

    a = [(0, 2), (0, 1), (1, 2)]
    r = [(-1, [(0, 2)]), (-1, [(0, 1), (1, 2)])]
    t = expand(a)

    print "test 1:"
    print "-as2 - as1a12"
    print "a = " + str(a)
    print "r = " + str(r)
    print "t = " + str(t)

    try:
        assert t == r
        print "PASS"
    except AssertionError:
        print "FAILED"
        exit()

    print

    a = [[(0, 2), (0, 1), (1, 2)], (2, 1), (1,  0)]
    r = [(1, [(0, 2)]), (1, [(0, 1), (1, 2)]), (-1, [(2, 1), (1, 0)])]
    t = expand(a)

    print "test 2:"
    print "-(-as2 - as1*a12) - a21*a1s"
    print "a = " + str(a)
    print "r = " + str(r)
    print "t = " + str(t)

    try:
        assert t == r
        print "PASS"
    except AssertionError:
        print "FAILED"
        exit()

    print 

    a = [(1, 0), (2, 1), [(0, 1), (1, 2), (2, 0)]]
    r = [(-1, [(1, 0)]), (1, [(2, 1), (0, 1)]), (1, [(2, 1), (1, 2), (2, 0)])]
    t = expand(a)

    print "test 3:"
    print "-a1s - a21*(-as1 - a12*a2s)"
    print "a = " + str(a)
    print "r = " + str(r)
    print "t = " + str(t)

    try:
        assert t == r
        print "PASS"
    except AssertionError:
        print "FAILED"
        exit()

    print                                                                     [57/418]

    a = [[(2, 0), (2, 1), (1, 0)], (2, 1), [(1, 0), (1, 2), [(2, 0), (2, 1), (1, 0)]]]
    r = [(1, [(2, 0)]), (1, [(2, 1), (1, 0)]), (1, [(2, 1), (1, 0)]), (-1, [(2, 1), (1
, 2), (2, 0)]), (-1, [(2, 1), (1, 2), (2, 1), (1, 0)])]
    t = expand(a)

    print "test 4:"
    print "-(-a2s - a21*a1s) - a21*(-a1s - a12*(-a2s - a21*a1s))"
    print "a = " + str(a)
    print "r = " + str(r)
    print "t = " + str(t)

    try:
        assert t == r
        print "PASS"
    except AssertionError:
        print "FAILED"
        exit()

    print

    a = [(0, 1), [(0, 2), (0, 1), (1, 2)], (2, 1)]
    r = [(-1, [(0, 1)]), (1, [(0, 2), (2, 1)]), (1, [(0, 1), (1, 2), (2, 1)])]
    t = expand(a)

    print "test 5:"
    print "-as1 - (-as2 - as1*a12)*a21"
    print "a = " + str(a)
    print "r = " + str(r)
    print "t = " + str(t)

    try:
        assert t == r
        print "PASS"
    except AssertionError:
        print "FAILED"
        exit()

    print

    a = [(1, 0), [(1, 2), (2, 0), (1, 0)], [(2, 1), (1, 0), (2, 0)]]
    r = [(-1, [(1, 0)]), (-1, [(1, 2), (2, 1)]),
         (-1, [(1, 2), (1, 0), (2, 0)]), (-1, [(2, 0), (1, 0), (2, 1)]),
         (-1, [(2, 0), (1, 0), (1, 0), (2, 0)])]
    t = expand(a)

    print "test 6:"
    print "-as1 - (-a12 + a2s*a1s)(-a21 - a1s*a2s)"
    print "a = " + str(a)
    print "r = " + str(r)
    print "t = " + str(t)

    try:
        assert t == r
        print "PASS"
    except AssertionError:
        print "FAILED"
        exit()

    print

    a = [(1, 0), [(1, 2), [(0, 2), (0, 1), (1, 2)], (1, 0)],
         [(2, 1), (1, 0), (2, 0)]]
    r = [(-1, [(1, 0)]), (-1, [(1,  2), (2, 1)]), 
         (-1, [(1, 2), (1, 0), (2, 0)]), 
         (1, [(0, 2), (1, 0), (2, 1)]), (1, [(0, 2), (1, 0), (1, 0), (2, 0)]),
         (1, [(0, 1), (1, 2), (1, 0), (2, 1)]), 
         (1, [(0, 1), (1, 2), (1, 0), (1, 0), (2, 0)])]
    t = expand(a)

    print "test 7:"
    print "-a1s - (-a12 - (-as2 - as1*a12)*a1s)*(-a12 - a1s*a2s)"
    print "a = " + str(a)
    print "r = " + str(r)
    print "t = " + str(t)

    try:
        assert t == r
        print "PASS"
    except AssertionError:
        print "FAILED"
        exit()

    print

    print "test 9:"

    a = [(1, 0), [(1, 2), (2, 0), (1, 0)], [(2, 1), [(0, 2), (0, 1), (1, 2)], 
                                            (2, 0)]]
    r = [(-1, [(1, 0)]),
         (-1, [(1, 2), (2, 1)]),
         (1, [(1, 2), (0, 2), (2, 0)]),
         (1, [(1, 2), (0, 1), (1, 2), (2, 0)]),
         (-1, [(2, 0), (1, 0), (2, 1)]),
         (1, [(2, 0), (1, 0), (0, 2), (2, 0)]),
         (1, [(2, 0), (1, 0), (0, 1), (1, 2), (2, 0)])]
    t = expand(a)

    print "-a1s - (-a12 - a2s*a1s)(-a21 - (-as2 - as1*a12)*a2s)"
    print "a = " + str(a)
    print "r = " + str(r)
    print "t = " + str(t)

    try:
        assert t == r
        print "PASS"
    except AssertionError:
        print "FAILED"
        exit()

    print

test_expand()

a = [[[[(3, 0), (3, 1), (1, 0)], [[(3, 2), (3, 1), (1, 2)], (3, 1), (1, 2)], [(2, 0), (2, 1), (1, 0)]], [[(3, 1), [[(3, 2), (3, 1), (1, 2)], (3, 1), (1, 2)], (2, 1)], [[[[(3, 4), (3, 1), (1, 4)], (3, 1), (1, 4)], [[(3, 2), (3, 1), (1, 2)], (3, 1), (1, 2)], [[(2, 4), (2, 1), (1, 4)], (2, 1), (1, 4)]], [[(3, 2), (3, 1), (1, 2)], (3, 1), (1, 2)], [[(2, 4), (2, 1), (1, 4)], (2, 1), (1, 4)]], [(4, 1), [[(4, 2), (4, 1), (1, 2)], (4, 1), (1, 2)], (2, 1)]], [[(1, 0), [(1, 4), (1, 2), [[(2, 4), (2, 1), (1, 4)], (2, 1), (1, 4)]], [[(4, 0), (4, 1), (1, 0)], [[(4, 2), (4, 1), (1, 2)], (4, 1), (1, 2)], [(2, 0), (2, 1), (1, 0)]]], [[(1, 3), (1, 2), [[(2, 3), (2, 1), (1, 3)], (2, 1), (1, 3)]], [(1, 4), (1, 2), [[(2, 4), (2, 1), (1, 4)], (2, 1), (1, 4)]], [[[[(4, 3), (4, 1), (1, 3)], (4, 1), (1, 3)], [[(4, 2), (4, 1), (1, 2)], (4, 1), (1, 2)], [[(2, 3), (2, 1), (1, 3)], (2, 1), (1, 3)]], [[(4, 2), (4, 1), (1, 2)], (4, 1), (1, 2)], [[(2, 3), (2, 1), (1, 3)], (2, 1), (1, 3)]]], [[(3, 0), (3, 1), (1, 0)], [[(3, 2), (3, 1), (1, 2)], (3, 1), (1, 2)], [(2, 0), (2, 1), (1, 0)]]]], [[[[(3, 2), (3, 1), (1, 2)], (3, 1), (1, 2)], [[[[(3, 4), (3, 1), (1, 4)], (3, 1), (1, 4)], [[(3, 2), (3, 1), (1, 2)], (3, 1), (1, 2)], [[(2, 4), (2, 1), (1, 4)], (2, 1), (1, 4)]], [[(3, 2), (3, 1), (1, 2)], (3, 1), (1, 2)], [[(2, 4), (2, 1), (1, 4)], (2, 1), (1, 4)]], [[(4, 2), (4, 1), (1, 2)], (4, 1), (1, 2)]], [[(3, 1), [[(3, 2), (3, 1), (1, 2)], (3, 1), (1, 2)], (2, 1)], [[[[(3, 4), (3, 1), (1, 4)], (3, 1), (1, 4)], [[(3, 2), (3, 1), (1, 2)], (3, 1), (1, 2)], [[(2, 4), (2, 1), (1, 4)], (2, 1), (1, 4)]], [[(3, 2), (3, 1), (1, 2)], (3, 1), (1, 2)], [[(2, 4), (2, 1), (1, 4)], (2, 1), (1, 4)]], [(4, 1), [[(4, 2), (4, 1), (1, 2)], (4, 1), (1, 2)], (2, 1)]], [[[[(1, 2), [(1, 4), (1, 2), [[(2, 4), (2, 1), (1, 4)], (2, 1), (1, 4)]], [[(4, 2), (4, 1), (1, 2)], (4, 1), (1, 2)]], [(1, 4), (1, 2), [[(2, 4), (2, 1), (1, 4)], (2, 1), (1, 4)]], [[(4, 2), (4, 1), (1, 2)], (4, 1), (1, 2)]], [[(1, 3), (1, 2), [[(2, 3), (2, 1), (1, 3)], (2, 1), (1, 3)]], [(1, 4), (1, 2), [[(2, 4), (2, 1), (1, 4)], (2, 1), (1, 4)]], [[[[(4, 3), (4, 1), (1, 3)], (4, 1), (1, 3)], [[(4, 2), (4, 1), (1, 2)], (4, 1), (1, 2)], [[(2, 3), (2, 1), (1, 3)], (2, 1), (1, 3)]], [[(4, 2), (4, 1), (1, 2)], (4, 1), (1, 2)], [[(2, 3), (2, 1), (1, 3)], (2, 1), (1, 3)]]], [[[(3, 2), (3, 1), (1, 2)], (3, 1), (1, 2)], [[[[(3, 4), (3, 1), (1, 4)], (3, 1), (1, 4)], [[(3, 2), (3, 1), (1, 2)], (3, 1), (1, 2)], [[(2, 4), (2, 1), (1, 4)], (2, 1), (1, 4)]], [[(3, 2), (3, 1), (1, 2)], (3, 1), (1, 2)], [[(2, 4), (2, 1), (1, 4)], (2, 1), (1, 4)]], [[(4, 2), (4, 1), (1, 2)], (4, 1), (1, 2)]]], [[(1, 3), (1, 2), [[(2, 3), (2, 1), (1, 3)], (2, 1), (1, 3)]], [(1, 4), (1, 2), [[(2, 4), (2, 1), (1, 4)], (2, 1), (1, 4)]], [[[[(4, 3), (4, 1), (1, 3)], (4, 1), (1, 3)], [[(4, 2), (4, 1), (1, 2)], (4, 1), (1, 2)], [[(2, 3), (2, 1), (1, 3)], (2, 1), (1, 3)]], [[(4, 2), (4, 1), (1, 2)], (4, 1), (1, 2)], [[(2, 3), (2, 1), (1, 3)], (2, 1), (1, 3)]]], [[[(3, 2), (3, 1), (1, 2)], (3, 1), (1, 2)], [[[[(3, 4), (3, 1), (1, 4)], (3, 1), (1, 4)], [[(3, 2), (3, 1), (1, 2)], (3, 1), (1, 2)], [[(2, 4), (2, 1), (1, 4)], (2, 1), (1, 4)]], [[(3, 2), (3, 1), (1, 2)], (3, 1), (1, 2)], [[(2, 4), (2, 1), (1, 4)], (2, 1), (1, 4)]], [[(4, 2), (4, 1), (1, 2)], (4, 1), (1, 2)]]]], [[[(2, 0), (2, 1), (1, 0)], [[(2, 4), (2, 1), (1, 4)], (2, 1), (1, 4)], [[(4, 0), (4, 1), (1, 0)], [[(4, 2), (4, 1), (1, 2)], (4, 1), (1, 2)], [(2, 0), (2, 1), (1, 0)]]], [[[(2, 3), (2, 1), (1, 3)], (2, 1), (1, 3)], [[(2, 4), (2, 1), (1, 4)], (2, 1), (1, 4)], [[[[(4, 3), (4, 1), (1, 3)], (4, 1), (1, 3)], [[(4, 2), (4, 1), (1, 2)], (4, 1), (1, 2)], [[(2, 3), (2, 1), (1, 3)], (2, 1), (1, 3)]], [[(4, 2), (4, 1), (1, 2)], (4, 1), (1, 2)], [[(2, 3), (2, 1), (1, 3)], (2, 1), (1, 3)]]], [[(3, 0), (3, 1), (1, 0)], [[(3, 2), (3, 1), (1, 2)], (3, 1), (1, 2)], [(2, 0), (2, 1), (1, 0)]]]]

print "calling expand on a"
print expand(a)