import java.util.Random;

/**
 * @author Andrew Rau-Chaplin
 * 
 * Partial implementation of the Set of Strings ADT 
 * - Defines constructor, hash functions, and a simple test class
 * - Designed for double hashing based on a pair of universal hash functions selected at random.
 * - Designed for tables of size m = 2^c for c in {1..32}
 * See http://en.wikipedia.org/wiki/Universal_hashing for details
 */
public class StringSet {

	int c; //log_2 of the hash table size
	int m; //table size
	int size; //the number of items in the hash table
	long a,b,a1,b1; //constants for universal hash functions
	final long p = 2236133941L; //the smallest prime number bigger than 2^32

	String[] buckets; //The hashtable
	
	public StringSet(int cap) {
	
		if(cap > 32 || cap < 1)
	        throw new IllegalArgumentException("Capacity not in range 2^1 ... 2^32");
	        
		c = cap;
		m = (int) Math.pow(2, c);
		size = 0;
		
		//Ideally we should be generating random values in the between 0 (or 1) and p
		//but p is larger than an int can hold so we will cheat a little and 
		//make the top end of the range to be the max int (instead of p).
		Random rand = new Random();
		a = Math.abs(rand.nextInt()) + 1; 
		a1 = Math.abs(rand.nextInt()) + 1;
		b = Math.abs(rand.nextInt());
		b1 = Math.abs(rand.nextInt());
		
		buckets = new String[m];
	}
	
	//Hash function h1 generates first probe location
	private long h1(int k){
		return ((a*k+b) % p);
	}
	
	//Hash function h2 generates step size used on collisions
	private long h2(int k){
		return ((a1*k+b1) % p) | 1; //Step size guaranteed to be odd and therefore mutually prime with m
	}
	
	//Example of double hashing of String s on attempt number i
	private int doubleHash(String s, int i){
		int k = Math.abs(s.hashCode()); //Map string to a 32 bit int
		return (int)((h1(k) + i * h2(k)) % m);
	}

	//Test
	public static void main(String[] args) {
		StringSet s = new StringSet(10); //Create a 2^10 = 1024 bucket hashtable
		int probeCounts[] = new int[1024]; 
		int probedOnce = 0;

		//The first 1024 places to look for happiness
		//probe the table 1024 times and add 1 to each probed location
		for (int j = 0; j<1024; j++){
			probeCounts[s.doubleHash("happiness", j)]++;
		}
		
		//Count of locations that were probed exactly once? Should be 1024!
		for (int j = 0; j<1024; j++)
			if (probeCounts[j] == 1) probedOnce++;
		System.out.println("Count of locations probed once: " + probedOnce);
		
	}
}