Development Class Java

/*
 * Copyright 2004-2011 H2 Group. Multiple-Licensed under the H2 License,
 * Version 1.0, and under the Eclipse Public License, Version 1.0
 * (http://h2database.com/html/license.html).
 * Initial Developer: H2 Group
 */
//package org.h2.util;
/*
 * Copyright 2004-2011 H2 Group. Multiple-Licensed under the H2 License,
 * Version 1.0, and under the Eclipse Public License, Version 1.0
 * (http://h2database.com/html/license.html).
 * Initial Developer: H2 Group
 */
//package org.h2.util;
/**
 * A hash map with int key and int values. There is a restriction: the
 * value -1 (NOT_FOUND) cannot be stored in the map. 0 can be stored.
 * An empty record has key=0 and value=0.
 * A deleted record has key=0 and value=DELETED
 */
public class IntIntHashMap extends HashBase {
    /**
     * The value indicating that the entry has not been found.
     */
    public static final int NOT_FOUND = -1;
    private static final int DELETED = 1;
    private int[] keys;
    private int[] values;
    private int zeroValue;
    protected void reset(int newLevel) {
        super.reset(newLevel);
        keys = new int[len];
        values = new int[len];
    }
    /**
     * Store the given key-value pair. The value is overwritten or added.
     *
     * @param key the key
     * @param value the value (-1 is not supported)
     */
    public void put(int key, int value) {
        if (key == 0) {
            zeroKey = true;
            zeroValue = value;
            return;
        }
        try {
            checkSizePut();
        } catch (Exception e) {
            // in fact, it is never thrown
            // TODO hash: maybe optimize it
        }
        int index = getIndex(key);
        int plus = 1;
        int deleted = -1;
        do {
            int k = keys[index];
            if (k == 0) {
                if (values[index] != DELETED) {
                    // found an empty record
                    if (deleted >= 0) {
                        index = deleted;
                        deletedCount--;
                    }
                    size++;
                    keys[index] = key;
                    values[index] = value;
                    return;
                }
                // found a deleted record
                if (deleted < 0) {
                    deleted = index;
                }
            } else if (k == key) {
                // update existing
                values[index] = value;
                return;
            }
            index = (index + plus++) & mask;
        } while(plus <= len);
    }
    /**
     * Remove the key-value pair with the given key.
     *
     * @param key the key
     */
    public void remove(int key) {
        if (key == 0) {
            zeroKey = false;
            return;
        }
        try {
            checkSizeRemove();
        } catch (Exception e) {
            // in fact, it is never thrown
            // TODO hash: maybe optimize it
        }
        int index = getIndex(key);
        int plus = 1;
        do {
            int k = keys[index];
            if (k == key) {
                // found the record
                keys[index] = 0;
                values[index] = DELETED;
                deletedCount++;
                size--;
                return;
            } else if (k == 0 && values[index] == 0) {
                // found an empty record
                return;
            }
            index = (index + plus++) & mask;
        } while(plus <= len);
        // not found
    }
    protected void rehash(int newLevel) {
        int[] oldKeys = keys;
        int[] oldValues = values;
        reset(newLevel);
        for (int i = 0; i < oldKeys.length; i++) {
            int k = oldKeys[i];
            if (k != 0) {
                put(k, oldValues[i]);
            }
        }
    }
    /**
     * Get the value for the given key. This method returns NOT_FOUND if the
     * entry has not been found.
     *
     * @param key the key
     * @return the value or NOT_FOUND
     */
    public int get(int key) {
        if (key == 0) {
            return zeroKey ? zeroValue : NOT_FOUND;
        }
        int index = getIndex(key);
        int plus = 1;
        do {
            int k = keys[index];
            if (k == 0 && values[index] == 0) {
                // found an empty record
                return NOT_FOUND;
            } else if (k == key) {
                // found it
                return values[index];
            }
            index = (index + plus++) & mask;
        } while(plus <= len);
        return NOT_FOUND;
    }
}
/**
 * The base for other hash classes.
 */
abstract class HashBase {
    private static final int MAX_LOAD = 90;
    /**
     * The bit mask to get the index from the hash code.
     */
    protected int mask;
    /**
     * The number of slots in the table.
     */
    protected int len;
    /**
     * The number of occupied slots, excluding the zero key (if any).
     */
    protected int size;
    /**
     * The number of deleted slots.
     */
    protected int deletedCount;
    /**
     * The level. The number of slots is 2 ^ level.
     */
    protected int level;
    /**
     * Whether the zero key is used.
     */
    protected boolean zeroKey;
    private int maxSize, minSize, maxDeleted;
    public HashBase() {
        reset(2);
    }
    /**
     * Increase the size of the underlying table and re-distribute the elements.
     *
     * @param newLevel the new level
     */
    protected abstract void rehash(int newLevel);
    /**
     * Get the size of the map.
     *
     * @return the size
     */
    public int size() {
        return size + (zeroKey ? 1 : 0);
    }
    /**
     * Check the size before adding an entry. This method resizes the map if
     * required.
     */
    void checkSizePut() {
        if (deletedCount > size) {
            rehash(level);
        }
        if (size + deletedCount >= maxSize) {
            rehash(level + 1);
        }
    }
    /**
     * Check the size before removing an entry. This method resizes the map if
     * required.
     */
    protected void checkSizeRemove() {
        if (size < minSize && level > 0) {
            rehash(level - 1);
        } else if (deletedCount > maxDeleted) {
            rehash(level);
        }
    }
    /**
     * Clear the map and reset the level to the specified value.
     *
     * @param newLevel the new level
     */
    protected void reset(int newLevel) {
        minSize = size * 3 / 4;
        size = 0;
        level = newLevel;
        len = 2 << level;
        mask = len - 1;
        maxSize = (int) (len * MAX_LOAD / 100L);
        deletedCount = 0;
        maxDeleted = 20 + len / 2;
    }
    /**
     * Calculate the index for this hash code.
     *
     * @param hash the hash code
     * @return the index
     */
    protected int getIndex(int hash) {
        return hash & mask;
    }
}