import java.util.LinkedList;
import java.util.Iterator;

public class MonsterHashTable {
	
	private LinkedList<KeyValuePair> ll[];
	private int bucketElements[];
	private KeyValuePair data[][];
	private int loadFactor;
	private int bucketSize;
	
	//create an index from the hash code of the key
	private int getIndexFromKey(Object key) {		
		return Math.abs(key.hashCode() % data.length);
	}
	
	//search a bucket to the end, and then search the list
	private Comparable searchBucketWithList(int index, Object key) {
		Comparable obj = searchBucket(index, bucketSize, key);
		KeyValuePair kvp = null;
		Iterator<KeyValuePair> itr = null;
		if(obj == null) {
			itr = ll[index].iterator();
			while(itr.hasNext()) {
				kvp = itr.next();
				if(key.equals(kvp.getKey()))
					obj = kvp.getValue();
			}
		}
		return obj;
	}
	
	//search a bucket to the specified index
	private Comparable searchBucket(int index, int maxBucket, Object key) {	
		KeyValuePair kvp = null;
		for(int i = 0; i < maxBucket; i++) {
			kvp = data[index][i];
			if(key.equals(kvp.getKey())) {
				return kvp.getValue();
			}
		}
		return null;
	}
	
	//search a bucket to the number of elements it contains
	private Comparable searchBucket(int index, Object key) {
		int numElements = bucketElements[index];
		return searchBucket(index, numElements, key);	
	}
	
	//find a key in a bucket
	private Comparable find(int index, Object key) {
		if(bucketElements[index] <= bucketSize)
			return searchBucket(index, key);
		else
			return searchBucketWithList(index, key);		
	}
	
	/**
	 * 
	 * @param numberBuckets the number of buckets
	 * @param bucketSize the size of each bucket
	 * @param loadFactor percentage of buckets to be filled for a reorganize
	 */
	public MonsterHashTable(int numberBuckets, int bucketSize, int loadFactor) {
		data 			= new KeyValuePair[numberBuckets][bucketSize];
		bucketElements 	= new int[numberBuckets];
		ll				= new LinkedList[numberBuckets];
		this.bucketSize = bucketSize;
		this.loadFactor = loadFactor;
	}
	
	
	private void addToList(int index, KeyValuePair kvp) {
		if(ll[index] == null)
			ll[index] = new LinkedList<KeyValuePair>();
		if(searchBucketWithList(index, kvp.getKey()) == null) {
			ll[index].add(kvp);
			bucketElements[index]++;
		}
	}
	
	private void addToBucket(int index, KeyValuePair kvp) {	
		if(searchBucket(index, kvp.getKey()) == null) {
			data[index][bucketElements[index]] = kvp;
			bucketElements[index]++;
		}
	}
	
	/**
	 * 
	 * @param key
	 * @param value
	 */
	public void add(Object key, Comparable value) {
		KeyValuePair kvp = new KeyValuePair(key, value);
		int index = getIndexFromKey(key);
		
		if(bucketElements[index] < bucketSize)
			addToBucket(index, kvp);
		else
			addToList(index, kvp);
	}
	
	/**
	 * 
	 * @param key
	 * @return
	 */
	public Comparable get(Object key) {
		return find(getIndexFromKey(key), key);
	}
	
	
	/**
	 * 
	 * @return
	 */
	public SortedIterator iterator() {
		
	}
	
	/**
	 * 
	 * @return
	 */
	public int numberCollisions() {
		
	}
	
	/**
	 * 
	 * @return
	 */
	public int numberOperations() {
		
	}
	
	
	/**
	 * 
	 * @param key
	 * @return
	 */
	public Comparable remove(Object key) {
		int index = getIndexFromKey(key);
		
	}
	
	/**
	 * 
	 * @param numberBuckets
	 * @param bucketSize
	 * @param loadFactor
	 */
	void reorganize(int numberBuckets, int bucketSize, int loadFactor) {
		
	}
	
	/**
	 * 
	 * @param key
	 * @param value
	 * @return
	 */
	public Comparable replace(Object key, Comparable value) {
		
	}
	
	/**
	 * 
	 * @return
	 */
	public String structureReport() {
		String str = "";
		for(int i = 0; i < data.length; i++) {
			for(int j = 0; j < bucketSize; j++) {
				if(data[i][j] != null) {
					str += "[" + data[i][j].getValue() + "] ";
				}	
				else
					str += "[ ] ";
			}
			if(ll[i] != null) {
				Iterator<KeyValuePair> itr = ll[i].iterator();
				str += ": ";
				while(itr.hasNext()) {
					str += " -> ";
					str += itr.next().getValue();
				}
			}
			str += "\n";
		}
		return str;
	}
}