#!/usr/bin/python

#CW complex to simplicial complex converter
#By Alden Walker
#awalker@caltech.edu



import copy

#input:
#list of vertex labels
#dictionary of edges d['edge label'] = [vertex 1, vertex 2]
#dictionary of cells d['cell label'] = [list of edges] such that consecutive edges match vertices
#convention X = x^{-1}

#Example (Torus):
#CWtoSimp( ['v'], {'a':['v','v'], 'b':['v','v']}, {'L':['a','b','A','B']})

#Projective Plane:
#CWtoSimp( ['v'],{'a':['v','v']}, {'L':['a','a']})

#flattens one level of a list
def flatten(L):
    ans = []
    for x in L:
        ans.extend(x)
    return ans


def CWtoSimp(verts, edges, cells):
    newVerts = copy.deepcopy(verts)
    newEdges = copy.deepcopy(edges)
    newCells = copy.deepcopy(cells)
    #if an edge begins and ends on the same vertex, bisect it with three new vertices, 
    #and add appropriate edges in attached cells.
    modifiedEdgesFour = []
    #modifiedEdgesTwo = []
    for e in edges.keys():
        if edges[e][0] == edges[e][1]:
            del newEdges[e]
            newVerts.append( e + edges[e][0] + edges[e][1] )
            newVerts.append( e + edges[e][0] + edges[e][1] + edges[e][1] )
            newVerts.append( edges[e][0] + e + edges[e][0] + edges[e][1] )
            newEdges[e + '0'] = [edges[e][0], edges[e][0] + e + edges[e][0] + edges[e][1] ]
            newEdges[e + '1'] = [edges[e][0] + e + edges[e][0] + edges[e][1], e + edges[e][0] + edges[e][1] ]
            newEdges[e + '2'] = [e + edges[e][0] + edges[e][1], e + edges[e][0] + edges[e][1] + edges[e][1] ]
            newEdges[e + '3'] = [e + edges[e][0] + edges[e][1] + edges[e][1], edges[e][1] ]
            modifiedEdgesFour.append(e)
        #else:
        #    newVerts.append( e + edges[e][0] + edges[e][1] )
        #    newEdges[e + '0'] = [edges[e][0], e + edges[e][0] + edges[e][1] ]
        #    newEdges[e + '1'] = [e + edges[e][0] + edges[e][1], edges[e][1] ]
        #    modifiedEdgesTwo.append(e)
    
    
    #define the function which changes the edges to the new ones
    def changeEdges(ed):
        if ed in modifiedEdgesFour:
            return (ed+'0', ed+'1', ed+'2', ed+'3')
        elif ed.swapcase() in modifiedEdgesFour:
            return (ed + '3', ed + '2', ed + '1', ed + '0')  #notice ed is capitals, so opposite direction
        else:
            return ed
        
    for C in cells.keys():
        newCells[C] = flatten(  map(changeEdges, newCells[C]) )
        
    #add a vertex for every cell
    for C in cells.keys():
        newVerts.append( 'v' + C )
      
    #now we go around: for every edge, we triangle it with the middle vertex and subdivide it
    twoSimps = []
    for C in newCells.keys():
        counts = {}
        addedVerts = []
        for eg in newCells[C]:
            ed = eg.lower()
            edgeCount = counts.get(ed, 0)
            counts[ed] = counts.get(ed, 0) + 1
            newVerts.append('v' + ed + str(edgeCount) )
            addedVerts.append(['v' + ed + str(edgeCount), eg] )  #note we append the actual eg, which could be uppercase
            twoSimps.append( [ 'v'+ed+str(edgeCount),  newEdges[ed][0], newEdges[ed][1] ] )
        
        #here we have to be careful--we must note which vertex is the correct end of the edges, since some are inverses
        for i in xrange(len(addedVerts)-1):
            ed = addedVerts[i][1]
            if ed.isupper():
                twoSimps.append( [ addedVerts[i][0], addedVerts[i+1][0], newEdges[ed.lower()][0] ] )
                twoSimps.append( [ addedVerts[i][0], addedVerts[i+1][0], 'v'+C ] )
            else:
                twoSimps.append( [ addedVerts[i][0], addedVerts[i+1][0], newEdges[ed.lower()][1] ] )
                twoSimps.append( [ addedVerts[i][0], addedVerts[i+1][0], 'v'+C ] )
        
        ed = addedVerts[len(addedVerts)-1][1]  
        if ed.isupper():
            twoSimps.append( [ addedVerts[len(addedVerts)-1][0], addedVerts[0][0], newEdges[ed.lower()][0] ] )
            twoSimps.append( [ addedVerts[len(addedVerts)-1][0], addedVerts[0][0], 'v'+C ] )
        else:
            twoSimps.append( [ addedVerts[len(addedVerts)-1][0], addedVerts[0][0], newEdges[ed.lower()][1] ] )
            twoSimps.append( [ addedVerts[len(addedVerts)-1][0], addedVerts[0][0], 'v'+C ] )
                
    
    simps = [x for x in newEdges.values() if x[0] != x[1]] + twoSimps
    
    return (newVerts, simps)









#    modifiedEdges = []
#    for e in edges.keys():
#        if edges[e][0] == edges[e][1]:
#            newVerts.append( e + edges[e][0] + edges[e][1] )
#            newEdges[e + '0'] = [edges[e][0], e + edges[e][0] + edges[e][1] ]
#            newEdges[e + '1'] = [e + edges[e][0] + edges[e][1], edges[e][1] ]
#           modifiedEdges.append(e)
#    
#    def changeEdges(ed):
#        if ed in modifiedEdges:
#            return (ed + '0', ed + '1')
#        elif ed.swapcase():
#            return (ed.swapcase()+'1', ed.swapcase()+'0')
#        else:
#            return ed