#!/usr/bin/env python3
import numpy as np
from sys import argv

def main(argv):
    method = "cs"

    inputpath = argv[2]

    if len(argv) == 4:
        if argv[3] == "-x":
            method = "cb"

    outputpath = inputpath[0:len(inputpath)-3] + ".xpm"

    matrix = ['0'] * 500
    for i in range(500):
        matrix[i] = ['0'] * 500

    #checks if the file has begun
    bof = False
    #checks for end of file
    eof = False

    inputfile = open(inputpath, "r")
    outputfile = open(outputpath, "w")

    polygon = []

    while not eof:
        line = inputfile.readline()

        polygonComplete = False

        if "%%%BEGIN" in line:
            bof = True
            line = inputfile.readline()
        if "moveto" in line and bof:
            input = line.split()
            polygon = [(int(input[0]), int(input[1]))]
        elif "lineto" in line and bof:
            input = line.split()
            polygon.append((int(input[0]), (int(input[1]))))
        elif "stroke" in line and bof:
            polygonComplete = True
        if "%%%END" in line:
            bof = False
            eof = True

        if bof and len(line.split()) > 3 and line.split()[4] == "Line":
            updatedArray = (getLineCoordinates(line.split()[0:4], method))
            matrix = pairsToMatrix(updatedArray, matrix)
        if bof and polygonComplete:
            vertices = sutherlandHodgman(polygon)
            updatedArray = (getPolygonCoordinates(vertices, polygon))
            if vertices != []:
                matrix = scanFillPolygon(vertices, matrix)
            matrix = pairsToMatrix(updatedArray, matrix)
            polygonComplete = False

    convertToXPM(outputfile, matrix)

def getPolygonCoordinates(vertices, polygon):
    updatedArray = []

    for i in range(len(vertices)):
        if i + 1 == len(vertices):
            coordinates = [vertices[i], vertices[0]]
        else:
            coordinates = [vertices[i], vertices[i + 1]]
        new = drawLine(*coordinates[0], *coordinates[1])
        updatedArray.extend(new)

    return updatedArray

def scanFillPolygon(vertices, matrix):
    sortByY = sorted(vertices, key=lambda x: x[1])

    ymin = sortByY[0][1]
    ymax = sortByY[len(sortByY)-1][1]
    fill = []

    y = ymax - 1
    while(y > ymin):
        #get intersections of scan line
        #for each edge
        extrema = []
        for i in range(len(vertices) - 1):
            edge = False
            if i == (len(vertices) - 1):
                if vertices[i][0] == 499 or vertices[0][0] == 499:
                    edge = True
                elif vertices[i][0] == 0 or vertices[0][0] == 0:
                    edge = True
                if vertices[i][1] != vertices[0][1] or edge:
                    x = getXIntercept(y, vertices[i], vertices[0])
                    if x != ():
                        extrema.append(x)
            else:
                if vertices[i][0] == 499 or vertices[i+1][0] == 499:
                    edge = True
                elif vertices[i][0] == 0 or vertices[i+1][0] == 0:
                    edge = True
                if vertices[i][1] != vertices[i + 1][1] or edge:
                    x = getXIntercept(y, vertices[i], vertices[i + 1])
                    if x != ():
                        extrema.append(x)

        #add to list, check if y min or y max
        #sort x ascending
        extrema = sorted(extrema, key=lambda x: x[0])

        for i in range(0, len(extrema)-1, 2):
            current = extrema[i][0]
            next = extrema[i+1][0]

            for j in range(int(current), int(next)):
                fill.append((j,y))

            #change values of matrix, once it hits the first intersection, switches to 1 until it hits the 2nd intersection, doesn't fill in 1

        y = y - 1
    return pairsToMatrix(fill, matrix)

def getXIntercept(y, endpoint1, endpoint2):
    if endpoint1[0] == endpoint2[0]:
        return (endpoint1[0],y)
    elif endpoint1[1] < y and endpoint2[1] < y:
        return ()
    elif endpoint1[1] > y and endpoint2[1] > y:
        return ()
    else:
        m = (endpoint2[1] - endpoint1[1])/(endpoint2[0] - endpoint1[0])

        x = endpoint1[0] + ((y - endpoint1[1]) / m)

        return (x,y)

def getLineCoordinates(array, method):
    if method == "cs":
        coordinates = cohenSutherland(array)

        if coordinates == []:
            updatedArray = []
        else:
            updatedArray = drawLine(*coordinates[0], *coordinates[1])

    elif method == "cb":
        p0 = (int(array[0]), int(array[1]))
        p1 = (int(array[2]), int(array[3]))
        coordinates = cyrusBeck(p0, p1)
        if coordinates == []:
            updatedArray = []
        else:
            updatedArray = drawLine(*coordinates[0], *coordinates[1])

    return updatedArray

