#! /usr/local/bin/python
#
# This file defines the function
#
# create_monesinos_projection(fracs, file_object)
#
# which takes a list of "fractions" e.g. [ (2,3), (-5,7), (-11/2) ]
# and writes a SnapPea link projection of the corresponding Montesinos
# link to file_object.
#
# IMPORTANT NOTE:  If only one fraction is given, its does _not_ create
# correpsonding two-bridge  knot, which is not quite the same as a
# Montesinos knot with one tangle.  The two-bridge knot p/q corresponds to
# the Montesinos knot with one tangle which is -q/p.
#
# When called from the command  line, it accepts args of the form 2/3 -5/7 2/3
# and prints the SnapPea link projection to standard out.  E.g. under UNIX:
#
#    python monesinos_projection.py  2/3 -5/7 2/3 > proj_file
#

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
            

        
# create vertices on edges of tangle of slope p/q.
# we regard the tangle as sitting on the surface of
# a pillow case so that there is both a front and a
# back.
#
#      b0 ... b(p-2)
#  v0 -------------- w0
#     |            |
#  v1 |            |
#  :  |            | :
#  :  |            | :
#     |            |
#     |            | w(q-1)
#     |            |
#  vq -------------- wq
#      a0 ... a(p-2)
#
# total size of tangle created will be size*p by size*q
# vq is at (0,0) and w0 is at (size*p, size*q)

# creates all edges on one side of the pillow case of the slope (p,q)

def edges_with_slope_pq(p, q, v, w, a, b):
    edges = []

    # if this case we're have to swap everything around
    if abs(p) > q:
        v, w, a, b  = [v[q]] + a + [w[q]],  [v[0]] + b + [w[0]],  w[1:q], v[1:q]
        a.reverse()
        b.reverse()
        p, q = -q, p
        if q < 0:
            p, q = -p, -q
        
    if p < 0:
        p = abs(p)
        for i in range(0, q - p + 1):
            edges.append( edge(v[i], w[i + p]))
        for i in range(q - p + 1, q):
            edges.append( edge(v[i], a[q - i - 1]) )
        for i in range(1, p):
            edges.append( edge(b[i - 1], w[p - i]) )
    else:
        for i in range(1, p):
            edges.append( edge(v[i], b[i - 1]) )
        for i in range(p, q + 1):
            edges.append( edge(v[i], w[i - p]) )
        for i in range(1, p):
            edges.append( edge(a[i - 1], w[q + i - p]) )

    return edges

# returns (verts, edges, crosssings) for the tangle p/q where the
# first four vertices in verts are the "free" ends of the tangle:
# (vq, wq, w0, v0)

def make_tangle(p,q,size = 30):
    v = map(lambda i, s=size : vert(0, s*i), range(0, q+1))
    w = map(lambda i, h=size*abs(p), s=size : vert(h, s*i), range(0, q+1))
    a = map(lambda i, v=size*abs(q), s=size : vert(s*i, v), range(1, abs(p)))
    b = map(lambda i, s=size : vert(s*i, 0), range(1, abs(p)))

    front_edges = edges_with_slope_pq(p, q, v, w, a, b)
    back_edges = edges_with_slope_pq(-p, q, v, w, a, b)

    crossings = []
    for ff in front_edges:
        for bb in back_edges:
            if do_cross(ff, bb):
                crossings.append(crossing(ff, bb))


    return ( [v[0], w[0], w[q], v[q]] + v[1:-1] + w[1:-1] + a + b,
             front_edges + back_edges, crossings)

# computes the gcd.  taken from snappea

def gcd(a, b):

    a = abs(a)
    b = abs(b)
    
    if a == 0:
	if b == 0: raise ValueError, "gcd(0,0) undefined."
	else: return b

    while 1:
	b = b % a
	if (b == 0): return a
	a = a % b
	if (a == 0): return b

# puts fractions in standard form:

def standard_form(fractions):
    new_fracs = []
    for f in fractions:
        g = gcd(f[0], f[1])
        p, q = f[0]/g, f[1]/g
        if q < 0:
            p, q = -p, -q
        new_fracs.append(p,q)
    return new_fracs

# takes a list of "fractions" (p,q) and returns the projection of the
# corresponding Montesinos link.

def montesinos(fractions, size = 40):
    fractions = standard_form(fractions)
    f = fractions[0]
    proj = apply( projection, make_tangle(f[0], f[1], size) )
    proj.shift(size, 2*size)
    max_h = size*(1 + abs(f[0]))
    max_v = size*(2 + f[1])
                  
    # these four vertices will be extremal points of our union of
    # tangles (so far)
    
    nw, ne, se, sw = proj.vertices[:4]
    
    for f in fractions[1:]:
        temp_proj = apply( projection, make_tangle(f[0], f[1], size) )
        temp_proj.shift(max_h + size, 2*size)
        # free end of new tangle
        nnw, nne, nse, nsw = temp_proj.vertices[:4]
        max_h = max_h + size*(1 + abs(f[0]))
        max_v = max(max_v, size*(2 + f[1]))
        proj.union(temp_proj)
        proj.edges.append(edge(nnw, ne))
        proj.edges.append(edge(nsw, se))
        ne, se = nne, nse

    # outide corners of link
    
    cnw = vert(size, size)
    cne = vert(max_h, size)
    cse = vert(max_h, max_v + size)
    csw = vert(size, max_v + size)

    new_edges = [edge(cnw, cne), edge(csw, cse), edge(cnw, nw),
                 edge(cne, ne), edge(cse,se), edge(csw, sw)]
        
    proj.union(projection([cnw, cne, cse, csw], new_edges, []))

    return proj
    
def create_montesinos_projection(fractions, file):
    if len(fractions) == 0:
        sys.stderror.write("no data to produce knot\n")
    proj = montesinos(fractions)
    file.write(proj.SnapPea_projection())

if __name__ == "__main__":
    import sys, re
    
    def string_to_frac(s):
        data = re.match("([+-]{0,1}\d+)/([+-]{0,1}\d+)$", s)
        if not data:
            data = re.match("[+-]{0,1}\d+$", s)
            if data:
                return (int(s), 1)
            else:
                raise ValueError, "need something of form a/b, a and b integers"
        p, q = map(int, data.groups())
        return (p, q)

    fractions = []
    for arg in sys.argv[1:]:
        try:
            fractions.append( string_to_frac(arg))
        except ValueError:
            print "%s is not a fraction\n" % arg
            sys.exit(0)

    create_montesinos_projection(fractions, sys.stdout)
    sys.exit(0)



## Below is code that was used in debuging
    
## 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 = two_bridge(2,5)
## print p.SnapPea_projection()
## view_link(p.edges)