from init_input import *

verbose = False

############################## CRIAÇÃO DO FRONT.
def get_initial_front_0 (R):
    '''
        Retorna uma lista que contém apenas a primeira linha de raster contida em R. 
        Caso já tenha sido considerada na solução, verifica se existe alguma linha
        de raster que ainda não foi considerada na solução e a retorna, caso exista.
    '''
    if R[0]['Tini'] == None:
        return [R[0]]
    
    else:
        for r in R:
            if r['Tini'] == None:
                return [r]
        return None

def get_initial_front_N (R):
    '''
        Retorna uma lista que contém apenas a última linha de raster contida em R. 
        Caso já tenha sido considerada na solução, verifica se existe alguma linha
        de raster que ainda não foi considerada na solução e a retorna, caso exista.
    '''
    if R[len(R)-1]['Tini'] == None:
        return [R[len(R)-1]]
    
    else:
        for r in R:
            if r['Tini'] == None:
                return [r]
        return None

def get_initial_front_fringe (R):
    '''
        Retorna uma lista que contém todas as linhas de raster que não possuem 
        entradas e/ou saídas e ainda não foram consideradas na solução.
    '''
    L = [].copy()

    for Rk in R:
        inputs = Rk['links'][0]
        outputs = Rk['links'][1]
        if len(inputs) == 0 or len(outputs) == 0 and Rk['Tini'] == None:
            L.append (Rk)

    if len(L) > 0:
        return L
    else:
        return None

def get_initial_front_all (R):
    '''
        Retorna uma lista que contém todas as linhas de raster que 
        não foram consideradas na solução.
    '''
    L = [].copy()

    for Rk in R:
        if Rk['Tini'] == None:
            L.append(Rk)

    if len(L) > 0:
        return L
    else:
        return None

############################## ATUALIZAR FRONT.
def update_front_h2 (Front, Rk):
    '''
        Removes the stroke {Rk} from the {Front} and adds all
        output strokes of {Rk} that are not yet on the {Front}. 
        Returns the updated {Front}.
    '''
    NewFront = [].copy()

    for Fk in Front:
        if Fk['sid'] != Rk['sid']:
            NewFront.append (Fk)

    for edge in range(2):
        for linki in Rk['links'][edge]:
            sidei = linki[0]

            if edge == 0:
                Rl = sidei[3]
                assert sidei[5] == Rk
            else:
                Rl = sidei[5]
                assert sidei[3] == Rk

            if Rl not in NewFront and Rl['Tini'] == None:
                NewFront.append (Rl)

    return NewFront

def update_front_h3 (Front, Rk, G, R):
    '''
        Cria um novo front {newFront} contendo todas as linhas de raters que
        ainda não foram adicionadas à solução. Adiciona também todas as linhas
        de raster que são vizinhas de {Rk} (entradas ou saídas) e ainda não 
        foram adicionadas na solução. Caso uma linha de raster vizinha não 
        seja uma das bordas de seu bloco, adiciona as linhas de raster da borda
        do bloco, caso ainda não estejam no {Front}.
    '''
    NewFront = [].copy()

    for Fk in Front:
        if Fk['sid'] != Rk['sid']:
            NewFront.append (Fk)

    for edge in range(2):
        for linki in Rk['links'][edge]:
            sidei = linki[0]

            if edge == 0:
                Rl = sidei[3]
                assert sidei[5] == Rk
            else:
                Rl = sidei[5]
                assert sidei[3] == Rk

            if Rl not in NewFront and Rl['Tini'] == None:
                NewFront.append (Rl)
                if Rl['group'] != Rk['group']: # Verifica se a nova linha adicionada é do mesmo grupo de Rk.
                    if not Rl['first'] and not Rl['last']: # Verifica se ela é início ou final.
                        Rb = R[list(G[Rl['group']])[0]]
                        if Rb not in NewFront and Rb['Tini'] == None:
                            NewFront.append (Rb)
                        Re = R[list(G[Rl['group']])[-2]]
                        if Re not in NewFront and Re['Tini'] == None:
                            NewFront.append (Re)
    return NewFront

############################## EXCLUIR CANDIDATO.
def exclude_bad_candidates (qend, Tend, Cands, Front, Delta, ind, parameters):
    '''
        Excludes from the list {Cands} every candidate which, if it was
        stroked next, would cause some half-covered side to exceed the
        max allowed cooling time {Delta}. Assumes that all half-covered sides
        are inputs or outputs of strokes in the {Front}. Assumes also that the nozzle
        is currently at {qend} and the current time is {Tend}. {Cands} is a list of triples
        {(R, rbit, tmove)} where {R} is a stroke that has not been extruded yet and has {R['rbit']=0},
        and {rbit} is a 0 or 1, and {tmove} is the air time from {qend} to the start of the candidate.
    '''
    indx = ' ' * ind

    if verbose: sys.stderr.write ('%s### enter exclude_bad_candidates (Tend: %.6f): \n' % (indx, Tend))

    if qend == None:
        if verbose: sys.stderr.write ('%s### exiting exclude_bad_candidates (trivial) \n' % indx)
        return Cands.copy()

    NewCands = [].copy()

    for Ck in Cands:
        assert len(Ck) == 3

        Rk = Ck[0]
        rbitk = Ck[1]

        if check_candidate (Ck, qend, Tend, Rk, rbitk, Front, Delta, ind, parameters):
            NewCands.append(Ck)

    if verbose: sys.stderr.write ('%s### exiting exclude_bad_candidates (eliminated %d) \n' % (indx, len(Cands) - len(NewCands)))
    return NewCands

