# Implementation of the Map ADT using closed hashing and a probe with 
# double hashing.
from array204 import Array

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

  def __init__( self, size = 7 ):                                     
    """Creates an empty map instance."""
    self._table = Array( size )   # some prime number to begin with
    self._count = 0
    # set the maximum load factor to be 0.7
    self._maxCount = len(self._table) - len(self._table) // 3  
    
    # Defines constants to represent the status of each table entry.
    self.UNUSED = None                                 
    self.EMPTY = _MapEntry( None, None )              
  
      
  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 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.
    return True if adding or replacing is successful
    return False if the table is full (rehash is commented out for now.)
    """

    if key in self :
      slot, entry = self._findSlot( key, False )
      # print( 'in key/value/slot : ', key, '/', value, '/', slot )
      self._table[ slot ].value = value
      return True
    else :
      slot, entry = self._findSlot( key, True )
      # print( 'not in key/value/slot : ', key, '/', value, '/', slot )
      if slot == -1:
          return False   # can't insert any more
      else:
          self._table[ slot ] = _MapEntry( key, value )
          self._count += 1
          if self._count == self._maxCount :
              #return False
              
              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.
    """
    probCount = 0
    M = len(self._table)
    step = 2
    slot = self._hash1(key)   # initial slot
    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
        #slot = (slot + step*step) % M  # quadratic prob
        slot = (slot + step) % M  
        step *= 2
        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
    self._table = Array( 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                      
    
  def _hash1( self, key ):                               
    """The main hash function for mapping keys to table entries."""
    return abs( hash( key ) ) % len( self._table )
    
  def _hash2( self, key ):
    """ The second hash function used with double hashing probes."""
    return 1 + abs( hash( key ) ) % ( len( self._table ) - 2 )    

# 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