1dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond/* 2dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Licensed to the Apache Software Foundation (ASF) under one or more 3dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * contributor license agreements. See the NOTICE file distributed with 4dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * this work for additional information regarding copyright ownership. 5dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * The ASF licenses this file to You under the Apache License, Version 2.0 6dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * (the "License"); you may not use this file except in compliance with 7dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * the License. You may obtain a copy of the License at 8dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * 9dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * http://www.apache.org/licenses/LICENSE-2.0 10dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * 11dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Unless required by applicable law or agreed to in writing, software 12dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * distributed under the License is distributed on an "AS IS" BASIS, 13dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * See the License for the specific language governing permissions and 15dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * limitations under the License. 16dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 17dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondpackage org.apache.commons.math.util; 18dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 19dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport java.io.IOException; 20dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport java.io.ObjectInputStream; 21dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport java.io.Serializable; 22dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport java.lang.reflect.Array; 23dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport java.util.ConcurrentModificationException; 24dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport java.util.NoSuchElementException; 25dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 26dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport org.apache.commons.math.Field; 27dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport org.apache.commons.math.FieldElement; 28dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport org.apache.commons.math.MathRuntimeException; 29dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport org.apache.commons.math.exception.util.LocalizedFormats; 30dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 31dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond/** 32dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Open addressed map from int to FieldElement. 33dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * <p>This class provides a dedicated map from integers to FieldElements with a 34dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * much smaller memory overhead than standard <code>java.util.Map</code>.</p> 35dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * <p>This class is not synchronized. The specialized iterators returned by 36dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * {@link #iterator()} are fail-fast: they throw a 37dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * <code>ConcurrentModificationException</code> when they detect the map has been 38dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * modified during iteration.</p> 39dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param <T> the type of the field elements 40dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @version $Revision: 990655 $ $Date: 2010-08-29 23:49:40 +0200 (dim. 29 août 2010) $ 41dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @since 2.0 42dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 43dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondpublic class OpenIntToFieldHashMap<T extends FieldElement<T>> implements Serializable { 44dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 45dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Status indicator for free table entries. */ 46dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected static final byte FREE = 0; 47dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 48dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Status indicator for full table entries. */ 49dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected static final byte FULL = 1; 50dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 51dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Status indicator for removed table entries. */ 52dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected static final byte REMOVED = 2; 53dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 54dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Serializable version identifier. */ 55dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private static final long serialVersionUID = -9179080286849120720L; 56dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 57dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Load factor for the map. */ 58dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private static final float LOAD_FACTOR = 0.5f; 59dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 60dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Default starting size. 61dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * <p>This must be a power of two for bit mask to work properly. </p> 62dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 63dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private static final int DEFAULT_EXPECTED_SIZE = 16; 64dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 65dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Multiplier for size growth when map fills up. 66dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * <p>This must be a power of two for bit mask to work properly. </p> 67dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 68dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private static final int RESIZE_MULTIPLIER = 2; 69dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 70dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Number of bits to perturb the index when probing for collision resolution. */ 71dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private static final int PERTURB_SHIFT = 5; 72dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 73dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Field to which the elements belong. */ 74dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private final Field<T> field; 75dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 76dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Keys table. */ 77dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private int[] keys; 78dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 79dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Values table. */ 80dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private T[] values; 81dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 82dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** States table. */ 83dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private byte[] states; 84dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 85dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Return value for missing entries. */ 86dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private final T missingEntries; 87dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 88dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Current size of the map. */ 89dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private int size; 90dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 91dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Bit mask for hash values. */ 92dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private int mask; 93dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 94dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Modifications count. */ 95dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private transient int count; 96dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 97dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 98dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Build an empty map with default size and using zero for missing entries. 99dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param field field to which the elements belong 100dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 101dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond public OpenIntToFieldHashMap(final Field<T>field) { 102dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond this(field, DEFAULT_EXPECTED_SIZE, field.getZero()); 103dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 104dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 105dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 106dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Build an empty map with default size 107dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param field field to which the elements belong 108dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param missingEntries value to return when a missing entry is fetched 109dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 110dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond public OpenIntToFieldHashMap(final Field<T>field, final T missingEntries) { 111dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond this(field,DEFAULT_EXPECTED_SIZE, missingEntries); 112dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 113dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 114dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 115dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Build an empty map with specified size and using zero for missing entries. 116dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param field field to which the elements belong 117dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param expectedSize expected number of elements in the map 118dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 119dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond public OpenIntToFieldHashMap(final Field<T> field,final int expectedSize) { 120dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond this(field,expectedSize, field.getZero()); 121dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 122dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 123dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 124dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Build an empty map with specified size. 125dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param field field to which the elements belong 126dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param expectedSize expected number of elements in the map 127dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param missingEntries value to return when a missing entry is fetched 128dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 129dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond public OpenIntToFieldHashMap(final Field<T> field,final int expectedSize, 130dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final T missingEntries) { 131dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond this.field = field; 132dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final int capacity = computeCapacity(expectedSize); 133dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond keys = new int[capacity]; 134dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond values = buildArray(capacity); 135dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond states = new byte[capacity]; 136dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond this.missingEntries = missingEntries; 137dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond mask = capacity - 1; 138dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 139dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 140dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 141dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Copy constructor. 142dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param source map to copy 143dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 144dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond public OpenIntToFieldHashMap(final OpenIntToFieldHashMap<T> source) { 145dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond field = source.field; 146dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final int length = source.keys.length; 147dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond keys = new int[length]; 148dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond System.arraycopy(source.keys, 0, keys, 0, length); 149dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond values = buildArray(length); 150dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond System.arraycopy(source.values, 0, values, 0, length); 151dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond states = new byte[length]; 152dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond System.arraycopy(source.states, 0, states, 0, length); 153dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond missingEntries = source.missingEntries; 154dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond size = source.size; 155dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond mask = source.mask; 156dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond count = source.count; 157dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 158dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 159dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 160dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Compute the capacity needed for a given size. 161dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param expectedSize expected size of the map 162dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return capacity to use for the specified size 163dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 164dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private static int computeCapacity(final int expectedSize) { 165dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (expectedSize == 0) { 166dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return 1; 167dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 168dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final int capacity = (int) FastMath.ceil(expectedSize / LOAD_FACTOR); 169dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final int powerOfTwo = Integer.highestOneBit(capacity); 170dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (powerOfTwo == capacity) { 171dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return capacity; 172dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 173dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return nextPowerOfTwo(capacity); 174dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 175dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 176dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 177dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Find the smallest power of two greater than the input value 178dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param i input value 179dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return smallest power of two greater than the input value 180dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 181dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private static int nextPowerOfTwo(final int i) { 182dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return Integer.highestOneBit(i) << 1; 183dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 184dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 185dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 186dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get the stored value associated with the given key 187dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param key key associated with the data 188dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return data associated with the key 189dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 190dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond public T get(final int key) { 191dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 192dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final int hash = hashOf(key); 193dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int index = hash & mask; 194dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (containsKey(key, index)) { 195dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return values[index]; 196dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 197dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 198dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (states[index] == FREE) { 199dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return missingEntries; 200dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 201dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 202dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int j = index; 203dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) { 204dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond j = probe(perturb, j); 205dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond index = j & mask; 206dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (containsKey(key, index)) { 207dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return values[index]; 208dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 209dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 210dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 211dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return missingEntries; 212dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 213dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 214dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 215dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 216dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Check if a value is associated with a key. 217dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param key key to check 218dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return true if a value is associated with key 219dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 220dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond public boolean containsKey(final int key) { 221dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 222dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final int hash = hashOf(key); 223dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int index = hash & mask; 224dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (containsKey(key, index)) { 225dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return true; 226dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 227dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 228dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (states[index] == FREE) { 229dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return false; 230dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 231dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 232dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int j = index; 233dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) { 234dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond j = probe(perturb, j); 235dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond index = j & mask; 236dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (containsKey(key, index)) { 237dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return true; 238dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 239dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 240dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 241dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return false; 242dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 243dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 244dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 245dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 246dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get an iterator over map elements. 247dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * <p>The specialized iterators returned are fail-fast: they throw a 248dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * <code>ConcurrentModificationException</code> when they detect the map 249dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * has been modified during iteration.</p> 250dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return iterator over the map elements 251dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 252dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond public Iterator iterator() { 253dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return new Iterator(); 254dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 255dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 256dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 257dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Perturb the hash for starting probing. 258dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param hash initial hash 259dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return perturbed hash 260dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 261dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private static int perturb(final int hash) { 262dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return hash & 0x7fffffff; 263dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 264dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 265dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 266dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Find the index at which a key should be inserted 267dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param key key to lookup 268dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return index at which key should be inserted 269dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 270dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private int findInsertionIndex(final int key) { 271dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return findInsertionIndex(keys, states, key, mask); 272dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 273dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 274dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 275dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Find the index at which a key should be inserted 276dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param keys keys table 277dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param states states table 278dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param key key to lookup 279dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param mask bit mask for hash values 280dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return index at which key should be inserted 281dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 282dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private static int findInsertionIndex(final int[] keys, final byte[] states, 283dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final int key, final int mask) { 284dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final int hash = hashOf(key); 285dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int index = hash & mask; 286dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (states[index] == FREE) { 287dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return index; 288dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } else if (states[index] == FULL && keys[index] == key) { 289dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return changeIndexSign(index); 290dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 291dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 292dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int perturb = perturb(hash); 293dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int j = index; 294dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (states[index] == FULL) { 295dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond while (true) { 296dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond j = probe(perturb, j); 297dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond index = j & mask; 298dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond perturb >>= PERTURB_SHIFT; 299dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 300dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (states[index] != FULL || keys[index] == key) { 301dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond break; 302dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 303dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 304dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 305dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 306dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (states[index] == FREE) { 307dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return index; 308dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } else if (states[index] == FULL) { 309dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond // due to the loop exit condition, 310dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond // if (states[index] == FULL) then keys[index] == key 311dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return changeIndexSign(index); 312dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 313dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 314dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final int firstRemoved = index; 315dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond while (true) { 316dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond j = probe(perturb, j); 317dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond index = j & mask; 318dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 319dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (states[index] == FREE) { 320dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return firstRemoved; 321dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } else if (states[index] == FULL && keys[index] == key) { 322dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return changeIndexSign(index); 323dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 324dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 325dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond perturb >>= PERTURB_SHIFT; 326dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 327dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 328dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 329dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 330dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 331dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 332dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Compute next probe for collision resolution 333dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param perturb perturbed hash 334dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param j previous probe 335dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return next probe 336dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 337dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private static int probe(final int perturb, final int j) { 338dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return (j << 2) + j + perturb + 1; 339dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 340dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 341dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 342dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Change the index sign 343dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param index initial index 344dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return changed index 345dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 346dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private static int changeIndexSign(final int index) { 347dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return -index - 1; 348dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 349dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 350dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 351dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get the number of elements stored in the map. 352dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return number of elements stored in the map 353dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 354dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond public int size() { 355dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return size; 356dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 357dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 358dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 359dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 360dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Remove the value associated with a key. 361dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param key key to which the value is associated 362dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return removed value 363dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 364dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond public T remove(final int key) { 365dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 366dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final int hash = hashOf(key); 367dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int index = hash & mask; 368dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (containsKey(key, index)) { 369dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return doRemove(index); 370dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 371dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 372dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (states[index] == FREE) { 373dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return missingEntries; 374dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 375dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 376dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int j = index; 377dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) { 378dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond j = probe(perturb, j); 379dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond index = j & mask; 380dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (containsKey(key, index)) { 381dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return doRemove(index); 382dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 383dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 384dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 385dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return missingEntries; 386dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 387dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 388dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 389dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 390dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Check if the tables contain an element associated with specified key 391dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * at specified index. 392dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param key key to check 393dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param index index to check 394dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return true if an element is associated with key at index 395dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 396dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private boolean containsKey(final int key, final int index) { 397dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return (key != 0 || states[index] == FULL) && keys[index] == key; 398dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 399dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 400dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 401dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Remove an element at specified index. 402dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param index index of the element to remove 403dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return removed value 404dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 405dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private T doRemove(int index) { 406dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond keys[index] = 0; 407dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond states[index] = REMOVED; 408dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final T previous = values[index]; 409dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond values[index] = missingEntries; 410dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond --size; 411dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond ++count; 412dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return previous; 413dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 414dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 415dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 416dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Put a value associated with a key in the map. 417dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param key key to which value is associated 418dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param value value to put in the map 419dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return previous value associated with the key 420dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 421dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond public T put(final int key, final T value) { 422dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int index = findInsertionIndex(key); 423dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond T previous = missingEntries; 424dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond boolean newMapping = true; 425dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (index < 0) { 426dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond index = changeIndexSign(index); 427dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond previous = values[index]; 428dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond newMapping = false; 429dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 430dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond keys[index] = key; 431dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond states[index] = FULL; 432dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond values[index] = value; 433dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (newMapping) { 434dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond ++size; 435dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (shouldGrowTable()) { 436dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond growTable(); 437dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 438dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond ++count; 439dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 440dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return previous; 441dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 442dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 443dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 444dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 445dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Grow the tables. 446dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 447dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private void growTable() { 448dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 449dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final int oldLength = states.length; 450dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final int[] oldKeys = keys; 451dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final T[] oldValues = values; 452dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final byte[] oldStates = states; 453dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 454dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final int newLength = RESIZE_MULTIPLIER * oldLength; 455dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final int[] newKeys = new int[newLength]; 456dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final T[] newValues = buildArray(newLength); 457dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final byte[] newStates = new byte[newLength]; 458dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final int newMask = newLength - 1; 459dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond for (int i = 0; i < oldLength; ++i) { 460dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (oldStates[i] == FULL) { 461dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final int key = oldKeys[i]; 462dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final int index = findInsertionIndex(newKeys, newStates, key, newMask); 463dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond newKeys[index] = key; 464dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond newValues[index] = oldValues[i]; 465dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond newStates[index] = FULL; 466dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 467dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 468dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 469dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond mask = newMask; 470dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond keys = newKeys; 471dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond values = newValues; 472dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond states = newStates; 473dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 474dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 475dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 476dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 477dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Check if tables should grow due to increased size. 478dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return true if tables should grow 479dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 480dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private boolean shouldGrowTable() { 481dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return size > (mask + 1) * LOAD_FACTOR; 482dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 483dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 484dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 485dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Compute the hash value of a key 486dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param key key to hash 487dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return hash value of the key 488dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 489dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private static int hashOf(final int key) { 490dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final int h = key ^ ((key >>> 20) ^ (key >>> 12)); 491dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return h ^ (h >>> 7) ^ (h >>> 4); 492dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 493dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 494dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 495dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Iterator class for the map. */ 496dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond public class Iterator { 497dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 498dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Reference modification count. */ 499dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private final int referenceCount; 500dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 501dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Index of current element. */ 502dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private int current; 503dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 504dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Index of next element. */ 505dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private int next; 506dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 507dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 508dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Simple constructor. 509dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 510dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private Iterator() { 511dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 512dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond // preserve the modification count of the map to detect concurrent modifications later 513dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond referenceCount = count; 514dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 515dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond // initialize current index 516dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond next = -1; 517dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond try { 518dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond advance(); 519dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } catch (NoSuchElementException nsee) { 520dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond // ignored 521dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 522dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 523dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 524dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 525dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 526dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Check if there is a next element in the map. 527dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return true if there is a next element 528dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 529dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond public boolean hasNext() { 530dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return next >= 0; 531dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 532dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 533dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 534dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get the key of current entry. 535dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return key of current entry 536dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @exception ConcurrentModificationException if the map is modified during iteration 537dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @exception NoSuchElementException if there is no element left in the map 538dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 539dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond public int key() 540dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond throws ConcurrentModificationException, NoSuchElementException { 541dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (referenceCount != count) { 542dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond throw MathRuntimeException.createConcurrentModificationException(LocalizedFormats.MAP_MODIFIED_WHILE_ITERATING); 543dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 544dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (current < 0) { 545dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond throw MathRuntimeException.createNoSuchElementException(LocalizedFormats.ITERATOR_EXHAUSTED); 546dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 547dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return keys[current]; 548dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 549dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 550dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 551dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get the value of current entry. 552dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return value of current entry 553dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @exception ConcurrentModificationException if the map is modified during iteration 554dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @exception NoSuchElementException if there is no element left in the map 555dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 556dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond public T value() 557dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond throws ConcurrentModificationException, NoSuchElementException { 558dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (referenceCount != count) { 559dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond throw MathRuntimeException.createConcurrentModificationException(LocalizedFormats.MAP_MODIFIED_WHILE_ITERATING); 560dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 561dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (current < 0) { 562dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond throw MathRuntimeException.createNoSuchElementException(LocalizedFormats.ITERATOR_EXHAUSTED); 563dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 564dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return values[current]; 565dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 566dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 567dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 568dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Advance iterator one step further. 569dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @exception ConcurrentModificationException if the map is modified during iteration 570dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @exception NoSuchElementException if there is no element left in the map 571dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 572dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond public void advance() 573dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond throws ConcurrentModificationException, NoSuchElementException { 574dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 575dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (referenceCount != count) { 576dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond throw MathRuntimeException.createConcurrentModificationException(LocalizedFormats.MAP_MODIFIED_WHILE_ITERATING); 577dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 578dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 579dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond // advance on step 580dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond current = next; 581dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 582dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond // prepare next step 583dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond try { 584dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond while (states[++next] != FULL) { 585dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond // nothing to do 586dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 587dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } catch (ArrayIndexOutOfBoundsException e) { 588dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond next = -2; 589dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (current < 0) { 590dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond throw MathRuntimeException.createNoSuchElementException(LocalizedFormats.ITERATOR_EXHAUSTED); 591dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 592dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 593dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 594dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 595dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 596dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 597dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 598dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 599dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Read a serialized object. 600dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param stream input stream 601dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @throws IOException if object cannot be read 602dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @throws ClassNotFoundException if the class corresponding 603dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * to the serialized object cannot be found 604dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 605dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private void readObject(final ObjectInputStream stream) 606dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond throws IOException, ClassNotFoundException { 607dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond stream.defaultReadObject(); 608dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond count = 0; 609dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 610dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 611dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Build an array of elements. 612dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param length size of the array to build 613dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return a new array 614dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 615dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond @SuppressWarnings("unchecked") // field is of type T 616dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private T[] buildArray(final int length) { 617dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return (T[]) Array.newInstance(field.getZero().getClass(), length); 618dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 619dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 620dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond} 621