def exclude_bad_candidates_group (Rend, R, G, Cands, Front, Delta, ind, parameters):
    '''
        Excludes from the list {Cands} every candidate which, if it was
        stroked next, would cause some half-covered side to exceed the
        max allowed cooling time {Delta}. Assumes that all half-covered sides
        are inputs or outputs of strokes in the {Front}. Assumes also that the nozzle
        is currently at {qend} and the current time is {Tend}. {Cands} is a list of triples
        {(R, rbit, tmove)} where {R} is a stroke that has not been extruded yet and has {R['rbit']=0},
        and {rbit} is a 0 or 1, and {tmove} is the air time from {qend} to the start of the candidate.
    '''
    indx = ' ' * ind

    if verbose: sys.stderr.write ('%s### enter exclude_bad_candidates (Tend: %.6f): \n' % (indx, Tend))

    if Rend == None:
        if verbose: sys.stderr.write ('%s### exiting exclude_bad_candidates (trivial) \n' % indx)
        return Cands.copy()

    NewCands = [].copy()

    for Ck in Cands:
        assert len(Ck) == 3

        Rk = Ck[0]
        rbitk = Ck[1]

        if check_candidate_group (Rend, R, G, Ck, Rk, rbitk, Front, Delta, ind, parameters):
            NewCands.append(Ck)

    if verbose: sys.stderr.write ('%s### exiting exclude_bad_candidates (eliminated %d) \n' % (indx, len(Cands) - len(NewCands)))
    return NewCands

############################## ANALISAR CANDIDATO.
def check_candidate (Ck, qend, Tend, Rk, rbitk, Front, Delta, ind, parameters):
    '''
        Checks whether choosing candidate {Rk}
        in the direction {rbitk} for the next stroke would
        not immediately imply excessive cooling time for any side in the current cutset.
    '''
    indx = ' ' * ind

    if verbose:
        sys.stderr.write ('%s### enter check_candidate: \n' % indx)
        print_stroke (Rk, rbitk, 'Candidate Rk', ind) 

    assert Rk['rbit'] == 0

    pk = Rk['p'][rbitk]
    qk = Rk['p'][1-rbitk]
    Tendk = Tend + Ck[2] + Rk['e'] #air_time (calculate_distance(qend, pk), parameters) + Rk['e']

    for Rf in Front:
        if verbose: print_stroke (Rf, 0, 'Front Rf') 

        if Rf == Rk:
            Coolf = worst_cooling (Tend + Ck[2], Tend, Rk, rbitk, ind, parameters)

        else:
            rasterLink = None

            for edge in range(2):
                for side in Rk['links'][edge]:
                    if (side[0][3]['sid'] == Rk['sid'] and side[0][5]['sid'] == Rf['sid']) or (side[0][3]['sid'] == Rf['sid'] and side[0][5]['sid'] == Rk['sid']):
                        if side[2 + (1 - rbitk)] != None:
                            rasterLink = side[2 + (1 - rbitk)][0]

            if rasterLink == None:
                pf = Rf['p'][0]
                qf = Rf['p'][1]

                Tmove = Tendk + air_time (calculate_distance(qk, pf), parameters)
                Coolf0 = worst_cooling (Tmove, Tendk, Rf, 0, ind, parameters) 

                Tmove = Tendk + air_time (calculate_distance(qk, qf), parameters)
                Coolf1 = worst_cooling (Tmove, Tendk, Rf, 1, ind, parameters) 

                Coolf = min (Coolf0, Coolf1)

            else:
                pf = Rf['p'][rbitk]
                Tmove = Tendk + air_time (calculate_distance(qk, pf), parameters)
                Coolf0 = worst_cooling (Tmove, Tendk,  Rf, rbitk, ind, parameters) 

                Tmove = Tendk + rasterLink
                Coolf1 = worst_cooling (Tmove, Tendk,  Rf, 1-rbitk, ind, parameters) 

                Coolf = min (Coolf0, Coolf1)

        if Coolf > Delta:
            sys.stderr.write ('%scooling time exceeded for candidate R%03d:%d (Tend: %.6f) between R%03d and some neighbor: %.6f\n' % (indx, Rk['sid'], rbitk, Tendk, Rf['sid'], Coolf)) 
            if verbose: sys.stderr.write ('%s### exiting check_candidate (false) \n' % indx)
            return False

    if verbose: sys.stderr.write ('%s### exiting check_candidate (true) \n' % indx)
   
    return True  

