import copy

def exterior1():
    t = {"name": "t", "source": "1", "target": "1", "degree": 1}
    astripped = {"objects": ["1"], "morphisms": [t], "compositions": []}
    a = addidentities(astripped)
    return a

def exterior2():
    s = {"name": "s", "source": "1", "target": "1", "degree": 1}
    t = {"name": "t", "source": "1", "target": "1", "degree": 1}
    u = {"name": "u", "source": "1", "target": "1", "degree": 2}
    st = {"inputs": [s,t], "output": u, "coefficient": 1}
    ts = {"inputs": [t,s], "output": u, "coefficient": -1}
    astripped = {"objects": ["1"], "morphisms": [s,t,u], "compositions": [st,ts]}   
    a = addidentities(astripped)
    return a

def a2quiver():
    a = {"name": "a", "source": "1", "target": "2", "degree": 0}
    b = {"name": "b", "source": "2", "target": "1", "degree": 1}
    t1 = {"name": "t1", "source": "1", "target": "1", "degree": 1}
    t2 = {"name": "t2", "source": "2", "target": "2", "degree": 1}
    ab = {"inputs": [b,a], "output": t1, "coefficient": 1}
    ba = {"inputs": [a,b], "output": t2, "coefficient": 1}
    astripped = {"objects": ["1","2"], "morphisms": [a,b,t1,t2], "compositions": [ab,ba]}
    a = addidentities(astripped)
    return a

def objid(obj):
    newid = {"source": obj, "target": obj, "degree": 0, "name": "e"+str(obj), "identity": "yes"}
    return(newid)

def addidentities(a):
    newmorphisms = []
    newcompositions = []
    for m in range(0,len(a["objects"])):
        obj = a["objects"][m]
        newid = objid(obj)
        newc = {"order": 2, "inputs": [newid,newid], "output": newid, "coefficient": 1}
        newmorphisms.append(newid)
        newcompositions.append(newc)
    for i in range(0,len(a["objects"])):
        for j in range(0,len(a["morphisms"])):
            oneside = a["morphisms"][j]
            if oneside["target"] == a["objects"][i]:
                newc = {"inputs": [newmorphisms[i],oneside], "output": oneside, "coefficient": 1}
                newcompositions.append(newc)
            if oneside["source"] == a["objects"][i]:
                newc = {"inputs": [oneside,newmorphisms[i]], "output": oneside, "coefficient": 1}
                newcompositions.append(newc)
    newa = {"objects": a["objects"], "morphisms": a["morphisms"] + newmorphisms, "compositions": a["compositions"] + newcompositions}
    return newa

def shorttensorgen(g):
    output = []
    for j in range(0,len(g)):
        output.append(g[j]["name"])
    return(output)

def sortshort(g,h):
    return g["degree"]-h["degree"]

def progress(level,str):
    if level<2:
        print("### "+str)
        
def diffmatrix(c,degree,length):
    progress(1,"Constructing the differential matrix")
    source = []
    target = []
    for i in range(0,len(c["generators"])):
        d = c["generators"][i]["degree"]
        w = c["generators"][i]["length"]
        if (d == degree) and (w == length):
            source.append(c["generators"][i])
        elif (d == degree+1) and (w == length-1):
            target.append(c["generators"][i])
    matrix = [[0 for j in range(0,len(source))] for i in range(0,len(target))]
    for i in range(0,len(c["differentials"])):
        if (c["differentials"][i]["input"]["degree"] == degree) and (c["differentials"][i]["input"]["length"] == length):
                dsource = c["differentials"][i]["input"]
                dtarget = c["differentials"][i]["output"]
                dcoeff = c["differentials"][i]["coefficient"]
                sourceindex = source.index(dsource)
                targetindex = target.index(dtarget)
                matrix[targetindex][sourceindex] = matrix[targetindex][sourceindex] + dcoeff
    return(matrix)

def matrixrank(a):
    rows = len(a)
    if rows == 0:
        cols = 0
    else:
        cols = len(a[0])
    progress(1,"Computing rank of matrix (size "+str(rows)+"x"+str(cols)+")")
    ranksofar = 0
    rowbound = 0
    colbound = 0
    ranksofar = 0    
    while (rowbound<rows) and (colbound<cols):
        progress(2,str(rowbound)+str(colbound))
        nonzerorow = rowbound
        while (nonzerorow<rows) and (a[nonzerorow][colbound] == 0):
            nonzerorow = nonzerorow+1
        if nonzerorow == rows:
            colbound = colbound+1
        elif nonzerorow == rowbound:
            for j in range(rowbound+1,rows):
                for k in range(colbound+1,cols):
                    a[j][k] = a[j][k] * a[rowbound][colbound] - a[j][colbound] * a[rowbound][k]
            rowbound = rowbound+1
            colbound = colbound+1
            ranksofar = ranksofar+1
        else:
            temp = a[rowbound]
            a[rowbound] = a[nonzerorow]
            a[nonzerorow] = temp
    progress(1,"Rank is "+str(ranksofar))
    return(ranksofar)

