import math
import numpy as np

ALPHA = (math.sqrt(5) - 1) / 2
TAILLE_TABLE = 4500
def transforme_chaine_entier(ch):
    '''
        transforme_chaine_entier( chaine :str ) -> int
        entree : chaine, chaine de caracteres à tranformer en entier
        sortie : resultat, entier resultat correspondant à la conversion de la chaine en entier
    '''
    lgchaine = len(chaine)
    resultat = 0
    for i in range(0,lgchaine):
        nb = ord( chaine[i] ) # nb prend la valeur ascii du ieme caractere de la chaine
        resultat = nb*256**i + resultat
    return resultat


def hachage_d(cle, taille_table=TAILLE_TABLE):
    return transforme_chaine_entier(cle) % taille_table

def hachage_mult(cle, taille_table=TAILLE_TABLE, c=ALPHA):
    return math.floor(taille_table * (c * transforme_chaine_entier(cle) % 1))


def recup_Donneescsv(fichier, separateur=","):
    """
        recup_Donneescsv(fichier : str, separateur: str):lst
        entree : fichier, chaine qui correspond au chemin du fichier à ouvrir
                 separateur, chaine qui indique le separateur de colonnes. Par defaut ","
        sortie : liste de tuples contenues dans le fichier
    """
    # ouverture du fichier
    with open(fichier, "r", encoding='utf-8') as fic:
        listeTuples = list()
        entete = fic.readline().split(separateur)

        for ligne in fic:
            donneesPays = ligne.split(',')
            listeTuples.append((donneesPays[0].strip(), donneesPays[1].strip())) # (nomPays,nomCapitale)
    return listeTuples

def creer_TableHachage(liste, taille_table, fonction_hachage):
    tableHachage = [ [] for i in range(taille_table) ]
    for cle, val in liste:
        valeurHachage = fonction_hachage(cle)
        tableHachage[valeurHachage].append((cle, val))
    return tableHachage


def obtenir_Valeur( cleCherchee, tableHachage ):
    index = hachage_d(cleCherchee)
    element = tableHachage[index]
    for cle, val in element:
        if cle == cleCherchee:
            return val
    return None



# test des fonctions sur le fichier capitales.csv
listeTuples = recup_Donneescsv('capitalesMonde.csv')
print(listeTuples)

t_hachage = creer_TableHachage(listeTuples, TAILLE_TABLE, hachage_d)
print(t_hachage)

nomPays = input("de quel pays voulez vous la capitale?")
print(nomPays , " a pour capitale : ", obtenir_Valeur( nomPays, t_hachage))

indicesAlveoles = []
for i, e in enumerate(t_hachage):
    if len(e) > 1:
        print("Pays stockés avec la meme valeur de hachage : ", e) #question 8
    if e:
        indicesAlveoles.append(i)

print(indicesAlveoles, len(indicesAlveoles))

print("nombre de cles dans la table de hachage--> ", len(indicesAlveoles))
for k in indicesAlveoles:
    print(k, t_hachage[k])