#!/usr/local/bin/python
#
# This is Python script for generating SnapPea link projections 
# of bridge presentations.
#
# Call from the command line like:
#
# python bridge.py   num_bridges  braid_word
#
#  where fibered_version is 0 if want the standard braid closure
#  and 1 if you want the one with the addional component.
#
# E.g. under UNIX (for MacOS see below).
#
# python bridge.py 2 "[2,2,2,2,2,-3,-3,2]"
#
# where the entry k in braid_word corresponds to the the kth standard
# generator (sigma_k) of the braid group and sigma_(-k) =
# (sigma_k)^(-1).  Link projection file is printed to standard out.  
#
# Under MacOS, use BuildApplet to build an executable, then run.
#
#  Version 1.0  2000/10/17   By Nathan Dunfield <nathand@math.harvard.edu>
#
# below classes taken from montesinos_projection.py

class vert:
    num_vert = 0
    def __init__(self, h, v):
        self.h, self.v = h, v
        self.n = 0 # set later when creating SnapPea proj
        
    def __repr__(self):
        return  "<%d, %d>" % (self.h, self.v)

    def shift(self, h, v):
        self.h, self.v = self.h + h, self.v + v

class edge:
    num_edges = 0
    def __init__(self, v, w):
        self.vert = (v, w)
        self.n = 0 # set later when creating SnapPea proj
        
    def __getitem__(self, i):
        return self.vert[i]
    
    def __repr__(self):
        return "%s -> %s" % self.vert

    def reverse(self):
        self.vert = (self.vert[1], self.vert[0])
        
    # evaluates the function vert -> a vert.h + b vert.v + c whose
    # zeros are the line containing the edge
    
    def funct_def_line(self, v):
        x0, y0 = self.vert[0].h, self.vert[0].v
        x1, y1 = self.vert[1].h, self.vert[1].v
        return (y1 - y0)*(v.v - y0) - (x1 - x0)*(v.h - x0)
        
# decides if two edges cross.  checks to see if the vertices of f are
# seperated by the line containing e and vise versa.  The first
# function is to avoid integer overflow.

def product_is_negative(a,b):
    if (a < 0 and b > 0) or (a > 0 and b < 0):
        return 1;
    return 0;

def do_cross(e,f):
    return (product_is_negative(e.funct_def_line(f[0]) ,  e.funct_def_line(f[1])) and
        product_is_negative(f.funct_def_line(e[0]) , f.funct_def_line(e[1]) ))
        
class crossing:
    def __init__(self, e, f):
        self.over, self.under = e, f

    def __repr__(self):
        return "(%s over %s)" % (self.over, self.under)

class projection:
    def __init__(self, vertices, edges, crossings):
        self.vertices = vertices
        self.edges = edges
        self.crossings = crossings

    # moves projection over by (x, y) -> (x + h, y + v)
    def shift(self, h, v):
        for w in self.vertices:
            w.shift(h,v)

    # adds another projection to this one

    def union(self, other):
        self.vertices = self.vertices + other.vertices
        self.edges = self.edges + other.edges
        self.crossings = self.crossings + other.crossings
        
    # returns a string containg the SnapPea projection.
    
    def SnapPea_projection(self):
        # First, sort edges into maximal connected strands
        strands = []
        edges = self.edges[:]
        while edges:
            strand = [edges[0]]
            edges.remove(strand[0])
            extended = 1
            while extended:
                extended = 0
                for e in edges:
                    if e[0] == strand[-1][1] or e[1] == strand[-1][1]:
                        if e[1] == strand[-1][1]:
                            e.reverse()
                        strand.append(e)
                        edges.remove(e)
                        extended = 1
                        break
            strands.append(strand)

        #set vertex numbers

        num_vert = 0
        for strand in strands:
            for e in strand:
                e[0].n = num_vert
                num_vert = num_vert + 1
            if strand[0][0] != strand[-1][1]:
                strand[-1][1].n = num_vert
                num_vert = num_vert + 1

        output = "% Link Projection\n"

        # data about components
        
        output = output + "%d\n" % len(strands)
        for strand in strands:
            output = output + "   %d  %d\n" % (strand[0][0].n, strand[-1][1].n)
        output = output + "\n"

        # data about vertices

        output = output + "%d\n" % num_vert
        self.vertices.sort(lambda x, y: cmp(x.n, y.n))
        for v in self.vertices:
            output = output + "   %d  %d\n" % (v.h, v.v)
        output = output + "\n"

        # data about edges

        num_edges = 0
        for strand in strands:
            for e in strand:
                e.n = num_edges
                num_edges = num_edges + 1

        output = output + "%d\n" % num_edges
        self.edges.sort(lambda x, y: cmp(x.n, y.n))
        for e in self.edges:
                output = output + "   %d  %d\n" % (e[0].n, e[1].n)
        output = output + "\n"

        # data about crossings
        
        output = output + "%d\n" % len(self.crossings)
        for c in self.crossings:
                output = output + "   %d  %d\n" % (c.under.n, c.over.n)
        output = output + "\n-1\n"

        return output

