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