from math import log
from Outils.Moteur_de_jeu import Plateau
from Outils.Moteur_de_jeu.Plateau import *



BASE_REFERENCE = 62     # base utilisées par toutes les fonctions ici


def tri_a_bulle(tab) :
    n = len(tab)

    for i in range(n - 1) :
        for j in range(n - 1) :
            if tab[j] > tab[j + 1] :
                (tab[j],tab[j + 1]) = (tab[j + 1],tab[j])



def insertion_place(tab, x, p) :
    # Insère x à l'indice p, sans tenir compte de l'ordre
    tab.append(x)

    for i in range(len(tab) - 1, p, -1) :
        (tab[i],tab[i - 1]) = (tab[i - 1], tab[i])



def insertion_ordonnee(tab, x) :
    tab.append(x)
    i = len(tab) - 1

    while tab[i] < tab[i - 1] and i > 0:
        (tab[i],tab[i - 1]) = (tab[i - 1], tab[i])
        i -= 1



def recherche(tab, e) :
    """ Recherche d'élément dans une tableau par dichotomie. Retourne un couple (booléen, indice) """
    a = 0
    b = len(tab) - 1

    if b == -1 :
        return (False, 0)

    if tab[0] >= e :
        return (tab[0] == e, 0)
    elif tab[b] == e :
        return (True, b)
    elif tab[b] < e :
        return (False, b + 1)
    
    c = 1
    while b - a > 1 :
        c = (a + b)//2

        if tab[c] == e :
            return (True, c)
        elif tab[c] < e :
            a = c
        else :
            b = c


    if tab[c] == e :
        return (True,c)
    else :
        if tab[c] < e :
            return (False, c + 1)
        else :
            return (False, c)




def conversion_base(x, bf) :
    """
        Convertit l'entier naturel x exprimée en base 10 dans la base bf
    """
    if x  == 0 :
        return "0"
    
    chiffres = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    s = ""

    for n in range(int(log(x,bf)), -1, -1) :
        s += chiffres[x//(bf**n)]
        x = x % bf**n

    return s



def retour_base_10(s, bi) :
    """
        Convertit le nombre s exprimée en base bi dans la base 10
    """
    chiffres = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

    x = 0
    n = len(s)
    
    for k in range(n) :
        x += chiffres.find(s[n - 1 - k]) * bi**k

    return x
        
    
    
        


def code_from_barriere(b) :
    """
        Concatène les données relatives à la barrière sous la forme x,y,o
        2 = v et 1 = h
        Convertit ensuite ce nombre en base 62
    """

    if b.orientation == "h" :
        n = 100*b.x + 10*b.y + 1
    else :
        n = 100*b.x + 10*b.y + 2

    return conversion_base(n, BASE_REFERENCE)

    
    

def code_from_plateau(plateau) :
    """
        Retourne l'entier associée au plateau
        Structure : b1o,b1x,b1y ; ... ; bno,bnx,bny ; x0,y0,b0 ; x1,y1,b1 ; t
        Les bio valent 1 si la barrière est horizontale et 2 sinon

        Ce nombre est ensuite converti en base 62, tout en classant les barrières dans l'ordre croissant.
    """    


    s = conversion_base(10**8 * plateau.pions[1][0] + 10**7 * plateau.pions[1][1] + 10**5 * plateau.barrieres_restantes[1] +\
                        10**4 * plateau.pions[0][0] + 10**3 * plateau.pions[0][1] + 10 * plateau.barrieres_restantes[0] +\
                        plateau.tour, 62)

        
    codes_barrieres = [code_from_barriere(b) for b in plateau.liste_barrieres]
    tri_a_bulle(codes_barrieres)

    for b in codes_barrieres :
        s = b + s
    return s





def coup_from_str(s) :
    x = int(s[2])
    y = int(s[4])

    if s[0] == "M" :
        return Coup("M", case = (x,y))
    else :
        return Coup("B", barriere = Barriere(s[6], x, y))






def code_from_str(s) :
    x = int(s[2])
    y = int(s[4])

    if s[0] == "M" :
        n = 100*x + 10*y + 2
    else :
        n = 100*x + 10*y

        if s[6] == "h" :
            n +=  1

    return conversion_base(n, BASE_REFERENCE)





def code_from_coup(coup) :
    if coup.type == "M" :
        n = 100 * coup.case[0] + 10 * coup.case[1] + 2
    else :
        n = 100 * coup.barriere.x + 10 * coup.barriere.y

        if coup.barriere.orientation == "h" :
            n += 1

    return conversion_base(n, BASE_REFERENCE)



def coup_from_code(code) :
    n = retour_base_10(code, BASE_REFERENCE)
    info = n%10
    x = n//100
    y = (n - 100*x)//10


    if info == 2 :
        return Coup("M", case = (x,y))
    else :
        return Coup("B", barriere = Barriere(["v","h"][info], x, y))
    
 



"""coup = coup_from_str("B_4_5_h")
print(coup.type, coup.barriere.x, coup.barriere.y, coup.barriere.orientation)

coup = coup_from_str("M_4_5")
print(coup.type, coup.case[0], coup.case[1])
"""



"""from random import shuffle
p = Plateau(9,9,10)
l = [Barriere("h",4,6), Barriere("h",2,6), Barriere("h",5,1), Barriere("h",3,2)]
l = []
shuffle(l)
for b in l :
    p.executer_coup(Coup("B", barriere = b))

print(code_from_plateau(p))
print(code_from_str("M_5_0"))
print(coup_from_code("86").get_code())"""

"""p = Plateau(9,9,10)
p.executer_coup(Coup("B", barriere = Barriere("h",4,6)))
p.executer_coup(Coup("B", barriere = Barriere("h",3,2)))
print(code_from_plateau(p))


p = Plateau(9,9,10)
p.executer_coup(Coup("B", barriere = Barriere("h",3,2)))
p.executer_coup(Coup("B", barriere = Barriere("h",4,6)))
print(code_from_plateau(p))"""



"""l = [4,9,4,57,547,5647,567,7,87,7,8]
insertion_place(l, 0, 7)
insertion_place(l, -1, 45)
print(l)"""