QUADRATIC_PROBING

import java.util.*;

public class QuadraticProbing<T>
{   
	private static final int DEFAULT_TABLE_SIZE = 101;
	private HashEntry<T>[] array;
	private int currentSize;
	
	public QuadraticProbing()
	{	this(DEFAULT_TABLE_SIZE); }
	
	public QuadraticProbing(int size)
	{	array = new HashEntry[size]; 
		makeEmpty();
	}
	
	public void makeEmpty()
	{   currentSize = 0;
		for(int i=0; i<array.length; i++)
			array[i] = null;
	}
	
	public boolean contains(T element)
	{
		int currentPos = findPos(element);
		return isActive(currentPos);
	}
	
	private int findPos(T element)
	{
		int offset = 1;
		int currentPos = myhash(element);
		while(array[currentPos]!=null&&!array[currentPos].element.equals(element))
		{
			currentPos += offset;
			offset += 2;
			if(currentPos>=array.length)
				currentPos -= array.length;
		}
		return currentPos;
	}
	
	private boolean isActive(int currentPos)
	{
		return array[currentPos]!=null && array[currentPos].isActive;
	}
	
	public void insert(T element)
	{
		int currentPos = findPos(element);
		if(isActive(currentPos))
			return;
		array[currentPos] = new HashEntry<>(element, true);
	}
	
	public void remove(T element)
	{
		int currentPos = findPos(element);
		if(isActive(currentPos))
				array[currentPos].isActive = false;
	}
	
	private int myhash(T element)
	{   
		int hashValue = element.hashCode();
		hashValue %= array.length;
		if(hashValue < 0)
			hashValue += array.length;
		return hashValue;
	}
	
	private static class HashEntry<T>
	{
		public T element;
		public boolean isActive;
		
		public HashEntry(T e)
		{ this(e, true); }
		
		public HashEntry(T e, boolean i)
		{ element = e; isActive = i; }
		
		public T getElement(){ return this.element; }
	}
	
	public void showAll()
	{   for(HashEntry each: array)
			if(each != null)
				System.out.print(each.getElement()+"  ");
			else
				System.out.print("None ");
	}
	
	public static void main(String[] args)
	{
		QuadraticProbing<Integer> sc = new QuadraticProbing(10);
		sc.insert(89); sc.insert(18); sc.insert(49); sc.insert(58); sc.insert(69); 
		sc.showAll();
		
	}
}