src/main/java/org/apache/commons/math/util/OpenIntToFieldHashMap.java - platform/external/apache-commons-math - Git at Google

 /*
  * 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.math.util;

 import java.io.IOException;
 import java.io.ObjectInputStream;
 import java.io.Serializable;
 import java.lang.reflect.Array;
 import java.util.ConcurrentModificationException;
 import java.util.NoSuchElementException;

 import org.apache.commons.math.Field;
 import org.apache.commons.math.FieldElement;
 import org.apache.commons.math.MathRuntimeException;
 import org.apache.commons.math.exception.util.LocalizedFormats;

 /**
  * Open addressed map from int to FieldElement.
  * <p>This class provides a dedicated map from integers to FieldElements with a
  * much smaller memory overhead than standard <code>java.util.Map</code>.</p>
  * <p>This class is not synchronized. The specialized iterators returned by
  * {@link #iterator()} are fail-fast: they throw a
  * <code>ConcurrentModificationException</code> when they detect the map has been
  * modified during iteration.</p>
  * @param <T> the type of the field elements
  * @version $Revision: 990655 $ $Date: 2010-08-29 23:49:40 +0200 (dim. 29 août 2010) $
  * @since 2.0
  */
 public class OpenIntToFieldHashMap<T extends FieldElement<T>> 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 = -9179080286849120720L;

     /** Load factor for the map. */
     private static final float LOAD_FACTOR = 0.5f;

     /** Default starting size.
      * <p>This must be a power of two for bit mask to work properly. </p>
      */
     private static final int DEFAULT_EXPECTED_SIZE = 16;

     /** Multiplier for size growth when map fills up.
      * <p>This must be a power of two for bit mask to work properly. </p>
      */
     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;

     /** Field to which the elements belong. */
     private final Field<T> field;

     /** Keys table. */
     private int[] keys;

     /** Values table. */
     private T[] values;

     /** States table. */
     private byte[] states;

     /** Return value for missing entries. */
     private final T 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 zero for missing entries.
      * @param field field to which the elements belong
      */
     public OpenIntToFieldHashMap(final Field<T>field) {
         this(field, DEFAULT_EXPECTED_SIZE, field.getZero());
     }

     /**
      * Build an empty map with default size
      * @param field field to which the elements belong
      * @param missingEntries value to return when a missing entry is fetched
      */
     public OpenIntToFieldHashMap(final Field<T>field, final T missingEntries) {
         this(field,DEFAULT_EXPECTED_SIZE, missingEntries);
     }

     /**
      * Build an empty map with specified size and using zero for missing entries.
      * @param field field to which the elements belong
      * @param expectedSize expected number of elements in the map
      */
     public OpenIntToFieldHashMap(final Field<T> field,final int expectedSize) {
         this(field,expectedSize, field.getZero());
     }

     /**
      * Build an empty map with specified size.
      * @param field field to which the elements belong
      * @param expectedSize expected number of elements in the map
      * @param missingEntries value to return when a missing entry is fetched
      */
     public OpenIntToFieldHashMap(final Field<T> field,final int expectedSize,
                                   final T missingEntries) {
         this.field = field;
         final int capacity = computeCapacity(expectedSize);
         keys   = new int[capacity];
         values = buildArray(capacity);
         states = new byte[capacity];
         this.missingEntries = missingEntries;
         mask   = capacity - 1;
     }

     /**
      * Copy constructor.
      * @param source map to copy
      */
     public OpenIntToFieldHashMap(final OpenIntToFieldHashMap<T> source) {
         field = source.field;
         final int length = source.keys.length;
         keys = new int[length];
         System.arraycopy(source.keys, 0, keys, 0, length);
         values = buildArray(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 T 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.
      * <p>The specialized iterators returned are fail-fast: they throw a
      * <code>ConcurrentModificationException</code> when they detect the map
      * has been modified during iteration.</p>
      * @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 T 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 T doRemove(int index) {
         keys[index]   = 0;
         states[index] = REMOVED;
         final T 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 T put(final int key, final T value) {
         int index = findInsertionIndex(key);
         T 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 T[] oldValues = values;
         final byte[] oldStates   = states;

         final int newLength = RESIZE_MULTIPLIER * oldLength;
         final int[] newKeys = new int[newLength];
         final T[] newValues = buildArray(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) {
                 // 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 MathRuntimeException.createConcurrentModificationException(LocalizedFormats.MAP_MODIFIED_WHILE_ITERATING);
             }
             if (current < 0) {
                 throw MathRuntimeException.createNoSuchElementException(LocalizedFormats.ITERATOR_EXHAUSTED);
             }
             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 T value()
             throws ConcurrentModificationException, NoSuchElementException {
             if (referenceCount != count) {
                 throw MathRuntimeException.createConcurrentModificationException(LocalizedFormats.MAP_MODIFIED_WHILE_ITERATING);
             }
             if (current < 0) {
                 throw MathRuntimeException.createNoSuchElementException(LocalizedFormats.ITERATOR_EXHAUSTED);
             }
             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 MathRuntimeException.createConcurrentModificationException(LocalizedFormats.MAP_MODIFIED_WHILE_ITERATING);
             }

             // advance on step
             current = next;

             // prepare next step
             try {
                 while (states[++next] != FULL) {
                     // nothing to do
                 }
             } catch (ArrayIndexOutOfBoundsException e) {
                 next = -2;
                 if (current < 0) {
                     throw MathRuntimeException.createNoSuchElementException(LocalizedFormats.ITERATOR_EXHAUSTED);
                 }
             }

         }

     }

     /**
      * 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;
     }

     /** Build an array of elements.
      * @param length size of the array to build
      * @return a new array
      */
     @SuppressWarnings("unchecked") // field is of type T
     private T[] buildArray(final int length) {
         return (T[]) Array.newInstance(field.getZero().getClass(), length);
     }

 }
	/*
	* 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.math.util;

	import java.io.IOException;
	import java.io.ObjectInputStream;
	import java.io.Serializable;
	import java.lang.reflect.Array;
	import java.util.ConcurrentModificationException;
	import java.util.NoSuchElementException;

	import org.apache.commons.math.Field;
	import org.apache.commons.math.FieldElement;
	import org.apache.commons.math.MathRuntimeException;
	import org.apache.commons.math.exception.util.LocalizedFormats;

	/**
	* Open addressed map from int to FieldElement.
	* <p>This class provides a dedicated map from integers to FieldElements with a
	* much smaller memory overhead than standard <code>java.util.Map</code>.</p>
	* <p>This class is not synchronized. The specialized iterators returned by
	* {@link #iterator()} are fail-fast: they throw a
	* <code>ConcurrentModificationException</code> when they detect the map has been
	* modified during iteration.</p>
	* @param <T> the type of the field elements
	* @version $Revision: 990655 $ $Date: 2010-08-29 23:49:40 +0200 (dim. 29 août 2010) $
	* @since 2.0
	*/
	public class OpenIntToFieldHashMap<T extends FieldElement<T>> 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 = -9179080286849120720L;

	/** Load factor for the map. */
	private static final float LOAD_FACTOR = 0.5f;

	/** Default starting size.
	* <p>This must be a power of two for bit mask to work properly. </p>
	*/
	private static final int DEFAULT_EXPECTED_SIZE = 16;

	/** Multiplier for size growth when map fills up.
	* <p>This must be a power of two for bit mask to work properly. </p>
	*/
	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;

	/** Field to which the elements belong. */
	private final Field<T> field;

	/** Keys table. */
	private int[] keys;

	/** Values table. */
	private T[] values;

	/** States table. */
	private byte[] states;

	/** Return value for missing entries. */
	private final T 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 zero for missing entries.
	* @param field field to which the elements belong
	*/
	public OpenIntToFieldHashMap(final Field<T>field) {
	this(field, DEFAULT_EXPECTED_SIZE, field.getZero());
	}

	/**
	* Build an empty map with default size
	* @param field field to which the elements belong
	* @param missingEntries value to return when a missing entry is fetched
	*/
	public OpenIntToFieldHashMap(final Field<T>field, final T missingEntries) {
	this(field,DEFAULT_EXPECTED_SIZE, missingEntries);
	}

	/**
	* Build an empty map with specified size and using zero for missing entries.
	* @param field field to which the elements belong
	* @param expectedSize expected number of elements in the map
	*/
	public OpenIntToFieldHashMap(final Field<T> field,final int expectedSize) {
	this(field,expectedSize, field.getZero());
	}

	/**
	* Build an empty map with specified size.
	* @param field field to which the elements belong
	* @param expectedSize expected number of elements in the map
	* @param missingEntries value to return when a missing entry is fetched
	*/
	public OpenIntToFieldHashMap(final Field<T> field,final int expectedSize,
	final T missingEntries) {
	this.field = field;
	final int capacity = computeCapacity(expectedSize);
	keys = new int[capacity];
	values = buildArray(capacity);
	states = new byte[capacity];
	this.missingEntries = missingEntries;
	mask = capacity - 1;
	}

	/**
	* Copy constructor.
	* @param source map to copy
	*/
	public OpenIntToFieldHashMap(final OpenIntToFieldHashMap<T> source) {
	field = source.field;
	final int length = source.keys.length;
	keys = new int[length];
	System.arraycopy(source.keys, 0, keys, 0, length);
	values = buildArray(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 T 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.
	* <p>The specialized iterators returned are fail-fast: they throw a
	* <code>ConcurrentModificationException</code> when they detect the map
	* has been modified during iteration.</p>
	* @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 T 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 T doRemove(int index) {
	keys[index] = 0;
	states[index] = REMOVED;
	final T 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 T put(final int key, final T value) {
	int index = findInsertionIndex(key);
	T 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 T[] oldValues = values;
	final byte[] oldStates = states;

	final int newLength = RESIZE_MULTIPLIER * oldLength;
	final int[] newKeys = new int[newLength];
	final T[] newValues = buildArray(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) {
	// 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 MathRuntimeException.createConcurrentModificationException(LocalizedFormats.MAP_MODIFIED_WHILE_ITERATING);
	}
	if (current < 0) {
	throw MathRuntimeException.createNoSuchElementException(LocalizedFormats.ITERATOR_EXHAUSTED);
	}
	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 T value()
	throws ConcurrentModificationException, NoSuchElementException {
	if (referenceCount != count) {
	throw MathRuntimeException.createConcurrentModificationException(LocalizedFormats.MAP_MODIFIED_WHILE_ITERATING);
	}
	if (current < 0) {
	throw MathRuntimeException.createNoSuchElementException(LocalizedFormats.ITERATOR_EXHAUSTED);
	}
	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 MathRuntimeException.createConcurrentModificationException(LocalizedFormats.MAP_MODIFIED_WHILE_ITERATING);
	}

	// advance on step
	current = next;

	// prepare next step
	try {
	while (states[++next] != FULL) {
	// nothing to do
	}
	} catch (ArrayIndexOutOfBoundsException e) {
	next = -2;
	if (current < 0) {
	throw MathRuntimeException.createNoSuchElementException(LocalizedFormats.ITERATOR_EXHAUSTED);
	}
	}

	}

	}

	/**
	* 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;
	}

	/** Build an array of elements.
	* @param length size of the array to build
	* @return a new array
	*/
	@SuppressWarnings("unchecked") // field is of type T
	private T[] buildArray(final int length) {
	return (T[]) Array.newInstance(field.getZero().getClass(), length);
	}

	}