public class ArrayList{
    Integer []list;
    int []ri;
    int length;
    public ArrayList(){
        list=new Integer[10];
        length=0;
    }

    public ArrayList(int size){
        list=new Integer[size];
        length=0;
    }

    public void insertLP(int item){//insertion for linear probing
        if(length!=list.length){
            linearProbing(item);
        }
    }
    public void insertRP(int item){//insertion for random probing
        if(length==0){
            ri=randomPermutation();
        }
        if(length!=list.length){
            randomProbing(item);
        }
    }
    public void insertQP(int item){//insertion for quadratic probing
        if(length!=list.length){
            quadraticProbing(item);
        }
    }

    public void linearProbing(int item){
        int index=modulo(item);
        boolean found=false;
        while(list[index]!=null){
            if(list[index]==item){
                found=true;
                break;
            }
            else{
                index=(index+1)%list.length;
            }
        }
        if(found){
            System.err.println("Item Already Exist");
        }
        else{
            list[index]=item;
            length++;
        }
    }

    public void randomProbing(int item){
        int index=modulo(item);
        boolean found=false;
        int i=0;
        int t=index;
        while(list[index]!=null){
            if(list[index]==item){
                found=true;
                break;
            }
            else{
                index=(t+ri[i])%list.length;
            }
            i++;
        }
        if(found){
            System.err.println("Item Already Exist");
        }
        else{
            list[index]=item;
            length++;
        }
    }
    public void quadraticProbing(int item){
        int index=modulo(item);
        boolean found=false;
        int t=index;
        int i=0;
        while(list[index]!=null){
            if(list[index]==item){
                found=true;
                break;
            }
            else{
                index=(int)(t+Math.pow(i,2))%list.length;
            }
            i++;
        }
        if(found){
            System.err.println("Item Already Exist");
        }
        else{
            list[index]=item;
            length++;
        }
    }

    public int modulo(int item){//get initial hash index
        return item%list.length;
    }

    public int []randomPermutation(){//random permutation of the numbers 1 to size-1(u can create ur own algorithm)
        int size=list.length-1;
        int []index=new int[size];
        for(int i=0;i<index.length;i++){
            index[i]=i+1;
        }
        for(int i=0;i<index.length;i++){
            int j=(int)Math.round(Math.random()*(size-1));
            int temp=index[j];
            index[j]=index[i];
            index[i]=temp;
        }
        return index;
    }

    public String toString(){
        String out=list[0]+"";
        for(int i=1;i<list.length;i++){
            out+=","+list[i];
        }
        return out;
    }

}