#! /usr/bin/python3
import sys
import os

import math as m
from math import sqrt

import pandas as pd

import time

from pyx import *
from PIL import Image, ImageDraw, ImageFont

#################################### FUNÇÕES AUXILIARES.
def isEqual (A, B, tolerance):
    if abs(A - B) <= tolerance:
        return True
    return False

def rotate_x (x, y, angle):
    return ((x*m.cos(-angle) - y*m.sin(-angle))*100)/100.0

def rotate_y (x, y, angle):
   return ((x*m.sin(-angle) + y*m.cos(-angle))*100)/100.0

#################################### CÁLCULO DE TEMPO.
############ ACELERAÇÃO.
def accelerationDistance(speed, acceleration):
    '''
        Retorna a distância necessária para atingir a velocidade máxima.
    '''
    return (speed*speed)/(2*acceleration)

def accelerationTime(speed, acceleration):
    '''
        Retorna o tempo necessário para atingir a velocidade máxima.
    '''
    return speed/acceleration

############ DISTÂNCIA.
def calculate_distance (p, q):
    '''
        Retorna a distância entre os pontos p e q.
    '''
    if p == None or q == None:
        return 0
        
    dx = p[0] - q[0]
    dy = p[1] - q[1]
    return m.sqrt (dx*dx + dy*dy)

############ TEMPO.
def extrude_time (distance, parameters):
    '''
        Returns the times of extruding a stroke from point {p} to point {q},
        accounting for acceleration and deceleration.
    '''
    maxSpeedDistance = distance - 2*parameters['filling_dist']
    
    if maxSpeedDistance > 0:
        return 2*parameters['filling_time'] + maxSpeedDistance/parameters['filling_speed']

    else:
        return m.sqrt(distance/parameters['acceleration'])

def air_time (distance, parameters):
    '''
        Returns the times of moving the nozzle from point {p} to point {q},
        without extruding, accounting for nozzle lifting and dropping, acceleration and deceleration.
    '''

    maxSpeedDistance = distance - 2*parameters['travel_dist']
    
    if maxSpeedDistance > 0:
        return 2*parameters['travel_time'] + maxSpeedDistance/parameters['travel_speed'] + 2 * parameters['z_time']

    else:
        return m.sqrt(distance/parameters['acceleration']) + 2 * parameters['z_time']

def extrude_time_passage (p, q, M, parameters):
    '''
    Assumes that a stroke is being extruded from point {p} to point {q};
    returns the time from the start until when nozzle passes the point {m}.
    '''
    dx = p[0] - q[0]
    dy = p[1] - q[1]
    d = m.sqrt (dx*dx + dy*dy)

    gx = p[0] - M[0]
    gy = p[1] - M[1]
    g = m.sqrt (gx*gx + gy*gy)
    
    if d >= 2 * parameters['filling_dist']:
        if g >= parameters['filling_dist'] and g <= d - parameters['filling_dist']:  
           return parameters['filling_time'] + (g - parameters['filling_dist'])/parameters['filling_speed']

        else:   
           return m.sqrt((calculate_distance(p, M))/parameters['acceleration'])

    else:   
        return m.sqrt((calculate_distance(p, M))/parameters['acceleration'])

def total_time (R, parameters):
    '''
        Retorna o tempo total de fabricação da camada (dividido em tempo de reposicionamento e extrusão).
    '''
    extrudeTime = 0
    airTime = 0

    rEnd = None
    qEnd = None

    for r in R:
        extrudeTime = extrudeTime + r['e']

        if rEnd != None:

            rasterLink = None

            if rEnd['rbit'] != r['rbit']:
                for edge in range(2):
                    for side in rEnd['links'][edge]:   
                        if (side[0][3]['sid'] == rEnd['sid'] and side[0][5]['sid'] == r['sid']) or (side[0][3]['sid'] == r['sid'] and side[0][5]['sid'] == rEnd['sid']):
                            if side[2 + r['rbit']] != None:
                                rasterLink = side[2 + r['rbit']][0]
                
            if rasterLink != None:
                extrudeTime = extrudeTime + rasterLink
            else:
                airTime = airTime + air_time(calculate_distance(qEnd, r['p'][r['rbit']]), parameters)

        qEnd = r['p'][1-r['rbit']]
        rEnd = r

    return extrudeTime, airTime

#################################### LINHAS DE RASTER.
def create_stroke (sid, p, q, w, rbit, group, parameters):
    '''
        This function creates a stroke object with endpoints {p,q} with width {w}
        and no sides and identifier {sid}.
    '''
    R = {
        'sid': sid, # Stroke ID.
        'p': [p, q], # Points that describe the stroke.
        'w': w, # Stroke width.
        'e': extrude_time(calculate_distance(p, q), parameters), # Time required to extrude the stroke.
        'links': [[].copy(),[].copy()], # Strokes that have an adjacent section.
        'group': group, # ID of the group the stroke belongs to.
        'Tini': None, # Time when the stroke started to be extruded.
        'Tend': None, # Time when the stroke finished being extruded.
        'rbit': rbit, # Final stroke direction.
        'rbitoriginal': rbit # Oringal stroke direction.
    }
    return R

