class DoubleHash(object):
    '''
    This class implements the basic functionality of a hash table
    using the double hashing approach.
    
    @author: Otto Sepp\u00E4l\u00E4, santtu
    '''

    SMALL_PRIME = 7
    # A small prime used by the second hash function.

    LOAD_FACTOR = 0.7
    # The limit for performing a rehash. In practice this is 
    #  the portion of array indices used for keys. 

    NOT_FOUND = -1
    # A value used for internal messaging about items not found.

    def __init__(self, initial_size):
        '''
        Creates a hash table with the requested size.
        
        @param initial_size: The initial size of the table inside the hash
                            structure. This should always be prime.
        '''
        self.table = [None] * initial_size    # The table used to store the hashed items.
        self.item_count = 0   # The amount of items contained in the hash structure.

    def first_hash(self, item):
        '''
        first hash function.
        
        @param item: The item for which this function calculates a value. The value
                     is used as an initial candidate for an index in the array.
        
        @return: value of the hash function (initial candidate for an index)
        '''
        return item.get_value_to_hash() % len(self.table)

    def second_hash(self, item):
        '''
        Second hash function.
        
        @param item: The item for which this function calculates a value. The value
        is used as an offset from the value found with the first_hash-method. 
        
        @return: value of the second hash function (used as an offset)
        '''
        return DoubleHash.SMALL_PRIME - (item.get_value_to_hash() % DoubleHash.SMALL_PRIME)

    def delete(self, item):
        '''
        Removes the given item from the structure.
        
        @param item: The item to be removed
        @return: did the deletion succeed
        '''

        position = self.find_item(item)

        if position == DoubleHash.NOT_FOUND:
            return False

        self.table[position] = 'DELETED' # Marks the position as used, but later deleted
        self.item_count -= 1
        return True


    def find_item(self, item):
        '''
        Attempts to find the given item. If found, the method returns the
        index in which the item was found.
        
        @param item: The item to be found 
        @return: the index where the item was found
        '''
        current_position = self.first_hash(item) # The first index candidate

        # As long as the spot is not completely empty
        # and the item sought for is not there, keep trying
        # new indices.

        while self.table[current_position] and item != self.table[current_position]:
            current_position += self.second_hash(item) # The value of the second hash-function is used as an offset
            current_position = current_position % len(self.table)

        # Either we found an empty spot or we found the key.
        # Tell the caller which one happened.

        if self.table[current_position]:
            return current_position
        else:
            return DoubleHash.NOT_FOUND

    def insert(self, item):
        '''
        Inserts the given item in the hash structure.
        
        @param item: The item to be inserted 
        '''

        # First check the load factor and perform rehash if needed.

        if self.item_count > len(self.table) * DoubleHash.LOAD_FACTOR:
            self.rehash()

        self.item_count += 1

        current_position = self.first_hash(item) # The first index candidate

        # Any empty or previously used spot will suffice.

        while self.table[current_position] not in [None, 'DELETED']:
            current_position += self.second_hash(item) # The value of the second hash-function is used as an offset
            current_position = current_position % len(self.table)

        # The index was found, let's put the item in.

        self.table[current_position] = item

    def rehash(self):
        '''
        Performs a rehash. This method is automatically called by insert
        when the load factor is exceeded.
        '''

        # Create a new table with at least twice the size.
        # Make sure the size is prime.

        old_table = self.table
        self.table = [None] * self.next_prime(len(old_table))

        # There are no items in the new table yet (insert will update this)
        self.item_count = 0

        # Rehash everything else but empty spots and deleted-markers.

        for i in range(len(old_table)):
            if old_table[i]  not in [None, 'DELETED']:
                self.insert(old_table[i])

    def next_prime(self, old):
        '''
        Given an integer, the method calculates the next prime number
        which is at least twice the given number.
        
        @param old: the value which the prime should be twice as big
        @return: the prime value found
        '''

        #************************************//
        # EXERCISE 1.1          
        #
        # PLEASE IMPLEMENT ME!
        #************************************//
        return 5 # Dummy mock-up value