import copy

def examplepair_cotangents2():
    m12_0 = {"name": "1->2(zero)", "source": "1", "target": "2", "degree": 0, "weight": 0}
    m12_1 = {"name": "1->2(one)", "source": "1", "target": "2", "degree": 1, "weight": 0}
    m21_0 = {"name": "2->1(zero)", "source": "2", "target": "1", "degree": 0, "weight": 0}
    m21_1 = {"name": "2->1(one)", "source": "2", "target": "1", "degree": 1, "weight": 0}
    m11_1 = {"name": "1->1(one)", "source": "1", "target": "1", "degree": 1, "weight": 0}
    m22_1 = {"name": "2->2(one)", "source": "2", "target": "2", "degree": 1, "weight": 0}
    c212_00 = {"order": 2, "inputs": [m12_0,m21_0], "output": objid("2"), "coefficient": 1}
    c121_00 = {"order": 2, "inputs": [m21_0,m12_0], "output": objid("1"), "coefficient": 1}
    c212_01 = {"order": 2, "inputs": [m12_0,m21_1], "output": m22_1, "coefficient": -1}
    c121_01 = {"order": 2, "inputs": [m21_0,m12_1], "output": m11_1, "coefficient": -1}
    c212_10 = {"order": 2, "inputs": [m12_1,m21_0], "output": m22_1, "coefficient": 1}
    c121_10 = {"order": 2, "inputs": [m21_1,m12_0], "output": m11_1, "coefficient": 1}
    c211_01 = {"order": 2, "inputs": [m12_0,m11_1], "output": m12_1, "coefficient": -1}
    c221_10 = {"order": 2, "inputs": [m22_1,m12_0], "output": m12_1, "coefficient": 1}
    c112_01 = {"order": 2, "inputs": [m11_1,m21_0], "output": m21_1, "coefficient": 1}
    c122_10 = {"order": 2, "inputs": [m21_0,m22_1], "output": m21_1, "coefficient": -1}
    astripped = {"objects": ["1","2"], "morphisms": [m12_0,m12_1], "compositions": []}
    a = modify_addidentities(astripped)
    bstripped = {"objects": ["1","2"], "morphisms": [m12_0,m12_1,m21_0,m21_1,m11_1,m22_1],"compositions": \
                 [c212_00,c121_00,c212_01,c121_01,c212_10,c121_10,c211_01,c221_10,c112_01,c122_10]}
    b = modify_addidentities(bstripped)
    return a,b

def progress(level,str):
    if level<0:
        print("# "+str)

""""
 A filtered complex c is a dictionary with two entries:
 (1) c["generators"] is a list of generators, each of them g a dictionary consisting of 3 entries
        g["name"], g["degree"], g["weight"]
 (2) c["differentials"] is a list of differentials d, each of them a dictionary consisting of 3 entries
        c["input"] is a generator, c["output"] is a generator, c["coefficient"] is a number
"""

def hatmorphism(m,weight):
    if weight == 0:
        newmorphism = m
        newmorphism["weight"] = 0
    else:
        newname = m["name"]+" t^"+str(weight)
        newmorphism = {"name": newname, "source": m["source"], "target": m["target"], "degree": m["degree"] + 2*weight, "weight": weight}
    return(newmorphism)

def addweights(c,weightlist):
    newinputs = []
    sumweights = 0
    for i in range(0,len(c["inputs"])):
        newinputs.append(hatmorphism(c["inputs"][i],weightlist[i]))
        sumweights = sumweights + weightlist[i]
    newoutput = hatmorphism(c["output"],sumweights)
    newc = {"order": c["order"], "inputs": newinputs, "output": newoutput, "coefficient": c["coefficient"]}
    return(newc)
                         