def add_side (R1, R2, rasterLink0, rasterLink1, parameters):
    '''
        Creates a side object which is an output of {R1} and input of {R2}. The two strokes
        must be adjacent. For now we assume that the strokes are horizontal, which R1
        below R2, and have the same width and starting point to the left of the endpoint.
        rasterLink0: raster link que liga os pontos R1['p'][0] e R2['p'][0].
        rasterLink1: raster link que liga os pontos R1['p'][1] e R2['p'][1].
    '''
    p1 = R1['p'][0]
    q1 = R1['p'][1]
    y1 = p1[1]

    assert y1 == q1[1] #R1 must be horizontal
    assert p1[0] <= q1[0] #R1 is left to right 

    p2 = R2['p'][0]
    q2 = R2['p'][1]
    y2 = p2[1]

    assert y2 == q2[1] #R2 must be horizontal
    assert p2[0] <= q2[0] #R2 is left to right 

    assert R1['w'] == R2['w'] #R1 and R2 must have the same width
    assert abs(y2 - y1) < 1.1*(R1['w'] + parameters['gap']) #R1 and R2 must be adjacent with R1 below R2
    
    x0 = max(p1[0], p2[0])
    x1 = min(q1[0], q2[0])

    assert x0 < x1

    xm = (x0 + x1)/2 #x of midpoint of side
    ym = (q1[1] + q2[1])/2 #y of side
    xl = x1 - x0 #lenght of side

    tm1 = extrude_time_passage (p1, q1, (xm, y1), parameters) # Time required to R1 reach the midpoint of side (xm).
    tm2 = extrude_time_passage (p2, q2, (xm, y2), parameters) # Time required to R2 reach the midpoint of side (xm).

    j1 = len(R1['links'][1]) # Number that identifies the side within the links vector of R1.
    i2 = len(R2['links'][0]) # Number that identifies the side within the links vector of R2.
    side = (xm, ym, xl, R1, j1, R2, i2)

    link1 = [side, tm1, rasterLink0, rasterLink1]
    link2 = [side, tm2, rasterLink0, rasterLink1]

    R1['links'][1].append(link1) #Append side to outputs of {R1}
    R2['links'][0].append(link2) #Append side to inputs of {R2}

    return side

def find_first_last (R, parameters):
    '''
        Percorre R e encontra as linhas de raster que estão nas bordas dos blocos.
        Como as linhas de raster estão ordenadas por altura, adotou-se como início {first} 
        de um bloco a primeira linha de raster encontrada na lista de linhas de raster {R}
        que pertence ao bloco em questão. Consequentemente, o final {last} de um bloco é a última
        linha de raster que pertence ao bloco.

        OBS: é possível que uma linha seja o ínicio e final de um bloco, ou seja, um bloco
        seja composto por apenas uma linha de raster.
    '''
    G = dict()

    for group in range(0, parameters['group'] + 1):
        G[group] = dict()
        i = 0
        pPrev = None

        for index in range(len(R)):
            r = R[index]

            if r['group'] == group:
                G[group][r['sid']] = i
                i += 1

                if pPrev == None: # Verifica se é começo do bloco.
                    r['first'] = True
                else:
                    r['first'] = False
                
                if index == len(R) - 1: # Verifica se é final do bloco.
                    r['last'] = True
                else:
                    r['last'] = False
                
                pPrev = index

            else:
                if index == len(R) - 1: # Verifica se é final do bloco.
                    R[pPrev]['last'] = True

    return G

def calculate_time (R, G, parameters):
    '''
        Para cada linha de raster em R, encontra o tempo para chegar nela
        a partir do início e do final de seu bloco. Também calcula o tempo 
        total para finalizar um bloco.
    '''
    maxTime = 0

    for group in G:
        totalTime1 = 0
        rPrev1 = None

        totalTime2 = 0
        rPrev2 = None

        for index in range(len(G[group])):
            r = R[list(G[group])[index]]

            if rPrev1 != None:
                for link in r['links'][0]:
                    side = link[0]
                    if side[3]['sid'] == r['sid'] and side[5]['sid'] == R[rPrev1]['sid']:
                        totalTime1 += link[2 + r['rbit']][0]
                    elif side[5]['sid'] == r['sid'] and side[3]['sid'] == R[rPrev1]['sid']:
                        totalTime1 += link[2 + r['rbit']][0]

            r['Tfirst'] = totalTime1
            totalTime1 += r['e']
            rPrev1 = r['sid']

        for index in range(len(G[group]) - 1, -1, -1):
            r = R[list(G[group])[index]]
            if rPrev2 != None:
                for link in r['links'][1]:
                    side = link[0]
                    if side[3]['sid'] == r['sid'] and side[5]['sid'] == R[rPrev2]['sid']:
                        totalTime2 += link[2 + R[rPrev2]['rbit']][0]
                    elif side[5]['sid'] == r['sid'] and side[3]['sid'] == R[rPrev2]['sid']:
                        totalTime2 += link[2 + R[rPrev2]['rbit']][0]

            r['Tlast'] = totalTime2
            totalTime2 += r['e']
            rPrev2 = r['sid']

        G[group]['totalTime'] = totalTime2
        if maxTime < totalTime2:
            maxTime = totalTime2

    return maxTime

