
public class HashTable {

	private HashNode []array;
	private int noOfObject;

	public HashTable(int noOfElement) {

		array = new HashNode[firstPrime(2*noOfElement)];

	}

	public void print(){
		for (int i = 0; i < array.length; i++) {
			if(array[i]==null)
				System.out.println(i+", -----");
			else
				System.out.println(i+", "+array[i]);
		}
	}
	
	public void insert(String key,Object data){
		if(noOfObject == (int)array.length/2)
		reHash();

		int index = getStringIndex(key) % array.length ;
		int i=0;

		while(array[index] != null){
			//++index;
			
			//index  = index % array.length;
			index = getNextIndex(key, ++i);
			
			
		}

		array[index] = new HashNode(data, key);

		++noOfObject;



	}
	public int getNextIndex(String s,int index){
		return (getStringIndex(s) + index*index) % array.length;
	}
	
	
	public void insert(int key,Object data){
		if(noOfObject == (int)array.length/2)
			reHash();

		int index = key % array.length;


		while(array[index] != null){
			++index;
			index  = index % array.length;
		}

		array[index] = new HashNode(data, key);

		++noOfObject;
	}

	public void reHash() {
		HashNode [] temp = array;

		array = new HashNode[firstPrime(2*temp.length)];

		for (int i = 0; i < temp.length; i++) {
			if(temp[i] != null){
				/*if(temp[i].getKey() instanceof Integer){
					insert((int)temp[i].getKey(), temp[i].getData());
				}*/
				 
					insert((String)temp[i].getKey(), temp[i].getData());
				
			}
		}



	}


	public Object delete(String key,Object data){
		int index = getStringIndex(key) % array.length;

		while(array[index] != null){

			if(array[index].equals(data)){
				Object temp = array[index];

				array[index]=null;

				--noOfObject;
				return temp;
			}

			++index;
			index = index % array.length;
		}
		return null;
	}


	public Object delete(int key,Object data){
		int index = key % array.length;

		while(array[index] != null){

			if(array[index].equals(data)){
				Object temp = array[index];

				array[index]=null;

				--noOfObject;
				return temp;
			}

			++index;
			index = index % array.length;
		}
		return null;
	}
	public Object find(String key,Object data){

		if(noOfObject == 0)
			return null;

		int index = getStringIndex(key) % array.length;
		while(array[index] != null){
			if(array[index].equals(data))
				return array[index];

			++index;
			index = index % array.length;

		}
		return null;
	}
	public Object find(int key,Object data){

		if(noOfObject == 0)
			return null;

		int index = key % array.length;
		while(array[index] != null){
			if(array[index].equals(data))
				return array[index];

			++index;
			index = index % array.length;

		}
		return null;
	}


	public Object getData(int index){
		return array[index];
	}
	
	public  int getStringIndex(String s){
		int index=0;
		for (int i = 1; i <= s.length(); i++) {
			index+=s.charAt(i-1)*Math.pow(31,s.length()-i);
		}
		return index;
	}

	

	public String getUsedFun(){
		return "h = s[0]*31^L-1 + .... +s[L-2]*31^1+s[L-1]*31^0 , /* L: String Length */";
	}

	public  int firstPrime(int x){
		int y=x+1;
		int counter=x;

		while(counter > 1){
			if(y % counter == 0 ){
				++y;
				counter = y-1;
			}
			else{
				--counter;
			}
		}
		return y;

	}

	public int getSize(){
		return array.length;
	}

}