#!/usr/bin/env python3
'''
Имитация хеш-таблиц
Формат одного объекта:
    [количество занятых элементов, хеш-функция, таблица элементов]
Незанятые ячейки заполнены объектом None
'''
# limit: 10
# stdout: | less

MINSZ = 8       # Minimal size
MAXFULL = 50    # Percents full

def Next(table, hsh):
    '''Повторное индексиование при коллизии'''
    return (hsh+1)%len(table[2])

def Makehash(t):
    '''Создать хеш-функцию для таблицы t или для таблицы размера t'''
    Len = t if type(t) is int else len(t[2])
    def Hash(value):
        return hash(value)%Len
    return Hash

def Init(size=MINSZ, seq=[]):
    '''Создать хеш-таблицу размера size из списка seq'''
    return Add([0,Makehash(size),[None]*size],*seq)

def Add(table, *values):
    '''Добавить в таблицу table элементы values'''
    for value in values:
        if value is None:
            continue
        if len(table[2])<table[0]*100/MAXFULL:
            Enlarge(table)
        hsh = table[1](value)
        while table[2][hsh] is not None and value != table[2][hsh]:
            hsh = Next(table, hsh)
        if table[2][hsh] is None:
            table[2][hsh] = value
            table[0] += 1
    return table

def Str(table):
    '''Строковое представление таблицы'''
    res = "===={}/{}\n".format(table[0],len(table[2]))
    def repr(i,v):
        '''Эелмент и его хеш или ..., если ячейка пуста'''
        if v is not None:
            hsh = table[1](v)
            coll = "collision " if hsh !=i else ""
            return "{:10} ({}{})".format(v, coll, hsh)
        else:
            return "..."
    res += "\n".join(repr(i,v) for i,v in enumerate(table[2]))
    res += "\n===="
    return res
    # то же самое в одну строку, слабонервным не читать:
    # return "===={}/{}\n".format(table[0],len(table[2]))+"\n".join("{:10} ({}{})".format(v, "collision " if table[1](v)!=i else "", table[1](v)) if v is not None else "..." for i,v in enumerate(table[2]))+"\n===="

def Iter(table):
    '''Вернуть итератор по элементам таблицы'''
    return (e for e in table[2] if e is not None)

def Enlarge(table):
    '''Увеличить таблицу в два раза'''
    # создадим новую таблицу и перепишем все её поля обратно в старую
    table[:] = Init(len(table[2])*2, table[2])[:]
    return table

def Search(table, value):
    '''Проверить, содержится ли value в table'''
    hsh = table[1](value)
    while table[2][hsh] is not None:
        if table[2][hsh] == value:
            return True
        hsh = Next(table, hsh)
    return False

if __name__ == "__main__":
    import random
    T = Init()
    for i in range(100000):
        action = random.choice(("add","search","failsearch")) if T[0] else "add"
        if action == "add":
            patt = random.randrange(1000)
            print("Add {}".format(patt))
            Add(T,patt)
            print(Str(T))
        elif action == "search":
            patt = random.choice(list(Iter(T)))
            print("Search for {}: {}".format(patt, Search(T, patt)))
        else:
            patt = random.randrange(1000)
            print("Search for {}: {}".format(patt, Search(T, patt)))