from itertools import count, accumulate, chain, cycle
from random import randrange, sample

empty = ("_empty", "_empty", 0)
deleted = ("_deleted", "_deleted", 0)

def is_prime(x):
    for f in accumulate(chain((2, 1, 2, 2), cycle((4, 2, 4, 2, 4, 6, 2, 6)))):
        if f * f > x:
            return True
        if x % f == 0:
            return False

def next_prime(x):
    return next(p for p in count(x|1, 2) if is_prime(p))

def inc_linprob(hashval, M):
    """ increment for linear probing"""
    return 1

def inc_double_hashing(hashval, M):
    """ increment for double hashing - make sure it is not in range [1, M-1]"""
    return hashval % (M-1) + 1

class dictlh(object):
    """ Store (key, value, hash(key))
    """
    def __init__(self, mode=inc_linprob, load_factor=0.5):
        self.M = 997
        self.buckets = [empty] * self.M
        self.load_factor = load_factor
        self.max_load = load_factor * self.M
        self.n_elements = 0
        self.n_deleted = 0
        self._increment = mode
        self.searches = 0

    def _find_insert_bucket(self, key):
        """ result: find the key OR find an empty bucket to insert """
        hashval = hash(key)
        b, M = self.buckets, self.M
        inc = self._increment(hashval, M)
        h = hashval % M
        bh = b[h]
        while bh != empty and bh[0] != key:
            h = (h + inc) % M
            bh = b[h]
            self.searches += 1
        return h

    def _insert(self, key, value, hashval=None):
        if hashval is None:
            hashval = hash(key)
        bi = self._find_insert_bucket(key)
        isempty = self.buckets[bi] == empty
        self.buckets[bi] = (key, value)
        if isempty:
            self.n_elements += 1
            if self.n_elements > self.max_load:
                self._rehash()

    def _find_key(self, key):
        bi = self._find_insert_bucket(key)
        if self.buckets[bi][0] == key:
            return bi
        raise KeyError("key not found")

    def _lookup(self, key):
        h = self._find_key(key)
        return self.buckets[h][1]

    def _rehash(self):
        load = self.n_elements - self.n_deleted
        self.M = next_prime(4 * load)
        self.max_load = self.load_factor * self.M
        self.n_elements = self.n_deleted = 0
        old_buckets = list(self.buckets)
        self.buckets = [empty] * self.M
        for item in old_buckets:
            if item not in (deleted, empty):
                self._insert(*item)

    def _delete(self, key):
        h = self._find_key(key)
        self.buckets[h] = deleted
        self.n_deleted += 1

    def __setitem__(self, key, value):
        self._insert(key, value)

    def __getitem__(self, key):
        return self._lookup(key)

    def __delitem__(self, key):
        self._delete(key)

    def get(self, key, default=None):
        try:
            return self._lookup(key)
        except KeyError:
            return default

    def __len__(self):
        return self.n_elements - self.n_deleted

    def __contains__(self, key):
        bi = self._find_insert_bucket(key)
        return self.buckets[bi][0] == key

    def __iter__(self):
        yield from (b[0] for b in self.buckets if b not in (empty, deleted))

    def keys(self):
        """a copy of all keys"""
        return list((b[0] for b in self.buckets if b not in (empty, deleted)))

    def values(self):
        """a copy of all values"""
        return list((b[1] for b in self.buckets if b not in (empty, deleted)))


if __name__ == '__main__':
    from time import clock
    from glob import glob
    from itertools import starmap, repeat

    def repeatfunc(func, times=None, *args):
        if times is None:
            return starmap(func, repeat(args))
        return starmap(func, repeat(args, times))

    load_factor = 0.50
    # Tests
    for mode in (inc_linprob, inc_double_hashing):
        D = dictlh(mode=mode, load_factor=load_factor)
        PD = {}
        for k, v in zip("abcdefghijklmnopqrstuvwxyz", range(26)):
            D[k] = v
            PD[k] = v

        assert D["v"] == PD["v"]

        del D["v"]
        del PD["v"]
        try:
            D["v"]
        except KeyError:
            pass

        for key in "abcdefghijklmnopqrstuwxyz":
            assert D[key] == PD[key]

        D["a"] = 99
        PD["a"] = 99
        assert D["a"] == PD["a"]

        def random_ints(N, start, stop):
            return list(repeatfunc(randrange, N, *(start, stop)))

        N = 1000
        rand1, rand2 = random_ints(N, 0, 50), random_ints(N, 0, 1000000)
        for key, val in zip(rand1, rand2):
            D[key] = val
            PD[key] = val
            assert D[key] == PD[key]

        for key in sample(rand1, N // 2):
            try:
                del D[key]
            except KeyError:
                pass
            try:
                del PD[key]
            except KeyError:
                pass
                

        for key, val in PD.items():
            assert D[key] == val, "{} {} {}".format(key, val, D[key])
        
        print(D.searches)
            
        print("tests OK")