#------End classes taken from montesinos_projection.py----------------------------

# MAIN FUNCTION
#
#   bridge_presentation( num_bridges, braid_word):
#
# fibers is 0 for the standard braid closure, 1 for the fibering one.  
# braid is of the form [1, 2, -3] which corresponds to the product of
# standard generators sigma_1 * sigma_2 * sigma_3^-1.  

def bridge_presentation( num_bridges, braid_word):

    s = 15
    n = 2*num_bridges
    l = len(braid_word)
    
    # check input.

    for x in braid_word:
        if abs(x) >= n:
            raise ValueError, "Generator index out of range"

    # Create all the vertices
    
    max_h = (2*n + 5)*s
    max_v = (2*n + l)*s

    nw_verts = []
    for i in range(0, n):
        nw_verts.append(vert(s*i, s*i))

    sw_verts = []
    for i in range(0, n):
        sw_verts.append(vert(s*i , max_v - s*i))

    w_verts = []

    for v in range(0, l+1):
        line = []
        for h in range(0, n):
            line.append(vert(s*h, (n + v)*s))
        w_verts.append(line)

    # create edges not in braid itself

    edges = []
    crossings = []
    east_edges =[]

    for i in range(0, n):
        edges.append(edge( nw_verts[i], w_verts[0][i]))
        edges.append(edge( sw_verts[i], w_verts[l][i]))

    for i in range(0, num_bridges):
        edges.append(edge( nw_verts[2*i], nw_verts[2*i+1]))
        edges.append(edge( sw_verts[2*i], sw_verts[2*i+1]))
        
    # create edges in braid itself

    for i in range(0, l):
        g = abs(braid_word[i]) - 1
        for j in range(0, n):
            if j ==  g:
                e1 = edge(w_verts[i][j], w_verts[i+1][j+1])
                edges.append(e1)
            elif j == g+1:
                e2 = edge(w_verts[i][j], w_verts[i+1][j-1])
                edges.append(e2)
            else:
                edges.append(edge(w_verts[i][j], w_verts[i+1][j]))
        
        if braid_word[i] > 0:
            c = crossing(e1, e2)
        else:
            c = crossing(e2, e1)

        crossings.append(c)

    # create projection

    all_verts = nw_verts + sw_verts
    
    for i in range(0, l+1):
        all_verts = all_verts + w_verts[i]
    
    proj =  projection(all_verts, edges, crossings)
    proj.shift(2*s, 2*s)
    return proj

#---- End function braid() -------------------------------------------

##from Tkinter import *

##def view_link(edges):
##    w = Frame()
##    w.pack()
##    c = Canvas(w, width="700", height="500")
##    c.pack(side=TOP)

##    for e in edges:
##        c.create_line(e[0].h, e[0].v, e[1].h, e[1].v, arrow = "last", fill = "red")

##    b = Button(w, text="Dismiss", command=w.quit)
##    b.pack(side=BOTTOM)
##    w.mainloop()

##p = bridge_presentation(2, [2,2,2,2,2,-3,-3,2])
##print p.SnapPea_projection()
##view_link(p.edges)


if __name__ == "__main__":
    import sys, string
    if len(sys.argv) == 3:
        inp = sys.argv[1:3]
        o = sys.stdout.write
    else:
        print "Enter num_bridges  braid_word"
        inp = string.split(sys.stdin.readline(), None, 2)
        print "Enter name of file to save to:"
        o = open(sys.stdin.readline()[:-1],"w").write

    a =  int(inp[0])
    c = eval(inp[1])
    p = bridge_presentation(a,c)
    o( p.SnapPea_projection())