def construct_hatalgebra(a,b,maxweight):
    objectlist = a["objects"][:]
    morphismlist = a["morphisms"][:]
    for q in range(1,maxweight+1):
        for i in range(0,len(b["morphisms"])):
            morphism = b["morphisms"][i]
            morphismlist.append(hatmorphism(morphism,q))
    compositionlist = a["compositions"][:]
    for i in range(0,len(b["compositions"])):
        c = b["compositions"][i]
        weightlist = [0 for j in range(0,c["order"])]
        while 1==1:
            k = 0
            while (k<len(weightlist)) and (weightlist[k] == maxweight):
                k = k + 1
            if k == len(weightlist):
                break
            weightlist[k] = weightlist[k]+1
            for l in range(0,k):
                weightlist[l] = 0
            cnew = addweights(c,weightlist)
            if cnew["output"]["weight"] <= maxweight:
                compositionlist.append(cnew)
    for i in range(0,len(a["morphisms"])):
        morphism = a["morphisms"][i]
        if "identity" in morphism:
            czero = {"order": 0, "inputs": [], "output": hatmorphism(morphism,1), "coefficient": 1}
            compositionlist.append(czero)
    hata = {"objects": objectlist, "morphisms": morphismlist, "compositions": compositionlist}
    return hata
                                 
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 prettyprint_complex(c):
    print
    print("Generators:")
    print
    olist = []
    for i in range(0,len(c["generators"])):
        """
        print c["generators"][i]
        """
        gen = c["generators"][i]["name"]
        olist.append({"name": shorttensorgen(gen), "degree": c["generators"][i]["degree"], "weight": c["generators"][i]["weight"]})
    olist.sort(sortshort)
    for i in range(0,len(c["generators"])):
        print(olist[i]["degree"], olist[i]["weight"], olist[i]["name"])
    print
    print("Differentials:")
    print
    for i in range(0,len(c["differentials"])):
        """
        print c["differentials"][i]
        """
        genin = c["differentials"][i]["input"]["name"]
        genout = c["differentials"][i]["output"]["name"]
        print(shorttensorgen(genin), "--->", c["differentials"][i]["coefficient"], "*", shorttensorgen(genout))
    return()

"""
 This takes a filtered complex c, and returns a dictionary with four entries
 (1) l["mindegree"],
 (2) l["maxdegree"],
 (3) l["chainranks"], which is a list (0...maxdegree-mindegree-1) of ranks of chain groups
 (4) l["differentials"], which is a list of matrices (realized as double lists of integers)
"""

def construct_filledcomplex(c):
    progress(1,"Turning the sparse complex into a full one")
    maxdegree = c["generators"][0]["degree"]
    mindegree = maxdegree
    for i in range(0,len(c["generators"])):
        if c["generators"][i]["degree"] > maxdegree:
            maxdegree = c["generators"][i]["degree"]
        if c["generators"][i]["degree"] < mindegree:
            mindegree = c["generators"][i]["degree"]
    ranks = [0 for i in range(mindegree,maxdegree+1)]
    progress(2,"Range of degrees: from "+str(mindegree)+" to "+str(maxdegree))
    orderedgenerators = [[] for i in range(mindegree,maxdegree+1)]
    for i in range(0,len(c["generators"])):
        deg = c["generators"][i]["degree"]
        ranks[deg-mindegree] = ranks[deg-mindegree]+1
        orderedgenerators[deg-mindegree].append(c["generators"][i])
    differentials = []
    for d in range(mindegree,maxdegree):
        progress(2,"Building differential in degree "+str(d)+" (size "+str(ranks[d-mindegree])+"x"+str(ranks[d-mindegree+1])+")")
        emptymatrix = [[0 for j in range(0,ranks[d-mindegree])] for i in range(0,ranks[d+1-mindegree])]
        differentials.append(emptymatrix)
        source = orderedgenerators[d-mindegree]
        target = orderedgenerators[d-mindegree+1]
        gdiff = []
        for i in range(0,len(c["differentials"])):
            if c["differentials"][i]["input"]["degree"] == d:
                dsource = c["differentials"][i]["input"]
                dtarget = c["differentials"][i]["output"]
                dcoeff = c["differentials"][i]["coefficient"]
                sourceindex = source.index(dsource)
                targetindex = target.index(dtarget)
                differentials[d-mindegree][targetindex][sourceindex] = differentials[d-mindegree][targetindex][sourceindex] + dcoeff
    l = {"mindegree": mindegree, "maxdegree": maxdegree, "chainranks": ranks, "differentials": differentials}
    return(l)

