package jsat.utils;

import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import static jsat.utils.ClosedHashingUtil.*;

/**
 * A hash map for storing the primitive types of integers (as keys) to doubles 
 * (as table). The implementation is based on Algorithm D (Open addressing with
 * double hashing) from Knuth's TAOCP page 528. 
 * 
 * @author Edward Raff
 */
public final class IntDoubleMap extends AbstractMap
{
    
    private float loadFactor;

    private int used = 0;
    private byte[] status;
    private int[] keys;
    private double[] table;
    
    public IntDoubleMap()
    {
        this(32);
    }
    
    public IntDoubleMap(int capacity)
    {
        this(capacity, 0.75f);
    }
    
    public IntDoubleMap(Map collection)
    {
        this(Math.max(1, collection.size()));
        for(Entry entry : collection.entrySet())
            put(entry.getKey(), entry.getValue());
    }
    
    public IntDoubleMap(int capacity, float loadFactor)
    {
        if(capacity < 1)
            throw new IllegalArgumentException("Capacity must be a positive value, not " + capacity);
        if(loadFactor <= 0 || loadFactor >= 1 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("loadFactor must be in (0, 1), not " + loadFactor);
        this.loadFactor = loadFactor;
        
        int size = getNextPow2TwinPrime((int) Math.max(capacity/loadFactor, 4));
        status = new byte[size];
        keys = new int[size];
        table = new double[size];
    }

    @Override
    public int size()
    {
        return used;
    }
    
    public int[] getRawKeyTable()
    {
        return keys;
    }
    
    public double[] getRawValueTable()
    {
        return table;
    }
    
    public byte[] getRawStatusTable()
    {
        return status;
    }

    @Override
    public Double put(Integer key, Double value)
    {
        double prev = put(key.intValue(), value.doubleValue());
        if(Double.isNaN(prev))
            return null;
        else
            return prev;
    }
    
    public double put(int key, double value)
    {
        if(Double.isNaN(value))
            throw new IllegalArgumentException("NaN is not an allowable value");
        long pair_index = getIndex(key);
        int deletedIndex = (int) (pair_index >>> 32);
        int valOrFreeIndex = (int) (pair_index & INT_MASK);
        
        double prev;
        if(status[valOrFreeIndex] == OCCUPIED)//easy case
        {
            prev = table[valOrFreeIndex];
            table[valOrFreeIndex] = value;
            return prev;
        }
        //else, not present
        prev = Double.NaN;
        int i = valOrFreeIndex;
        if(deletedIndex >= 0)//use occupied spot instead
            i = deletedIndex;
        
        status[i] = OCCUPIED;
        keys[i] = key;
        table[i] = value;
        used++;
        
        enlargeIfNeeded();
        
        return prev;
    }

    /**
     * 
     * @param key the key whose associated value is to be incremented. All
     * non-present keys behave as having an implicit value of zero, in which
     * case the delta value is directly inserted into the map.
     * @param delta the amount by which to increment the key's stored value.
     * @return the new value stored for the given key
     */
    public double increment(int key, double delta)
    {
        if(Double.isNaN(delta))
            throw new IllegalArgumentException("NaN is not an allowable value");
        
        long pair_index = getIndex(key);
        int deletedIndex = (int) (pair_index >>> 32);
        int valOrFreeIndex = (int) (pair_index & INT_MASK);
        
        if(status[valOrFreeIndex] == OCCUPIED)//easy case
            return (table[valOrFreeIndex] += delta);
        //else, not present
        double toReturn;
        int i = valOrFreeIndex;
        if(deletedIndex >= 0)//use occupied spot instead
            i = deletedIndex;
        
        status[i] = OCCUPIED;
        keys[i] = key;
        toReturn = table[i] = delta;
        used++;
        
        enlargeIfNeeded();
        
        return toReturn;
    }
    
    /**
     * Returns the value to which the specified key is mapped, or
     * {@link Double#NaN} if this map contains no mapping for the key.
     *
     * @param key the key whose associated value is to be returned
     * @return the value to which the specified key is mapped, or
     * {@link Double#NaN} if this map contains no mapping for the key
     */
    public double get(int key)
    {
        long pair_index = getIndex(key);
        int valOrFreeIndex = (int) (pair_index & INT_MASK);
        
        if(status[valOrFreeIndex] == OCCUPIED)//easy case
            return table[valOrFreeIndex];
        //else, return NaN for missing
        return Double.NaN;
    }

    @Override
    public Double get(Object key)
    {
        if(key == null)
            return null;
        
        if(key instanceof Integer)
        {
            double d = get( ((Integer)key).intValue());
            if(Double.isNaN(d))
                return null;
            return d;
        }
        else
            throw new ClassCastException("Key not of integer type");
    }
    
    @Override
    public Double remove(Object key)
    {
        if(key instanceof Integer)
        {
            double oldValue = remove(((Integer)key).intValue());
            if(Double.isNaN(oldValue))
                return null;
            else
                return oldValue;
        }
        
        return null;
    }
    
    /**
     * 
     * @param key
     * @return the old value stored for this key, or {@link Double#NaN} if the
     * key was not present in the map
     */
    public double remove(int key)
    {
        long pair_index = getIndex(key);
        int valOrFreeIndex = (int) (pair_index & INT_MASK);
        if(status[valOrFreeIndex] == EMPTY)//ret index is always EMPTY or OCCUPIED
            return Double.NaN;
        //else
        double toRet = table[valOrFreeIndex];
        status[valOrFreeIndex] = DELETED;
        used--;
        return toRet;
    }
    
    @Override
    public void clear()
    {
        used = 0;
        Arrays.fill(status, EMPTY);
    }
    
    private void enlargeIfNeeded()
    {
        if(used < keys.length*loadFactor)
            return;
        //enlarge
        final byte[] oldSatus = status;
        final int[] oldKeys = keys;
        final double[] oldTable = table;
        
        int newSize = getNextPow2TwinPrime(status.length*3/2);//it will actually end up doubling in size since we have twin primes spaced that was
        status = new byte[newSize];
        keys = new int[newSize];
        table = new double[newSize];
        
        used = 0;
        for(int oldIndex = 0; oldIndex < oldSatus.length; oldIndex++)
            if(oldSatus[oldIndex] == OCCUPIED)
                put(oldKeys[oldIndex], oldTable[oldIndex]);
    }
    
    @Override
    public boolean containsKey(Object key)
    {
        if(key instanceof Integer)
            return containsKey( ((Integer)key).intValue());
        else
            return false;
    }
    
    public boolean containsKey(int key)
    {
        int index = (int) (getIndex(key) & INT_MASK);
        return status[index] == OCCUPIED;//would be FREE if we didn't have the key
    }
    
    
    private final static long EXTRA_INDEX_INFO = ((long)Integer.MIN_VALUE) << 32;
    
    /**
     * Gets the index of the given key. Based on that {@link #status} variable,
     * the index is either the location to insert OR the location of the key.
     * 
     * This method returns 2 integer table in the long. The lower 32 bits are
     * the index that either contains the key, or is the first empty index. 
     * 
     * The upper 32 bits is the index of the first position marked as
     * {@link #DELETED} either {@link Integer#MIN_VALUE} if no position was
     * marked as DELETED while searching.
     *
     * @param key they key to search for
     * @return the mixed long containing the index of the first DELETED position
     * and the position that the key is in or the first EMPTY position found
     */
    private long getIndex(int key)
    {
        long extraInfo = EXTRA_INDEX_INFO;
        //D1 
        final int hash = h(key) & INT_MASK;
        int i = hash % keys.length;
        
        //D2
        int satus_i = status[i];
        if((keys[i] == key && satus_i != DELETED) || satus_i == EMPTY)
            return extraInfo | i;
        if(extraInfo == EXTRA_INDEX_INFO && satus_i == DELETED)
            extraInfo = ((long)i) << 32;
        
        //D3
        final int c = 1 + (hash % (keys.length -2));
        
        while(true)//this loop will terminate
        {
            //D4
            i -= c;
            if(i < 0)
                i += keys.length;
            //D5
            satus_i = status[i];
            if( (keys[i] == key && satus_i != DELETED) || satus_i == EMPTY)
                return extraInfo | i;
            if(extraInfo == EXTRA_INDEX_INFO && satus_i == DELETED)
                extraInfo = ((long)i) << 32;
        }
    }
    
    /**
     * Returns a non-negative hash value 
     * @param key
     * @return 
     */
    public static int h(int key)
    {
        //http://stackoverflow.com/questions/664014/what-integer-hash-function-are-good-that-accepts-an-integer-hash-key
        key = ((key >>> 16) ^ key ) & 0x45f9f3b;
        key = ((key >>> 16) ^ key ) & 0x45f9f3b;
        key = ((key >>> 16) ^ key ) ;
        return key;
    }
    

    @Override
    public Set> entrySet()
    {
        return new EntrySet(this);
    }
    
    /**
     * EntrySet class supports remove operations
     */
    private final class EntrySet extends AbstractSet>
    {
        final IntDoubleMap parentRef;
        
        public EntrySet(IntDoubleMap parent)
        {
            this.parentRef = parent;
        }

        @Override
        public Iterator> iterator()
        {
            //find the first starting inded
            int START = 0;
            while(START < status.length && status[START] != OCCUPIED)
                START++;
            if(START == status.length)
                return Collections.emptyIterator();
            final int startPos = START;
            
            return new Iterator>()
            {
                int pos = startPos;
                int prevPos = -1;

                @Override
                public boolean hasNext()
                {
                    return pos < status.length;
                }

                @Override
                public Entry next()
                {
                    //final int make so that object remains good after we call next again
                    final int oldPos = prevPos = pos++;
                    //find next
                    while (pos < status.length && status[pos] != OCCUPIED)
                        pos++;
                    //and return new object
                    return new Entry()
                    {

                        @Override
                        public Integer getKey()
                        {
                            return keys[oldPos];
                        }

                        @Override
                        public Double getValue()
                        {
                            return table[oldPos];
                        }

                        @Override
                        public Double setValue(Double value)
                        {
                            double old = table[oldPos];
                            table[oldPos] = value;
                            return old;
                        }
                    };
                }

                @Override
                public void remove()
                {
                    //its ok to just call remove b/c nothing is re-ordered when we remove an element, we just set the status to DELETED
                    parentRef.remove(keys[prevPos]);
                }
            };
        }

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

 

Ads help maintain this website.