package dictionary;

import arraylist.ArrayIndexList;
import arraylist.IndexList;
import exceptions.HashExceptionKey;
import exceptions.InvalidEntryException;
import position.NodePositionList;
import priorityqueue.Entry;
import priorityqueue.MyEntry;

import exceptions.InvalidKeyException;
import java.util.Iterator;

/**
 * Created with MONSTER.
 * User: xgiovio
 * Date: 11/05/2014
 * Time: 19:28
 */

 //Complete implementation by xgiovio
 // Collisions resolved with linear probing

public class LinearProbingHashTable<K,V> implements Dictionary<K,V> {

        IndexList<Entry<K,V>> table = null;
        Entry<K,V> AVAIBLE = null;
        int avaible_slots = 0;
        int elements = 0;
        int p = 0;
        int scale = 0;
        int shift = 0;

    public LinearProbingHashTable(int in_p, int in_size){
        table = new ArrayIndexList<Entry<K, V>>(in_size);
        AVAIBLE = new MyEntry<K, V>(null,null);
        p = in_p;
        java.util.Random rand = new java.util.Random();
        scale = rand.nextInt(p-1) + 1;
        shift = rand.nextInt(p);

        for (int i= 0 ; i< in_size ;i++){
            table.add(i,AVAIBLE);
            avaible_slots ++;
        }
    }

    public LinearProbingHashTable(int in_size){
        this(109345121,in_size);
    }

    public LinearProbingHashTable(){
        this(109345121,100);
    }



    public   float load_factor () throws InvalidKeyException{
        float ret =  (size() / (float)raw_size());
        if ( ret >= 0.5 ) {
            reformat();
            return load_factor();
        }
        return ret;
    }

    public  int raw_size (){
        return table.size();
    }

    @Override
    public int size() {
        return elements;
    }

    @Override
    public boolean isEmpty() {
        return (size() == 0);
    }

    protected int hash ( K key) {
        return (int) ((Math.abs(key.hashCode()*scale + shift) % p) % raw_size());
    }



    @Override
    public Entry<K, V> find(K key) throws InvalidKeyException {

            checkKey(key);
            int h = hash(key);
            int count = 0;
            for (;count < raw_size();){
                if (table.get( (h+count)%raw_size()  ) == AVAIBLE)
                    return null;
                if (table.get((h+count)%raw_size()) == null)
                    continue;
                if (table.get((h+count)%raw_size()).getKey().equals(key))
                    return table.get((h+count)%raw_size());
                count++;
            }
        return null;
    }

    @Override
    public Iterable<Entry<K, V>> findAll(K key) throws InvalidKeyException {
        checkKey(key);
        NodePositionList<Entry<K,V>> to_return = new NodePositionList<Entry<K, V>>();
        int h = hash(key);
        int count = 0;
        for (;count < raw_size();){
            if (table.get((h+count)%raw_size()) == AVAIBLE)
                return to_return;
            if (table.get((h+count)%raw_size()) == null)
                continue;
            if (table.get((h+count)%raw_size()).getKey().equals(key))
                to_return.addLast( table.get((h+count)%raw_size()));
            count++;
        }
        return to_return;
    }

    @Override
    public Entry<K, V> insert(K key, V value) throws InvalidKeyException {
             checkKey(key);
             if (load_factor() >= 0.5 )
                 reformat();
             int h = hash(key);
             if (table.get(h) == AVAIBLE || table.get(h ) == null ) {
                 MyEntry<K, V> n = new MyEntry<K, V>(key,value);
                 table.set(h,n);
                 avaible_slots--;
                 elements++;
                 return n;
             } else {
                 int count = 1;
                 for ( ; count < raw_size() ;) {
                     if (table.get((h+count)%raw_size()) == AVAIBLE || table.get((h+count)%raw_size()) == null   ) {
                         MyEntry<K, V> n = new MyEntry<K, V>(key, value);
                         table.set((h+count)%raw_size(), n);
                         avaible_slots--;
                         elements++;
                         return n;
                     }
                     count++;
                 }
                 return null; // non dovresti essere qui a causa del load factor
             }
    }
    protected Entry<K, V> insert_refactor(Entry<K, V> in_e) throws InvalidKeyException {
        // no check of in_e because this function is used internally from reformat
        int h = hash(in_e.getKey());
        if (table.get(h) == AVAIBLE || table.get(h ) == null ) {
            Entry<K, V> n = in_e;
            table.set(h,n);
            avaible_slots--;
            elements++;
            return n;
        } else {
            int count = 1;
            for ( ; count < raw_size() ;) {
                if (table.get((h+count)%raw_size()) == AVAIBLE || table.get((h+count)%raw_size()) == null   ) {
                    Entry<K, V> n = in_e;
                    table.set((h+count)%raw_size(), n);
                    avaible_slots--;
                    elements++;
                    return n;
                }
                count++;
            }
            return null; // non dovresti essere qui a causa del load factor
        }
    }

    @Override
    public Entry<K, V> remove(Entry<K, V> e) throws InvalidEntryException {
        if (e == null)
            throw new InvalidEntryException();
        int h = hash(e.getKey());
        if (table.get(h) == AVAIBLE)
            throw new InvalidEntryException();
        if (table.get(h) == null){

        } else {
            if (table.get(h) == e) {
                table.set(h, null);
                elements--;
                avaible_slots++;
                return e;
            }
        }
        int count = 1;
        for (; count < raw_size() ;){
            if (table.get((h+count)%raw_size()) == AVAIBLE)
                throw new InvalidEntryException();
            if (table.get((h+count)%raw_size()) == null){

            } else {
                if (table.get((h+count)%raw_size()) == e) {
                    table.set((h+count)%raw_size(), null);
                    elements--;
                    avaible_slots++;
                    return e;
                }
            }
            count++;
        }
        throw new InvalidEntryException();

    }

    @Override
    public Iterable<Entry<K, V>> entries() {

        NodePositionList<Entry<K,V>> ret = new NodePositionList<Entry<K, V>>();

        for (int i = 0 ; i< raw_size() ;i++){
            if (table.get(i) != AVAIBLE && table.get(i) != null ){
                ret.addLast(table.get(i));
            }
        }
        return ret;
    }


    protected void checkKey(K key) throws InvalidKeyException {
        if (key == null )
            throw new InvalidKeyException("Invalid key");
    }


    void reformat () throws InvalidKeyException{

        Iterable<Entry<K,V>> ite = entries();
        int new_size = raw_size() * 2;
        IndexList<Entry<K,V>>  table2 = new ArrayIndexList<Entry<K, V>>(new_size);
        avaible_slots = 0;
        elements = 0;
        java.util.Random rand = new java.util.Random();
        scale = rand.nextInt(p-1) + 1;    	// new hash scaling factor
        shift = rand.nextInt(p);  //// new hash shifting factor

        for (int i= 0 ; i< (new_size) ;i++){
            table2.add(i,AVAIBLE);
        }
        table = table2;

        for (Entry<K,V> e : ite){
            insert_refactor(e);

        }
    }


    public String toString() {

        Iterator<Entry<K,V>> it = entries().iterator();

        String to_return = "";
        to_return = to_return + "[";

        for (;it.hasNext();){
            Entry<K,V>  t = it.next();

            if (it.hasNext())  {

                to_return+=(t.toString() + " , ");
            }    else {

                to_return+=(t.toString());
            }
        }

        return to_return+= "]";
    }
}