class Array(object):

 def __init__(self, size=32, init=None):
  self._size = size
  self._items = [init] * self._size

 def __getitem__(self, index):
  return self._items[index]

 def __setitem__(self, index, value):
  self._items[index] = value

 def __len__(self):
  return self._size

 def clear(self, value=None):
  for i in range(len(self._items)):
   self._items[i] = value

 def __iter__(self):
  for item in self._items:
   yield item

class Slot(object):
 """定义一个 hash 表 数组的槽
 注意，一个槽有三种状态，看你能否想明白
 1.从未使用 HashMap.UNUSED。此槽没有被使用和冲突过，查找时只要找到 UNUSED 就不用再继续探查了
 2.使用过但是 remove 了，此时是 HashMap.EMPTY，该探查点后边的元素扔可能是有key
 3.槽正在使用 Slot 节点
 """
 def __init__(self, key, value):
  self.key, self.value = key, value

class HashTable(object):
 # 表示从未被使用过
 UNUSED = None
 # 使用过，但是被删除了
 EMPTY = Slot(None, None)

 def __init__(self):
  self._table = Array(8, init=HashTable.UNUSED)
  self.length = 0

 # 负载因子
 @property
 def _load_factor(self):
  return self.length/float(len(self._table))

 def __len__(self):
  return self.length

 # 哈希函数 用内置的哈希哈数进行哈希一下，然后对数组长度取模
 def _hash(self, key):
  return abs(hash(key)) % len(self._table)

 def _find_key(self, key):
  # 得到第一个值的位置
  index = self._hash(key)
  _len = len(self._table)
  # 当这个槽不是未使用过的，才接着往下找；如果是未使用过的，这个key肯定不存在
  while self._table[index] is not HashTable.UNUSED:
   # 槽使用过，但是被删除了
   if self._table[index] is HashTable.EMPTY:
    # cpython解决哈希冲突的一种方式
    index = (index*5 + 1) % _len
    continue
   elif self._table[index] == key:
    return index
   else:
    index = (index * 5 + 1) % _len
  return None

 # 检测槽是否能被插入
 def _slot_can_insert(self, index):
  return (self._table[index] is HashTable.EMPTY or self._table[index] is HashTable.UNUSED)

 # 找到能被插入的槽的index
 def _find_slot_insert(self, key):
  # 得到第一个值的位置
  index = self._hash(key)
  _len = len(self._table)
  while not self._slot_can_insert(index):
   index = (index * 5 + 1) % _len
  return index

 # in 操作符
 def __contains__(self, key):
  index = self._find_key(key)
  return index is not None

 def add(self, key, value):
  if key in self:
   index = self._find_key(key)
   # 更新值
   self._table[index].value = value
   return False
  else:
   index = self._find_slot_insert(key)
   self._table[index] = Slot(key, value)
   self.length += 1
   if self._load_factor > 0.8:
    return self._rehash()
   return True

 def _rehash(self):
  oldtable = self._table
  newsize = len(self._table) * 2
  # 新的table
  self._table = Array(newsize, HashTable.UNUSED)
  self.length = 0
  for slot in oldtable:
   if slot is not HashTable.UNUSED and slot is not HashTable.EMPTY:
    index = self._find_slot_insert(slot.key)
    self._table[index] = slot
    self.length += 1

 def get(self, key, default=None):
  index = self._find_key(key)
  if index is None:
   return default
  else:
   return self._table[index].value

 def remove(self, key):
  index = self._find_key(key)
  if index is None:
   raise KeyError
  value = self._table[index].value
  self.length -= 1
  # 把槽设置为空槽
  self._table[index] = HashTable.EMPTY
  return value

 def __iter__(self):
  for slot in self._table:
   if slot not in (HashTable.UNUSED, HashTable.EMPTY):
    yield slot.value


class SetADT(HashTable):

 def add(self, key):
  return super(SetADT, self).add(key, True)

 def __and__(self, other_set):
  # 求交集
  new_set = SetADT()
  for element_a in self:
   if element_a in other_set:
    new_set.add(element_a)
  return new_set

 def __sub__(self, other_set):
  # 求差集
  new_set = SetADT()
  for element_a in self:
   if element_a not in other_set:
    new_set.add(element_a)
  return new_set

 def __or__(self, other_set):
  # 求交集
  new_set = SetADT()
  for element_a in self:
   new_set.add(element_a)
  for element_b in other_set:
   new_set.add(element_b)
  return new_set