#Compression

def numerotation(T):
    D = {}
    L = []
    n = 0
    for x in T:
        if x not in D:
            D[x] = n
            n = n+1
            L.append(x)
    return L,D

def phrase(T):
    if T==[]:
        return ""
    p = T[0]
    for i in range(1,len(T)):
        p = p+' '
        p = p+T[i]
    return p



def compresser(nom_source, nom_comp):
    fichier_source = open(nom_source,'r')
    T = []
    for ligne in fichier_source.readlines():
        ligne = ligne.strip()
        T += ligne.split(' ')
    L,D = numerotation(T)
    fichier_comp = open(nom_comp, 'w')
    fichier_comp.write(phrase(L))
    fichier_comp.write("\n")
    for ligne in fichier_source.readlines():
        ligne = ligne.strip()
        fichier_comp.write(phrase([str(D[mot]) for mot in ligne.split(' ')]))
        fichier_comp.write('\n')
    fichier_comp.close()
    fichier_source.close()

def decompresser(nom_comp, nom_dec):
    fichier_comp = open(nom_comp, 'r')
    L =  fichier_comp.readline().strip().split(' ')
    fichier_dec = open(nom_dec, 'w')
    for ligne in fichier_comp.readlines():
        ligne = ligne.strip()
        T = ligne.split(' ')
        T_dec = [L[int(num)] for num in T]
        fichier_dec.write(phrase(T_dec))
        fichier_dec.write('\n')
    fichier_comp.close()
    fichier_dec.close()


#Table de hachage


def hash(ch,n):
    h = 0
    for c in ch:
        h += ord(c)
    return h%n

def hash(ch,n):
    h = 0
    p = 1
    for c in ch:
        h = (h + ord(c)*p)%n
        p = p * 101
    return h

def hash(ch,n):
    h = 0
    for c in ch:
        h += ord(c)
    return h%n

def creer_dico(n):
    D = [[] for _ in range(n)]
    return D

def cle_presente(D,cle):
    n = len(D)
    h = hash(cle,n)
    for (x,y) in D[h]:
        if x==cle:
            return True
    return False

def ajouter(D,cle,valeur):
    n = len(D)
    h = hash(cle,n)
    D[h].append([cle,valeur])

def valeur_associee(D,cle):
    n = len(D)
    h = hash(cle,n)
    for (x,y) in D[h]:
        if x==cle:
            return y

def modifier_valeur(D,cle,valeur):
    n = len(D)
    h = hash(cle,n)
    for i in range(len(T[h])):
        if cle==D[h][i][0]:
            D[h][i][1] = valeur
            return

def supprimer(D,cle):
    n = len(D)
    h = hash(cle,n)
    for i in range(len(T[h])):
        if cle==D[h][i][0]:
            D[h].pop(i)
            return



#Compression avec l'implémentation maison

def numerotation(T):
    D = creer_dico(len(T))
    L = []
    n = 0
    for x in T:
        if not cle_presente(D,x):
            ajouter(D,x,n)
            n = n+1
            L.append(x)
    return L,D


def compresser(nom_source, nom_comp):
    fichier_source = open(nom_source,'r')
    T = []
    for ligne in fichier_source.readlines():
        ligne = ligne.strip()
        T += ligne.split(' ')
    L,D = numerotation(T)
    fichier_comp = open(nom_comp, 'w')
    fichier_comp.write(phrase(L))
    fichier_comp.write("\n")
    for ligne in fichier_source.readlines():
        ligne = ligne.strip()
        fichier_comp.write(phrase([str(valeur_associee(D,mot)) for mot in ligne.split(' ')]))
        fichier_comp.write('\n')
    fichier_comp.close()
    fichier_source.close()

def decompresser(nom_comp, nom_dec):
    fichier_comp = open(nom_comp, 'r')
    L =  fichier_comp.readline().strip().split(' ')
    fichier_dec = open(nom_dec, 'w')
    for ligne in fichier_comp.readlines():
        ligne = ligne.strip()
        T = ligne.split(' ')
        T_dec = [L[int(num)] for num in T]
        fichier_dec.write(phrase(T_dec))
        fichier_dec.write('\n')
    fichier_comp.close()
    fichier_dec.close()


def f_collisions(D):
    n = 0
    d = 0
    for L in D:
        if len(L)>1:
            n+=len(L)
        d+=len(L)
    return n/d