# top_boundary.py
# Constructs the matrix \del_{n+2} for the complex F/(F\cap C)
# for n = 4, 5, 6, 7, 8,
# described in Section 6 of http://arxiv.org/abs/1507.03878

# Usage: top_boundary(n)

def shapes_of(n):
    if n == 4:
        return (211,)
    if n == 5:
        return (311,221)
    if n == 6:
        return (411, 321, 222)
    if n == 7:
        return (511, 421, 331, 322)
    if n == 8:
        return (611, 521, 431, 422, 332)

def bottom_shapes_of(n):
    if n == 4:
        return (1111,)
    if n == 5:
        return (1211,)
    if n == 6:
        return (1311, 1221)
    if n == 7:
        return (1411, 1321, 1222)
    if n == 8:
        return (1511, 1421, 1331, 1322)

def top_types(shape):
    ret = list({})
    if shape == 211:
        for pi in Permutations(4).list():
            if pi[0] < pi[1] and pi[2] < pi[3]:
                ret.append( (211, ( (pi[0],pi[1]), (pi[2],), (pi[3],) ) ))
    if shape == 311:
        for pi in Permutations(5).list():
            if pi[0] < pi[2] and pi[3] < pi[4]:
                ret.append( (311, ( (pi[0],pi[1],pi[2]), (pi[3],), (pi[4],) )))
    if shape == 221:
        for pi in Permutations(5).list():
            if pi[0] < min (pi[1], pi[2], pi[3]):
                ret.append( (221, ( (pi[0],pi[1]), (pi[2],pi[3]), (pi[4],) )))
    if shape == 411:
        for pi in Permutations(6).list():
            if pi[0] < pi[3] and pi[4] < pi[5]:
                ret.append( (411, ( (pi[0],pi[1],pi[2],pi[3]), (pi[4],), (pi[5],) )))
    if shape == 321:
        for pi in Permutations(6).list():
            if pi[0] < pi[2]:
                ret.append( (321, ((pi[0],pi[1],pi[2]), (pi[3],pi[4]), (pi[5],) ) ))
    if shape == 222:
        for pi in Permutations(6).list():
            if pi[0] == 1 and pi[2] < pi[4]:
                ret.append( (222, ((pi[0],pi[1]), (pi[2],pi[3]), (pi[4],pi[5]) ) ))
    if shape == 511:
        for pi in Permutations(7).list():
            if pi[0] < pi[4] and pi[5] < pi[6]:
                ret.append( (511, ((pi[0],pi[1],pi[2],pi[3],pi[4]), (pi[5],), (pi[6],))))
    if shape == 421:
        for pi in Permutations(7).list():
            if pi[0] < pi[3]:
                ret.append( (421, ((pi[0],pi[1],pi[2],pi[3]), (pi[4],pi[5]), (pi[6],))))
    if shape == 331:
        for pi in Permutations(7).list():
            if pi[0] < min(pi[2],pi[3],pi[5]):
                ret.append( (331, ((pi[0], pi[1], pi[2]), (pi[3], pi[4], pi[5]), (pi[6],))))
    if shape == 322:
        for pi in Permutations(7).list():
            if pi[0] < pi[2] and pi[3] < pi[5]:
                ret.append( (322, ((pi[0],pi[1],pi[2]), (pi[3],pi[4]), (pi[5],pi[6]))))
    if shape == 611:
        for pi in Permutations(8).list():
            if pi[0] < pi[5] and pi[6] < pi[7]:
                ret.append( (611, ((pi[0],pi[1],pi[2],pi[3],pi[4],pi[5]), (pi[6],), (pi[7],))))
    if shape == 521:
        for pi in Permutations(8).list():
            if pi[0] < pi[4]:
                ret.append( (521, ((pi[0],pi[1],pi[2],pi[3],pi[4]), (pi[5],pi[6]), (pi[7],))))
    if shape == 431:
        for pi in Permutations(8).list():
            if pi[0] < pi[3]:
                ret.append( (431, ((pi[0],pi[1],pi[2],pi[3]), (pi[4],pi[5],pi[6]), (pi[7],))))
    if shape == 422:
        for pi in Permutations(8).list():
            if pi[0] < pi[3] and pi[4] < pi[6]:
                ret.append( (422, ((pi[0],pi[1],pi[2],pi[3]), (pi[4],pi[5]), (pi[6],pi[7]))))
    if shape == 332:
        for pi in Permutations(8).list():
            if pi[0] < min(pi[2],pi[3],pi[5]):
                ret.append( (332, ((pi[0],pi[1],pi[2]), (pi[3],pi[4],pi[5]), (pi[6],pi[7]))))
    return ret