def simplify_complex(c):
    progress(1,"Simplifying sparse complex")
    inputoutput = [{"input": x["input"], "output": x["output"]} for x in c["differentials"]]
    coeffs = [x["coefficient"] for x in c["differentials"]]
    for i in range(0,len(inputoutput)):
        io = inputoutput[i]
        j = i
        while io in inputoutput[j+1:]:
            j = j+1+inputoutput[j+1:].index(io)
            coeffs[i] = coeffs[i] + coeffs[j]
            coeffs[j] = 0
    newd = []
    for i in range(0,len(coeffs)):
        if coeffs[i] != 0:
            newentry = {"input": inputoutput[i]["input"], "output": inputoutput[i]["output"], "coefficient": coeffs[i]}
            newd.append(newentry)
    c["differentials"] = newd
  
    ticker = 0
    i = 0
    while i<len(c["generators"]):
        source = c["generators"][i]
        n = 0
        for j in range(0,len(c["differentials"])):
            if c["differentials"][j]["input"] == source:
                n = n+1
                target = c["differentials"][j]["output"]
        if n == 1:
            m = 0
            for j in range(0,len(c["differentials"])):
                if c["differentials"][j]["output"] == target:
                    m = m+1
                    diff = c["differentials"][j]
            if m == 1:
                ticker = ticker + 1
                c["generators"].remove(source)
                c["generators"].remove(target)
                c["differentials"].remove(diff)
            else:
                i = i+1
        else:
            i = i+1
    progress(1,str(ticker)+" pairs of generators removed")
    return()

def check_filledcomplex(l):
    fail = "pass"
    for d in range(l["mindegree"],l["maxdegree"]-1):
        for j in range(0,l["chainranks"][d-l["mindegree"]]):
            for k in range(0,l["chainranks"][d+2-l["mindegree"]]):
                prod = 0
                for i in range(0,l["chainranks"][d+1-l["mindegree"]]):
                    prod = prod + l["differentials"][d+1-l["mindegree"]][k][i] * l["differentials"][d-l["mindegree"]][i][j]
                if prod != 0:
                    fail = "fail"
    return(fail)

def matrixrank(a):
    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)+")")
    ranksofar = 0
    """
    checkrows = 0
    ranksofar = 0
    while checkrows < rows:
        n = 0
        [n = n+1 for c in a[checkrows] if c <> 0]
        if n == 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(2,"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(2,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 betti(l):
    progress(1,"Computing Betti numbers")
    ranks = [0]
    for d in range(l["mindegree"],l["maxdegree"]):
        a = copy.deepcopy(l["differentials"][d-l["mindegree"]])
        ranks.append(matrixrank(a))
    ranks.append(0)
    be = []
    for d in range(l["mindegree"],l["maxdegree"]+1):
        b = l["chainranks"][d-l["mindegree"]] - ranks[d-l["mindegree"]+1] - ranks[d-l["mindegree"]]
        be.append(b)
    outcome = {"mindegree": l["mindegree"], "maxdegree": l["maxdegree"], "betti": be}
    return outcome

def bettimodp(l,p):
    progress(1,"Computing Betti numbers mod "+str(p))
    ranks = [0]
    for d in range(l["mindegree"],l["maxdegree"]):
        a = copy.deepcopy(l["differentials"][d-l["mindegree"]])
        ranks.append(matrixrankmodp(a,p))
    ranks.append(0)
    betti = []
    for d in range(l["mindegree"],l["maxdegree"]+1):
        b = l["chainranks"][d-l["mindegree"]] - ranks[d-l["mindegree"]+1] - ranks[d-l["mindegree"]]
        betti.append(b)
    outcome = {"mindegree": l["mindegree"], "maxdegree": l["maxdegree"], "betti": betti}
    return outcome

"""
 An A_\infty-category a is a dictionary with three entries:
 (1) a["objects"] is a list of names of objects (should be strings)
 (2) a["morphisms"] is a list of morphisms. Each morphism m = a["morphisms"][i] is a dictionary
     with the following entries:
         m["source"] is an object
         m["target"] is an object
         m["degree"] is an integer
         m["weight"] is a nonnegative integer. This is supposed to be zero for the identity
         m["identity"] (optional) = "yes" if it's a strict identity element