#################################### RASTER LINKS.
def find_rasterLink (PR1, PR2, O, R, parameters):
    '''
        Recebe dois pares de pontos (PR1 e PR2) que representam linhas de raster e 
        verifica se existem interseções entre elas através dos offsets da camada. 
        Caso exista, cria e retorna os raster links existentes.
    '''

    # Verifica se as duas linhas de raster analisadas podem possuir um raster link entre elas pelos pontos p (PR1[0] e PR2[0]).
    allowedRasterLink0 = sameLine(R, PR1[0], PR2[0]) and sameLine(R, PR2[0], PR1[0])
    
    # Verifica se as duas linhas de raster analisadas podem possuir um raster link entre elas pelos pontos q (PR1[1] e PR2[1]).
    allowedRasterLink1 = sameLine(R, PR1[1], PR2[1]) and sameLine(R, PR2[1], PR1[1]) 

    if allowedRasterLink0 or allowedRasterLink1:
        rasterLink0 = list()
        rasterLink1 = list()

        # Para cada offset existente, caso seja possível, procura por uma ligação entre as duas linhas de raster.
        for indexOffset in range(len(O)):
            offset = O[indexOffset]

            for index in range(len(offset)):
                if index == 0:
                    indexPrev = len(offset) - 1
                else:
                    indexPrev = index - 1

                A = offset[indexPrev]
                B = offset[index]

                # Caso seja possível, procura pelos dois pontos (e quais offsets pertencem) que os pontos p de cada linha se encontra entre.
                if allowedRasterLink0:
                    if verify_point_line(A, B, PR1[0]):
                        rasterLink0.append(['PR1', indexOffset, indexPrev, index])

                    if verify_point_line(A, B, PR2[0]):
                        rasterLink0.append(['PR2', indexOffset, indexPrev, index])
                
                # Caso seja possível, procura pelos dois pontos (e quais offsets pertencem) que os pontos q de cada linha se encontra entre.
                if allowedRasterLink1:
                    if verify_point_line(A, B, PR1[1]):
                        rasterLink1.append(['PR1', indexOffset, indexPrev, index])
                    
                    if verify_point_line(A, B, PR2[1]):
                        rasterLink1.append(['PR2', indexOffset, indexPrev, index])

    # Cria os rasterLinks com base no que foi encontrado.
    rasterLink0 = create_rasterLink (rasterLink0, O, PR1[0], PR2[0], parameters)
    rasterLink1 = create_rasterLink (rasterLink1, O, PR1[1], PR2[1], parameters)

    return rasterLink0, rasterLink1

def create_rasterLink (rasterLink, O, p, q, parameters):
    '''
        Recebe uma lista com as interseções encontradas entre as linhas de raster/offsets e 
        verifica se existe um raster link. Caso exista, retorna os raster links encontrados.
        
        Um rasterLink é composto por: 
            rasterLink[0] - tempo total.
            rasterLink[1] - lista de pontos que o compõe.
    '''
    # Verifica se existe mais de uma interseção entre os segmentos de offsets e as linhas de raster.
    if len(rasterLink) > 1: 
        # Verifica se todas as interseções encontradas acontecem com o mesmo offset.
        if rasterLink[0][1] == rasterLink[1][1]: 
            # Verifica se os dois pontos das linhas de raster estão entre o mesmo par de pontos do offset.
            if rasterLink[0][2] == rasterLink[1][2] and rasterLink[0][3] == rasterLink[1][3]: 
                return [extrude_time(calculate_distance(p, q), parameters), [p, q]]
            
            # Verifica se existe um ponto compartilhado entre os pares de pontos do offset.
            elif rasterLink[0][2] == rasterLink[1][3]:
                aux = O[rasterLink[0][1]][rasterLink[0][2]]
                return [extrude_time(calculate_distance(p, aux), parameters) + extrude_time(calculate_distance(aux, q), parameters), [p, aux, q]]
            
            elif rasterLink[0][3] == rasterLink[1][2]:
                aux = O[rasterLink[0][1]][rasterLink[0][3]]
                return [extrude_time(calculate_distance(p, aux), parameters) + extrude_time(calculate_distance(aux, q), parameters), [p, aux, q]]
            
            # Verifica se os pares são compostos por pontos sequentes.
            elif ((rasterLink[0][3] + 1) == rasterLink[1][2]) or ((rasterLink[0][3] == len(O[rasterLink[0][1]]) - 1) and (rasterLink[1][2] == 0)):
                if rasterLink[0][0] == 'PR1':
                    aux1 = O[rasterLink[0][1]][rasterLink[0][3]]
                    aux2 = O[rasterLink[0][1]][rasterLink[1][2]]
                else:
                    aux1 = O[rasterLink[0][1]][rasterLink[1][2]]
                    aux2 = O[rasterLink[0][1]][rasterLink[0][3]]
                return [extrude_time(calculate_distance(p, aux1), parameters) + extrude_time(calculate_distance(aux1, aux2), parameters) + extrude_time(calculate_distance(aux2, q), parameters), [p, aux1, aux2, q]]

            elif ((rasterLink[1][3] + 1) == rasterLink[0][2]) or ((rasterLink[1][3] == len(O[rasterLink[0][1]]) - 1) and (rasterLink[0][2] == 0)):
                if rasterLink[0][0] == 'PR1':
                    aux1 = O[rasterLink[0][1]][rasterLink[1][3]]
                    aux2 = O[rasterLink[0][1]][rasterLink[0][2]]
                else:
                    aux1 = O[rasterLink[0][1]][rasterLink[0][2]]
                    aux2 = O[rasterLink[0][1]][rasterLink[1][3]]
                return [extrude_time(calculate_distance(p, aux1), parameters) + extrude_time(calculate_distance(aux1, aux2), parameters) + extrude_time(calculate_distance(aux2, q), parameters), [p, aux1, aux2, q]]

            # Casos em que existem mais pontos no raster link que liga as duas linhas.
            # Cria um raster link pelo lado que precisa de menos pontos para realizar a ligação.
            else:
                indexRasterA = list()
                indexRasterB = list()
                
                if rasterLink[0][3] > rasterLink[1][3] or rasterLink[0][3] == 0:
                    dA = rasterLink[0][2] - rasterLink[1][3] - 1
                    indexRasterA.append([rasterLink[0][0], rasterLink[0][2]])
                    indexRasterA.append([rasterLink[1][0], rasterLink[1][3]])
                    indexRasterB.append([rasterLink[0][0], rasterLink[0][3]])
                    indexRasterB.append([rasterLink[1][0], rasterLink[1][2]])

                else:
                    dA = rasterLink[1][2] - rasterLink[0][3] - 1
                    indexRasterA.append([rasterLink[1][0], rasterLink[1][2]])
                    indexRasterA.append([rasterLink[0][0], rasterLink[0][3]])
                    indexRasterB.append([rasterLink[1][0], rasterLink[1][3]])
                    indexRasterB.append([rasterLink[0][0], rasterLink[0][2]])

                dB = len(O[rasterLink[0][1]]) - dA - 4

                indexBegin, indexEnd, i = find_index(dA, indexRasterA, dB, indexRasterB)

                tTotal = 0
                rasterLinkPoints = list()
                
                pPrev = p
                rasterLinkPoints.append(p)

                for n in range(indexBegin + i, indexEnd, i):
                    point = O[rasterLink[0][1]][n % len(O[rasterLink[0][1]])]
                    rasterLinkPoints.append(point)
                    tTotal += extrude_time(calculate_distance(pPrev, point), parameters)
                    pPrev = point

                rasterLinkPoints.append(q)
                tTotal += extrude_time(calculate_distance(pPrev, q), parameters)
                return [tTotal, rasterLinkPoints]

    return None

