def distance2(p,q):
    #entree: 2 listes de longueur 2 , retourne le carre de la distance euclidienne
    return (p[0]-q[0])**2+(p[1]-q[1])**2
    
#Creation du tableau des dtistances
def liste_Distances(data, individu):
    l=[]
    n=len(data)
    for i in range(n):
        l.append([distance2(individu,data[i][0:2]),data[i][2]])
    return(l)    

# Fonctions auxiliaires
def estIndice(T,i):
    return(0<=i and i<len(T))

def echange(T,i,j):
    assert(estIndice(T,i) and estIndice(T,j))
    aux  = T[i]
    T[i] = T[j]
    T[j] = aux

def triSelectionModif(data, individu):
    T=liste_Distances(data, individu)
    for i in range(len(T)-1):
        iMin=i
        for j in range(i+1,len(T)):
            if T[j][0]<T[iMin][0]:
                iMin = j
        if iMin != i :
            echange(T,i,iMin)
    return(T)


def lesKplusProchesVoisins_sans_tri (data, individu,k):
  listeDistances = liste_Distances(data, individu)
  Kppv = []
  liste_indices_utilises=[]
  for i in range (k):
    p = float ("inf")
    for j in range (len (data)):
      if listeDistances [j][0] != 0 and listeDistances [j][0] < p and j not in liste_indices_utilises:
        p = listeDistances [j][0]
        indice = j
    Kppv. append (listeDistances [indice][1])
    liste_indices_utilises.append(indice)
  return (Kppv)
  
def lesKplusProchesVoisins_avec_tri (data, individu,k):
  assert(k<=len(data))
  L=triSelectionModif(data,individu)
  return [L[i][1] for i in range(k)]



#attribution  d'une etiquette ou classe pour un individu

def etiquette_avec_tri(data,individu, k):
    etiquettesKvoisins=lesKplusProchesVoisins_avec_tri(data,individu,k)
    lstEtiquettes=[etiquettesKvoisins[0]]#liste sans doublon des etiquettes des k voisins
    lstOccurrences=[1]#liste des occurences des etiquettes
    occMax=1
    indMax=0#pour recuperer l'etiquette correspondant à occMax
    #construction de la liste sans doublons et recherche de l'etiquette la plus presente
    for i in range (1,k):
        n=len(lstEtiquettes)
        trouve=False# l'etiquette testee est elle deja dans la liste?
        for j in range(n):
            if etiquettesKvoisins[i] == lstEtiquettes[j]:
                lstOccurrences[j]+=1
                if lstOccurrences[j]>occMax:
                    occMax=lstOccurrences[j]
                    indMax=j
                trouve=True
        if not trouve:
            lstEtiquettes.append(etiquettesKvoisins[i])
            lstOccurrences.append(1)
    #print(lstEtiquettes,lstOccurrences,occMax,indMax)
    return lstEtiquettes[indMax]        


def etiquette_sans_tri(data,individu, k):
    etiquettesKvoisins=lesKplusProchesVoisins_sans_tri(data,individu,k)
    lstEtiquettes=[etiquettesKvoisins[0]]#liste sans doublon des etiquettes des k voisins
    lstOccurrences=[1]#liste des occurences des etiquettes
    occMax=1
    indMax=0#pour recuperer l'etiquette correspondant à occMax
    #construction de la liste sans doublons et recherche de l'etiquette la plus presente
    for i in range (1,k):
        n=len(lstEtiquettes)
        trouve=False# l'etiquette testee est elle deja dans la liste?
        for j in range(n):
            if etiquettesKvoisins[i] == lstEtiquettes[j]:
                lstOccurrences[j]+=1
                if lstOccurrences[j]>occMax:
                    occMax=lstOccurrences[j]
                    indMax=j
                trouve=True
        if not trouve:
            lstEtiquettes.append(etiquettesKvoisins[i])
            lstOccurrences.append(1)
    #print(lstEtiquettes,lstOccurrences,occMax,indMax)
    return lstEtiquettes[indMax]        


if __name__=="__main__":
    # on importe le module CSV. 
    import csv



    data=[]
    #On crée un objet "reader"
    with open('C:/data/Dropbox/data1/Numérique et informatique/formation NSI/Bloc 2 - Algo/projet/meteo_mai_2019_France.csv', 'r') as f:
        reader = csv.reader(f)     
        for row in reader:
            if (row[1]!="") and (row[2]!=""):
                temp=[float(row[1]),float(row[2]),row[0]]
                data.append(temp)       
    
    # Choix de k
    k=30

    # Quelques tests

    # Senlis (60)
    moy_temp=12.6
    cumul_prec=93.3
    individu=(moy_temp,cumul_prec)
    prediction= etiquette_avec_tri(data,individu,k)
    print ("Senlis (60) - valeur prédite : ", prediction)


    # Arvert (17)
    moy_temp=14.6
    cumul_prec=22.8
    individu=(moy_temp,cumul_prec)
    prediction= etiquette_avec_tri(data,individu,k)
    print ("Arvert (17) - valeur prédite : ", prediction)

    # Quimper-Pluguffan (29)
    moy_temp=12.9
    cumul_prec=51.1
    individu=(moy_temp,cumul_prec)
    prediction= etiquette_avec_tri(data,individu,k)
    print ("Quimper-Pluguffan (29) - valeur prédite : ", prediction)

    # Biarritz-Anglet (64)
    moy_temp=14.1
    cumul_prec=178.2
    individu=(moy_temp,cumul_prec)
    prediction= etiquette_avec_tri(data,individu,k)
    print ("Biarritz-Anglet (64) - valeur prédite : ", prediction)

    # Saint-Laurent-du-Pont (38)
    moy_temp=12.3
    cumul_prec=183.2
    individu=(moy_temp,cumul_prec)
    prediction= etiquette_avec_tri(data,individu,k)
    print ("Saint-Laurent-du-Pont (38) - valeur prédite : ", prediction)

    #  Figari (2A)
    moy_temp=15.38
    cumul_prec=34.6
    individu=(moy_temp,cumul_prec)
    prediction= etiquette_avec_tri(data,individu,k)
    print ("Figari (2A) - valeur prédite : ", prediction)