def matrixrankmodp(a,p):
    rows = len(a)
    if rows == 0:
        cols = 0
    else:
        cols = len(a[0])
    progress(2,"Computing rank of matrix (size "+str(rows)+"x"+str(cols)+")")
    rowbound = 0
    colbound = 0
    ranksofar = 0    
    while (rowbound<rows) and (colbound<cols):
        nonzerorow = rowbound
        progress(3,"At row and column "+str(rowbound)+" "+str(colbound))
        while (nonzerorow<rows) and ((a[nonzerorow][colbound] % p) == 0):
            nonzerorow = nonzerorow+1
        if nonzerorow == rows:
            colbound = colbound+1
        elif nonzerorow == rowbound:
            for j in range(rowbound+1,rows):
                for k in range(colbound+1,cols):
                    a[j][k] = (a[j][k] * a[rowbound][colbound] - a[j][colbound] * a[rowbound][k]) % p
            rowbound = rowbound+1
            colbound = colbound+1
            ranksofar = ranksofar+1
        else:
            temp = a[rowbound]
            a[rowbound] = a[nonzerorow]
            a[nonzerorow] = temp
    progress(2,"Rank is "+str(ranksofar))
    return(ranksofar)

def bettinumber(c,degree,length):
    progress(1,"Computing betti number in degree "+str(degree)+" and length "+str(length))
    a = copy.deepcopy(diffmatrix(c,degree,length))
    b = copy.deepcopy(diffmatrix(c,degree-1,length+1))
    s = len(b)
    ra = matrixrank(a)
    rb = matrixrank(b)
    betti = s - ra - rb
    progress(1,"Size of matrix and ranks are "+str(s)+" "+str(ra)+" "+str(rb))
    return betti

def bettinumbermodp(c,degree,length,p):
    progress(1,"Computing betti number in degree "+str(degree)+" and length "+str(length))
    a = copy.deepcopy(diffmatrix(c,degree,length))
    b = copy.deepcopy(diffmatrix(c,degree-1,length+1))
    s = len(b)
    ra = matrixrankmodp(a,p)
    rb = matrixrankmodp(b,p)
    betti = s - ra - rb
    progress(1,"Size of matrix and ranks are "+str(s)+" "+str(ra)+" "+str(rb))
    return betti

def checkcomplex(c):
    progress(1,"Checking sparse complex for d^2 = 0")
    errors = 0
    for i in range(0,len(c["generators"])):
        for j in range(0,len(c["generators"])):
            coeff = 0
            for k in range(0,len(c["differentials"])):
                m1 = c["differentials"][k]
                if m1["input"] == c["generators"][i]:
                    for l in range(0,len(c["differentials"])):
                        m2 = c["differentials"][l]
                        if m2["output"] == c["generators"][j]:
                            if m2["input"] == m1["output"]:
                                coeff = coeff + m2["coefficient"]*m1["coefficient"]
            if coeff != 0:
                errors = errors + 1
                progress(0,"Failure of d^2 = 0 at the following entry:")
                progress(0,"Source: "+str(c["generators"][i]))
                progress(0,"Target: "+str(c["generators"][j]))
                progress(0,"Nonzero coefficient: "+str(coeff))
    return(errors)

def prettyprintalgebra(a):
    print
    print("Objects:")
    print
    for i in range(0,len(a["objects"])):
        print(a["objects"][i])
    print
    print("Morphisms:")
    print
    for i in range(0,len(a["morphisms"])):
        morphism = a["morphisms"][i]
        print(morphism["name"], morphism["source"], morphism["target"], morphism["degree"])
    print
    print("Compositions:")
    print
    for ccounter in range(0,len(a["compositions"])):
        com = a["compositions"][ccounter]
        print(com["inputs"][0]["name"], com["inputs"][1]["name"], "--->", com["coefficient"], "*", com["output"]["name"])
    return()

def epsilon(degree):
    if degree % 2 == 0:
        sign = 1
    else:
        sign = -1
    return(sign)


def reducedtensorfixed(a,fixedlength): 
    reducedmorphisms = [] 
    for m in range(0,len(a["morphisms"])):
        if "identity" in a["morphisms"][m]:
            continue
        else:
            reducedmorphisms.append(a["morphisms"][m])
    if fixedlength == 1:
        new = []
        for i in range(0,len(reducedmorphisms)):
              new.append({"name" : [reducedmorphisms[i]], "degree" : reducedmorphisms[i]["degree"]-1})
    else:
        oneless = reducedtensorfixed(a,fixedlength-1)
        new = []
        for i in range(0,len(oneless)):
            for j in range(0,len(reducedmorphisms)):
                first = reducedmorphisms[j]
                second = oneless[i]
                if first["source"] == second["name"][0]["target"]:
                    newelements = [first] + second["name"]
                    newdegree = first["degree"] - 1 + second["degree"]
                    build = {"name": newelements, "degree": newdegree}
                    new.append(build)
    return new    