def sameLine (R, PR1, PR2):
    '''
        Verifica se existe uma linha de raster na mesma altura que o raster 2,
        impossibilitando a realização de uma ligação direta entre o raster 1 e o raster 2.
    '''
    x1 = min(PR1[0], PR2[0])
    x2 = max(PR1[0], PR2[0])
    y2 = PR2[1]

    for r in R:
        p1 = r['p'][0][0]
        p2 = r['p'][1][0]
        yr = r['p'][0][1]
        if isEqual(yr, y2, 0.01):
            if x1 < p1 and p1 < x2:
                return False
            if x1 < p2 and p2 < x2:
                return False
    return True

def verify_point_line (A, B, p):
    '''
        Verifica se o ponto p se encontra no segmento de reta delimitados pelos pontos A e B.
    '''
    if isEqual(A[0], p[0], 0.01): # Verifica se os pontos A e p são o mesmo.
        if isEqual(A[1], p[1], 0.01): 
            return True

    if isEqual(B[0], p[0], 0.01): # Verifica se os pontos B e p são o mesmo.
        if isEqual(B[1], p[1], 0.01): 
            return True

    if isEqual(A[0], B[0], 0.01): # Verifica se a reta é vertical (possui o coeficiente angular de 90°).
        if isEqual(A[0], p[0], 0.01): # Verifica se o ponto p está na mesma reta que os pontos A e B.
            if p[1] > min(A[1], B[1]) and p[1] < max(A[1], B[1]): # Verifica se o ponto p está entre os pontos A e B.
                return True

    else:
        coefAngular = (B[1] - A[1]) / (B[0] - A[0])

        if isEqual((p[1] - A[1]), coefAngular*(p[0] - A[0]), 0.01): # Verifica se o ponto p está na mesma reta que os pontos A e B.
            if p[0] > min(A[0], B[0]) and p[0] < max(A[0], B[0]):  # Verifica se o ponto p está entre os pontos A e B no eixo X.
                if p[1] > min(A[1], B[1]) and p[1] < max(A[1], B[1]):  # Verifica se o ponto p está entre os pontos A e B no eixo Y.
                    return True

    return False

def find_index(dA, indexRasterA, dB, indexRasterB):
    '''
        Define os índices que serão utilizados para percorrer o offset, selecionando os pontos que irão criar um raster link.
        (O raster link sempre vai do raster 1 para o raster 2.)
    '''
    indexBegin = 0
    indexEnd = 0
    i = 1

    if dB > dA:
        # Verifica qual das posições pertencem ao raster 1.
        if indexRasterA[0][0] == 'PR1': 
            iP1 = 0
        else:
            iP1 = 1
        
        # Verifica qual o sentido que será percorido.
        if indexRasterA[iP1][1] > indexRasterA[1 - iP1][1]:
            i = -1
        else:
            i = 1
        
        indexBegin = indexRasterA[iP1][1]
        indexEnd = indexRasterA[1 - iP1][1]

    else:
        # Verifica qual das posições pertencem ao raster 1.
        if indexRasterB[0][0] == 'PR1':
            iP1 = 0
        else:
            iP1 = 1
        
        # Verifica qual o sentido que será percorido.
        if indexRasterB[iP1][1] > indexRasterB[1 - iP1][1]:
            i = 1
        else:
            i = -1
        
        indexBegin = indexRasterB[iP1][1]
        indexEnd = indexRasterB[1 - iP1][1]

    return indexBegin, indexEnd, i

#################################### NOVOS BLOCOS.
def split_blocks(R, parameters): 
    '''
        Divide os blocos existentes com base na quantidade
        de sides de entrada e saída que uma linha de raster possui.
    '''
    # Para cada bloco existente.
    totalOriginal = parameters['group'] + 1
    for i in range(0, totalOriginal):
        swap_later = False
        group = i
      
        for r in R:
            # Cria um novo bloco.
            if swap_later == True:
                swap_later = False
                group = parameters['group'] + 1

            # Verifica se a linha de raster pertencem ao bloco analisado.
            if r['group'] == i:
                input_lines = 0
                output_lines = 0

                # Verifica se existe mais de um side de entrada ou de saída.
                if len(r['links'][0]) > 1 or len(r['links'][1]) > 1:
                    # Contabiliza o número de sides de entrada o raster possui.
                    for j in r['links'][0]:
                        if(r['p'][0][1] > j[0][1]):
                            input_lines += 1
                        else:
                            output_lines += 1
                    
                    # Contabiliza o número de sides de saída o raster possui.
                    for j in r['links'][1]:
                        if(r['p'][0][1] > j[0][1]):
                            input_lines += 1
                        else:
                            output_lines += 1
                
                    '''
                        Verifica se o raster em questão se "dividi" ou é a "união" de outros rasters.
                        -- Mais de um side de entrada indica a "união" de rasters anteriores, ou seja, 
                        um novo bloco será iniciado.
                        -- Mais de um side de saída indica a "divisão" do raster analisado, ou seja, 
                        os próximos rasters que tenham o raster atual como side iniciarão novos blocos.
                    '''
                    # Caso exista mais de um side de entrada, o bloco é alterado nessa iteração.
                    if input_lines > 1:
                        group = parameters['group'] + 1

                    # Caso exista mais de um side de saída, o bloco é alterado na próxima iteração.
                    if output_lines > 1:
                        swap_later = True

                r['group'] = group
                
                if r['group'] > parameters['group']:
                    parameters['group'] = r['group']
    return

