class hash_table:
    def __init__(self, size, n_elements, collision_treatment_type, hash_function_type):
        self.size = size
        self.n_elements = n_elements
        self.collision_treatment_type = collision_treatment_type
        self.hash_function_type = hash_function_type
        self.table = [[None] for i in range(size)]
        self.collisions = 0
        self.positions_occupied = 0
        self.occupancy_rate = 0
        self.least = 0
        self.most = 0
        self.least_name = []
        self.most_name = []

    def hash_func(self, string):
        if self.hash_function_type == 1:
            aux = 0
            cont = 0
            for c in string:
                aux+= ord(c)**2
            hax = (aux)%len(self.table)
            #print('nome: ', string,'tamanho da hash table: ', len(self.table), 'hash: ', hax)
            return hax

        elif self.hash_function_type == 2:
            hax = 0
            cont = 0
            p = 31
            for c in string:
                hax = hax + ord(c)*(p**cont)
                cont+=1
            return (hax%len(self.table))
        else:
            print('funcao hash de tipo invalido')


    def insert(self, string):
        hash_key = self.hash_func(string)
        if self.table[hash_key][0] == None:
            self.table[hash_key][0] = string
            self.positions_occupied+=1
            self.occupancy_rate= 100*(self.positions_occupied)/self.size
        else:
            if self.collision_treatment_type == 1:
                self.table[hash_key].append(string)
                self.collisions+=1

            elif self.collision_treatment_type == 2:
                hash_key+= 1
                while self.table[hash_key][0] != None:
                    hash_key += 1
                    self.collisions+=1
                self.table[hash_key][0] = string
                self.positions_occupied+=1
                self.occupancy_rate= 100*(self.positions_occupied)/self.size

            else:
                print('tipo de tratamento de colisao da hash table invalido')

    def search(self, string):
        acessos = 0
        hash_key = self.hash_func(string)
        flag = False
        if self.collision_treatment_type == 1:
            for item in self.table[hash_key]:
                acessos+=1
                if item == string:
                    flag = True
                    print('nome', string, 'encontrado no index: ', hash_key, 'e o total de acessos foi: ', acessos)

                    if self.least == 0:
                        self.least = acessos
                        self.least_name.append(string)
                    elif acessos < self.least:
                        self.least = acessos
                        self.least_name.clear()
                        self.least_name.append(string)
                    elif acessos == self.least:
                        self.least_name.append(string)

                    if self.most == 0:
                        self.most = acessos
                        self.most_name.append(string)
                    elif acessos > self.most:
                        self.most = acessos
                        self.most_name.clear()
                        self.most_name.append(string)
                    elif acessos == self.most:
                        self.most_name.append(string)

            if flag == False:
                print('nome', string, 'nao foi encontrado')
        elif self.collision_treatment_type == 2:
            condition = False
            while (condition == False):
                if ((self.table[hash_key][0] == string) or (self.table[hash_key][0] == None)):
                    condition = True
                    if self.table[hash_key][0] == string:
                        flag = True
                else:
                    hash_key+=1
                acessos+=1
            if flag == True:
                print('nome', string, 'encontrado no index: ', hash_key, 'e o total de acessos foi: ', acessos)

                if self.least == 0:
                    self.least = acessos
                    self.least_name.append(string)
                elif acessos < self.least:
                    self.least = acessos
                    self.least_name.clear()
                    self.least_name.append(string)
                elif acessos == self.least:
                    self.least_name.append(string)

                if self.most == 0:
                    self.most = acessos
                    self.most_name.append(string)
                elif acessos > self.most:
                    self.most = acessos
                    self.most_name.clear()
                    self.most_name.append(string)
                elif acessos == self.most:
                    self.most_name.append(string)

            else:
                print('nome', string, 'nao foi encontrado')
        else:
            print('tipo de tratamento de colisao da hash table invalido')


table = hash_table(3169 , 10000, 1, 1) #hash table containing modal hash function and chained collision treatment
table2 = hash_table(3169, 10000, 1, 2)  #hash table containing polinomial hash function and chained collision treatment
table3 = hash_table(20123, 10000, 2, 1) #hash table containing modal hash function and linear search (EABL) collision treatment
table4 = hash_table(20123, 10000, 2, 2) #hash table containing polinomial hash function and linear search (EABL) collision treatment
#defining R, a small prime number that will be used in the modular hash function
R = 53
M = len(table.table)

#to read the archive building all the 4 possible hash tables containing the names in each line:
f= open("nomes_10000.txt","r")
for line in f:
    aux = line[0:len(line) - 1]
    table.insert(aux)
    table2.insert(aux)
    table3.insert(aux)
    table4.insert(aux)

f.close()
print('')
print('TABELA COM HASH MODAL E ENCADEAMENTO FECHADO:')
print('numero de colisoes: ', table.collisions)
print('taxa de ocupacao da tabela:', table.occupancy_rate,'%')
print('')
print('TABELA COM HASH POLINOMIAL E ENCADEAMENTO FECHADO:')
print('numero de colisoes: ', table2.collisions)
print('taxa de ocupacao da tabela:', table2.occupancy_rate,'%')
print('')
print('TABELA COM HASH MODAL E EABL:')
print('numero de colisoes: ', table3.collisions)
print('taxa de ocupacao da tabela:', table3.occupancy_rate,'%')
print('')
print('TABELA COM HASH POLINOMIAL E EABL:')
print('numero de colisoes: ', table4.collisions)
print('taxa de ocupacao da tabela:', table4.occupancy_rate,'%')
print('')
print('consultas:')
#to read the second archive:
f = open("consultas.txt", "r")
for line in f:
   aux = line[0:len(line) - 1]
   table.search(aux)
print('')
print('nome(s) com menor numero de acessos:',table.least_name)
print('com ', table.least, ' acesso(s)')
print('')
print('nome(s) com maior numero de acessos:',table.most_name)
print('com ', table.most, ' acesso(s)')

f.close()