Wojciech Jaworski / ENIAM

package is2.data;

import java.util.Arrays;

final public class IntIntHash {

	protected int _size;
	protected int _free;
	protected float _loadFactor;
	public int _maxSize;
	protected int _autoCompactRemovesRemaining;
	protected float _autoCompactionFactor;
	public int _set[];
	private int _values[];

	public IntIntHash() {
		this(102877, 0.5F);
	}

	public IntIntHash(int initialCapacity, float loadFactor) {
		_loadFactor = loadFactor;
		_autoCompactionFactor = loadFactor;
		setUp((int) Math.ceil(initialCapacity / loadFactor));
	}

	public int size() {
		return _size;
	}

	public void ensureCapacity(int desiredCapacity) {

		if (desiredCapacity > _maxSize - size()) {
			rehash(PrimeFinder.nextPrime((int) Math.ceil((desiredCapacity + size()) / _loadFactor) + 1));
			computeMaxSize(capacity());
		}
	}

	public void compact() {
		rehash(PrimeFinder.nextPrime((int) Math.ceil(size() / _loadFactor) + 1));
		computeMaxSize(capacity());
		if (_autoCompactionFactor != 0.0F)
			computeNextAutoCompactionAmount(size());
	}

	public void setAutoCompactionFactor(float factor) {
		if (factor < 0.0F) {
			throw new IllegalArgumentException(
					(new StringBuilder()).append("Factor must be >= 0: ").append(factor).toString());
		} else {
			_autoCompactionFactor = factor;
			return;
		}
	}

	public float getAutoCompactionFactor() {
		return _autoCompactionFactor;
	}

	private void computeMaxSize(int capacity) {
		_maxSize = Math.min(capacity - 1, (int) Math.floor(capacity * _loadFactor));
		_free = capacity - _size;
	}

	private void computeNextAutoCompactionAmount(int size) {
		if (_autoCompactionFactor != 0.0F)
			_autoCompactRemovesRemaining = Math.round(size * _autoCompactionFactor);
	}

	protected final void postInsertHook(boolean usedFreeSlot) {
		if (usedFreeSlot)
			_free--;
		if (++_size > _maxSize || _free == 0) {
			int newCapacity = _size <= _maxSize ? capacity() : PrimeFinder.nextPrime(capacity() << 1);
			rehash(newCapacity);
			computeMaxSize(capacity());
		}
	}

	protected int calculateGrownCapacity() {
		return capacity() << 1;
	}

	protected int capacity() {
		return _values.length;
	}

	public boolean contains(int val) {
		return index(val) >= 0;
	}

	private int index(int v) {

		int length = _set.length;
		int index = Math.abs((computeHashCode(v) /* & 2147483647 */ ) % length);

		while (true) {
			// first
			long l = _set[index];
			if (l == 0) {
				// good++;
				return -1;
			}
			// second
			if (l == v) {
				return index;
			}
			if (--index < 0)
				index += length;
		}
		// return -1;
	}

	protected int insertionIndex(long val) {
		int length = _set.length;
		int index = Math.abs((computeHashCode(val) /* & 2147483647 */ ) % length);
		while (true) {
			if (_set[index] == 0)
				return index;
			if (_set[index] == val)
				return -index - 1;
			if (--index < 0)
				index += length;

		}
	}

	public int computeHashCode(long value) {
		return (int) ((value ^ (value & 0xffffffff00000000L) >>> 32) * 31);// 0x811c9dc5
																			// ^
																			// //
																			// 29
	}

	protected int setUp(int initialCapacity) {
		int capacity = PrimeFinder.nextPrime(initialCapacity);
		computeMaxSize(capacity);
		computeNextAutoCompactionAmount(initialCapacity);
		_set = new int[capacity];
		_values = new int[capacity];
		return capacity;
	}

	public void put(int key, int value) {
		int index = insertionIndex(key);
		doPut(key, value, index);
	}

	private void doPut(int key, int value, int index) {
		boolean isNewMapping = true;
		if (index < 0) {
			index = -index - 1;
			isNewMapping = false;
		}
		_set[index] = key;
		_values[index] = value;
		if (isNewMapping)
			postInsertHook(true);

	}

	protected void rehash(int newCapacity) {
		int oldCapacity = _set.length;
		int oldKeys[] = _set;
		int oldVals[] = _values;
		_set = new int[newCapacity];
		_values = new int[newCapacity];
		int i = oldCapacity;

		while (true) {
			if (i-- <= 0)
				break;
			if (oldVals[i] != 0) {
				int o = oldKeys[i];
				int index = insertionIndex(o);
				_set[index] = o;
				_values[index] = oldVals[i];
			}
		}
	}

	int index = 0;

	public int get(int key) {
		int index = index(key);
		return index >= 0 ? _values[index] : 0;
	}

	public void clear() {
		_size = 0;
		_free = capacity();
		Arrays.fill(_set, 0, _set.length, 0);
		// Arrays.fill(_values, 0, _values.length, 0);
	}

	public int remove(int key) {
		int prev = 0;
		int index = index(key);
		if (index >= 0) {
			prev = _values[index];
			_values[index] = 0;
			_set[index] = 0;
			_size--;
			if (_autoCompactionFactor != 0.0F) {
				_autoCompactRemovesRemaining--;
				if (_autoCompactRemovesRemaining <= 0)
					compact();
			}
		}
		return prev;
	}

	public int[] getValues() {
		int vals[] = new int[size()];
		int v[] = _values;
		int i = v.length;
		int j = 0;
		do {
			if (i-- <= 0)
				break;
			if (v[i] != 0)
				vals[j++] = v[i];
		} while (true);
		return vals;
	}

	public int[] keys() {
		int keys[] = new int[size()];
		int k[] = _set;
		// byte states[] = _states;
		int i = k.length;
		int j = 0;
		do {
			if (i-- <= 0)
				break;
			if (k[i] != 0)
				keys[j++] = k[i];
		} while (true);
		return keys;
	}

	/**
	 * @param index2
	 * @param i
	 * @return
	 */
	public boolean adjustValue(int key, int i) {
		int index = index(key);
		if (index >= 0) {
			_values[index] += i;
			return true;
		}
		return false;
	}

}