######################################
# RECUPERE LES PROBLEMES
######################################

def getProbleme(nom):
    # si on veut pb sokoban
    if nom == "sokoban":
        import probleme_sokoban
        return probleme_sokoban.Sokoban()

    # si on veut pb sokoban
    if nom == "sokoban_facile":
        import probleme_sokoban_facile
        return probleme_sokoban_facile.Sokoban()

    # si on veut pb sokoban
    if nom == "sokoban_dur":
        import probleme_sokoban_dur
        return probleme_sokoban_dur.Sokoban()

    # si on veut pb cafe
    if nom == "cafe":
        import probleme_cafe
        return probleme_cafe.Cafe()


######################################
# ALGO LEE AVEC LISTE OUVERTE
######################################

def calculDistance(probleme, etatDepart, PRINT = True):
    """
    effectue le calcul des distances en utilisant une liste ouverte
    - probleme : le probleme sur lequel on travaille
    - etatDepart : etat a partir calculer les distances (chainage avant)
    - PRINT : affichage du traitement (par defaut oui)
    """
    # utilise un dictionnaire pour stocker les distances
    # structure du dict [etat -> (distance du depart, parent, action)]
    distance={}

    # stocke etat d'arrivee à distance 0 sans parent ni action
    distance[etatDepart] = (0, "debut", "XXX")

    # liste ouverte : etats a explorer
    ouverte = [etatDepart]

    # gerer les numeros d'iteration (affichage)
    num = 0

    # tant qu'il reste des elements
    while len(ouverte)>0 :
        # get element
        # WARNING : pop(0) si on veut le fonctionnement d'une file
        #           sinon pop() prend en fin de liste
        etatADevelopper = ouverte.pop(0)

        # calcule la distance actuelle + 1
        nouvelleDistance = distance[etatADevelopper][0] + 1

        # pour chaque action possible
        for action in probleme.actions() :

            # etat d'arrivee (resultat de l'action)
            arrivee = probleme.transition(etatADevelopper,action)

            # si l'etat d'arrivee n'existe pas dans le dictionnaire
            if not arrivee in distance :
                # ajoute arrivee dans dictionnaire (et origine)
                distance[arrivee] = (nouvelleDistance, etatADevelopper, action)
                # ajoute a la liste comme nouvel etat a explorer
                ouverte.append(arrivee)

        # affiche la liste ouverte et le chemin parcouru a chaque iteration
        if PRINT :
            num = num + 1
            print ("")
            print ("--------------------iteration ",num,"--------------------")
            print (" * liste ouverte : ")
            print(ouverte)
            print (" * distance : ")
            print (distance)

    # fin retourner dictionnaire
    return distance


######################################
# CALCUL DU CHEMIN
######################################

def getChemin(distance, arrivee):
    """
    retourne le chemin a partir du dictionnaire construit
    - le dictionnaire de distance [ etat -> (distance, parent, action) ]
    """

    # on se place a l'arrivee et on va remonter le chemin
    chemin = [ (arrivee, "(fin)") ]
    etatCourant = arrivee

    # tant qu'on est pas au debut
    while not etatCourant == "debut" :
        # on remonte le temps
        # => cherche le parent et l'action qui a mene a cet etatCourant
        dist, parent, action = distance [ etatCourant ]

        # ajoute le parent et l'action au debut du le chemin
        chemin.insert(0,(parent,action))

        # met a jour etatCourant et on va chercher son antecedant à l'iteration suivante
        etatCourant = parent

    # fin retourne chemin
    return chemin


######################################
# EXECUTER CHEMIN
######################################

def executerChemin(pb, chem):
    """
    affiche le chemin a executer
    """

    # copie le chemin et retire le debut
    chemin = list(chem)
    chemin.pop(0)

    # numeroter les etapes pour l'affichage
    num_etape = 0

    # pour chaque etape du chemin
    for element in chemin:
        # recupere etat correspondant et l'action a effectuer
        etat, action = element
        num_etape = num_etape + 1

        # affiche etat
        print ("\n ** etat etape ", num_etape,"**")
        print (pb.toString(etat))
        # affiche action
        print ("\n **action ** ")
        print (action)



######################################
# MAIN
######################################

def main(probleme):
    """
    code appele par le __main__
    creer et dessine le probleme
    """

    # recuperer le probleme
    pb = getProbleme(probleme)

    # construire distances
    print("\n\n############# CONSTRUIRE DISTANCE ##############")
    distance = calculDistance(pb,pb.depart)

    # affiche le contenu du dictionnaire
    print ("\n\n#################### RESULTAT ################## ")
    print ("etat -> (distance,  etat parent, action qui mene du parent à etat )")
    print ("")
    for etat in distance:
        print (etat, " -> ", distance[etat])

    # creer chemin
    print("\n\n############# CONSTRUIRE CHEMIN ##############")
    chemin = getChemin(distance, pb.arrivee)
    print (chemin)

    print("\n\n############# EXECUTER CHEMIN ##############")
    executerChemin(pb, chemin)


######################################
# lancement du module python
######################################


if __name__ == "__main__":
    import sys

    # si pas d'argument, probleme cafe par defaut
    if len(sys.argv) == 1 :
        nomProbleme = "cafe"
    else :
        # sinon utilise argument
        nomProbleme = sys.argv[1]

    main(nomProbleme)