# Implementation of the Map ADT using closed hashing and a probe with 
# double hashing.

class HashMap :
  """A closed hashing with a double hashing probe"""

  def __init__( self ):                                     
    """Creates an empty map instance."""
    self.SIZE = 1277     # a prime number

    # Defines constants to represent the status of each table entry.
    self.UNUSED = None                                 
    self.EMPTY = _MapEntry( None, None )     

    # Create the data storage (empty hash table)
    self._table = [ self.UNUSED for i in range ( self.SIZE ) ]

    # keep track of the number of elements
    self._count = 0
    # set the maximum load factor to be 0.7
    self._maxCount = len(self._table) - len(self._table) // 3  
    
      
  def __len__( self ):
    """Returns the number of entries in the map."""
    return self._count

  def __contains__( self, key ):
    """ Determines if the map contains the given key."""
    slot, entry = self._findSlot( key, False )
    return entry is not None
    
  def _hash1( self, key ):                               
    """The main hash function for mapping keys to table entries."""
    return abs( hash( key ) ) % len( self._table )
#    return key % len( self._table )
    
  def _hash2( self, key, step ):
    """ The second hash function used with double hashing probes."""
    return 1 + abs( hash( key ) ) % ( len( self._table ) - 2 )    
#    return 1     # linear
#    return ( step + 1 )**2

  def print( self ):
    """Print the contents of the hash table using the iterator"""
    print( '[', end = '' )
    for v in self :
      print( v.key, end = ', ' )
    print(']')

  def add( self, key, value ):
    """Adds a new entry to the map if the key does not exist. Otherwise, the
    new value replaces the current value associated with the key.
    """

    if key in self :
      slot, entry = self._findSlot( key, False )
#      print( 'in key/value/slot : ', key, '/', value, '/', slot )
      self._table[ slot ].value = value
      return False
    else :
      slot, entry = self._findSlot( key, True )
#      print( 'not in key/value/slot : ', key, '/', value, '/', slot )
      self._table[ slot ] = _MapEntry( key, value )
      self._count += 1
      if self._count == self._maxCount :
        print( 'rehash ...' )
        self._rehash()
      return True   
      
  def valueOf( self, key ):
    """ Returns the value associated with the key."""
    slot, entry = self._findSlot( key, False )
    assert entry is not None, "Invalid map key for value."
    return entry.value
   
  def remove( self, key ):
    """ Removes the entry associated with the key."""

    # assert False, "Need to implement the 'remove()' method"
    slot, entry = self._findSlot( key, False )
    assert entry is not None, "Invalid map key for removal."
    self._table[ slot ] = self.EMPTY
    
  def __iter__( self ):
    """ Returns an iterator for traversing the keys in the map."""
    return _HashIterator( self._table )


  def _findSlot( self, key, forInsert ):         
    """Finds the slot containing the key or where the key can be added.
    forInsert indicates if the search is for an insertion, which locates
    the slot into which the new key can be added.
    """

    # Compute the home slot and the step size.
    slot = self._hash1( key )
  
    # Probe for the key.
    M = len(self._table)
    probCount = 0
    while self._table[ slot ] is not self.UNUSED and probCount < M :
      if (not forInsert) and self._table[ slot ].key == key :
        # we found the right spot
        break
      step = self._hash2( key, probCount )
      slot = (slot + step) % M               
      probCount += 1
    
    if probCount >= M :
      return -1, None
    else:
      return slot, self._table[ slot ]

  def _rehash( self ) :                        
    """ Rebuilds the hash table."""

     # Create a new larger table. 
    origTable = self._table
    newSize = len(self._table) * 2 + 1
    # Create the data storage (empty hash table)
    self._table = [ self.UNUSED for i in range ( newSize ) ]
    
     # Modify the size attributes.
    self._count = 0
    self._maxCount = newSize - newSize // 3     
    
     # Add the keys from the original array to the new table.
    for entry in origTable :
      if entry is not self.UNUSED and entry is not self.EMPTY :
        slot, item = self._findSlot( entry.key, True )
        self._table[ slot ] = entry
        self._count += 1                      
    

# Storage class for holding the key/value pairs.   
class _MapEntry :                       

  def __init__( self, key, value ):
    """Create the entry with key and value """
    self.key = key
    self.value = value 
  
  def __eq__( self, rhs ):
    """Overload __eq__ so items can be compared using '==' sign"""
    if rhs == None:
      return False
    return ( self.key == rhs.key and self.value == rhs.value )


# Hash Iterator
class _HashIterator:

  def __init__( self, theTable ):
    """Create the data set and the count"""
    self._table = theTable
    self._count = len( theTable )
    # Defines constants to represent the status of each table entry.
    self.UNUSED = None                                 
    self.EMPTY = _MapEntry( None, None )              
    self._curIndex = 0

  def __iter__( self ):
    return self

  def __next__( self ):
    """Return next entry in the hash table """
    if self._curIndex >= self._count :
      raise StopIteration
      
    element = self._table[ self._curIndex ]
    # skip over the un-used or empty entries
    while  self._curIndex < self._count and  \
          ( element == self.UNUSED or \
          element == self.EMPTY ) :
      self._curIndex += 1
      if self._curIndex < self._count :
        element = self._table[ self._curIndex ]

#    print( self._curIndex, self._count, end = ', ' )
    if self._curIndex >= self._count :
      raise StopIteration
    else :
      self._curIndex += 1
      return element