def sutherlandHodgman(vertices):
    updatedVertices = []

    for j in range(2):
        for i in range(len(vertices)):
            inout = []

            if vertices[i][j] < 0:
                inout.append("outside")
            else:
                inout.append("inside")

            if (i + 1) == len(vertices):
                if vertices[0][j] < 0:
                    inout.append("outside")
                else:
                    inout.append("inside")
            else:
                if vertices[i + 1][j] < 0:
                    inout.append("outside")
                else:
                    inout.append("inside")

            if inout[0] == "inside" and inout[1] == "inside":
                if (i + 1) == len(vertices):
                    updatedVertices.append(vertices[0])
                else:
                    updatedVertices.append(vertices[i + 1])
            if inout[0] == "inside" and inout[1] == "outside":
                if (i + 1) == len(vertices):
                    v = cyrusBeck(vertices[i], vertices[0])
                else:
                    v = cyrusBeck(vertices[i], vertices[i + 1])
                if v != []:
                    updatedVertices.append(v[1])
            if inout[0] == "outside" and inout[1] == "inside":
                if (i + 1) == len(vertices):
                    v = cyrusBeck(vertices[i], vertices[0])
                else:
                    v = cyrusBeck(vertices[i], vertices[i + 1])
                if v != []:
                    updatedVertices.append(v[0])
                    updatedVertices.append(v[1])

        vertices = updatedVertices
        updatedVertices = []

    for j in range(2):
        for i in range(len(vertices)):
            inout = []
            if vertices[i][j] > 499:
                inout.append("outside")
            else:
                inout.append("inside")

            if (i + 1) == len(vertices):
                if vertices[0][j] > 499:
                    inout.append("outside")
                else:
                    inout.append("inside")
            else:
                if vertices[i + 1][j] > 499:
                    inout.append("outside")
                else:
                    inout.append("inside")

            if inout[0] == "inside" and inout[1] == "inside":
                if (i + 1) == len(vertices):
                    updatedVertices.append(vertices[0])
                else:
                    updatedVertices.append(vertices[i + 1])
            if inout[0] == "inside" and inout[1] == "outside":
                if (i + 1) == len(vertices):
                    v = cyrusBeck(vertices[i], vertices[0])
                else:
                    v = cyrusBeck(vertices[i], vertices[i + 1])
                if v != []:
                    updatedVertices.append(v[1])
            if inout[0] == "outside" and inout[1] == "inside":
                if (i + 1) == len(vertices):
                    v = cyrusBeck(vertices[i], vertices[0])
                else:
                    v = cyrusBeck(vertices[i], vertices[i + 1])
                if v != []:
                    updatedVertices.append(v[0])
                    updatedVertices.append(v[1])

        vertices = updatedVertices
        updatedVertices = []

    return vertices

def cohenSutherland(array):
    coordinates = [(int(array[0]), int(array[1])),(int(array[2]), int(array[3]))]

    bitcode = [assignBitCode(*coordinates[0]), assignBitCode(*coordinates[1])]

    i = 0
    outside = False
    while i < 4:
        if bitcode[0][i] == 1 and (bitcode[0][i] == bitcode[1][i]):
            outside = True
        i = i + 1

    if outside:
        return []
    elif 1 in bitcode[0] or 1 in bitcode[1]:
        return clipLine(bitcode, coordinates)
    elif (1 not in bitcode[0] and 1 not in bitcode[1]):
        return coordinates

def assignBitCode(x, y):
    bitcode = [0,0,0,0]

    if y < 0:
        bitcode[1] = 1
    if x < 0:
        bitcode[3] = 1
    if y > 499:
        bitcode[0] = 1
    if x > 499:
        bitcode[2] = 1

    return bitcode

def clipLine(bitcode, currentCoordinates):
    if (currentCoordinates[1][0] - currentCoordinates[0][0]) == 0:
        if 1 in bitcode[0]:
            if bitcode[0][0] == 1:
                currentCoordinates[0][1] = 499
            elif bitcode[0][1] == 1:
                currentCoordinates[0][1] = 0

        if 1 in bitcode[1]:
            if bitcode[1][0] == 1:
                currentCoordinates[1][1] = 499
            elif bitcode[1][1] == 1:
                currentCoordinates[1][1] = 0
    else:
        m = (currentCoordinates[1][1] - currentCoordinates[0][1]) / (currentCoordinates[1][0] - currentCoordinates[0][0])

        if 1 in bitcode[0]:
            if bitcode[0][0] == 1:
                x = currentCoordinates[0][0] + ((499 - currentCoordinates[0][1]) / m)
                currentCoordinates[0][0] = x
                currentCoordinates[0][1] = 499
            elif bitcode[0][1] == 1:
                x = currentCoordinates[0][0] - (currentCoordinates[0][1] / m)
                currentCoordinates[0][0] = x
                currentCoordinates[0][1] = 0

            bitcode[0] = assignBitCode(*currentCoordinates[0])

            if bitcode[0][2] == 1:
                y = currentCoordinates[0][1] + (m * (499 - currentCoordinates[0][0]))
                currentCoordinates[0][1] = y
                currentCoordinates[0][0] = 499
            elif bitcode[0][3] == 1:
                y = currentCoordinates[0][1] - (m * currentCoordinates[0][0])
                currentCoordinates[0][1] = y
                currentCoordinates[0][0] = 0

        if 1 in bitcode[1]:
            if bitcode[1][0] == 1:
                x = currentCoordinates[1][0] + ((499 - currentCoordinates[1][1]) / m)
                currentCoordinates[1][0] = x
                currentCoordinates[1][1] = 499
            elif bitcode[1][1] == 1:
                x = currentCoordinates[1][0] - (currentCoordinates[1][1] / m)
                currentCoordinates[1][0] = x
                currentCoordinates[1][1] = 0

            bitcode[1] = assignBitCode(*currentCoordinates[1])

            if bitcode[1][2] == 1:
                y = currentCoordinates[1][1] + (m * (499 - currentCoordinates[1][0]))
                currentCoordinates[1][1] = y
                currentCoordinates[1][0] = 499
            elif bitcode[1][3] == 1:
                y = currentCoordinates[1][1] - (m * currentCoordinates[1][0])
                currentCoordinates[1][1] = y
                currentCoordinates[1][0] = 0

    return currentCoordinates


