from typing import Union, Tuple
from functools import partial


class HashMap:
    def __init__(self, size: int = 10, hashfn=lambda x: x % 10, alignment: int = 2) -> None:
        self._data = [None] * size
        self._ptrs = [None] * size
        self._hashfn = hashfn
        self._alignment = alignment

    def _find_pos(self, key) -> Tuple[Union[int, None], Union[int, None], Union[int, None]]:
        raise NotImplementedError()

    def resize(self):
        raise NotImplementedError()

    def insert(self, key):
        pos, prev_pos, next_pos = self._find_pos(key)
        if pos is None:
            self.resize()
            pos, prev_pos, next_pos = self._find_pos(key)

        assert pos is not None

        if self._data[pos] is not None and self._data[pos] == key:
            return  # key already in hashmap

        self._data[pos] = key
        if prev_pos is not None:
            self._ptrs[prev_pos] = pos
        if next_pos is not None:
            self._ptrs[pos] = next_pos

    def find(self, key) -> bool:
        pos, _, _ = self._find_pos(key)
        return pos is not None and self._data[pos] == key

    def __str__(self) -> str:
        s = ""
        s += "I: [" + ", ".join([(f"{d:>{self._alignment}}" if d is not None else f"{'--':>{self._alignment}}") for d in range(len(self._data))]) + "]\n"
        s += "D: [" + ", ".join([(f"{d:>{self._alignment}}" if d is not None else f"{'--':>{self._alignment}}") for d in self._data]) + "]\n"
        s += "P: [" + ", ".join([(f"{d:>{self._alignment}}" if d is not None else f"{'--':>{self._alignment}}") for d in self._ptrs]) + "]\n"
        s += "\n"

        return s


class CoalescedHashMap(HashMap):

    def __init__(self, size: int = 10, hashfn=lambda x: x % 10, alignment: int = 2) -> None:
        super().__init__(size, hashfn, alignment)
        self._last_free = size - 1

    def _update_last_free(self):
        for i in range(self._last_free, -1, -1):
            if self._data[i] is None:
                self._last_free = i
                return
        self._last_free = None

    def _find_pos_for_new(self, key, hash, last_pos, last_prev_pos) -> Tuple[
        Union[int, None], Union[int, None], Union[int, None]]:
        raise NotImplementedError()

    def _find_pos(self, key) -> Tuple[Union[int, None], Union[int, None], Union[int, None]]:
        hash = self._hashfn(key)

        prev_pos = None
        next_pos = None
        pos = hash

        while self._data[pos] is not None and self._data[pos] != key:
            if self._ptrs[pos] is None:
                if self._last_free is None:
                    self.resize()
                pos, prev_pos, next_pos = self._find_pos_for_new(key, hash, pos, prev_pos)
                break
            prev_pos = pos
            pos = self._ptrs[pos]

        return pos, prev_pos, next_pos

    def insert(self, key):
        super().insert(key)
        self._update_last_free()


class LISCH(CoalescedHashMap):

    def _find_pos_for_new(self, key, hash, last_pos, last_prev_pos) -> Tuple[
        Union[int, None], Union[int, None], Union[int, None]]:
        prev_pos = last_pos
        pos = self._last_free
        self._update_last_free()

        return pos, prev_pos, None

    def __str__(self) -> str:
        return "LISCH\n" + super().__str__()


class EISCH(CoalescedHashMap):

    def _find_pos_for_new(self, key, hash, last_pos, last_prev_pos) -> Tuple[
        Union[int, None], Union[int, None], Union[int, None]]:
        # the right cell is empty
        if self._data[hash] is None:
            return hash, None, None

        next_pos = self._ptrs[hash]
        prev_pos = hash
        pos = self._last_free
        self._update_last_free()

        return pos, prev_pos, next_pos

    def __str__(self) -> str:
        return "EISCH\n" + super().__str__()


class HashMapWithCellar(CoalescedHashMap):

    def __init__(self, size: int = 8, cellar: int = 2, hashfn=lambda x: x % 8, alignment: int = 2) -> None:
        super().__init__(size + cellar, hashfn, alignment)
        self._cellar = cellar

    def _is_in_cellar(self, pos) -> bool:
        return pos >= len(self._data) - self._cellar

    def __str__(self) -> str:
        if self._cellar == 0:
            return super().__str__()

        base_len = len(self._data) - self._cellar

        s = ""
        s += "I: [" + ", ".join([(f"{d:>{self._alignment}}" if d is not None else f"{'--':>{self._alignment}}") for d in range(base_len)])
        s += " | " + ", ".join([(f"{d:>{self._alignment}}" if d is not None else f"{'--':>{self._alignment}}") for d in range(base_len, base_len + self._cellar)]) + "]\n"

        s += "D: [" + ", ".join([(f"{d:>{self._alignment}}" if d is not None else f"{'--':>{self._alignment}}") for d in self._data[0:base_len]])
        s += " | " + ", ".join([(f"{d:>{self._alignment}}" if d is not None else f"{'--':>{self._alignment}}") for d in self._data[base_len:]]) + "]\n"

        s += "P: [" + ", ".join([(f"{d:>{self._alignment}}" if d is not None else f"{'--':>{self._alignment}}") for d in self._ptrs[0:base_len]])
        s += " | " + ", ".join([(f"{d:>{self._alignment}}" if d is not None else f"{'--':>{self._alignment}}") for d in self._ptrs[base_len:]]) + "]\n"

        s += "\n"
        return s