def limit_blocks(R, parameters):
    '''
        Divide os blocos existentes com base na quantidade 
        máxima de linhas de raster permitidas em cada bloco.
    '''
    for i in range(0, parameters['group'] + 1):
        group = i
        lines = 0

        for r in R:
            if r['group'] == i:
                if lines < parameters['maxLine']:
                    lines = lines + 1
                else:
                    lines = 1
                    parameters['group'] = parameters['group'] + 1
                    group = parameters['group']

                r['group'] = group

def check_delta (R, G, parameters):
    '''
        Verifica se todos os blocos possuem como tempo total um valor menor que delta.
        Caso encontre algum que ultrapssse, divide o bloco.
    '''
    checkChange = False # Indica que um novo bloco foi criado.

    for group in range(len(G)):
        checkDelta = False # Verifica se o tempo total do bloco analisado ultrapassou o valor de delta.
        g = G[group]

        ''' 
            Verifica se o tempo total do grupo é maior que delta E
            se esse grupo é composto por mais de uma linha. 
        '''
        if g['totalTime'] > parameters['delta'] and len(g) > 2: 
            for i in range(len(g)-1):
                r = R[list(g)[i]]

                if (r['Tfirst'] + r['e']) > parameters['delta'] and not checkDelta:
                    parameters['group'] += 1
                    checkDelta = True
                    checkChange = True
                    
                if checkDelta: # Caso o tempo do bloco tenha ultrapassado o valor de delta, atualiza o bloco da linha.
                    r['group'] = parameters['group']

    return checkChange

def delete_rasterLink (R):
    '''
        Exclui raster links entre linhas de raster de blocos diferentes.

        ***A principio, a função era utilizada quando um bloco era dividido,
        mas para permitir que novos blocos sejam criados a partir dos blocos
        originais, essa função não é mais utilizada.
    '''
    for r in R:
        for edge in range(2):
            for link in r['links'][edge]:
                R1 = link[0][3]
                R2 = link[0][5]
                if R1['group'] != R2['group']:
                    link[2] = None
                    link[3] = None

#################################### VERIFICAR MELHOR DELTA POSSÍVEL.
def find_cooling_h2 (R, parameters):
    '''
        Procura o melhor caso de "maior resfriamento" para todos pares de linhas de raster vizinhas.
        (Considerando a heurística 2).
    '''
    max_cooling = 0

    for R1 in R:
        for edge in range(2):
            links1 = R1['links'][edge]

            for j1 in range(len(links1)):
                link1 = links1[j1]
                side = link1[0]

                tR1 = list()
                tR1.append(link1[1])
                tR1.append(R1['e'] - link1[1])

                if edge == 0:
                    R2 = side[3]
                    j2 = side[4]
                    assert side[5] == R1
                    assert side[6] == j1

                else:
                    R2 = side[5]
                    j2 = side[6]
                    assert side[3] == R1
                    assert side[4] == j1
                
                link2 = R2['links'][1-edge][j2]
                assert link2[0] == side

                tR2 = list()
                tR2.append(link2[1])
                tR2.append(R2['e'] - link2[1])

                Cool = list()
                '''
                    [0]: rbit1 = 0 | rbit2 = 0
                    [1]: rbit1 = 0 | rbit2 = 1
                    [2]: rbit1 = 1 | rbit2 = 0
                    [3]: rbit1 = 1 | rbit2 = 1
                '''

                # Verifica se existe um raster link que realiza a ligação entre R1 e R2 pelos pontos "q" de ambos.
                if link1[3] == None:
                    Cool.append(tR1[1] + tR2[1] + air_time(calculate_distance(R1['p'][1], R2['p'][1]), parameters))
                else:
                    Cool.append(tR1[1] + tR2[1] + link1[3][0])

                Cool.append(tR1[1] + tR2[0] + air_time(calculate_distance(R1['p'][1], R2['p'][0]), parameters))
                Cool.append(tR1[0] + tR2[1] + air_time(calculate_distance(R1['p'][0], R2['p'][1]), parameters))

                # Verifica se existe um raster link que realiza a ligação entre R1 e R2 pelos pontos "p" de ambos.
                if link1[2] == None:
                    Cool.append(tR1[0] + tR2[0] + air_time(calculate_distance(R1['p'][0], R2['p'][0]), parameters))
                else:
                    Cool.append(tR1[0] + tR2[0] + link1[2][0])

                max_cooling = max(max_cooling, min(Cool))

    return max_cooling