def bottom_types(shape):
    ret = list({})
    if shape == 1111:
        for pi in Permutations(4).list():
            if pi[1] < pi[2] and pi[2] < pi[3]:
                ret.append( (1111, ( (pi[0],), (pi[1],), (pi[2],), (pi[3],))) )
    if shape == 1211:
        for pi in Permutations(5).list():
            if pi[3] < pi[4]:
                ret.append( (1211, ( (pi[0],), (pi[1],pi[2]), (pi[3],), (pi[4],))))
    if shape == 1311:
        for pi in Permutations(6).list():
            if pi[4] < pi[5]:
                ret.append( (1311, ( (pi[0],), (pi[1],pi[2],pi[3]), (pi[4],), (pi[5],))))
    if shape == 1221:
        for pi in Permutations(6).list():
            if pi[1] < pi[3]:
                ret.append( (1221, ( (pi[0],), (pi[1],pi[2]), (pi[3],pi[4]), (pi[5],))))
    if shape == 1411:
        for pi in Permutations(7).list():
            if pi[5] < pi[6]:
                ret.append( (1411, ( (pi[0],), (pi[1],pi[2],pi[3],pi[4]), (pi[5],), (pi[6],))))
    if shape == 1321:
        for pi in Permutations(7).list():
            ret.append( (1321, ( (pi[0],), (pi[1],pi[2],pi[3]), (pi[4],pi[5]), (pi[6],))))
    if shape == 1222:
        for pi in Permutations(7).list():
            if pi[1] < pi[3] and pi[3] < pi[5]:
                ret.append( (1222, ( (pi[0],), (pi[1],pi[2]), (pi[3],pi[4]), (pi[5],pi[6]))))
    if shape == 1511:
        for pi in Permutations(8).list():
            if pi[6] < pi[7]:
                ret.append( (1511, ( (pi[0],), (pi[1],pi[2],pi[3],pi[4],pi[5]), (pi[6],), (pi[7],))))
    if shape == 1421:
        for pi in Permutations(8).list():
            ret.append( (1421, ( (pi[0],), (pi[1],pi[2],pi[3],pi[4]), (pi[5],pi[6]), (pi[7],))))
    if shape == 1331:
        for pi in Permutations(8).list():
            if pi[1] < pi[4]:
                ret.append( (1331, ( (pi[0],), (pi[1],pi[2],pi[3]), (pi[4],pi[5],pi[6]), (pi[7],))))
    if shape == 1322:
        for pi in Permutations(8).list():
            if pi[4] < pi[6]:
                ret.append( (1322, ( (pi[0],), (pi[1],pi[2],pi[3]), (pi[4],pi[5]), (pi[6],pi[7]))))
    return ret

def normalize(bottom_type, given_coefficient):
    (shape, nums) = bottom_type
    if shape == 1111:
        ((a,),(b,),(c,),(d,)) = nums
        (bb,cc,dd) = sorted((b,c,d))
        return ( (1111, ((a,),(bb,),(cc,),(dd,))), given_coefficient)
    if shape == 1211:
        ((a,), (b,c), (d,), (e,)) = nums
        if d < e:
            return ((1211, ((a,), (b,c), (d,), (e,))), given_coefficient)
        else:
            return ((1211, ((a,), (b,c), (e,), (d,))), given_coefficient)
    if shape == 1311:
        ((a,), (b,c,d), (e,), (f,)) = nums
        if e < f:
            return ((1311, ((a,), (b,c,d), (e,), (f,))), given_coefficient)
        else:
            return ((1311, ((a,), (b,c,d), (f,), (e,))), given_coefficient)
    if shape == 1221:
        ((a,), (b,c), (d,e), (f,)) = nums
        if b < d:
            return ((1221, ((a,), (b,c), (d,e), (f,))), given_coefficient)
        else:
            return ((1221, ((a,), (d,e), (b,c), (f,))), -1*given_coefficient)
    if shape == 1411:
        ((a,), (b,c,d,e,), (f,), (g,)) = nums
        if f < g:
            return ((1411, ((a,), (b,c,d,e,), (f,), (g,))), given_coefficient)
        else:
            return ((1411, ((a,), (b,c,d,e,), (g,), (f,))), given_coefficient)            
    if shape == 1321:
        return (bottom_type, given_coefficient)
    if shape == 1222:
        ((a,), (b,c), (d,e), (f,g)) = nums
        if b < d and d < f:
            return ((1222, ((a,), (b,c), (d,e), (f,g))),  given_coefficient)
        if b < f and f < d:
            return ((1222, ((a,), (b,c), (f,g), (d,e))), -1*given_coefficient)
        if d < b and b < f:
            return ((1222, ((a,), (d,e), (b,c), (f,g))), -1*given_coefficient)
        if f < b and b < d:
            return ((1222, ((a,), (f,g), (b,c), (d,e))), given_coefficient)
        if d < f and f < b:
            return ((1222, ((a,), (d,e), (f,g), (b,c))), given_coefficient)
        if f < d and d < b:
            return ((1222, ((a,), (f,g), (d,e), (b,c))), -1*given_coefficient)
    if shape == 1511:
        ((a,), (b,c,d,e,f), (g,), (h,)) = nums
        if g < h:
            return ((1511, ((a,), (b,c,d,e,f), (g,), (h,))), given_coefficient)
        else:
            return ((1511, ((a,), (b,c,d,e,f), (h,), (g,))), given_coefficient)            
    if shape == 1421:
        return (bottom_type, given_coefficient)
    if shape == 1331:
        ((a,), (b,c,d), (e,f,g), (h,)) = nums
        if b < e:
            return ((1331, ((a,), (b,c,d), (e,f,g), (h,))), given_coefficient)
        else:
            return ((1331, ((a,), (e,f,g), (b,c,d), (h,))), given_coefficient)
    if shape == 1322:
        ((a,), (b,c,d), (e,f), (g,h)) = nums
        if e < g:
            return ((1322, ((a,), (b,c,d), (e,f), (g,h))), given_coefficient)
        else:
            return ((1322, ((a,), (b,c,d), (g,h), (e,f))), -1*given_coefficient)