def check_candidate_group (Rend, R, G, Ck, Rk, rbitk, Front, Delta, ind, parameters):
    '''
        Checks whether choosing candidate {Rk}
        in the direction {rbitk} for the next stroke would
        not immediately imply excessive cooling time for any side in the current cutset.
    '''
    indx = ' ' * ind

    if verbose:
        sys.stderr.write ('%s### enter check_candidate: \n' % indx)
        print_stroke (Rk, rbitk, 'Candidate Rk', ind) 

   #assert Rk['rbit'] == 0

    qend = Rend['p'][1-Rend['rbit']]
    Tend = Rend['Tend']

    pk = Rk['p'][rbitk]
    qk = Rk['p'][1-rbitk]

    # Tempo para chegar ao final de {Rk}.
    Tendk = Tend + Ck[2] + Rk['e']

    for Rf in Front:
        if verbose: print_stroke (Rf, 0, 'Front Rf') 

        if Rf == Rk:
            Coolf = worst_cooling (Tend + Ck[2], Tend, Rk, rbitk, ind, parameters)

        elif Rf['group'] == Rk['group']:
            '''
                Caso {Rk} e {Rf} pertençam ao mesmo grupo, só é necessário 
                adicionar o tempo do raster link entre eles.
            '''

            indexRk = G[Rk['group']][Rk['sid']]
            indexRf = G[Rk['group']][Rf['sid']]

            if indexRk < indexRf:
                Tmove = Rf['Tfirst'] - Rk['Tfirst'] - Rk['e']
            else:
                Tmove = Rk['Tfirst'] - Rf['Tfirst'] - Rf['e']

            Tmove += Tendk
            Coolf = worst_cooling (Tmove, Tendk,  Rf, 1-rbitk, ind, parameters) 
        
        else:
            '''
                Caso os grupos sejam diferentes, é necessário considerar o tempo
                para finalizar o bloco de {Rk}, o tempo de reposicionamento e o 
                tempo para atingir a linha {Rf} em seu bloco.
            '''
            # Tempo para finalizar o bloco que {Rk} pertence.
            if Rk['first'] and Rk['last']: # Se o bloco de {Rk} só contém ele mesmo.
                Tendb = 0
            
            elif Rk['rbitoriginal'] == rbitk: # Se {Rk} está indo em direção ao final do bloco.
                Tendb = Rk['Tlast']
                rb = R[list(G[Rk['group']])[-2]]
                rbitb = 1-rb['rbitoriginal']
                qk = rb['p'][rbitb]

            elif Rk['rbitoriginal'] == 1 - rbitk: # Se {Rk} está indo em direção ao início do bloco.
                Tendb = Rk['Tfirst']
                rb = R[list(G[Rk['group']])[0]]
                rbitb = rb['rbitoriginal']
                qk = rb['p'][rbitb]


            if Rf['first'] and Rf['last']:
                '''
                    Caso {Rf} esteja em um bloco sozinho, pode ser considerado como uma linha.
                    Não exite tempo para chegar nele e pode ser iniciado por qualquer lado.
                '''
                pf = Rf['p'][0]
                qf = Rf['p'][1]

                Tmove = Tendk + Tendb + air_time (calculate_distance(qk, pf), parameters)
                Coolf0 = worst_cooling (Tmove, Tendk, Rf, 0, ind, parameters)

                Tmove = Tendk + Tendb + air_time (calculate_distance(qk, qf), parameters)
                Coolf1 = worst_cooling (Tmove, Tendk, Rf, 1, ind, parameters) 

                Coolf = min (Coolf0, Coolf1)
            
            else:
                '''
                    Caso {Rf} pertença à um bloco com mais de uma linha, é necessário considerar o tempo 
                    para chegar até ele por cada uma das bordas do bloco.
                '''
                r = R[list(G[Rk['group']])[0]]
                rbit = r['rbitoriginal']
                pf = r['p'][rbit]
                
                Tmove = Tendk + Tendb + air_time (calculate_distance(qk, pf), parameters) + Rf['Tfirst']
                Coolfb = worst_cooling (Tmove, Tendk, Rf, rbit, ind, parameters)

                r = R[list(G[Rk['group']])[-2]]
                rbit = 1-r['rbitoriginal']
                pf = r['p'][rbit]
                
                Tmove = Tendk + Tendb + air_time (calculate_distance(qk, pf), parameters) + Rf['Tlast']
                Coolfe = worst_cooling (Tmove, Tendk, Rf, rbit, ind, parameters)

                Coolf = min(Coolfb, Coolfe)

        if Coolf > Delta:
            sys.stderr.write ('%scooling time exceeded for candidate R%03d:%d (Tend: %.6f) between R%03d and some neighbor: %.6f\n' % (indx, Rk['sid'], rbitk, Tendk, Rf['sid'], Coolf)) 
            if verbose: sys.stderr.write ('%s### exiting check_candidate (false) \n' % indx)
            return False

    if verbose: sys.stderr.write ('%s### exiting check_candidate (true) \n' % indx)
   
    return True  

############################## ORDENAR CANDIDATO.  
def sort_candidates_none (qend, Cands):
    '''
        Sorts the candidate list based on air time from {qend} to the starting point.
        Returns the sorted list.
    '''
    return Cands.copy()    

def sort_candidates_dist (qend, Cands):
    '''
        Sorts the candidate list based on air time from {qend} to the starting point.
        Returns the sorted list.
    '''
    return(sorted(Cands, key = lambda x: x[2]))    

def sort_candidates_raster (qend, Cands):
    '''
        Sorts the candidate list based on Y with ties broken by X.
        Returns the sorted list.
    '''
    return(sorted(Cands, key = lambda Ck: raster_order(Ck[0])+1000000*Ck[1]))    