def find_cooling_h3 (R, G, parameters):
    '''
        Procura o melhor caso de "maior resfriamento" para todos pares de linhas de raster vizinhas.
        (Considerando a heurística 3).
    '''
    max_cooling = 0

    for R1 in R:
        for edge in range(2):
            links1 = R1['links'][edge]

            for j1 in range(len(links1)):
                link1 = links1[j1]
                side = link1[0]

                tR1 = list()
                tR1.append(link1[1])
                tR1.append(R1['e'] - link1[1])

                if edge == 0:
                    R2 = side[3]
                    j2 = side[4]
                    assert side[5] == R1
                    assert side[6] == j1

                else:
                    R2 = side[5]
                    j2 = side[6]
                    assert side[3] == R1
                    assert side[4] == j1
                
                link2 = R2['links'][1-edge][j2]
                assert link2[0] == side

                tR2 = list()
                tR2.append(link2[1])
                tR2.append(R2['e'] - link2[1])

                Cool = list()

                if R1['group'] == R2['group']:
                    '''
                        Caso {R1} e {R2} sejam do mesmo grupo, é necessário considerar 
                        o tempo do meio até o final da linha de raster (considerando seu 
                        sentido) e a diferença entre o tempo de {R1} até {R2}.
                    '''
                    indexR1 = G[R1['group']][R1['sid']]
                    indexR2 = G[R1['group']][R2['sid']]

                    if indexR1 < indexR2:
                        Tmove = R2['Tfirst'] - R1['Tfirst'] - R1['e']
                    else:
                        Tmove = R1['Tfirst'] - R2['Tfirst'] - R2['e']

                    Cool = tR1[1-R1['rbitoriginal']] + tR2[1-R2['rbitoriginal']] + Tmove
                    max_cooling = max(max_cooling, Cool)

                else:
                    '''
                        Cool:
                            [0]: rbit1 = 0 | rbit2 = 0
                            [1]: rbit1 = 0 | rbit2 = 1
                            [2]: rbit1 = 1 | rbit2 = 0
                            [3]: rbit1 = 1 | rbit2 = 1
                    '''

                    R1F = R[list(G[R1['group']])[0]]
                    R1L = R[list(G[R1['group']])[-2]]
                    R2F = R[list(G[R2['group']])[0]]
                    R2L = R[list(G[R2['group']])[-2]] 
                    
                    '''
                        Verifica se existe um raster link que realiza a ligação entre R1 e R2 pelos pontos "q" de ambos e se é possível realizar essa ligação.
                        CONDIÇÕES:
                            RX ser início de um trecho de raster e seu rbit ser 1, permitindo que o ponto "q" realize ligações com outros blocos.
                            RY ser final de um trecho de raster e seu rbit ser 0, permitindo que o ponto "q" realize ligações com outros blocos.
                    '''
                    if (link1[3] != None) and (((R1['first'] and R1['rbit'] == 1) and (R2['last'] and R2['rbit'] == 0)) or (R2['first'] and R2['rbit'] == 1) and (R1['last'] and R1['rbit'] == 0)):
                        Tmove11 = link1[3][0]
                    else:
                        Tmove11 = air_time(calculate_distance(R1F['p'][R1F['rbitoriginal']], R2F['p'][R2F['rbitoriginal']]), parameters)

                    '''
                        Verifica se existe um raster link que realiza a ligação entre R1 e R2 pelos pontos "p" de ambos e se é possível realizar essa ligação.
                        CONDIÇÕES:
                            RX ser início de um trecho de raster e seu rbit ser 0, permitindo que o ponto "p" realize ligações com outros blocos.
                            RY ser final de um trecho de raster e seu rbit ser 1, permitindo que o ponto "p" realize ligações com outros blocos.
                    '''                        
                    if (link1[2] != None) and (((R1['first'] and R1['rbit'] == 0) and (R2['last'] and R2['rbit'] == 1)) or (R2['first'] and R2['rbit'] == 0) and (R1['last'] and R1['rbit'] == 1)):
                        Tmove00 = link1[2][0]
                    else:
                        Tmove00 = air_time(calculate_distance(R1L['p'][1-R1F['rbitoriginal']], R2L['p'][1-R2F['rbitoriginal']]), parameters)

                    Cool.append(tR1[1] + tR2[1] + Tmove11 + R1['Tlast'] + R2['Tfirst'])
                    Cool.append(tR1[1] + tR2[0] + air_time(calculate_distance(R1F['p'][R1F['rbitoriginal']], R2L['p'][1-R2F['rbitoriginal']]), parameters) + R1['Tlast'] + R2['Tlast'])
                    Cool.append(tR1[0] + tR2[1] + air_time(calculate_distance(R1L['p'][1-R1F['rbitoriginal']], R2F['p'][R2F['rbitoriginal']]), parameters) + R1['Tfirst'] + R2['Tfirst'])
                    Cool.append(tR1[0] + tR2[0] + Tmove00 + R1['Tfirst'] + R2['Tlast'])

                    max_cooling = max(max_cooling, min(Cool))
    
    return max_cooling