def boundary_of(typ):
    (shape,nums) = typ
    if shape == 211:
        ((a,b),(c,),(d,)) = nums
        return (  normalize( (1111,((a,),(b,),(c,),(d,))), 1),
                  normalize( (1111,((b,),(a,),(c,),(d,))), -1)
                  )
    if shape == 311:
        ((a,b,c),(d,),(e,)) = nums
        return (  normalize( (1211,((a,), (b,c), (d,), (e,))), 1),
                  normalize( (1211,((c,), (b,a), (d,), (e,))), 1)
                  )
    if shape == 221:
        ((a,b),(c,d),(e,)) = nums
        return (  normalize( (1211,((a,), (c,d), (b,), (e,))), 1),
                  normalize( (1211,((b,), (d,c), (a,), (e,))), -1),
                  normalize( (1211,((c,), (a,b), (d,), (e,))), -1),
                  normalize( (1211,((d,), (b,a), (c,), (e,))), 1)
                  )
    if shape == 411:
        ((a,b,c,d), (e,), (f,)) = nums
        return (  normalize( (1311, ((a,), (b,c,d), (e,), (f,))), 1),
                  normalize( (1311, ((d,), (c,b,a), (e,), (f,))), 1)
                  )
    if shape == 321:
        ((a,b,c), (d,e), (f,)) = nums
        return (  normalize( (1221, ((a,), (b,c), (d,e), (f,))), 1),
                  normalize( (1221, ((c,), (b,a), (e,d), (f,))), 1),
                  normalize( (1311, ((d,), (a,b,c), (e,), (f,))), 1),
                  normalize( (1311, ((e,), (c,b,a), (d,), (f,))), 1)
                  )
    if shape == 222:
        ((a,b), (c,d), (e,f)) = nums
        return (  normalize( (1221, ((a,), (c,d), (e,f), (b,))), 1),
                  normalize( (1221, ((b,), (d,c), (f,e), (a,))), -1),
                  normalize( (1221, ((c,), (a,b), (e,f), (d,))), -1),
                  normalize( (1221, ((d,), (b,a), (f,e), (c,))), 1),
                  normalize( (1221, ((e,), (a,b), (c,d), (f,))), 1),
                  normalize( (1221, ((f,), (b,a), (d,c), (e,))), -1)
                  )
    if shape == 511:
        ((a,b,c,d,e), (f,), (g,)) = nums
        return (  normalize( (1411, ((a,), (b,c,d,e), (f,), (g,))), 1),
                  normalize( (1411, ((e,), (d,c,b,a), (f,), (g,))), -1)
                  )
    if shape == 421:
        ((a,b,c,d), (e,f), (g,)) = nums
        return (  normalize( (1321, ((a,), (b,c,d), (e,f), (g,))), 1),
                  normalize( (1321, ((d,), (c,b,a), (f,e), (g,))), 1),
                  normalize( (1411, ((e,), (a,b,c,d), (f,), (g,))), -1),
                  normalize( (1411, ((f,), (d,c,b,a), (e,), (g,))), -1)
                  )
    if shape == 331:
        ((a,b,c), (d,e,f), (g,)) = nums
        return (  normalize( (1321, ((a,), (d,e,f), (b,c), (g,))), 1),
                  normalize( (1321, ((c,), (f,e,d), (b,a), (g,))), -1),
                  normalize( (1321, ((d,), (a,b,c), (e,f), (g,))), 1),
                  normalize( (1321, ((f,), (c,b,a), (e,d), (g,))), -1)
                  )
    if shape == 322:
        ((a,b,c), (d,e), (f,g)) = nums
        return (  normalize( (1222, ((a,), (b,c), (d,e), (f,g))), 1),
                  normalize( (1222, ((c,), (b,a), (e,d), (g,f))), 1),
                  normalize( (1321, ((d,), (a,b,c), (f,g), (e,))), 1),
                  normalize( (1321, ((e,), (c,b,a), (g,f), (d,))), 1),
                  normalize( (1321, ((f,), (a,b,c), (d,e), (g,))), -1),
                  normalize( (1321, ((g,), (c,b,a), (e,d), (f,))), -1)
                  )
    if shape == 611:
        ((a,b,c,d,e,f), (g,), (h,)) = nums
        return (  normalize( (1511, ((a,), (b,c,d,e,f), (g,), (h,))), 1),
                  normalize( (1511, ((f,), (e,d,c,b,a), (g,), (h,))), -1)
                  )
    if shape == 521:
        ((a,b,c,d,e), (f,g), (h,)) = nums
        return (  normalize( (1421, ((a,), (b,c,d,e), (f,g), (h,))), 1),
                  normalize( (1421, ((e,), (d,c,b,a), (g,f), (h,))), -1),
                  normalize( (1511, ((f,), (a,b,c,d,e), (g,), (h,))), 1),
                  normalize( (1511, ((g,), (e,d,c,b,a), (f,), (h,))), -1)
                  )
    if shape == 431:
        ((a,b,c,d), (e,f,g), (h,)) = nums
        return (  normalize( (1331, ((a,), (b,c,d), (e,f,g), (h,))), 1),
                  normalize( (1331, ((d,), (c,b,a), (g,f,e), (h,))), -1),
                  normalize( (1421, ((e,), (a,b,c,d), (f,g), (h,))), -1),
                  normalize( (1421, ((g,), (d,c,b,a), (f,e), (h,))), 1)
                  )
    if shape == 422:
        ((a,b,c,d), (e,f), (g,h)) = nums
        return (  normalize( (1322, ((a,), (b,c,d), (e,f), (g,h))), 1),
                  normalize( (1322, ((d,), (c,b,a), (f,e), (h,g))), 1),
                  normalize( (1421, ((e,), (a,b,c,d), (g,h), (f,))), -1),
                  normalize( (1421, ((f,), (d,c,b,a), (h,g), (e,))), -1),
                  normalize( (1421, ((g,), (a,b,c,d), (e,f), (h,))), 1),
                  normalize( (1421, ((h,), (d,c,b,a), (f,e), (g,))), 1)
                  )
    if shape == 332:
        ((a,b,c), (d,e,f), (g,h)) = nums
        return (  normalize( (1322, ((a,), (d,e,f), (b,c), (g,h))), 1),
                  normalize( (1322, ((c,), (f,e,d), (b,a), (h,g))), -1),
                  normalize( (1322, ((d,), (a,b,c), (e,f), (g,h))), 1),
                  normalize( (1322, ((f,), (c,b,a), (e,d), (h,g))), -1),
                  normalize( (1331, ((g,), (a,b,c), (d,e,f), (h,))), 1),
                  normalize( (1331, ((h,), (c,b,a), (f,e,d), (g,))), -1)
                  )

def list_columns(n):
    ret = list({})
    for shape in shapes_of(n):
        ret.extend(top_types(shape))
    return ret

def column_of (n):
    list_columns_n = list_columns(n)
    return dict((list_columns_n[i], i) for i in range(len(list_columns_n)))

def list_rows(n):
    ret = list({})
    for shape in bottom_shapes_of(n):
        ret.extend(bottom_types(shape))
    return ret

def row_of(n):
    list_rows_n = list_rows(n)
    return dict((list_rows_n[i], i) for i in range(len(list_rows_n)))

def top_boundary(n):
    row_of_n = row_of(n)
    column_of_n = column_of(n)
    ret = matrix(len(list_rows(n)),len(list_columns(n)), sparse=True)
    for shape in shapes_of(n):
        for typ in top_types(shape):
            boundary = boundary_of(typ)
            for (bottom_type, coefficient) in boundary:
                ret[ row_of_n[bottom_type], column_of_n[typ] ] = coefficient
    return ret