#! /usr/bin/env python3
# -*- coding: utf-8 -*-


from random import randint


"""
    Les algorithmes du programme de première :
    - savoir écrire ces méthodes en langage naturel
    - savoir les implémenter en langage Python
    - savoir faire fonctionner ces algorithmes sur des exemples
    - connaître leur complexité et savoir ce que cela signifie
    - savoir faire de ce fichier un module importable dans un autre programme python
"""


# fonction qui renvoie une liste de 'longueur' entiers aléatoires choisis entre 'debut' et 'fin' compris
def liste_entiers_aleatoires(debut : int, fin : int, longueur : int) -> list:

    assert isinstance(debut, int) and isinstance(fin, int) and isinstance(longueur, int)
    assert debut <= fin and longueur >= 1

    liste = []
    for entier in range(longueur):
        liste.append(randint(debut, fin))

    return liste


# même fonction simplifiée, sans les assertions sur les arguments
def random_integer_list(lower, upper, length) -> list:

    return [ randint(lower, upper) for _ in range(length) ]


# recherche naïve d'une occurence dans une liste non triée
def occurence(tableau : list, valeur : int) -> int:
    """
        la fonction renvoie la position de valeur dans tableau
        si la valeur est présente et -1 sinon
    """

    assert isintance(tableau, list) and isintance(valeur, int)

    for indice in range(len(tableau)):
        if tableau[indice] == valeur:

            return indice

    return -1


# fonction qui renvoie les indices des valeurs extrêmes d'une liste
def extremums(tableau : list) -> tuple:

    assert isinstance(tableau, list) and len(tableau)

    indice_mini = 0
    indice_maxi = 0

    for indice in range(1, len(tableau)):
        if tableau[indice] < tableau[indice_mini]:
            indice_mini = indice
        elif tableau[indice] > tableau[indice_maxi]:
            indice_maxi = indice

    return indice_mini, indice_maxi


# fonction de tri par insertion
def insertion(tableau : list):
    """
        la fonction trie la variable tableau dans l'ordre croissant
        en utilisant l'algorithme de tri par insertion
    """

    assert isinstance(tableau, list) and len(tableau)

    for i in range(1, len(tableau)):
        valeur = tableau[i]
        j = i
        while j > 0 and tableau[j-1] > valeur:
            tableau[j] = tableau[j-1]
            j = j - 1
        tableau[j] = valeur


# fonction de tri par sélection
def selection(tableau : list):
    """
        la fonction trie la variable tableau dans l'ordre croissant
        en utilisant l'algorithme de tri par sélection
    """

    assert isinstance(tableau, list) and len(tableau)

    for i in range(len(tableau) - 1):
        index_mini = i
        for j in range(i + 1, len(tableau)):
            if tableau[j] < tableau[index_mini]:
                index_mini = j
        if index_mini != i:
            tableau[index_mini], tableau[i] = tableau[i], tableau[index_mini]


# fonction de tri à bulle
def tri_bulle(tableau : list) -> tuple:
    """
        cette fonction renvoie un tuple composé de la liste triée et du nombre d'étapes nécessaires au tri
    """

    assert isinstance(tableau, list)

    nb_etapes = 0
    permutation = True
    passage = 0
    while permutation == True:
        permutation = False
        passage = passage + 1
        for en_cours in range(0, len(tableau) - passage):
            if tableau[en_cours] > tableau[en_cours + 1]:
                nb_etapes += 1
                permutation = True
                tableau[en_cours], tableau[en_cours + 1] = tableau[en_cours + 1], tableau[en_cours]

    return tableau, nb_etapes


# recherche dichotomique dans une liste triée
def recherche_dicho(tableau : list, valeur : int) -> tuple:

    assert isinstance(tableau, list) and isinstance(valeur, int)

    indice_mini = 0
    indice_maxi = len(tableau) - 1

    # la variable qui compte le nombre de boucles effectuées
    nb_etapes = 0

    while indice_mini <= indice_maxi:

        nb_etapes += 1

        # affichage de la liste dans laquelle la recherche est effectuée au début de chaque boucle
        # print(tableau[indice_mini : indice_maxi + 1])

        indice_milieu = (indice_mini + indice_maxi) // 2
        if tableau[indice_milieu] == valeur:

            return indice_milieu, nb_etapes

        elif tableau[indice_milieu] > valeur:
            indice_maxi = indice_milieu - 1
        else:
            indice_mini = indice_milieu + 1

    return -1, nb_etapes


# programme principal

if __name__ == "__main__":

    debut, fin, longueur = 0, 100, 32
    liste = liste_entiers_aleatoires(debut, fin, longueur)
    print("Liste initiale :\n\t", liste)
    print()
    # on affecte les deux valeurs du tuple renvoyé par la fonction tri_bulle() à deux variables distinctes
    liste_triee, nb_etapes_tri = tri_bulle(liste)
    print("Liste triée :\n\t", liste_triee)
    print("L'algorithme de tri a effectué", nb_etapes_tri, "étapes.")
    print()
    nombre_a_trouver = 73
    # on affecte les deux valeurs du tuple renvoyé par la fonction recherche_dico() à deux variables distinctes
    indice_a_trouver, nb_etapes_recherche = recherche_dicho(liste_triee, nombre_a_trouver)
    print("L'indice du nombre", nombre_a_trouver, "dans la liste est :", indice_a_trouver)
    print("L'algorithme de recherche a effectué", nb_etapes_recherche, "boucles.")

else:

    print("Le module pnsi_programmes_bases est utilisé !")