############################## MAIOR RESFRIAMENTO.
def worst_cooling (Tmove, Tend, Rf, rbitf, ind, parameters):
    '''
        Assumes that the nozzle is currently at {qend} and
        the current time is {Tend}. Enumerates the sides of 
        the front stroke {Rf} that have been already half-covered
        and computes their cooling times, assuming that {Rf} will
        be extruded in the direction {rbitf}. Returns the largest 
        of those cooling times.
    '''
    indx = ' ' * ind

    if verbose: 
        sys.stderr.write ('%s### enter worst_cooling (Tend: %.6f) \n' % (indx, Tend))
        print_stroke (Rf, rbitf, 'Rf', ind)

    Coolmax = 0
    ef = Rf['e']

    for edge in range(2):
        linksf = Rf['links'][edge]
        for jf in range(len(linksf)):
            linkfj = linksf[jf]
            side = linkfj[0]
            if edge == 0:
                Ra = side[3]  
                ja = side[4]
                assert side[5] == Rf
                assert side[6] == jf
            else:
                Ra = side[5]  
                ja = side[6]
                assert side[3] == Rf
                assert side[4] == jf
            
            if Ra['Tini'] != None:
                linkaj = Ra['links'][1-edge][ja]
                rbita = Ra['rbit']
                ea = Ra['e']

                if verbose: print_stroke (Ra, 0, 'Ra', ind + 2)

                if rbitf == 0: 
                    Tfj = Tmove + linkfj[1]
                else: 
                    Tfj = Tmove + (ef - linkfj[1])

                if rbita == 0: 
                    Taj = Ra['Tini'] + linkaj[1] 
                else: 
                    Taj = Ra['Tini'] + (ea - linkaj[1])
            
                if verbose: sys.stderr.write ('Ra[Tini]: %.6f, Taj: %.6f, Tend: %.6f, Tfj: %.6f\n' % (Ra['Tini'], Taj, Tend, Tfj))   

                assert Taj < Tfj
                assert Taj < Tend
                assert Tend < Tfj

                Coolj = Tfj - Taj

                if Coolj > Coolmax:
                    Coolmax = Coolj

    if verbose:
        sys.stderr.write ('%sCoolmax: %.6f\n' % (indx, Coolmax))   
        sys.stderr.write ('%s### exiting worst_cooling \n' % indx)

    return Coolmax         

def worst_cooling_one (Rk):
    '''
    Computes the worst cooling time for the sides of a stroke {Rk} that
    has just been added to the solution list. Returns the worst cooling time
    {Cmax} and the corresponding side {smax}.
    '''
    assert Rk['Tini'] != None
    Cmax = 0
    smax = None
    ek = Rk['e']
    for edge in range(2): 
      linksk = Rk['links'][edge]
      for ik in range(len(linksk)):
        linkik = linksk[ik]
        side = linkik[0]
        if Rk['rbit'] == 0:
           Tik = Rk['Tini'] + linkik[1]
        else:  
           Tik = Rk['Tini'] + (ek - linkik[1])
        if edge == 0:
          Rl = side[3]
          jl = side[4]
          assert side[5] == Rk
          assert side[6] == ik
        else:
          Rl = side[5]
          jl = side[6]
          assert side[3] == Rk
          assert side[4] == ik
        linkjl = Rl['links'][1-edge][jl]
        assert linkjl[0] == side
        if Rl['Tini'] != None:
           if Rl['rbit'] == 0: 
               Tjl = Rl['Tini'] + linkjl[1]
           else:    
               Tjl = Rl['Tini'] + (Rl['e'] - linkjl[1])
           Cooljk = Tik - Tjl #cooling time of segment 
           if Cooljk > Cmax:
              Cmax = Cooljk
              smax = side
    return Cmax, smax

############################## HEURÍSTICA 1 / SCAN LINE ORDER.
def scan_line_order (R, parameters):
    '''
        Returns the optimal order {S} of the strokes according to heurist 1,
        and also the total extrusion time {Tend} of {S} and also the maximum cooling
        time {Cmax} for any side, and the corresponding side {smax}. For now we assume that the input strokes are given 
        in the proper order: bottom to top rows, and left to right within each row.
        It does not extrude the raster links for now.
    '''

    Tend = 0
    Cmax = 0
    smax = None
    qend = None
    for k in range(len(R)):
        Rk = R[k]
        assert Rk['rbit'] == 0
        pk = Rk['p'][0]
        qk = Rk['p'][1]
        ek = Rk['e']
        if k > 0:
           Tini = Tend + air_time (calculate_distance(qend, pk), parameters)
        else:
           Tini = 0
        Rk['Tini'] = Tini
        Tend = Tini + ek
        Rk['Tend'] = Tend
        qend = qk
        #Analise todas as entradas de Rk para ver o resfriamento delas.
        #Ou seja, se vou extrudar o Rk, significa que os caras que eu 
        #extrudei antes estao resfriando, entao veja o tempo desses caras.
        #Por isso que usa o Rk['links'][0] -> entradas
        #O Rk['links'][1] -> saidas
        #         0   1   2   3   4   5   6
        #side = (xm, ym, xl, R1, j1, R2, i2)
        for ik in range(len(Rk['links'][0])):
            linkik = Rk['links'][0][ik]
            side = linkik[0]
            Tik = Tini + linkik[1]
            Rl = side[3]
            jl = side[4]
            assert side[5] == Rk
            assert side[6] == ik
            assert Rl['rbit'] == 0
            linkjl = Rl['links'][1][jl]
            assert linkjl[0] == side
            Tjl = Rl['Tini'] + linkjl[1]
            Ck = Tik - Tjl #cooling time of segment
            if Ck > Cmax:
                Cmax = Ck
                smax = side
    return R, Tend, Cmax, smax

