PositiveIntMap

gistfile1.java

import java.util.Arrays;

public class PositiveIntMap {

    static final int INITIAL_SIZE = 8;
    static final double DEFAULT_LOAD_FACTOR = 0.5;

    // This is the size-1 of the key and value array length. Array length is a value power of two
    private int modulo = INITIAL_SIZE - 1;

    // Key array.
    int[] keys;

    // Carries count values.
    int[] values;

    int keyCount;

    // When structure has this amount of keys, it expands the key and count arrays.
    int threshold = (int) (INITIAL_SIZE * DEFAULT_LOAD_FACTOR);

    // Only used for debugging.
    int collisionCount;

    public PositiveIntMap() {
        this(INITIAL_SIZE);
    }

    public PositiveIntMap(int size) {
        size += (int) (size * (1 - DEFAULT_LOAD_FACTOR));
        if (size < 2)
            size = 2;
        if ((size & (size - 1)) != 0) { // check for power of two
            int power = (int) (Math.log(size) / Math.log(2));
            size = 1 << (power + 1);
        }
        keys = new int[size];
        Arrays.fill(keys, -1);
        values = new int[size];
        threshold = (int) (size * DEFAULT_LOAD_FACTOR);
        modulo = size - 1;
    }

    private int firstProbe(int hashCode) {
        return hashCode & modulo;
    }

    private int nextProbe(int previousIndex, int probeCount) {
        return (previousIndex + probeCount) & modulo;
    }

    private int locate(int key) {
        int probeCount = 0;
        int slot = firstProbe(key);
        int pointer = -1;
        while (true) {
            final int k = keys[slot];
            if (k == -1) {
                return pointer < 0 ? (-slot - 1) : (-pointer - 1);
            }
            if (k == -2) {
                if (pointer < 0) {
                    pointer = slot;
                }
                slot = nextProbe(slot, ++probeCount);
                continue;
            }
            if (k == key)
                return slot;
            slot = nextProbe(slot, ++probeCount);
            collisionCount++;
        }
    }

    /**
     * Returns the value for the key. If key does not exist, returns 0.
     *
     * @param key key
     * @return count of the key
     */
    public int get(int key) {
        if (key < 0)
            throw new IllegalArgumentException("Key cannot be negative. But it is:" + key);
        int probeCount = 0;
        int slot = firstProbe(key);
        while (true) {
            final int t = keys[slot];
            if (t == -1) {
                return 0;
            }
            if (t == -2) {
                slot = nextProbe(slot, ++probeCount);
                continue;
            }
            if (t == key)
                return values[slot];
            slot = nextProbe(slot, ++probeCount);
            collisionCount++;
        }
    }

    public boolean contains(int key) {
        return locate(key) >= 0;
    }

    public void remove(int key) {
        int k = locate(key);
        if (k < 0)
            return;
        keys[k] = -2; // mark deletion
        keyCount--;
    }

    private void expand() {
        PositiveIntMap h = new PositiveIntMap(values.length * 2);
        for (int i = 0; i < keys.length; i++) {
            if (keys[i] >= 0)
                h.set(keys[i], values[i]);
        }
        assert (h.keyCount == keyCount);
        this.values = h.values;
        this.keys = h.keys;
        this.keyCount = h.keyCount;
        this.modulo = h.modulo;
        this.threshold = h.threshold;
    }

    public void set(int key, int value) {
        if (key < 0)
            throw new IllegalArgumentException("Key cannot be negative. But it is:" + key);
        if (keyCount == threshold) {
            expand();
        }
        int loc = locate(key);
        if (loc >= 0) {
            values[loc] = value;
        } else {
            loc = -loc - 1;
            keys[loc] = key;
            values[loc] = value;
            keyCount++;
        }
    }

    /**
     * @return a clone of value array.
     */
    public int[] copyOfValues() {
        return values.clone();
    }
}