#!/usr/bin/env python3
# -*- coding:utf-8 -*-

class ADTMap:
    def __init__(self) -> None:
        # 初始容量为8
        self.cap = 8
        # 已有键值对个数为0
        self.size = 0
        # 初始map
        self.map = [[None] * 3] * self.cap
        # map顺序表
        self.order = [None] * self.cap

    def set(self, key, value):
        # 求hash值
        hashValue = self.__getHash(key)
        # 求插入或者更新槽位
        slotIdx = self.__getSlot(hashValue)
        # 检查是否需要扩容, 当容量超过三分之二时，即进行扩容（resize）机制
        if (self.size + 1 > round(self.cap * (2 / 3))):
            self.__resize()
        # 添加键值对
        self.map[slotIdx] = [hashValue, key, value]
        self.size += 1
        # 添加顺序表，如果是更新value，则不用添加
        for i in range(len(self.order)):
            if self.order[i] is None or slotIdx == self.order[i]:
                self.order[i] = slotIdx
                break

    def get(self, key):
        # 求hash值
        hashValue = self.__getHash(key)
        # 求key所在槽位
        slotIdx = self.__getSlot(hashValue)
        return self.map[slotIdx][2]

    def pop(self, key):
        # 求hash值
        hashValue = self.__getHash(key)
        # 求key所在槽位
        slotIdx = self.__getSlot(hashValue)
        if self.map[slotIdx][2] == None:
            raise KeyError("%s" % key)

        # 移除key
        self.size -= 1
        retValue = self.map[slotIdx][2]
        self.map[slotIdx] = [None] * 3
        for idx in range(len(self.order)):
            if self.order[idx] == slotIdx:
                # 删除
                del self.order[idx]
                # 在最后添加空的，确保前面都是有序的不会出现None
                self.order.append([None] * 3)
                break
        return retValue

    def keys(self):
        for idx in self.order:
            if idx is not None:
                yield self.map[idx][1]
            else:
                break

    def values(self):
        for idx in self.order:
            if idx is not None:
                yield self.map[idx][2]
            else:
                break

    def items(self):
        for idx in self.order:
            if idx is not None:
                yield self.map[idx][1], self.map[idx][2]
            else:
                break

    def clear(self):
        self.cap = 8
        self.size = 0
        self.map = [[None] * 3] * self.cap
        self.order = [None] * self.cap

    def __setitem__(self, name, value):
        self.set(key=name, value=value)

    def __getitem__(self, name):
        return self.get(key=name)

    def __delitem__(self, name):
        # del map["k1"] 无返回值
        self.pop(key=name)

    def __contains__(self, item):
        keyList = self.keys()
        for key in keyList:
            if key == item:
                return True
        return False

    def __iter__(self):
        # 直接迭代map则返回keys列表
        return self.keys()

    def __getHash(self, key):
        # int类型的keyhash值是其本身
        if isinstance(key, int):
            return key
        # str类型需要使用ord()进行转换，并添加位权
        if isinstance(key, str):
            idx = 0
            v = 0
            while idx < len(key):
                v += ord(key[idx]) * (idx + 1)
                idx += 1
            return v

        # 暂不支持其他类型
        raise KeyError("key not supported type %s" % (type(key)))

    def __getSlot(self, hashValue):
        # 求初始槽位
        slotIdx = hashValue % (self.cap)
        # 检测没有hash冲突的槽位
        return self.__checkSlot(slotIdx, hashValue)

    def __checkSlot(self, slotIdx, hashValue):
        # 获取原有槽位的hash
        slotHash = self.map[slotIdx][0]

        # 如果原有槽位不为空，且与新的key值hash不同
        if slotHash is not None and slotHash != hashValue:
            # 避免线性探测超过散列表长度
            if slotIdx < self.cap - 1:
                return self.__checkSlot(slotIdx + 1, hashValue)
            # 如果线性探测超过散列表长度，则从头开始探测
            return self.__checkSlot(0, hashValue)

        # 否则就是空槽位，或者旧hash与新hash相同，直接返回即可
        return slotIdx

    def __resize(self):
        # 计算新容量，已有散列表键值对个数 * 2
        self.cap += self.size * 2
        # 执行扩容
        self.map.extend(
            [[None] * 3] * (self.size * 2)
        )
        # 顺序表也进行扩容
        self.order.extend([None] * (self.size * 2))

    def __len__(self):
        return self.size

    def __str__(self) -> str:
        retStr = ""
        for idx in self.order:
            if idx is not None:
                retStr += " <%r : %r> " % (self.map[idx][1], self.map[idx][2])
            else:
                break
        retStr = "[" + retStr + "]"
        return retStr