import java.io.*;
import java.lang.*;

abstract public class AbstractHashTable {
	// Methods already exist in Part A

	// In your implementation, the constructor must take an int argument
	// as table size/capacity. If the argument is negative or not a prime,
	// set the table size to be the smallest prime larger than requested
	// size. Unlike class Hashtable in JDK, the hash table in this
	// programming assignment is not expandable.

	// Returns the size/capacity of hash table.
	abstract public int getSize ();

	// For grading purpose, the public variable probeCount is incrememted
	// by 1 whenever a probe was made, useful or useless, as
	// put/containsKey/remove routines are called.
	public int probeCount;

	// Returns true if the input i is a prime; otherwise return false.
	public static boolean isPrime (int i) {
		if (i <= 1)
			return false;
		for (int j = (int)Math.sqrt((double)i); j>1; j--)
			if (i%j == 0)
				return false;
		return true;
	}

	// Returns the hash value of the given key.
	// See Horner's rule and MAD method in lecture slides.
	public int hashValue (String key) {
		int hashVal = 0;
		for (int i=0; i<key.length(); i++)
			hashVal = 37*hashVal + key.charAt(i);
		hashVal %= getSize();
		if (hashVal < 0)
			hashVal += getSize();
		return hashVal;
	}

	// Returns the hash value of the given key for probing.
	public int probeHashValue (String key) {
		if (getSize() <= 2)
			return 1;
		int hashVal = 0, p;
		for (int i=0; i<key.length(); i++)
			hashVal = 41*hashVal + key.charAt(i);
		for (p = getSize()-1; !isPrime(p); p--)
			; // p is the largest prime less than getSize()
		hashVal %= p;
		if (hashVal < 0)
			hashVal += p;
		return p-hashVal;
	}

	// Note that in the following 3 routines, you need to call
	// probeHashValue(key) to get probing offset.

	// Maps the specified key to the specified value in this hashtable.
	// Returns true if succeed, false if failed.
	// If the table is full or there is a duplicate key already in the
	// table, then return false.
	abstract public boolean put (String key, Object value);

	// Tests if some key maps into the specified value in this hashtable.
	abstract public boolean containsKey (String key);

	// Removes the key (and its corresponding value) from this hashtable.
	// Returns true if succeed, false if not found.
	abstract public boolean remove (String key);


	// Methods new in Part B

	// Returns the value to which the specified key is mapped in this
	// hashtable.
	abstract public Object get (String key);

	// Returns the longest length of successful probe sequence.
	abstract public int longestProbe ();
}