def drawLine(x1, y1, x2, y2):
    yk = y1
    xk = x1

    deltax = x2 - x1
    deltay = y2 - y1

    if deltax == 0:
        updatedArray = [(xk, yk)]
        while yk - 1 > y2:
            yk = yk - 1
            updatedArray.append((xk, yk))
        while yk + 1 < y2:
            yk = yk + 1
            updatedArray.append((xk, yk))
        return updatedArray

    m = deltay / deltax

    if abs(m) < 1:
        if(x1 > x2):
            xk = x2
            x2 = x1
            yk = y2
            y2 = y1

        deltax = 1
        deltay = (y2 - yk) / (x2 - xk)

        updatedArray = [(xk, yk)]

        while xk + deltax < x2:
            xk = xk + deltax
            yk = yk + deltay
            updatedArray.append((xk, yk))

    else:
        if(y1 > y2):
            xk = x2
            x2 = x1
            yk = y2
            y2 = y1

        m = (y2 - yk) / (x2 - xk)
        deltay = 1
        deltax = 1 / m

        updatedArray = [(xk, yk)]

        while yk + deltay < y2:
            yk = yk + deltay
            xk = xk + deltax
            updatedArray.append((xk, yk))

    return updatedArray


def pairsToMatrix(updatedArray, matrix):
    for i in updatedArray:
        x = round(float(i[0]))
        y = round(float(i[1]))
        matrix[x][y] = '1'
    return matrix

def convertToXPM(outputfile, matrix):
    outputfile.write("/* XPM */ \n")
    outputfile.write("static char *sco100[] = { \n")

    outputfile.write("/* width height num_colors chars_per_pixel */ \n")
    outputfile.write("\"500 500 2 1\", \n")

    outputfile.write("/* colors */ \n")
    outputfile.write("\"0 c #ffffff\", \n")
    outputfile.write("\"1 c #000000\", \n")

    outputfile.write("/* pixels */ \n")

    matrix = np.rot90(matrix, k=1)

    temp = "\""""

    k = 0
    for i in matrix:
        k = k + 1
        for j in i:
            temp = temp + str(j)
        if(k == len(matrix)):
            temp = temp + "\"""\n"
        else:
            temp = temp + "\""",\n\""""
    temp = temp + "};"

    outputfile.write(temp)

def cyrusBeck(p0, p1):
    normal = [(-1, 0),(0, -1),(0, 1),(1, 0)]
    entering = [0]
    leaving = [1]

    gridpoints = [(0, 0),(499, 0),(0, 499),(499, 499)]
    d = subtractVectors(p1, p0)

    for i in range(4):
        type = dotProduct(normal[i], d)

        if type == 0:
            continue

        t = (dotProduct(normal[i], (subtractVectors(p0, gridpoints[i]))) / type) * -1

        if type > 0:
            leaving.append(t)
        elif type < 0:
            entering.append(t)

    timeEntering = max(entering)
    timeLeaving = min(leaving)

    pte = addVectors(p0, multiplyVectors(timeEntering, d))
    ptl = addVectors(p0, multiplyVectors(timeLeaving, d))

    if timeEntering > timeLeaving:
        return []
    elif any((c < 0 or c > 499) for c in [*pte, *ptl]):
        return []
    else:
        return [pte, ptl]

def subtractVectors(v1, v2):
    return ((v1[0] - v2[0]),(v1[1] - v2[1]))

def addVectors(v1, v2):
    return ((v1[0] + v2[0]),(v1[1] + v2[1]))

def multiplyVectors(c, v):
    return ((c * v[0]),(c * v[1]))

def dotProduct(v1, v2):
    return sum(x * y for (x, y) in zip(v1, v2))

main(argv)