"""
 hash_table_lab.py

 Implement a hash table !
 
 Jim Mahoney | cs.bennington.college | MIT License | March 2021
"""

#from utilities import random_words
from time import time

def hash_function(string):
    """ Given a string, return a (largish) integer hash value """
    # TODO : Replace this "return" with your code.
    # Hint : See https://en.wikipedia.org/wiki/Hash_function
    return 0
    
class HashTable:
    """ a hash table (python dictionary) with "get" and "set" methods """

    def __init__(self, size=1001):
        """ create an initially empty hash table """
        # Each entry in self.table is either
        #   (a)   None  (meaning that it is empty), or
        #   (b)   (key, value) 
        self.size = size       # number of bins (both filled & empty).
        self.entries = 0       # number of bins with stuff in 'em.
        self.table = [ None ] * self.size

    def show(self):
        # return a string showing the whole table 
        return f"<HashTable {str(self.table)} >"
        
    def _index_of(self, key):
        """ Look for the index for a given key.
            If the key is already in the table, return (index, True).
            If not, return (index, False) 
            where index is where it should be put.
        """
        # TODO : Replace this "return" with your code.
        # Hint - look at https://en.wikipedia.org/wiki/Linear_probing
        return (0, False)
        
    def set(self, key, value):
        """ add (or replace) a (key,value) in the hash table """
        (index, _) = self._index_of(key)
        self.table[index] = (key, value)
        self.entries += 1

    def get(self, key):
        """ return the corresponding value or None if not found """
        (index, exists) = self._index_of(key)
        return self.table[index][1] if exists else None

def test1():
    print("-- hash table test 1")
    smalltable = HashTable(7)
    smalltable.set('cat', 'meow')
    print(smalltable.show())
    smalltable.set('dog', 'woof')
    print(smalltable.show())
    print(" get('cat') : ", smalltable.get('cat'))
    print(" get('dog') : ", smalltable.get('dog'))    
    print(" get('not in table') : ", smalltable.get('not in table'))
    
def test2():
    # Some sample data to put into the table.
    # (Note that 'bbb' has the same hash as 'abc'.)
    print("-- hash table test 2 --")
    hashtable = HashTable(5)
    pairs = [('abc', 1), ('abcd', 2), ('bbb', 3)]
    for (key, value) in pairs:
        hashtable.set(key, value)
        print(hashtable.show())
    test_keys = ('abc', 'def', 'bbb')
    for key in test_keys:
        value = hashtable.get(key)
        if value:
            print(f"Found key '{key}', value is '{value}'. ")
        else:
            print(f"Did not find key '{key}'.")
    

def time_test(n, yes_words, no_words):
    """ return time it takes to put in yes_words, check yes_words & no_words """
    start = time()
    hash_table = HashTable(n)
    for word in yes_words:
        hash_table.set(word, len(word))
    for word in yes_words:
        try:
            assert hash_table.get(word) == len(word)
        except AssertionError:
            print(f"Failed to hit word {word}; got {hash_table.get(word)}")
    for word in no_words:
        try:
            assert hash_table.get(word) == None
        except AssertionError:
            print(f"Failed to miss word {word}; got {hash_table.get(word)}")
    return time() - start
            
#def test3():
#    print("-- hash table test 3 --")
#    for n in (101, 1001, 10001):
#        words = random_words(n)
#        yes_words = words[0:n//2]  # words to be put in hashtable
#        no_words = words[n//2:]     # words not in hashtable
#        elapsed = time_test(n, yes_words, no_words)
#        print(f"With n={n:>5}, half each yes/no,  elapsed={elapsed:>12.6f}.")

def main():
    test1()
    test2()
    # test3() ... only after things are working ...

if __name__ == '__main__':
    main()