#################################### LEITURA DE ARQUIVOS.
def read_config():
    '''
        Abre o arquivo de configuração e realiza a leitura das informações 
        necessárias para executar o algoritmo.
    '''
    parameters = dict()

    with open('config.py', 'r', encoding="ISO-8859-1") as f:
        for line in f:
            if 'Z Axis Acceleration:' in line:
                parameters['z_acceleration'] = float(line.replace('Z Axis Acceleration:', ""))

            elif 'Acceleration:' in line:
                parameters['acceleration'] = float(line.replace('Acceleration:', ""))


            elif 'Angle:' in line:
                parameters['angle'] = float(line.replace('Angle:', ""))

            elif 'Filling Speed:' in line:
                line = line.replace('Filling Speed:', "")
                parameters['filling_speed'] = float(line.replace('Filling Speed:', ""))
                parameters['filling_dist'] = accelerationDistance(parameters['filling_speed'], parameters['acceleration'])
                parameters['filling_time'] = accelerationTime(parameters['filling_speed'], parameters['acceleration'])
            
            elif 'Travel Speed:' in line:
                parameters['travel_speed'] = float(line.replace('Travel Speed:', ""))
                parameters['travel_dist'] = accelerationDistance(parameters['travel_speed'], parameters['acceleration'])
                parameters['travel_time'] = accelerationTime(parameters['travel_speed'], parameters['acceleration'])
            
            elif 'Z Axis Speed:' in line:
                # Por enquanto este parametro representa o tempo gasto para retrair/extrair o filamento antes/depois de realizar o reposicionamento.
                parameters['z_speed'] = float(line.replace('Z Axis Speed:', ""))
                parameters['z_time'] = 2/40#accelerationTime(parameters['z_speed'], parameters['z_acceleration'])

            elif 'Filament Diamenter:' in line:
                parameters['filamentDiamenter'] = float(line.replace('Filament Diamenter:', ""))

            elif 'Extrusion Temperature:' in line:
                parameters['temperature'] = int(line.replace('Extrusion Temperature:', ""))

            elif 'Thickness:' in line:
                parameters['thickness'] = float(line.replace('Thickness:', ""))

            elif 'Road Width:' in line:
                parameters['width'] = float(line.replace('Road Width:', ""))
            
            elif 'Raster/Road Gap:' in line:
                parameters['gap'] = float(line.replace('Raster/Road Gap:', ""))
            

            elif 'Heuristic:' in line:
                parameters['heuristic'] = int(line.replace('Heuristic:', ""))

            elif 'Delta:' in line:
                parameters['delta'] = float(line.replace('Delta:', ""))

            elif 'Split Blocks:' in line:
                if 'Y' in line:
                    parameters['splitBlocks'] = True
                else:
                    parameters['splitBlocks'] = False

            elif 'Block Time Limit:' in line:
                if 'Y' in line:
                    parameters['limitTime'] = True
                else:
                    parameters['limitTime'] = False

            elif 'Block Lines Limit:' in line:
                if 'Y' in line:
                    parameters['limitBlocks'] = True
                else:
                    parameters['limitBlocks'] = False

            elif 'Number Lines Blocks:' in line:
                parameters['maxLine'] = int(line.replace('Number Lines Blocks:', ""))


            elif 'Sides:' in line:
                if 'Y' in line:
                    parameters['sides'] = True
                else:
                    parameters['sides'] = False

            elif 'Air Jump:' in line:
                if 'Y' in line:
                    parameters['airJump'] = True
                else:
                    parameters['airJump'] = False

            elif 'Raster Link:' in line:
                if 'Y' in line:
                    parameters['rasterLink'] = True
                else:
                    parameters['rasterLink'] = False

            elif 'Begin Point:' in line:
                if 'Y' in line:
                    parameters['beginPoint'] = True
                else:
                    parameters['beginPoint'] = False

            elif 'Block Number:' in line:
                if 'Y' in line:
                    parameters['printBlock'] = True
                else:
                    parameters['printBlock'] = False

            elif 'Raster Number:' in line:
                if 'Y' in line:
                    parameters['printRaster'] = True
                else:
                    parameters['printRaster'] = False


            elif 'Input:' in line:
                if 'Y' in line:
                    parameters['input'] = True
                else:
                    parameters['input'] = False

            elif 'Debug:' in line:
                if 'Y' in line:
                    parameters['debug'] = True
                else:
                    parameters['debug'] = False

            elif 'PNG:' in line:
                if 'Y' in line:
                    parameters['png'] = True
                else:
                    parameters['png'] = False

            elif 'TEX:' in line:
                if 'Y' in line:
                    parameters['tex'] = True
                else:
                    parameters['tex'] = False

            elif 'LOG:' in line:
                if 'Y' in line:
                    parameters['log'] = True
                else:
                    parameters['log'] = False

            elif 'GCODE:' in line:
                if 'Y' in line:
                    parameters['gcode'] = True
                else:
                    parameters['gcode'] = False

            elif 'CSV:' in line:
                if 'Y' in line:
                    parameters['csv'] = True
                else:
                    parameters['csv'] = False

    return parameters

def read_offset (filename, parameters):
    '''
        Abre o arquivo de entrada, realiza a leitura dos pontos que 
        compõem os offsets da camada e cria um dicionário com eles.
        (Os offsets são utilizados para criar raster links).
    '''
    O = None

    with open(filename, 'r', encoding="ISO-8859-1") as f:
        for line in f:
            if line.strip() and line[0] != '#':
                if line[0] == 'Q': # Linha do arquivo de entrada que indica o número de offsets existentes na camada.
                    O = [None]*int(line[1:])

                elif line[0] == 'O':
                    o = line[1:].split(",")

                    p_x = rotate_x(float(o[1]), float(o[2]), parameters['angle'])
                    p_y = rotate_y(float(o[1]), float(o[2]), parameters['angle'])

                    p = (p_x, p_y)

                    if(O[int(o[0])] == None): # Verifica se já existe uma lista para o offset em questão.
                        O[int(o[0])] = list()

                    O[int(o[0])].append(p)
    return O

def read_raster (filename, parameters):
    '''
        Abre o arquivo de entrada, realiza a leitura das linhas de 
        raster e cria um dicionário com elas.
    '''

    parameters['group'] = 0 # Indica a quantidade de blocos existentes.

    with open(filename, 'r', encoding="ISO-8859-1") as f:
        for line in f:
            if line.strip() and line[0] != '#':

                if line[0] == 'N':
                    R = [None]*int(line[1:])

                elif line[0] == 'R': # Adiciona uma nova linha de raster.
                    r = line[1:].split(",")

                    p_x = rotate_x(float(r[1]), float(r[2]), parameters['angle'])
                    p_y = rotate_y(float(r[1]), float(r[2]), parameters['angle'])

                    q_x = rotate_x(float(r[3]), float(r[4]), parameters['angle'])
                    q_y = rotate_y(float(r[3]), float(r[4]), parameters['angle'])

                    if p_y != q_y: # Verifica se existe divergância entre os valores de y (arredondamento).
                        if(p_y > q_y):
                            q_y = p_y
                        else:
                            p_y = q_y

                    if p_x > q_x: # Verifica se o sentido dos pontos é da "esquerda para direita".
                        x_aux = q_x
                        q_x = p_x
                        p_x = x_aux

                    p = (p_x, p_y)
                    q = (q_x, q_y)

                    if parameters['heuristic'] == 3:
                        rbit = int(r[5])
                    else:
                        rbit = 0

                    # Cria uma nova linha de raster. 
                    R[int(r[0])] = create_stroke(int(r[0]), p, q, parameters['width'], rbit, int(r[6]), parameters)

                    if parameters['group'] < int(r[6]): # Verifica se o bloco atual é o maior.
                        parameters['group'] = int(r[6])

    return R

