#
# Kingston 7.24
#

class Hashtable:

  def __init__(self, size):
    self.list = [None] * (size + 1)
    self.maxsize = size
    self.size = 0
    
  def __repr__(self):
    return `self.list`
        
  def hashfunc(self, x):
    return x % len(self.list)
    
  def insert(self, x):
    """Indsætter x i hashtabellen hvis der er plads"""
    if self.size >= self.maxsize:
      raise "Hashtable full"
    
    i = self.hashfunc(x)
    
    if self.list[i] != None:
      starthash = self.hashfunc(self.list[i])
      
      while self.list[i] != None:
        y = self.list[i]
        if (self.hashfunc(y) - starthash) % len(self.list) > \
           (self.hashfunc(x) - starthash) % len(self.list):
          self.list[i] = x
          x = y
        i = (i + 1) % len(self.list)
      
    self.list[i] = x
    self.size = self.size + 1
    
  def empty(self):
    """Returnerer sand, hvis hashtabellen er tom"""
    return self.size == 0

  def find(self, x):
    """Returnerer x, hvis x er i hashtabellen - ellers returneres None"""
    
    i = self.hashfunc(x)
    
    if self.list[i] != None:
      starthash = self.hashfunc(self.list[i])
      
      while self.list[i] != None and self.list[i] != x:
        y = self.list[i]
        if (self.hashfunc(y) - starthash) % len(self.list) > \
           (self.hashfunc(x) - starthash) % len(self.list):
          return None
        i = (i + 1) % len(self.list)

    return self.list[i]    
    
  def delete(self, x):
    """Sletter x fra hashtabellen - hvis x ikke er der, gives der en exception"""
    if self.empty():
      raise "Hashtable empty"
    
    i = self.hashfunc(x)
    
    # find først x (som under .find())
    if self.list[i] != None:
      starthash = self.hashfunc(self.list[i])
      
      while self.list[i] != None and self.list[i] != x:
        y = self.list[i]
        if (self.hashfunc(y) - starthash) % len(self.list) > \
           (self.hashfunc(x) - starthash) % len(self.list):
          raise "Element not found"
        i = (i + 1) % len(self.list)

    if self.list[i] == None:
      raise "Element not found"
    else:
      # vi har fundet x i listen - slet x
      self.list[i] = None
      self.size = self.size - 1
      lastNone = i
      i = (i + 1) % len(self.list)
      
      # og flyt evt. nogle elementer
      while self.list[i] != None:
        y = self.list[i]
        if (lastNone - self.hashfunc(y)) % len(self.list) < \
           (i        - self.hashfunc(y)) % len(self.list):
          self.list[lastNone] = self.list[i]
          self.list[i] = None
          lastNone = i
        i = (i + 1) % len(self.list)
        

#
# Test
#

h = Hashtable(9)

elms = [7,7,9,9,8,1,6,6,9]

for x in elms:
  h.insert(x)
  print h
  
for x in range(10):
  print x,x in elms,h.find(x)

for x in elms:
  h.delete(x)
  print h