# -*- coding: utf-8 *-*

"""
Table de hachage : la fonction de hachage retenue est de considérer un mot
comme un nombre écrit en base 256, les chiffres étant les codes ascii des
caractères, modulo la taille choisie pour la table de hachage (par défaut 31) :

hash(w0w1...wk) = w0 + 256*w1 + ... + 256^k*wk % len_table
"""

LENGTH_TABLE = 31

def bad_hash(word, len_table = LENGTH_TABLE):
    """Cette fonction implémente un très mauvais algorithme pour calculer le
       hachage d'un mot"""
    h = 0
    for i in range(0, len(word)):
        h += ord(word[i]) * 256**i
    return h % len_table

def rec_hash(word, len_table = LENGTH_TABLE):
    """Fonction récursive implémentant la formule hash(w0w1...wk) = w0 +
       256*hash(w1...wk) modulo len_table"""
    if len(word) == 0:
        return 0
    else:
        return (ord(word[0]) + 256 * rec_hash(word[1:], len_table)) % len_table

def loop_hash(word, len_table = LENGTH_TABLE):
    """Fonction de hachage implémentée au moyen d'une boucle"""
    hash = 0
    base = 256 % len_table
    i = len(word)
    while i > 0:
        i -= 1
        hash *= base
        hash += ord(word[i])
        hash %= len_table
    return hash

def make_hashtable(len_table = LENGTH_TABLE):
    """Construction d'une table de hachage vide : un tableau de taille
       len_table de listes vides"""
    table = [None] * len_table # Initialisation du tableau
    # On met une liste vide dans chaque cellule du tableau
    for i in range(0, len_table):
        table[i] = []
    return table

def insert_word(table, word, value):
    """Insertion d'une paire (word, value) dans la table table"""
    hash = loop_hash(word, len(table))

    # On cherche si ce mot est déjà dans la table et si on le trouve, on
    # remplace la valeur associée
    for entry in table[hash]:
        if entry[0] == word:
            old_val = entry[1]
            entry[1] = value
            return old_val

    # Le mot n'apparaît pas dans la table, on ajoute la paire [word, value]
    table[hash].append([word, value])
    return value

def find_word(table, word):
    """Recherche de la valeur associée à un mot dans la table"""
    hash = loop_hash(word, len(table))

    for entry in table[hash]:
        if entry[0] == word:
            return entry[1]

    # Pas trouvé, on ne retourne rien
    return None

def delete_word(table, word):
    """Effacement d'une paire (clef, valeur) de la table"""
    hash = loop_hash(word, len(table))
    entries = []
    value = None

    # On reconstruit la liste des paires en omettant celle que l'on veut enlever
    for entry in table[hash]:
        if entry[0] == word:
            value = entry[1]
        else:
            entries.append(entry)
    table[hash] = entries
    return value

# Réimplémentation en utilisant les classes
class hashtable(object):
    """
Usage :
>>> t = hashtable(31)
>>> t.table_size
31
>>> t.table
[[], [], [], [], [], [], [], [], [], [],
 [], [], [], [], [], [], [], [], [], [],
 [], [], [], [], [], [], [], [], [], [],
 []]
>>> t.hash('abc')
25
>>> t.insert_word('abc', 1)
1
>>> t.table
[[], [], [], [], [], [], [], [], [], [],
 [], [], [], [], [], [], [], [], [], [],
 [], [], [], [], [], [['abc', 1]], [], [], [], [],
 []]
>>> t.find_word('abc')
1
>>> t.insert_word('abc', 2)
2
>>> t.table
[[], [], [], [], [], [], [], [], [], [],
 [], [], [], [], [], [], [], [], [], [],
 [], [], [], [], [], [['abc', 2]], [], [], [], [],
 []]
>>> t.find_word('abc')
2
>>> t.delete_word('abc')
2
>>> t.find_word('abc')
None
    """

    DEFAULT_TABLE_SIZE = 31

    def __init__(self, len_table = DEFAULT_TABLE_SIZE):
        """Initialisation de la table ; cette méthode est appelée
           automatiquement lorsque l'on crée un objet de la classe"""
        self.table_size = len_table
        self.table = [None] * len_table
        for i in range(0, len_table):
            self.table[i] = []

    def hash(self, word):
        hash = 0
        base = 256 % self.table_size
        i = len(word)
        while i > 0:
            i -= 1
            hash *= base
            hash += ord(word[i])
            hash %= self.table_size
        return hash

    def insert_word(self, word, value):
        hash = self.hash(word)
        for entry in self.table[hash]:
            if entry[0] == word:
                old_value = entry[0]
                entry[1] = value
                return old_value
        self.table[hash].append([word, value])
        return value

    def find_word(self, word):
        hash = self.hash(word)
        for entry in self.table[hash]:
            if entry[0] == word:
                return entry[1]
        return None

    def delete_word(self, word):
        hash = self.hash(word)
        entries = []
        value = None

        # On reconstruit la liste des paires en omettant celle que l'on veut
        # enlever
        for entry in self.table[hash]:
            if entry[0] == word:
                value = entry[1]
            else:
                entries.append(entry)
        self.table[hash] = entries
        return value

# Tests