"""

def check_complex(c):
    progress(1,"Checking sparse complex for d^2 = 0")
    fail = "pass"
    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:
                fail = "fail"
                progress(2,"Failure of d^2 = 0 at the following entry-")
                progress(2,"Source: "+str(c["generators"][i]))
                progress(2,"Target: "+str(c["generators"][j]))
                progress(2,"Nonzero coefficient: "+str(coeff))
    return(fail)

def prettyprint_algebra(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
    ccounter = 0
    order = 0
    index = 0
    while ccounter < len(a["compositions"]):
        com = a["compositions"][index]
        if com["order"] == order:
            description = []
            for i in range(0,order):
                name = com["inputs"][i]["name"]
                description.append(name)
            print(description, "--->", com["coefficient"], "*", com["output"]["name"])
            ccounter=ccounter+1
        index = index+1
        if index >= len(a["compositions"]):
            index = 0
            order = order+1
    return()

"""
 Standard sign (-1)^{epsilon}
"""
   
def epsilon(degree):
    if degree % 2 == 0:
        sign = 1
    else:
        sign = -1
    return(sign)

"""
 Adds strict identity morphisms to a give A_\infty-category a. The new morphisms
 have names "e_obj" where "obj" is the object in question.
"""

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

def modify_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 = {"order": 2, "inputs": [newmorphisms[i],oneside], "output": oneside, "coefficient": epsilon(oneside["degree"])}
                newcompositions.append(newc)
            if oneside["source"] == a["objects"][i]:
                newc = {"order": 2, "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

"""
 Gives back the generators in k=fixedlength tensor copies of A^+[1] (reduced by omitting identities,
 and shifted by degrees). The generators come as entries of a list, and each g is a three-element
 dictionary:
   g["name"]: a list of the morphisms making up the tensor product
   g["degree"]: total (reduced) degree
   g["weight"]: sum of the weights
"""

def reducedtensorfixed(a,fixedlength,maxweight): 
    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)):
            if reducedmorphisms[i]["weight"] <= maxweight:
                new.append({"name" : [reducedmorphisms[i]], "degree" : reducedmorphisms[i]["degree"]-1, "weight" : reducedmorphisms[i]["weight"]})
    else:
        oneless = reducedtensorfixed(a,fixedlength-1,maxweight)
        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"]
                    newweight = first["weight"] + second["weight"]
                    build = {"name": newelements, "degree": newdegree, "weight": newweight}
                    if newweight <= maxweight:
                        new.append(build)
    return new    

def reducedbarchains(a,maxlength,maxweight):
    all = []
    for mm in range(1,maxlength+1):
        progress(2,"Listing generators of length "+str(mm))
        all.extend(reducedtensorfixed(a,mm,maxweight))
    return(all)

"""
 Same thing as reducedtensorfixed, except the output is A \otimes (A^+[1])^{otimes k-1},
 which is the corresponding piece of the Hochschild complex (reduced cyclic bar complex).
 For k = 1 one gets only the direct sums of the endomorphisms of all the objects of a