############################## HEURÍSTICA 2 / GREEDY SELECTION - LINES (WITHOUT RASTER LINK).
def greedy_selection_lines_withoutRL (R, Delta, parameters, start_time):
    '''
    Returns the optimal order {S} of the strokes according to heuristic 2,
    with maximum allowed cooling {Delta}, and also the total extrusion time {Tend} of {S} and also the maximum cooling
    time {Cmax} for any side, and the corresponding side {smax}. 
    It does not extrude the raster links for now. Each element of {S} is a pair (stroke, reversebit).

    The solution will start with stroke R[0] and each new stroke will be adjacent at least one previously extruded
    stroke. Uses backtracking.
    '''
    S_end = [].copy()
    T_end = None
    Cmax_end = 0
    smax_end = 0
    

    while True:
        Front = get_initial_front_0 (R)
        #Front = get_initial_front_N (R)
        #Front = get_initial_front_fringe (R)
        #Front = get_initial_front_all (R)

        if Front != None:
            S_end, Cmax, smax = heuristic2R_aux_withoutRL (S_end, Front, Delta, parameters, start_time)

            if S_end == None or S_end == -3:
                T_end = None
                break
            else:
                T_end = S_end[len(S_end)-1]['Tend']
            if Cmax > Cmax_end:
                Cmax_end = Cmax
                smax_end = smax
        else:
            break      
    
    return S_end, T_end, Cmax_end, smax_end

def heuristic2R_aux_withoutRL (S, Front, Delta, parameters, start_time):
    '''
      Given a partial solution {S} for the stroke order optimization problem, and
      the corresponding list of {Front} strokes tries to complete it into a full
      solution {Sfull}. If it succeds returns the {Sfull}, the maximum cooling time
      {Cmax} among the new strokes added, and the corresponding side {smax}. If it fails returns None in place of
      {Sfull}. Assumes that the {Front} has at least one stroke in each component of the connectivity graph that
      has not been yet completey extruded.
    '''
    ind = 2 * len(S)
    indx = ' ' * ind

    if len(Front) == 0:
        return S, 0, None

    N = len(S)
    if N == 0:
        Tend = 0
        qend = None
    else:
        Tend = S[len(S)-1]['Tend']
        rbitend = S[len(S)-1]['rbit']
        qend = S[len(S)-1]['p'][1-rbitend]

    Cands = [].copy() #List of pairs (stroke, reversebit) 

    for i in range(len(Front)):
        assert Front[i]['rbit'] == 0

        Cands.append((Front[i], 0, air_time(calculate_distance(qend, Front[i]['p'][0]), parameters)))
        Cands.append((Front[i], 1, air_time(calculate_distance(qend, Front[i]['p'][1]), parameters)))

    
    Cands = exclude_bad_candidates (qend, Tend, Cands, Front, Delta, ind, parameters, start_time)
    #Cands = sort_candidates_raster (qend, Cands)
    Cands = sort_candidates_dist (qend, Cands)
    #Cands = sort_candidates_none (qend, Cands)

    if len(S) == 99999:
        print_cands (Cands, ind)
        sys.exit()

    #if (time.time() - start_time) > 3600:
    #   return -3, 0, 0

    for k in range(len(Cands)):
        Ck = Cands[k]
        Rk = Ck[0]
        assert Rk['rbit'] == 0
        rbitk = Ck[1]
        pk = Rk['p'][rbitk]
        qk = Rk['p'][1-rbitk]
        ek = Rk['e']
        assert Rk['Tini'] == None
        assert Rk['Tend'] == None

        if qend != None:
            Tinik = Tend + Ck[2]#air_time (calculate_distance(qend, pk), parameters)
        else:
            Tinik = 0

        Rk['Tini'] = Tinik
        Tendk = Tinik + ek
        Rk['Tend'] = Tendk
        qend = qk
        Rk['rbit'] = rbitk
        S.append(Rk)

        if verbose:
           sys.stderr.write("%s---------------------------------------------\n" % indx)
           print_stroke (Rk, 0, 'appended', ind)
           sys.stderr.write("%s---------------------------------------------\n" % indx)
        else:
           sys.stderr.write("%sappended R%03d:%d, Tini = %.6f, Tend = %.6f \n" % (indx, Rk['sid'], Rk['rbit'], Rk['Tini'], Rk['Tend']))
        
        Cmax_k, smax_k = worst_cooling_one (Rk)
        NewFront = update_front_h2 (Front, Rk)
        S_rec, Cmax_rec, smax_rec = heuristic2R_aux_withRL (S, NewFront, Delta, parameters)

        if S_rec != None:
            if Cmax_rec > Cmax_k:
                return S_rec, Cmax_rec, smax_rec
            else:
                return S_rec, Cmax_k, smax_k
        else:
            Rk['rbit'] = 0
            Rk['Tini'] = None
            Rk['Tend'] = None
            S.pop()

            if verbose:
               sys.stderr.write("%s---------------------------------------------\n" % indx)
               print_stroke (Rk, rbitk, 'deleted', ind)
               sys.stderr.write("%s---------------------------------------------\n" % indx)
            else:
               sys.stderr.write("%sdeleted R%03d:%d \n" % (indx, Rk['sid'], rbitk))

    sys.stderr.write("%s**FAILED\n" % indx)
    return None, None, None