def hochschildchainsfixed(a,fixedlength):
    progress(2,"Listing generators of length "+str(fixedlength))
    morphisms = a["morphisms"]
    new = []
    if fixedlength == 1:
        for m in range(0,len(morphisms)):
            if morphisms[m]["source"] == morphisms[m]["target"]:
                build = {"name": [morphisms[m]], "degree": morphisms[m]["degree"], "length": 1}
                new.append(build)
    else:
        tensor = reducedtensorfixed(a,fixedlength-1)
        for i in range(0,len(morphisms)):
            for j in range(0,len(tensor)):
                first = morphisms[i]
                second = tensor[j]
                if (first["source"] == second["name"][0]["target"]) and (first["target"] == second["name"][-1]["source"]):
                    newelements = [first] + second["name"]
                    newdegree = first["degree"] + second["degree"]
                    build = {"name": newelements, "degree": newdegree, "length": len(newelements)}
                    new.append(build)
    return new

def hochschildchains(a,maxlength):
    all = []
    for mm in range(1,maxlength+1):
        all.extend(hochschildchainsfixed(a,mm))
    return(all)

def totaldegree(tensor):
    tot = 0    
    for r in range(0,len(tensor)):
        tot = tot + tensor[r]["degree"]
    return(tot)

def hochschilddifferential(a,complex):
    diff = []
    for i in range(0,len(complex)):
        gen = complex[i]["name"]
        for j in range(0,len(gen)-1):
            cutdown = gen[j:j+2]
            for m in range(0,len(a["compositions"])):
                if cutdown == a["compositions"][m]["inputs"]:
                    mapstoname = gen[0:j]
                    mapstoname.append(a["compositions"][m]["output"])
                    mapstoname.extend(gen[j+2:len(gen)])
                    mapstodegree = complex[i]["degree"]+1
                    mapsto = {"name": mapstoname, "degree": mapstodegree, "length": len(gen)-1}
                    coeff = a["compositions"][m]["coefficient"] * epsilon(j)
                    newentry = {"input": complex[i], "output": mapsto, "coefficient": coeff}
                    diff.append(newentry)
    for i in range(0,len(complex)):
        gen = complex[i]["name"]
        if (len(gen) > 1):
            rotated = [gen[len(gen)-1],gen[0]]
            for m in range(0,len(a["compositions"])):
                if rotated == a["compositions"][m]["inputs"]:
                    mapstoname = [a["compositions"][m]["output"]]
                    mapstoname.extend(gen[1:len(gen)-1])
                    mapstodegree = complex[i]["degree"]+1
                    mapsto = {"name": mapstoname, "degree": mapstodegree, "length": len(gen)-1}
                    sign = epsilon(totaldegree(gen[0:len(gen)-1]) * gen[len(gen)-1]["degree"] + len(gen) - 1)
                    """
                    permutesign = epsilon(totaldegree(gen[k:len(gen)]) * totalreduceddegree(gen[0:k]))
                    coeff = permutesign * epsilon(totalreduceddegree(gen[j:k])) * a["compositions"][m]["coefficient"]
                    """
                    coeff = a["compositions"][m]["coefficient"] * sign
                    newentry = {"input": complex[i], "output": mapsto, "coefficient": coeff}
                    diff.append(newentry)
    return(diff)

def hochschildcomplex(a,maxlength):
    progress(1,"Constructing the Hochschild complex")
    chains = hochschildchains(a, maxlength)
    progress(2,"Number of generators: "+str(len(chains)))
    diff = hochschilddifferential(a, chains)
    progress(2,"Number of differentials: "+str(len(diff)))
    c = {"generators": chains, "differentials": diff}
    return c

def hochschildbetti(a,maxlength):
    h = hochschildcomplex(a,maxlength+1)
    maxdegree = h["generators"][0]["degree"]
    mindegree = h["generators"][0]["degree"]
    for i in range(1,len(h["generators"])):
        d = h["generators"][i]["degree"]
        w = h["generators"][i]["length"]
        if (d > maxdegree) and (w <= maxlength):
            maxdegree = d
        elif (d < mindegree) and (w <= maxlength):
            mindegree = d
    bettilist = []
    for d in range(mindegree,maxdegree+1):
        betti = []
        btot = 0
        for l in range(1,maxlength+1):
            b = bettinumber(h,d,l)
            btot = btot + b 
            betti.append(b)
        if btot > 0:
            bettilist.append({"degree": d, "bylength": betti})
    return(bettilist)

def hochschildbettimodp(a,maxlength,p):
    h = hochschildcomplex(a,maxlength+1)
    maxdegree = h["generators"][0]["degree"]
    mindegree = h["generators"][0]["degree"]
    for i in range(1,len(h["generators"])):
        d = h["generators"][i]["degree"]
        w = h["generators"][i]["length"]
        if (d > maxdegree) and (w <= maxlength):
            maxdegree = d
        elif (d < mindegree) and (w <= maxlength):
            mindegree = d
    bettilist = []
    for d in range(mindegree,maxdegree+1):
        betti = []
        btot = 0
        for l in range(1,maxlength+1):
            b = bettinumbermodp(h,d,l,p)
            btot = btot + b 
            betti.append(b)
        if btot > 0:
            bettilist.append({"degree": d, "bylength": betti})
    return(bettilist)

a = a2quiver()
b = hochschildbettimodp(a,11,29)
for i in range(0,len(b)):
    print(b[i])