class QuadraticHashTable():
    """Is a child class of OpenAddressHashTable.
    If a collision then uses a quadratic probing function to find a free slot
    >>> hash_table = QuadraticHashTable(11)
    >>> hash_table.store('Dianna')
    >>> hash_table.store('Bobby')
    >>> hash_table.store('Dirk')
    >>> hash_table.store('Darlene')
    >>> hash_table.store('Paul')
    >>> hash_table.store('Paula')
    >>> hash_table.store('David')
    >>> hash_table.store('Harry')
    >>> print(hash_table)
    QuadraticOpenAddressHashTable:
    slot        0 = David
    slot        1 = Darlene
    slot        2 = Paul
    slot        3 = -
    slot        4 = Paula
    slot        5 = Harry
    slot        6 = Dirk
    slot        7 = -
    slot        8 = -
    slot        9 = Dianna
    slot       10 = Bobby
    n_slots = 11
    n_items in table = 8
    Load factor =  0.727
    <BLANKLINE>
    >>> 'Harry' in hash_table
    True
    >>> 'Paul' in hash_table
    True
    >>> 'Paula' in hash_table
    True
    >>> 'David' in hash_table
    True
    >>> 'Bobby' in hash_table
    True
    >>> 'Dianna' in hash_table
    True
    >>> 'Dirk' in hash_table
    True
    >>> 'Darlene' in hash_table
    True
    >>> 'Dingus' in hash_table
    False

    """

    def __init__(self, slots=11):
        """
        Creates a new hashtable with a number of slots (default: 10).
        Remember we can't have a load factor greater than 1 for an open hash...
        """
        self._data = [None for i in range(slots)]
        self.n_slots = slots
        self.n_items = 0

    def _next_free_slot(self, first_hash):
        """
        Keeps incrementing hash index until an empty slot is found.
        Then returns the index of that slot.
        Used by the store method to help deal with a collisions.
        Note: this method isn't useful in __contains__ but you shoul
              follow a similar series of probing there.
        """
        curr_index = first_hash
        try_number = 0
        tried = []
        #print self._data
        while self._data[curr_index] is not None:
            tried.append(curr_index)
            try_number += 1
            if try_number > self.n_slots // 2:
                #print self._data
                print('Size = ' + str(self.n_slots))
                print('Number of items = ' + str(self.n_items))
                print('Failed to find an empty slot...')
                print('Try number = ' + str(try_number))
                print('List of tried slots = ' + str(tried))
                print('Current table = ' + str(self._data))
                print('*** Failed to find an empty slot!!!! ')
                print('*** This can happen with quadratic probing')
                print('*** if the table is over half full')
                raise ValueError('Failed to find an empty slot!!!!')
            else:
                curr_index = (first_hash + try_number**2) % self.n_slots
        return curr_index

    def store(self, item):
        """Stores an item in the hashtable."""
        if self.n_slots == self.n_items:
            #Argh - crash, who made the hashtable too small?
            print(self._data)
            print('Size = ' + str(self.n_slots))
            print('Slots used = ' + str(self.n_items))
            print("Hash table is full!!!! You eeediot")
            print("A good Hasher would have resized the hash table by now!")
            raise ValueError("Hash table is full!!!!")
        # **************************************************
        # ---start student section---
        index_initial = self._hash(item)
        index_current = self._hash(item)
        i_counter = 0
        if not self.__contains__(item):
            slot_found = False
            while slot_found == False:
                if self._data[index_current] == None:
                    self._data[index_current] = item
                    slot_found = True
                else:
                    index_current = index_initial + i_counter^2
                    i_counter += 1
                    if index_current == self.n_slots:
                        index_current = 1
        # ===end student section===
        self.n_items += 1

    def _hash(self, item):
        """Computes the hash of an item."""
        return nice_hash(item) % self.n_slots

    def __contains__(self, item):
        """
        Checks to see if an item is stored within the hashtable.
        Returns True if it is, otherwise it returns False.
        Note: The function should give up and return False if
        the try_number reaches the number of slots in the table.
        At this stage we definitely know we are in a never ending
        cycle and will never find the item...
        You can call this method using Python's 'in' keyword:
            ht = HashTable()
            ...
            if 'foo' in ht:
                ...
        """
        first_hash = self._hash(item)
        i_counter = 0
        try_number = 0
        current_index = first_hash
        # ---start student section---
        first_hash = self._hash(item)
        have_wrapped = False
        if self._data[first_hash] == item:
            return True
        else:
            current_index = first_hash
            while self._data[current_index] is not None:
                if self._data[current_index] == item:
                    # horay we found it
                    return True
                if (current_index == first_hash) and have_wrapped:
                    # back to original hash and didn't find item
                    # phew - the hashtable is full!
                    return False
                if current_index == (self.n_slots -1):
                    # wrap back to start of hash table
                    current_index = 0
                    have_wrapped = True
                else:
                    current_index = (first_hash + i_counter^2) % self.n_slots
        # ===end student section===

    def __str__(self):
        output = 'QuadraticOpenAddressHashTable:\n'
        for i in range(self.n_slots):
            output += f'slot {i:8} = '
            item = self._data[i]
            if item == None:
                output = output + '-'
            else:
                output = output + str(item)
            output += '\n'
        load_factor = float(self.n_items) /self.n_slots
        output += f'n_slots = {self.n_slots}\n'
        output += f'n_items in table = {self.n_items}\n'
        output += f'Load factor = {load_factor:6.3f}\n'
        return output

    def __repr__(self):
        return str(self)