import java.util.Arrays;

/**
 * A class implementing a hash table using open addressing.  The open addressing
 * scheme is quadratic probing -- try the locations 1, 4, 9, 16, ... positions
 * after the original location.
 *
 * @author Mark Young (A00000000)
 */
public class QuadraticProbeHashTable {
    
    private static final int DEFAULT_SIZE = 13;
    private static final double MAX_LOAD = 0.75;
    
    private Integer[] contents;
    private int numInTable;
    
    /**
     * Create an empty hash table.
     */
    public QuadraticProbeHashTable() {
        contents = new Integer[DEFAULT_SIZE];
        numInTable = 0;
    }
    
    /**
     * Add the given item to this HT.
     *
     * @param anItem the item to add.
     * @return true if {@code anItem} was added; false otherwise.
     */
    public boolean insert(int anItem) {
        int posn, step;
        
        // check for overload
        if ((numInTable + 1)/MAX_LOAD > contents.length) {
            if (!resize()) {
                return false;
            }
        }
        
        // insert the item (or fail if it's found)
        step = 0;
        do {
            posn = (anItem + step*step) % contents.length;
            if (contents[posn] == null) {
                contents[posn] = anItem;
                ++numInTable;
                return true;
            }
            if (contents[posn].equals(anItem)) {
                return false;
            }
            ++step;
        } while (true);
    }
    
    /**
     * Remove the given item from this HT.STUB!
     *
     *
     * @param anItem the item to remove.
     * @return true if {@code anItem} was deleted; false otherwise.
     */
    public boolean delete(int anItem) {
        throw new UnsupportedOperationException();
    }
    
    /**
     * Check whether this HT contains the given value.
     *
     * @param anItem the item to check for.
     * @return true if anItem is in this HT; false otherwise.
     */
    public boolean contains(int anItem) {
        int posn, step;
        
        // look for the item
        step = 0;
        do {
            posn = (anItem + step*step) % contents.length;
            if (contents[posn] == null) {
                return false;
            }
            if (contents[posn].equals(anItem)) {
                return true;
            }
            ++step;
        } while (true);
    }
    
    /**
     * Make a String representation of this HT.
     *
     * @return a String representing the array of this HT's contents.
     */
    @Override
    public String toString() {
        return Arrays.toString(contents);
    }
    
    /**
     * Make this HT larger.
     *
     * STUB!
     *
     * @return true if this HT was enlarged; false otherwise.
     */
    private boolean resize() {
        return false;
    }

}