############################## HEURÍSTICA 2 / GREEDY SELECTION - LINES (WITH RASTER LINK).
def greedy_selection_lines_withRL (R, Delta, parameters, start_time):
    '''
    Returns the optimal order {S} of the strokes according to heuristic 2,
    with maximum allowed cooling {Delta}, and also the total extrusion time {Tend} of {S} and also the maximum cooling
    time {Cmax} for any side, and the corresponding side {smax}. 
    It does not extrude the raster links for now. Each element of {S} is a pair (stroke, reversebit).

    The solution will start with stroke R[0] and each new stroke will be adjacent at least one previously extruded
    stroke. Uses backtracking.
    '''
    S_end = [].copy()
    T_end = None
    Cmax_end = 0
    smax_end = 0

    while True:
        Front = get_initial_front_0 (R)
        #Front = get_initial_front_N (R)
        #Front = get_initial_front_fringe (R)
        #Front = get_initial_front_all (R)

        if Front != None:
            S_end, Cmax, smax = heuristic2R_aux_withRL (S_end, Front, Delta, parameters, start_time)

            if S_end == None or S_end == -3:
                T_end = None
                break
            else:
                T_end = S_end[len(S_end)-1]['Tend']
            if Cmax > Cmax_end:
                Cmax_end = Cmax
                smax_end = smax
        else:
            break      
    
    return S_end, T_end, Cmax_end, smax_end

def heuristic2R_aux_withRL (S, Front, Delta, parameters, start_time):
    '''
      Given a partial solution {S} for the stroke order optimization problem, and
      the corresponding list of {Front} strokes tries to complete it into a full
      solution {Sfull}. If it succeds returns the {Sfull}, the maximum cooling time
      {Cmax} among the new strokes added, and the corresponding side {smax}. If it fails returns None in place of
      {Sfull}. Assumes that the {Front} has at least one stroke in each component of the connectivity graph that
      has not been yet completey extruded.
    '''
    ind = 2 * len(S)
    indx = ' ' * ind

    if len(Front) == 0:
        return S, 0, None

    N = len(S)
    if N == 0:
        Tend = 0
        qend = None
    else:
        Tend = S[len(S)-1]['Tend']
        rbitend = S[len(S)-1]['rbit']
        qend = S[len(S)-1]['p'][1-rbitend]

    Cands = [].copy() #List of pairs (stroke, reversebit) 

    for i in range(len(Front)):
        assert Front[i]['rbit'] == 0

        rasterLink = None

        if len(S) > 0:
            for edge in range(2):
                R1 = S[len(S)-1]
                R2 = Front[i]
                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 + (1 - R1['rbit'])] != None:
                            rasterLink = side[2 + (1 - R1['rbit'])][0]
                            Cands.append((Front[i], (1 - R1['rbit']), rasterLink))
                            Cands.append((Front[i], (R1['rbit']), air_time(calculate_distance(qend, Front[i]['p'][(R1['rbit'])]), parameters)))

        if rasterLink == None:                        
            Cands.append((Front[i], 0, air_time(calculate_distance(qend, Front[i]['p'][0]), parameters)))
            Cands.append((Front[i], 1, air_time(calculate_distance(qend, Front[i]['p'][1]), parameters)))

    Cands = exclude_bad_candidates (qend, Tend, Cands, Front, Delta, ind, parameters)
    #Cands = sort_candidates_raster (qend, Cands)
    Cands = sort_candidates_dist (qend, Cands)
    #Cands = sort_candidates_none (qend, Cands)

    if len(S) == 99999:
        print_cands (Cands, ind)
        sys.exit()

    #if (time.time() - start_time) > 3600:
    #   return -3, 0, 0

    for k in range(len(Cands)):
        Ck = Cands[k]
        Rk = Ck[0]
        assert Rk['rbit'] == 0
        rbitk = Ck[1]
        pk = Rk['p'][rbitk]
        qk = Rk['p'][1-rbitk]
        ek = Rk['e']
        assert Rk['Tini'] == None
        assert Rk['Tend'] == None

        if qend != None:
            Tinik = Tend + Ck[2]#air_time (calculate_distance(qend, pk), parameters)
        else:
            Tinik = 0

        Rk['Tini'] = Tinik
        Tendk = Tinik + ek
        Rk['Tend'] = Tendk
        qend = qk
        Rk['rbit'] = rbitk
        S.append(Rk)

        if verbose:
           sys.stderr.write("%s---------------------------------------------\n" % indx)
           print_stroke (Rk, 0, 'appended', ind)
           sys.stderr.write("%s---------------------------------------------\n" % indx)
        else:
           sys.stderr.write("%sappended R%03d:%d, Tini = %.6f, Tend = %.6f \n" % (indx, Rk['sid'], Rk['rbit'], Rk['Tini'], Rk['Tend']))
        
        Cmax_k, smax_k = worst_cooling_one (Rk)
        NewFront = update_front_h2 (Front, Rk)
        S_rec, Cmax_rec, smax_rec = heuristic2R_aux_withRL (S, NewFront, Delta, parameters, start_time)

        if S_rec != None:
            if Cmax_rec > Cmax_k:
                return S_rec, Cmax_rec, smax_rec
            else:
                return S_rec, Cmax_k, smax_k
        else:
            Rk['rbit'] = 0
            Rk['Tini'] = None
            Rk['Tend'] = None
            S.pop()

            if verbose:
               sys.stderr.write("%s---------------------------------------------\n" % indx)
               print_stroke (Rk, rbitk, 'deleted', ind)
               sys.stderr.write("%s---------------------------------------------\n" % indx)
            else:
               sys.stderr.write("%sdeleted R%03d:%d \n" % (indx, Rk['sid'], rbitk))

    sys.stderr.write("%s**FAILED\n" % indx)
    return None, None, None

