/* * Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package org.apache.commons.math3.util; import java.io.IOException; import java.io.ObjectInputStream; import java.io.Serializable; import java.util.ConcurrentModificationException; import java.util.NoSuchElementException; /** * Open addressed map from int to double. * *
This class provides a dedicated map from integers to doubles with a much smaller memory
* overhead than standard java.util.Map
.
*
*
This class is not synchronized. The specialized iterators returned by {@link #iterator()} are
* fail-fast: they throw a ConcurrentModificationException
when they detect the map has
* been modified during iteration.
*
* @since 2.0
*/
public class OpenIntToDoubleHashMap implements Serializable {
/** Status indicator for free table entries. */
protected static final byte FREE = 0;
/** Status indicator for full table entries. */
protected static final byte FULL = 1;
/** Status indicator for removed table entries. */
protected static final byte REMOVED = 2;
/** Serializable version identifier */
private static final long serialVersionUID = -3646337053166149105L;
/** Load factor for the map. */
private static final float LOAD_FACTOR = 0.5f;
/**
* Default starting size.
*
*
This must be a power of two for bit mask to work properly. */ private static final int DEFAULT_EXPECTED_SIZE = 16; /** * Multiplier for size growth when map fills up. * *
This must be a power of two for bit mask to work properly. */ private static final int RESIZE_MULTIPLIER = 2; /** Number of bits to perturb the index when probing for collision resolution. */ private static final int PERTURB_SHIFT = 5; /** Keys table. */ private int[] keys; /** Values table. */ private double[] values; /** States table. */ private byte[] states; /** Return value for missing entries. */ private final double missingEntries; /** Current size of the map. */ private int size; /** Bit mask for hash values. */ private int mask; /** Modifications count. */ private transient int count; /** Build an empty map with default size and using NaN for missing entries. */ public OpenIntToDoubleHashMap() { this(DEFAULT_EXPECTED_SIZE, Double.NaN); } /** * Build an empty map with default size * * @param missingEntries value to return when a missing entry is fetched */ public OpenIntToDoubleHashMap(final double missingEntries) { this(DEFAULT_EXPECTED_SIZE, missingEntries); } /** * Build an empty map with specified size and using NaN for missing entries. * * @param expectedSize expected number of elements in the map */ public OpenIntToDoubleHashMap(final int expectedSize) { this(expectedSize, Double.NaN); } /** * Build an empty map with specified size. * * @param expectedSize expected number of elements in the map * @param missingEntries value to return when a missing entry is fetched */ public OpenIntToDoubleHashMap(final int expectedSize, final double missingEntries) { final int capacity = computeCapacity(expectedSize); keys = new int[capacity]; values = new double[capacity]; states = new byte[capacity]; this.missingEntries = missingEntries; mask = capacity - 1; } /** * Copy constructor. * * @param source map to copy */ public OpenIntToDoubleHashMap(final OpenIntToDoubleHashMap source) { final int length = source.keys.length; keys = new int[length]; System.arraycopy(source.keys, 0, keys, 0, length); values = new double[length]; System.arraycopy(source.values, 0, values, 0, length); states = new byte[length]; System.arraycopy(source.states, 0, states, 0, length); missingEntries = source.missingEntries; size = source.size; mask = source.mask; count = source.count; } /** * Compute the capacity needed for a given size. * * @param expectedSize expected size of the map * @return capacity to use for the specified size */ private static int computeCapacity(final int expectedSize) { if (expectedSize == 0) { return 1; } final int capacity = (int) FastMath.ceil(expectedSize / LOAD_FACTOR); final int powerOfTwo = Integer.highestOneBit(capacity); if (powerOfTwo == capacity) { return capacity; } return nextPowerOfTwo(capacity); } /** * Find the smallest power of two greater than the input value * * @param i input value * @return smallest power of two greater than the input value */ private static int nextPowerOfTwo(final int i) { return Integer.highestOneBit(i) << 1; } /** * Get the stored value associated with the given key * * @param key key associated with the data * @return data associated with the key */ public double get(final int key) { final int hash = hashOf(key); int index = hash & mask; if (containsKey(key, index)) { return values[index]; } if (states[index] == FREE) { return missingEntries; } int j = index; for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) { j = probe(perturb, j); index = j & mask; if (containsKey(key, index)) { return values[index]; } } return missingEntries; } /** * Check if a value is associated with a key. * * @param key key to check * @return true if a value is associated with key */ public boolean containsKey(final int key) { final int hash = hashOf(key); int index = hash & mask; if (containsKey(key, index)) { return true; } if (states[index] == FREE) { return false; } int j = index; for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) { j = probe(perturb, j); index = j & mask; if (containsKey(key, index)) { return true; } } return false; } /** * Get an iterator over map elements. * *
The specialized iterators returned are fail-fast: they throw a
* ConcurrentModificationException
when they detect the map has been modified during
* iteration.
*
* @return iterator over the map elements
*/
public Iterator iterator() {
return new Iterator();
}
/**
* Perturb the hash for starting probing.
*
* @param hash initial hash
* @return perturbed hash
*/
private static int perturb(final int hash) {
return hash & 0x7fffffff;
}
/**
* Find the index at which a key should be inserted
*
* @param key key to lookup
* @return index at which key should be inserted
*/
private int findInsertionIndex(final int key) {
return findInsertionIndex(keys, states, key, mask);
}
/**
* Find the index at which a key should be inserted
*
* @param keys keys table
* @param states states table
* @param key key to lookup
* @param mask bit mask for hash values
* @return index at which key should be inserted
*/
private static int findInsertionIndex(
final int[] keys, final byte[] states, final int key, final int mask) {
final int hash = hashOf(key);
int index = hash & mask;
if (states[index] == FREE) {
return index;
} else if (states[index] == FULL && keys[index] == key) {
return changeIndexSign(index);
}
int perturb = perturb(hash);
int j = index;
if (states[index] == FULL) {
while (true) {
j = probe(perturb, j);
index = j & mask;
perturb >>= PERTURB_SHIFT;
if (states[index] != FULL || keys[index] == key) {
break;
}
}
}
if (states[index] == FREE) {
return index;
} else if (states[index] == FULL) {
// due to the loop exit condition,
// if (states[index] == FULL) then keys[index] == key
return changeIndexSign(index);
}
final int firstRemoved = index;
while (true) {
j = probe(perturb, j);
index = j & mask;
if (states[index] == FREE) {
return firstRemoved;
} else if (states[index] == FULL && keys[index] == key) {
return changeIndexSign(index);
}
perturb >>= PERTURB_SHIFT;
}
}
/**
* Compute next probe for collision resolution
*
* @param perturb perturbed hash
* @param j previous probe
* @return next probe
*/
private static int probe(final int perturb, final int j) {
return (j << 2) + j + perturb + 1;
}
/**
* Change the index sign
*
* @param index initial index
* @return changed index
*/
private static int changeIndexSign(final int index) {
return -index - 1;
}
/**
* Get the number of elements stored in the map.
*
* @return number of elements stored in the map
*/
public int size() {
return size;
}
/**
* Remove the value associated with a key.
*
* @param key key to which the value is associated
* @return removed value
*/
public double remove(final int key) {
final int hash = hashOf(key);
int index = hash & mask;
if (containsKey(key, index)) {
return doRemove(index);
}
if (states[index] == FREE) {
return missingEntries;
}
int j = index;
for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
j = probe(perturb, j);
index = j & mask;
if (containsKey(key, index)) {
return doRemove(index);
}
}
return missingEntries;
}
/**
* Check if the tables contain an element associated with specified key at specified index.
*
* @param key key to check
* @param index index to check
* @return true if an element is associated with key at index
*/
private boolean containsKey(final int key, final int index) {
return (key != 0 || states[index] == FULL) && keys[index] == key;
}
/**
* Remove an element at specified index.
*
* @param index index of the element to remove
* @return removed value
*/
private double doRemove(int index) {
keys[index] = 0;
states[index] = REMOVED;
final double previous = values[index];
values[index] = missingEntries;
--size;
++count;
return previous;
}
/**
* Put a value associated with a key in the map.
*
* @param key key to which value is associated
* @param value value to put in the map
* @return previous value associated with the key
*/
public double put(final int key, final double value) {
int index = findInsertionIndex(key);
double previous = missingEntries;
boolean newMapping = true;
if (index < 0) {
index = changeIndexSign(index);
previous = values[index];
newMapping = false;
}
keys[index] = key;
states[index] = FULL;
values[index] = value;
if (newMapping) {
++size;
if (shouldGrowTable()) {
growTable();
}
++count;
}
return previous;
}
/** Grow the tables. */
private void growTable() {
final int oldLength = states.length;
final int[] oldKeys = keys;
final double[] oldValues = values;
final byte[] oldStates = states;
final int newLength = RESIZE_MULTIPLIER * oldLength;
final int[] newKeys = new int[newLength];
final double[] newValues = new double[newLength];
final byte[] newStates = new byte[newLength];
final int newMask = newLength - 1;
for (int i = 0; i < oldLength; ++i) {
if (oldStates[i] == FULL) {
final int key = oldKeys[i];
final int index = findInsertionIndex(newKeys, newStates, key, newMask);
newKeys[index] = key;
newValues[index] = oldValues[i];
newStates[index] = FULL;
}
}
mask = newMask;
keys = newKeys;
values = newValues;
states = newStates;
}
/**
* Check if tables should grow due to increased size.
*
* @return true if tables should grow
*/
private boolean shouldGrowTable() {
return size > (mask + 1) * LOAD_FACTOR;
}
/**
* Compute the hash value of a key
*
* @param key key to hash
* @return hash value of the key
*/
private static int hashOf(final int key) {
final int h = key ^ ((key >>> 20) ^ (key >>> 12));
return h ^ (h >>> 7) ^ (h >>> 4);
}
/** Iterator class for the map. */
public class Iterator {
/** Reference modification count. */
private final int referenceCount;
/** Index of current element. */
private int current;
/** Index of next element. */
private int next;
/** Simple constructor. */
private Iterator() {
// preserve the modification count of the map to detect concurrent modifications later
referenceCount = count;
// initialize current index
next = -1;
try {
advance();
} catch (NoSuchElementException nsee) { // NOPMD
// ignored
}
}
/**
* Check if there is a next element in the map.
*
* @return true if there is a next element
*/
public boolean hasNext() {
return next >= 0;
}
/**
* Get the key of current entry.
*
* @return key of current entry
* @exception ConcurrentModificationException if the map is modified during iteration
* @exception NoSuchElementException if there is no element left in the map
*/
public int key() throws ConcurrentModificationException, NoSuchElementException {
if (referenceCount != count) {
throw new ConcurrentModificationException();
}
if (current < 0) {
throw new NoSuchElementException();
}
return keys[current];
}
/**
* Get the value of current entry.
*
* @return value of current entry
* @exception ConcurrentModificationException if the map is modified during iteration
* @exception NoSuchElementException if there is no element left in the map
*/
public double value() throws ConcurrentModificationException, NoSuchElementException {
if (referenceCount != count) {
throw new ConcurrentModificationException();
}
if (current < 0) {
throw new NoSuchElementException();
}
return values[current];
}
/**
* Advance iterator one step further.
*
* @exception ConcurrentModificationException if the map is modified during iteration
* @exception NoSuchElementException if there is no element left in the map
*/
public void advance() throws ConcurrentModificationException, NoSuchElementException {
if (referenceCount != count) {
throw new ConcurrentModificationException();
}
// advance on step
current = next;
// prepare next step
try {
while (states[++next] != FULL) { // NOPMD
// nothing to do
}
} catch (ArrayIndexOutOfBoundsException e) {
next = -2;
if (current < 0) {
throw new NoSuchElementException();
}
}
}
}
/**
* Read a serialized object.
*
* @param stream input stream
* @throws IOException if object cannot be read
* @throws ClassNotFoundException if the class corresponding to the serialized object cannot be
* found
*/
private void readObject(final ObjectInputStream stream)
throws IOException, ClassNotFoundException {
stream.defaultReadObject();
count = 0;
}
}