import java.util.*;

public class HashTableTester {
	public static void main(String[] args) {
		testInsertLookup();
		testInsertDelete();
		testDump();
		testExceedLoadFactor();
		testChaining();
		testExceedMaxChainLength();
		header("done testing");
	}

	private static void testInsertLookup() {
		header("testing insert/lookup");
		HashTable<Item> table = new HashTable<Item>(11, 10.0); 
	
		try {
			table.insert(null);
			error("insert(null) did not throw exception");
		} catch (NullPointerException e) {
			// expected
		} catch (Exception e) {
			error("insert(null) threw wrong exception");
		}
		
		for (int i = 0; i < 10; i++)
			try {
			table.insert(new Item(i, ""+i));
			} catch (Exception e) {
				error("insert(" + i + ") threw exception " + e.toString());
			}
		
		// look for each item that was just inserted
		for (int i = 0; i < 10; i++) {
			try {
			Item value = table.lookup(new Item(i, ""));
			if (value == null)
				error("lookup failed to find item in table");
			else if (!value.id.equals(""+i))
				error("lookup didn't return exact item inserted into table");
			else {
				value = table.lookup(new Item(i, ""));
				if (value == null)
					error("lookup failed to find item second time in table");
				else if (!value.id.equals(""+i))
					error("lookup second time didn't return exact item inserted into table");
			}
			} catch (Exception e) {
				error("lookup(" + i + ") threw exception " + e.toString());
			}
		}
		
		// look for stuff not in the table
		for (int i = 20; i < 25; i++) {
			try {
				Item value = table.lookup(new Item(i, ""));
				if (value != null)
					error("lookup found item not inserted into table");
			} catch (Exception e) {
				error("lookup(" + i + ") threw exception " + e.toString());
			}
		}
	}
	
	private static void testInsertDelete() {
		header("testing insert/delete");
		HashTable<Item> table = new HashTable<Item>(11, 10.0); 
		
		for (int i = 0; i < 10; i++)
			try {
			table.insert(new Item(i, ""+i));
			} catch (Exception e) {
				error("insert(" + i + ") threw exception " + e.toString());
			}
		
		// delete for each item that was just inserted
		for (int i = 0; i < 10; i++) {
			try {
			Item value = table.delete(new Item(i, ""));
			if (value == null)
				error("delete of item inserted into table returned null");
			else if (!value.id.equals(""+i))
				error("delete didn't return exact item inserted into table");
			else {
				value = table.lookup(new Item(i, ""));
				if (value != null)
					error("lookup after delete was not null");
				value = table.delete(new Item(i, ""));
				if (value != null)
					error("delete second time was not null");
			}
			} catch (Exception e) {
				error("unexpected exception " + e.toString());
			}
		}
		
		// delete stuff not in the table
		for (int i = 20; i < 25; i++) {
			try {
				Item value = table.delete(new Item(i, ""));
				if (value != null)
					error("delete of item not inserted into table was not null");
			} catch (Exception e) {
				error("delete(" + i + ") threw exception " + e.toString());
			}
		}
	}

	private static void testDump() {
		header("testing dump");
		HashTable<Item> table = new HashTable<Item>(11, 10.0);
		System.out.println("Empty hashtable:");
		table.dump(System.out);  // dump empty table
		System.out.println();
		
		for (int i = 0; i < 10; i++) {
			try {
			table.insert(new Item(i, ""+i));
			} catch (Exception e) {
				error("insert(" + i + ") threw exception " + e.toString());
			}
		}
		
		System.out.println("Hashtable with 10 items");
		table.dump(System.out);
		System.out.println();
	}
	
	private static void testExceedLoadFactor() {
		header("testing exceeding load factor");
		HashTable<Item> table = new HashTable<Item>(11, 1.0); 
		
		for (int i = 0; i < 90; i+=10) {
			try {
			table.insert(new Item(i, ""+i));
			} catch (Exception e) {
				error("insert(" + i + ") threw exception " + e.toString());
			}
		}
			
		// display stats - table should still have size 11
		table.displayStats(System.out);
		table.dump(System.out);
		
		try {
			table.insert(new Item(90, ""+90));
			// load factor not yet reached - should not resize
			table.displayStats(System.out);
			table.dump(System.out);
		} catch (Exception e) {
			error("insert(90) threw exception " + e.toString());
		}
		
		try {
			table.insert(new Item(100, ""+100));
			// hit load factor exactly - should not resize
			table.displayStats(System.out);
			table.dump(System.out);
		} catch (Exception e) {
			error("adding item to cause exact load factor threw exception " + e.toString());
		}
		
		try {
			table.insert(new Item(110, ""+110));
			// load factor exceeded - should resize to table size 23
			table.displayStats(System.out);
			table.dump(System.out);
		} catch (Exception e) {
			error("adding item to exceed load factor threw exception " + e.toString());
		}
	}
	
	private static void testChaining() {
		header("testing chaining");
		HashTable<Item> table = new HashTable<Item>(11, 10.0);
		
		for (int i = 0; i < 5; i++) {
			try {
			table.insert(new Item(5, ""+i));
			} catch (Exception e) {
				error("insert(" + i + ") threw exception " + e.toString());
			}
		}
		table.dump(System.out);  // all should be in same bucked in order
	}
	
	private static void testExceedMaxChainLength() {
		header("testing exceed max chain length");
		HashTable<Item> table = new HashTable<Item>(5, 10.0, 2);
		
		for (int i = 0; i < 5; i++) {
			try {
			table.insert(new Item(i, ""+i));
			} catch (Exception e) {
				error("insert(" + i + ") threw exception " + e.toString());
			}
		}
		// all chains of length 1
		table.displayStats(System.out);
		table.dump(System.out);  
		
		for (int i = 5; i < 10; i++) {
			try {
			table.insert(new Item(i, ""+i));
			} catch (Exception e) {
				error("insert(" + i + ") threw exception " + e.toString());
			}
		}
		// all chains of length 2
		table.displayStats(System.out);
		table.dump(System.out);  
		
		// cause 1 resize
		for (int i = 10; i < 13; i++) {
			try {
			table.insert(new Item(i, ""+i));
			} catch (Exception e) {
				error("insert(" + i + ") threw exception " + e.toString());
			}
		}
		table.displayStats(System.out);
		table.dump(System.out);  
	}
	
	private static void error(String msg) {
		System.out.println("ERROR: " + msg);
	}
	
	private static void header(String msg) {
		System.out.println("***** " + msg + " *****");
	}
}


class Item implements Comparable<Item> {
	int value;
	String id;
	
	Item(int v, String i) { 
		value = v;
		id = i;
	}
	
	public int compareTo(Item other) { return (value - other.value); }
	
	public String toString() { return value + "(" + id + ")"; }
	
	public boolean equals(Object obj) {
		if (obj == null || !(obj instanceof Item)) return false;
		return value == ((Item)obj).value;
	}
	
	public int hashCode() { return value; }
}