############################## HEURÍSTICA 3 / GREEDY SELECTION - BLOCKS.
def greedy_selection_blocks (R, G, Delta, parameters, start_time):
    '''
        Returns the optimal order {S} of the strokes according to heuristic 2,
        with maximum allowed cooling {Delta}, and also the total extrusion time {Tend} of {S} and also the maximum cooling
        time {Cmax} for any side, and the corresponding side {smax}. 
        It does not extrude the raster links for now. Each element of {S} is a pair (stroke, reversebit).

        The solution will start with stroke R[0] and each new stroke will be adjacent at least one previously extruded
        stroke. Uses backtracking.
    '''
    S_end = [].copy()
    T_end = None
    Cmax_end = 0
    smax_end = 0

    while True:
        Front = get_initial_front_0 (R)
        #Front = get_initial_front_N (R)
        #Front = get_initial_front_fringe (R)
        #Front = get_initial_front_all (R)

        if Front != None:
            S_end, Cmax, smax = heuristic3R_aux (S_end, Front, Delta, G, R, parameters, start_time)

            if S_end == None or S_end == -3:
                T_end = None
                break
            else:
                T_end = S_end[len(S_end)-1]['Tend']
            if Cmax > Cmax_end:
                Cmax_end = Cmax
                smax_end = smax
        else:
            break
    
    return S_end, T_end, Cmax_end, smax_end

