package gregtech.api.objects;

import java.util.Arrays;

/**
 * Object-2-object map based on IntIntMap4a
 */
public class ObjMap<K, V>
{
    private static final Object FREE_KEY = new Object();
    private static final Object REMOVED_KEY = new Object();

    /** Keys and values */
    private Object[] m_data;

    /** Value for the null key (if inserted into a map) */
    private Object m_nullValue;
    private boolean m_hasNull;

    /** Fill factor, must be between (0 and 1) */
    private final float m_fillFactor;
    /** We will resize a map once it reaches this size */
    private int m_threshold;
    /** Current map size */
    private int m_size;
    /** Mask to calculate the original position */
    private int m_mask;
    /** Mask to wrap the actual array pointer */
    private int m_mask2;

    public ObjMap( final int size, final float fillFactor )
    {
        if ( fillFactor <= 0 || fillFactor >= 1 )
            throw new IllegalArgumentException( "FillFactor must be in (0, 1)" );
        if ( size <= 0 )
            throw new IllegalArgumentException( "Size must be positive!" );
        final int capacity = arraySize(size, fillFactor);
        m_mask = capacity - 1;
        m_mask2 = capacity * 2 - 1;
        m_fillFactor = fillFactor;

        m_data = new Object[capacity * 2];
        Arrays.fill( m_data, FREE_KEY );

        m_threshold = (int) (capacity * fillFactor);
    }

    @SuppressWarnings("unchecked")
	public V get( final K key )
    {
        if ( key == null )
            return (V) m_nullValue; //we null it on remove, so safe not to check a flag here

        int ptr = (key.hashCode() & m_mask) << 1;
        Object k = m_data[ ptr ];

        if ( k == FREE_KEY )
            return null;  //end of chain already
        if ( k.equals( key ) ) //we check FREE and REMOVED prior to this call
            return (V) m_data[ ptr + 1 ];
        while ( true )
        {
            ptr = (ptr + 2) & m_mask2; //that's next index
            k = m_data[ ptr ];
            if ( k == FREE_KEY )
                return null;
            if ( k.equals( key ) )
                return (V) m_data[ ptr + 1 ];
        }
    }

    @SuppressWarnings("unchecked")
	public V put( final K key, final V value )
    {
        if ( key == null )
            return insertNullKey(value);

        int ptr = getStartIndex(key) << 1;
        Object k = m_data[ptr];

        if ( k == FREE_KEY ) //end of chain already
        {
            m_data[ ptr ] = key;
            m_data[ ptr + 1 ] = value;
            if ( m_size >= m_threshold )
                rehash( m_data.length * 2 ); //size is set inside
            else
                ++m_size;
            return null;
        }
        else if ( k.equals( key ) ) //we check FREE and REMOVED prior to this call
        {
            final Object ret = m_data[ ptr + 1 ];
            m_data[ ptr + 1 ] = value;
            return (V) ret;
        }

        int firstRemoved = -1;
        if ( k == REMOVED_KEY )
            firstRemoved = ptr; //we may find a key later

        while ( true )
        {
            ptr = ( ptr + 2 ) & m_mask2; //that's next index calculation
            k = m_data[ ptr ];
            if ( k == FREE_KEY )
            {
                if ( firstRemoved != -1 )
                    ptr = firstRemoved;
                m_data[ ptr ] = key;
                m_data[ ptr + 1 ] = value;
                if ( m_size >= m_threshold )
                    rehash( m_data.length * 2 ); //size is set inside
                else
                    ++m_size;
                return null;
            }
            else if ( k.equals( key ) )
            {
                final Object ret = m_data[ ptr + 1 ];
                m_data[ ptr + 1 ] = value;
                return (V) ret;
            }
            else if ( k == REMOVED_KEY )
            {
                if ( firstRemoved == -1 )
                    firstRemoved = ptr;
            }
        }
    }