def read_sides (filename, parameters, R):
    '''
        Abre o arquivo de entrada, realiza a leitura dos trechos 
        adjacentes e atualiza o dicionário de linhas de raster.
    '''
    newFile = False
    O = None

    with open(filename, 'r', encoding="ISO-8859-1") as f:
        for line in f:
            if line.strip() and line[0] != '#':
                if line[0] == 'L': #Adiciona um novo trecho adjacente.
                    s = line[1:].split(",")

                    raster1 = R[int(s[0].replace('L', ''))]
                    raster2 = R[int(s[1].replace('L', ''))]

                    if parameters['heuristic'] == 1 or (parameters['heuristic'] == 2 and not parameters['rasterLink']):
                        # A heurística 1 e a heurística 2 sem raster link não precisam de raster links.
                        rasterLink0 = None
                        rasterLink1 = None

                    elif parameters['heuristic'] == 2 or parameters['heuristic'] == 3:
                        # A heurística 2 com raster link precisa de todos os raster links possíveis.
                        if len(s) == 2: # Verifica se o arquivo já possui informação sobre os raster links.
                            if not newFile:
                                newFile = True
                                O = read_offset(filename, parameters)
                            rasterLink0, rasterLink1 = find_rasterLink (raster1['p'], raster2['p'], O, R, parameters)
                        else:
                            rasterLink0 = read_rasterLink(s[2])
                            rasterLink1 = read_rasterLink(s[3])

                    add_side(R[int(s[0].replace('L', ''))], R[int(s[1].replace('L', ''))], rasterLink0, rasterLink1, parameters)

    '''
        Caso o arquivo ainda não contenha informações sobre os raster links,
        cria um novo com as informações necessárias.
    '''
    if newFile:
        new_input_file(parameters, R)

def read_rasterLink (link):
    '''
        Retira as informações necessárias sobre um raster link da string recebida.
    '''
    if 'None' in link:
        rasterLink = None
        
    else:
        aux = link.split(';')
        rasterLinkAux = list()

        for index in range(1, len(aux)):
            p = aux[index].split('&')
            rasterLinkAux.append((float(p[0]), float(p[1])))
    
        rasterLink = [float(aux[0]), rasterLinkAux]

    return rasterLink

#################################### CRIAÇÃO DE ARQUIVO DE ENTRADA.
def create_link (rasterLink):
    '''
        Caso exista, cria uma string contendo informações sobre um raster link.
    '''
    link = 'None'

    if rasterLink != None:
        link = str(rasterLink[0]) + ';' + str(rasterLink[1]).replace(', (', '(')
        link = link.replace(', ', '&')
        link = link.replace(')(', ';')
        link = link.replace('][', '/')
        link = link.replace('(', '')
        link = link.replace(')', '')
        link = link.replace('[', '')
        link = link.replace(']', '')

    return link

def new_input_file (parameters, R):
    '''
        Cria um novo arquivo de entrada contendo os possíveis raster links que ligam duas linhas de raster vizinhas.
    '''
    fileInput = './INPUT/' + parameters['filename'] + '.txt'
    fileOutput = fileInput.replace('INPUT', 'INPUT - V2')

    if not os.path.exists('./INPUT - V2'):
        os.makedirs('./INPUT - V2')

    out = sys.stdout

    with open(fileInput, 'r', encoding="ISO-8859-1") as fI:
        with open(fileOutput, 'w') as fO:
            sys.stdout = fO 
            for line in fI:
                if line[0] != 'L' and line[0] != 'O':
                    if '###' in line and not ('OFFSET' in line): # Comentários.
                        print(line, end = '')
                    elif '\n' == line: # Linhas em branco.
                        print(line, end = '')

                    elif '- N' in line or '- Rasters s' in line or 'N' == line[0] or 'R' == line[0]: # Informações sobre os raster.
                        print(line, end = '')
                    
                    elif '- K' in line or '- Contornos' in line or 'K' == line[0] or 'C' == line[0]: # Informações sobre os contornos.
                        print(line, end = '')

                    elif '- Rasters a' in line: # Altera o comentário sobre as linhas que descrevem raster adjacentes.
                        print('# - Rasters adjacentes são descritos através dos índices de ambos, raster link pelo ponto p, raster link pelo ponto q e bit que indica quais pontos são ligados quando está dentro de um bloco.')

                    elif 'LA' in line: # Altera o comentário sobre as linhas que descrevem raster adjacentes.
                        print('#    LA,LB,RL1,RL2,RBIT')

                elif line[0] == 'L': # Atualiza as informações os raster adjacentes, adicionando informações sobre os raster links.
                    s = line[1:].split(",L")

                    R1 = R[int(s[0])]
                    R2 = R[int(s[1])]

                    rasterLink0 = None
                    rasterLink1 = None

                    for edge in range(2):
                        for side in R1['links'][edge]:   
                            if (side[0][3]['sid'] == R1['sid'] and side[0][5]['sid'] == R2['sid']) or (side[0][3]['sid'] == R2['sid'] and side[0][5]['sid'] == R1['sid']):
                                if side[2] != None:
                                    rasterLink0 = side[2]
                                
                                if side[3] != None:
                                    rasterLink1 = side[3]

                    link0 = create_link (rasterLink0)
                    link1 = create_link (rasterLink1)

                    newLine = line.replace('\n', '') + ',' +  link0 + ',' + link1 + '\n'
                    print(newLine, end = '')
    
    sys.stdout = out