"""

def bardifferential(a,complex,maxweight):
    diff = []
    for k in range(0,len(a["compositions"])):
        if a["compositions"][k]["order"] == 0:
            mzero = a["compositions"][k]["output"]
            for i in range(0,len(complex)):
                gen = complex[i]["name"]
                if gen[0]["target"] == mzero["source"]:
                    mapstoname = [mzero]
                    mapstoname.extend(gen)
                    mapstodegree = complex[i]["degree"]+1
                    mapstoweight = complex[i]["weight"]+mzero["weight"]
                    mapsto = {"name": mapstoname, "degree": mapstodegree, "weight": mapstoweight}                        
                    coeff = epsilon(totalreduceddegree(gen)) * a["compositions"][k]["coefficient"]
                    newentry = {"input": complex[i], "output": mapsto, "coefficient": coeff}
                    if mapstoweight <= maxweight:
                        diff.append(newentry)              
                for j in range(0,len(gen)):
                    if gen[j]["source"] == mzero["target"]:
                        mapstoname = gen[:j+1]
                        mapstoname.append(mzero)
                        mapstoname.extend(gen[j+1:])
                        mapstodegree = complex[i]["degree"]+1
                        mapstoweight = complex[i]["weight"]+mzero["weight"]
                        mapsto = {"name": mapstoname, "degree": mapstodegree, "weight": mapstoweight}                        
                        coeff = epsilon(totalreduceddegree(gen[j+1:len(gen)])) * a["compositions"][k]["coefficient"]
                        newentry = {"input": complex[i], "output": mapsto, "coefficient": coeff}
                        if mapstoweight <= maxweight:
                            diff.append(newentry)
    for i in range(0,len(complex)):
        gen = complex[i]["name"]
        for j in range(0,len(gen)):
            for k in range(j+1,len(gen)+1):
                cutdown = gen[j:k]
                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[k:len(gen)])
                        mapstodegree = complex[i]["degree"]+1
                        mapstoweight = complex[i]["weight"]+diffweight(a["compositions"][m])
                        mapsto = {"name": mapstoname, "degree": mapstodegree, "weight": mapstoweight}
                        coeff = epsilon(totalreduceddegree(gen[k:len(gen)])) * a["compositions"][m]["coefficient"]
                        newentry = {"input": complex[i], "output": mapsto, "coefficient": coeff}
                        if mapstoweight <= maxweight:
                            diff.append(newentry)
    return(diff)

def zerogen(obj):
    name = {"name": "oo_"+obj, "degree": 0, "weight": 0}
    gen = {"name":[name], "degree": 0, "weight": 0}
    return gen

def construct_reducedbarcomplex(a,maxlength,maxweight):
    progress(1,"Constructing the reduced bar complex")
    chains = reducedbarchains(a,maxlength,maxweight)
    progress(2,"Number of generators: "+str(len(chains)+len(a["objects"])))
    diff = bardifferential(a,chains,maxweight)
    for i in range(0,len(a["objects"])):
        chains.append(zerogen(a["objects"][i]))
    for k in range(0,len(a["compositions"])):
        if a["compositions"][k]["order"] == 0:
            input = zerogen(a["compositions"][k]["output"]["target"])
            output = {"name": [a["compositions"][k]["output"]], "degree": a["compositions"][k]["output"]["degree"]-1, "weight": a["compositions"][k]["output"]["weight"]}
            coeff = a["compositions"][k]["coefficient"]
            newentry = {"input": input, "output": output, "coefficient": coeff}
            if output["weight"] <= maxweight:
                diff.append(newentry)
    progress(2,"Number of differentials: "+str(len(diff)))
    c = {"generators": chains, "differentials": diff}
    return c

def hochschildchainsfixed(a,fixedlength,maxweight):
    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"], "weight": morphisms[m]["weight"]}
                if build["weight"] <= maxweight:
                    new.append(build)
    else:
        tensor = reducedtensorfixed(a,fixedlength-1,maxweight)
        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"]
                    newweight = first["weight"] + second["weight"]
                    build = {"name": newelements, "degree": newdegree, "weight": newweight}
                    if build["weight"] <= maxweight:
                        new.append(build)
    return new

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

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

def diffweight(compose):
    diff = compose["output"]["weight"]
    for r in range(0,len(compose["inputs"])):
        diff = diff - compose["inputs"][r]["weight"]
    return diff

def purify_complex(c,weight):
    newgen = []
    for i in range(0,len(c["generators"])):
        g = c["generators"][i]
        if g["weight"] == weight:
            newgen.append(g)
    newdiff = []
    for i in range(0,len(c["differentials"])):
        d = c["differentials"][i]
        if (d["input"]["weight"] == weight) and (d["output"]["weight"] == weight):
            newdiff.append(d)
    newc = {"generators": newgen, "differentials": newdiff}
    return newc

def hochschilddifferential(a,complex,maxweight):
    diff = []
    for k in range(0,len(a["compositions"])):
        if a["compositions"][k]["order"] == 0:
            mzero = a["compositions"][k]["output"]
            for i in range(0,len(complex)):
                gen = complex[i]["name"]
                for j in range(0,len(gen)):
                    if gen[j]["source"] == mzero["target"]:
                        mapstoname = gen[:j+1]
                        mapstoname.append(mzero)
                        mapstoname.extend(gen[j+1:])
                        mapstodegree = complex[i]["degree"]+1
                        mapstoweight = complex[i]["weight"]+mzero["weight"]
                        mapsto = {"name": mapstoname, "degree": mapstodegree, "weight": mapstoweight}                        
                        coeff = epsilon(totalreduceddegree(gen[j+1:len(gen)])) * a["compositions"][k]["coefficient"]
                        newentry = {"input": complex[i], "output": mapsto, "coefficient": coeff}
                        if mapstoweight <= maxweight:
                            diff.append(newentry)
    for i in range(0,len(complex)):
        gen = complex[i]["name"]
        for j in range(0,len(gen)):
            for k in range(j+1,len(gen)+1):
                cutdown = gen[j:k]
                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[k:len(gen)])
                        mapstodegree = complex[i]["degree"]+1
                        mapstoweight = complex[i]["weight"]+diffweight(a["compositions"][m])
                        mapsto = {"name": mapstoname, "degree": mapstodegree, "weight": mapstoweight}
                        coeff = epsilon(totalreduceddegree(gen[k:len(gen)])) * a["compositions"][m]["coefficient"]
                        newentry = {"input": complex[i], "output": mapsto, "coefficient": coeff}
                        if mapstoweight <= maxweight:
                            diff.append(newentry)
    for i in range(0,len(complex)):
        gen = complex[i]["name"]
        for j in range(1,len(gen)):
            for k in range(j,len(gen)):
                """ print i,j,k """
                rotated = gen[k:len(gen)]
                rotated.extend(gen[0:j])
                for m in range(0,len(a["compositions"])):
                    if rotated == a["compositions"][m]["inputs"]:
                        mapstoname = [a["compositions"][m]["output"]]
                        mapstoname.extend(gen[j:k])
                        """ print mapstoname """
                        mapstodegree = complex[i]["degree"]+1
                        mapstoweight = complex[i]["weight"]+diffweight(a["compositions"][m])
                        mapsto = {"name": mapstoname, "degree": mapstodegree, "weight": mapstoweight}
                        permutesign = epsilon(totalreduceddegree(gen[k:len(gen)]) * totalreduceddegree(gen[0:k]))
                        coeff = permutesign * epsilon(totalreduceddegree(gen[j:k])) * a["compositions"][m]["coefficient"]
                        newentry = {"input": complex[i], "output": mapsto, "coefficient": coeff}
                        if mapstoweight <= maxweight:
                            diff.append(newentry)
    return(diff)

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

def compute_hochschild(a,maxlength,maxweight):
    h = construct_hochschildcomplex(a,maxlength,maxweight)
    f = construct_filledcomplex(h)
    b = betti(f)
    return b

a,b = examplepair_cotangents2()
prettyprint_algebra(b)
hata = construct_hatalgebra(a,b,2)
h = construct_hochschildcomplex(hata,5,2)
f = construct_filledcomplex(h)
bet2 = bettimodp(f,2)
print("mod 2 betti numbers")
print(bet2)
bet3 = bettimodp(f,3)
print("mod 3 betti numbers")
print(bet3)