    @SuppressWarnings("unchecked")
	public V remove( final K key )
    {
        if ( key == null )
            return removeNullKey();

        int ptr = getStartIndex(key) << 1;
        Object k = m_data[ ptr ];
        if ( k == FREE_KEY )
            return null;  //end of chain already
        else if ( k.equals( key ) ) //we check FREE and REMOVED prior to this call
        {
            --m_size;
            if ( m_data[ ( ptr + 2 ) & m_mask2 ] == FREE_KEY )
                m_data[ ptr ] = FREE_KEY;
            else
                m_data[ ptr ] = REMOVED_KEY;
            final V ret = (V) m_data[ ptr + 1 ];
            m_data[ ptr + 1 ] = null;
            return ret;
        }
        while ( true )
        {
            ptr = ( ptr + 2 ) & m_mask2; //that's next index calculation
            k = m_data[ ptr ];
            if ( k == FREE_KEY )
                return null;
            else if ( k.equals( key ) )
            {
                --m_size;
                if ( m_data[ ( ptr + 2 ) & m_mask2 ] == FREE_KEY )
                    m_data[ ptr ] = FREE_KEY;
                else
                    m_data[ ptr ] = REMOVED_KEY;
                final V ret = (V) m_data[ ptr + 1 ];
                m_data[ ptr + 1 ] = null;
                return ret;
            }
        }
    }

    @SuppressWarnings("unchecked")
	private V insertNullKey(final V value)
    {
        if ( m_hasNull )
        {
            final Object ret = m_nullValue;
            m_nullValue = value;
            return (V) ret;
        }
        else
        {
            m_nullValue = value;
            ++m_size;
            return null;
        }
    }

    @SuppressWarnings("unchecked")
	private V removeNullKey()
    {
        if ( m_hasNull )
        {
            final Object ret = m_nullValue;
            m_nullValue = null;
            m_hasNull = false;
            --m_size;
            return (V) ret;
        }
        else
        {
            return null;
        }
    }

    public int size()
    {
        return m_size;
    }

    @SuppressWarnings("unchecked")
	private void rehash( final int newCapacity )
    {
        m_threshold = (int) (newCapacity/2 * m_fillFactor);
        m_mask = newCapacity/2 - 1;
        m_mask2 = newCapacity - 1;

        final int oldCapacity = m_data.length;
        final Object[] oldData = m_data;

        m_data = new Object[ newCapacity ];
        Arrays.fill( m_data, FREE_KEY );

        m_size = m_hasNull ? 1 : 0;

        for ( int i = 0; i < oldCapacity; i += 2 ) {
            final Object oldKey = oldData[ i ];
            if( oldKey != FREE_KEY && oldKey != REMOVED_KEY )
                put( (K)oldKey, (V)oldData[ i + 1 ]);
        }
    }

    public int getStartIndex( final Object key )
    {
        //key is not null here
        return key.hashCode() & m_mask;
    }
    
    /** Taken from FastUtil implementation */

    /** Return the least power of two greater than or equal to the specified value.
   	 *
   	 * <p>Note that this function will return 1 when the argument is 0.
   	 *
   	 * @param x a long integer smaller than or equal to 2<sup>62</sup>.
   	 * @return the least power of two greater than or equal to the specified value.
   	 */
   	public static long nextPowerOfTwo( long x ) {
   		if ( x == 0 ) return 1;
   		x--;
   		x |= x >> 1;
   		x |= x >> 2;
   		x |= x >> 4;
   		x |= x >> 8;
   		x |= x >> 16;
   		return ( x | x >> 32 ) + 1;
   	}

    /** Returns the least power of two smaller than or equal to 2<sup>30</sup> and larger than or equal to <code>Math.ceil( expected / f )</code>.
   	 *
   	 * @param expected the expected number of elements in a hash table.
   	 * @param f the load factor.
   	 * @return the minimum possible size for a backing array.
   	 * @throws IllegalArgumentException if the necessary size is larger than 2<sup>30</sup>.
   	 */
   	public static int arraySize( final int expected, final float f ) {
   		final long s = Math.max( 2, nextPowerOfTwo( (long)Math.ceil( expected / f ) ) );
   		if ( s > (1 << 30) ) throw new IllegalArgumentException( "Too large (" + expected + " expected elements with load factor " + f + ")" );
   		return (int)s;
   	}

    //taken from FastUtil
    private static final int INT_PHI = 0x9E3779B9;

    public static int phiMix( final int x ) {
   		final int h = x * INT_PHI;
   		return h ^ (h >> 16);
}
    
}