#!/usr/local/bin/python
#
# This is Python script for generating SnapPea link projections of
# either of the two link complements associated to a braid (Theses
# are: the standard braid closure, and the one with an
# additional component which always fibers over the circle).
#
# Call from the command line like:
#
# python braids.py   num_strands   fibered_version  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 braids.py 4 0 "[1, 2, -3, -3, -2, 1]"
#
# 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  1999/6/7   By Nathan Dunfield <nathand@math.harvard.edu>
#
#  Version 1.1  2000/10/16  made so will prompt for input if none given
#                           at command line.
#
# 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
#
#   braid( num_strands, fibers, 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 braid( num_strands, fibers, braid_word):

    s = 15
    n = num_strands
    l = len(braid_word)
    
    # check input.

    for x in braid_word:
        if abs(x) >= num_strands:
            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))

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

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

    se_verts = []
    for i in range(0, n):
        se_verts.append(vert(max_h  -  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)

    # add vertices of extra components in fibered case

    if fibers:
        f_verts = [vert((n+4)*s, (n+1)*s), vert(max_h + s, (n+1)*s),
                  vert(max_h + s , (n+2)*s), vert((n+4)*s, (n+2)*s)]

    # 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( nw_verts[i], ne_verts[i]))
        east_edge = edge( ne_verts[i], se_verts[i])
        edges.append(east_edge)
        east_edges.append(east_edge)
        edges.append(edge( se_verts[i], sw_verts[i]))
        edges.append(edge( sw_verts[i], w_verts[l][i]))

    # 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)

    #  if wanting extra component

    if fibers:
        e1 = edge(f_verts[0], f_verts[1])
        e2 = edge(f_verts[1], f_verts[2])
        e3 = edge(f_verts[2], f_verts[3])
        e4 = edge(f_verts[3], f_verts[0])
        edges.append(e1)
        edges.append(e2)
        edges.append(e3)
        edges.append(e4)
        
        for i in range(0, n):
            crossings.append( crossing(e1, east_edges[i]))
            crossings.append(crossing(east_edges[i], e3))

    # create projection

    all_verts = nw_verts + ne_verts + se_verts + sw_verts
    
    for i in range(0, l+1):
        all_verts = all_verts + w_verts[i]

    if fibers:
        all_verts = all_verts + f_verts
    
    proj =  projection(all_verts, edges, crossings)
    proj.shift(2*s, 2*s)
    return proj

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

if __name__ == "__main__":
    import sys, string
    if len(sys.argv) == 4:
        inp = sys.argv[1:4]
        o = sys.stdout.write
    else:
        print "Enter num_strands   fibered_version  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, b, c =  inp[:3]
    a, b = int(a), int(b)
    c = eval(c)
    p = braid(a,b,c)
    o( p.SnapPea_projection())