def heuristic3R_aux (S, Front, Delta, G, R, parameters, start_time):
    '''
        Given a partial solution {S} for the stroke order optimization problem, and
        the corresponding list of {Front} strokes tries to complete it into a full
        solution {Sfull}. If it succeds returns the {Sfull}, the maximum cooling time
        {Cmax} among the new strokes added, and the corresponding side {smax}. If it fails returns None in place of
        {Sfull}. Assumes that the {Front} has at least one stroke in each component of the connectivity graph that
        has not been yet completey extruded.
    '''
    ind = 2 * len(S)
    indx = ' ' * ind

    if len(Front) == 0:
        return S, 0, None

    N = len(S)
    
    if N == 0:
        Rend = None
        Tend = 0
        qend = None
    else:
        Rend = S[len(S)-1]
        Tend = Rend['Tend']
        rbitend = Rend['rbit']
        qend = Rend['p'][1-rbitend]

    Cands = [].copy() #List of pairs (stroke, reversebit) 

    sameGroup = False # Variável utilizada para controlar a criação da lista candidatos {Cands}.

    '''
        Adiciona na lista de canditados {Cands} apenas as linhas de raster 
        que atendem as restrições impostas na heurística 3.
    '''
    for i in range(len(Front)):
        if not sameGroup: # Verifica se é autorizado adicionar novos candidatos à lista de candidatos {Cands}.
            assert Front[i]['Tini'] == None # Certifica-se que a linha de raster {Front[i]} ainda não foi visitada.

            rasterLink = None 

            if len(S) > 0: # Verifica se já existe alguma linha de raster adicionada na solução {S}.
                R1 = S[len(S)-1] # Última linha de raster adicionada à solução {S}.
                R2 = Front[i] # Linha de raster sendo analisada.
                '''
                    Caso a linha de raster sendo analisada pertença ao mesmo bloco que a última linha de 
                    raster adicionada na solução {S}, procura o raster link que realiza a ligação entre elas.
                '''
                if R1['group'] == R2['group'] or ((R2['first'] and R1['rbit'] == 1-R2['rbit'])or (R2['last'] and R1['rbit'] == R2['rbit'])): 
                    for edge in range(2):
                        R2 = Front[i]
                        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 + (1 - R1['rbit'])] != None:
                                    '''
                                        Como existe uma restrição que obriga que todas as linhas de raster de um bloco sejam visitadas em sequência
                                        (ou seja, ao entrar em um bloco só é possível sair do mesmo depois que todas suas linhas são adicionadas à solução {S}),
                                        quando existe uma linha de raster no {Front} que pertence ao mesmo bloco que a última linha adicionada à {S}, esta se
                                        torna a única opção viável para ser adicionada em seguida à solução.

                                        OBS: apenas o lado da linha de raster que possui uma ligação com a linha de raster anterior é adicionado à
                                        lista de candidatos.

                                        OBS2: caso existam duas linhas de raster no {Front} do mesmo grupo que a última linha de raster adicionada
                                        em {S} pertence, apenas quem possui um raster link é adicionada aos candidatos.

                                        Nesse caso, a lista de candidatos é esvaziada, e apenas a linha de raster do mesmo bloco a compõe.
                                    '''
                                    if R1['group'] == R2['group']:
                                        sameGroup = True 
                                        Cands = [].copy()
                                    rasterLink = side[2 + (1 - R1['rbit'])][0]
                                    Cands.append((Front[i], 1 - R1['rbit'], rasterLink))
                                    if R2['first'] and R2['last']:
                                        '''
                                            No caso da linha de raster em questão pertencer à um bloco composto por uma única linha de raster,
                                            ou seja, {Front[i]} ser o início e o final do bloco ao mesmo tempo, é possível adicionar à lista de candidatos 
                                            os dois lados da linha de raster como entrada para o bloco.

                                        '''
                                        Cands.append((R2, R1['rbit'], air_time(calculate_distance(qend, R2['p'][R1['rbit']]), parameters)))

            '''
                Caso a linha de raster analisada {Front[i]} não pertença ao mesmo bloco que a última linha de raster adicionada à
                solução {S}, e {Front[i]} seja a primeira e/ou última linha de raster de outro bloco, ela pode ser adicionada à
                lista de candidatos {Cands}.
            '''
            if rasterLink == None and (Front[i]['first'] or Front[i]['last']): 
                '''
                    Caso {Front[i]} não esteja conectada diretamente com a última linha de raster adicionada em {S},
                    apenas linhas de raster que estão nas bordas de blocos podem entrar na lista de candidatos.
                '''
                Front[i]['rbit'] = Front[i]['rbitoriginal']
                
                if Front[i]['first'] and Front[i]['last']:
                    '''
                        No caso da linha de raster em questão pertencer à um bloco composto por uma única linha de raster,
                        ou seja, {Front[i]} ser o início e o final do bloco ao mesmo tempo, é possível adicionar à lista de candidatos 
                        os dois lados da linha de raster como entrada para o bloco.

                    '''
                    Cands.append((Front[i], 1-Front[i]['rbit'], air_time(calculate_distance(qend, Front[i]['p'][1-Front[i]['rbit']]), parameters)))

                elif Front[i]['last']:
                    '''
                        Caso a linha de raster seja o "final" de um bloco, é necessário inverter seu sentido 
                        antes de adicionar como candidata.
                    '''
                    Front[i]['rbit'] = 1-Front[i]['rbit']

                Cands.append((Front[i], Front[i]['rbit'], air_time(calculate_distance(qend, Front[i]['p'][Front[i]['rbit']]), parameters)))

    Cands = exclude_bad_candidates_group (Rend, R, G, Cands, Front, Delta, ind, parameters)
    #Cands = sort_candidates_raster (qend, Cands)
    Cands = sort_candidates_dist (qend, Cands)
    #Cands = sort_candidates_none (qend, Cands)

    if len(S) == 99999:
        print_cands (Cands, ind)
        sys.exit()
    
    if (time.time() - start_time) > 600:
       return -3, 0, 0

    for k in range(len(Cands)):
        Ck = Cands[k]
        Rk = Ck[0]

        #assert Rk['rbit'] == 0

        rbitk = Ck[1]
        pk = Rk['p'][rbitk]
        qk = Rk['p'][1-rbitk]
        ek = Rk['e']

        assert Rk['Tini'] == None
        assert Rk['Tend'] == None

        if qend != None:
            Tinik = Tend + Ck[2]#air_time (calculate_distance(qend, pk), parameters)
        else:
            Tinik = 0

        Rk['Tini'] = Tinik
        Tendk = Tinik + ek
        Rk['Tend'] = Tendk
        qend = qk
        Rk['rbit'] = rbitk
        S.append(Rk)

        if verbose:
           sys.stderr.write("%s---------------------------------------------\n" % indx)
           print_stroke (Rk, 0, 'appended', ind)
           sys.stderr.write("%s---------------------------------------------\n" % indx)
        else:
           sys.stderr.write("%sappended R%03d:%d, Tini = %.6f, Tend = %.6f \n" % (indx, Rk['sid'], Rk['rbit'], Rk['Tini'], Rk['Tend']))
        
        Cmax_k, smax_k = worst_cooling_one (Rk)
        NewFront = update_front_h3 (Front, Rk, G, R)
        S_rec, Cmax_rec, smax_rec = heuristic3R_aux (S, NewFront, Delta, G, R, parameters, start_time)

        if S_rec != None:
            if Cmax_rec > Cmax_k:
                return S_rec, Cmax_rec, smax_rec
            else:
                return S_rec, Cmax_k, smax_k
        else:
            Rk['rbit'] = Rk['rbitoriginal']
            Rk['Tini'] = None
            Rk['Tend'] = None
            S.pop()

            if verbose:
               sys.stderr.write("%s---------------------------------------------\n" % indx)
               print_stroke (Rk, rbitk, 'deleted', ind)
               sys.stderr.write("%s---------------------------------------------\n" % indx)
            else:
               sys.stderr.write("%sdeleted R%03d:%d \n" % (indx, Rk['sid'], rbitk))

    sys.stderr.write("%s**FAILED\n" % indx)
    return None, None, None