class LICH(HashMapWithCellar):

    def __init__(self, size: int = 8, cellar: int = 2, hashfn=lambda x: x % 8, alignment: int = 2) -> None:
        super().__init__(size, cellar, hashfn, alignment)
        self._find_pos_for_new = partial(LISCH._find_pos_for_new, self)

    def __str__(self) -> str:
        return "LICH\n" + super().__str__()


class EICH(HashMapWithCellar):

    def __init__(self, size: int = 8, cellar: int = 2, hashfn=lambda x: x % 8, alignment: int = 2) -> None:
        super().__init__(size, cellar, hashfn, alignment)
        self._find_pos_for_new = partial(EISCH._find_pos_for_new, self)

    def __str__(self) -> str:
        return "EICH\n" + super().__str__()


class VICH(HashMapWithCellar):

    def _find_pos_for_new(self, key, hash, last_pos, last_prev_pos) -> Tuple[Union[int, None], Union[int, None], Union[int, None]]:
        # the right cell is empty
        if self._data[hash] is None:
            return hash, None, None

        last_in_cellar = None
        p = hash
        while self._data[p] is not None and self._data[p] != key:
            if self._is_in_cellar(p):
                last_in_cellar = p
            if self._ptrs[p] is not None:
                p = self._ptrs[p]
            else:
                break

        if last_in_cellar is None:
            return EISCH._find_pos_for_new(self, key, hash, last_pos, last_prev_pos)

        next_pos = self._ptrs[last_in_cellar]
        prev_pos = last_in_cellar
        pos = self._last_free
        self._update_last_free()

        return pos, prev_pos, next_pos

    def __str__(self) -> str:
        return "VICH\n" + super().__str__()


if __name__ == '__main__':
    types = (LISCH, EISCH, LICH, EICH, VICH)
    sizes = dict.fromkeys(types, None)
    hashfns = dict.fromkeys(types, None)
    datas = dict.fromkeys(types, None)
    cellars = dict.fromkeys(types, None)
    alignments = dict.fromkeys(types, 2)

    # sizes[LISCH] = sizes[EISCH] = 10
    # sizes[LICH] = sizes[VICH] = 8
    # sizes[EICH] = 7
    sizes[LISCH] = sizes[EISCH] = 9
    sizes[LICH] = sizes[EICH] = sizes[VICH] = 7
    cellar = 2
    data = (10, 12, 20, 23, 32, 39, 40)
    data2 = (9, 11, 18, 27, 29, 36, 43, 45)
    data3 = (9, 11, 18, 27, 29, 36, 43, 45, 50)
    cellars[LICH] = cellars[EICH] = cellars[VICH] = cellar
    for t in types:
        hashfns[t] = lambda x, t=t: x % sizes[t]
    # datas = dict.fromkeys(types, data)
    # datas[EICH] = data2
    # datas = dict.fromkeys(types, data2)
    datas = dict.fromkeys(types, data3)

    # size = 5
    # data = (1, 5, 21, 10, 15)
    # sizes[LISCH] = sizes[EISCH] = size
    # hashfns[LISCH] = hashfns[EISCH] = lambda x: x % size
    # datas = dict.fromkeys(types, data)

    names = ("Ann", "Ben", "Cole", "Dana", "Edna", "Fred", "Gene", "Hugo", "Irma")
    hashes = {
        LISCH: (0, 2, 0, 3, 2, 9, 0, 8, 7),
        EISCH: (0, 2, 0, 3, 2, 9, 0, 2, 6),
        LICH: (0, 2, 0, 0, 2, 0, 7, 5, 8),
        EICH: (0, 2, 0, 0, 2, 0, 7, 0, 8),
        VICH: (0, 2, 0, 0, 2, 0, 2, 0, 6)
    }

    def names_hash(h: Tuple):
        return lambda name: h[names.index(name)]

    # sizes[LISCH] = sizes[EISCH] = 10
    # sizes[LICH] = sizes[EICH] = sizes[VICH] = 9
    # for t in types:
    #     hashfns[t] = names_hash(hashes[t])
    # cellar = 2
    # cellars[LICH] = cellars[EICH] = cellars[VICH] = cellar
    # datas = dict.fromkeys(types, names)
    # alignments = dict.fromkeys(types, 4)

    maps = dict()
    for t in (LISCH, EISCH):
        maps[t] = t(sizes[t], hashfns[t], alignments[t])
    for t in (LICH, EICH, VICH):
        if sizes[t] is not None:
            maps[t] = t(sizes[t], cellars[t], hashfns[t], alignments[t])

    map_type = LISCH
    hashmap = maps[map_type]

    for d in datas[type(hashmap)]:
        hashmap.insert(d)
        print(f"INSERT: {d} ({hashmap._hashfn(d)})")
        print(str(hashmap))