001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017
018package org.apache.commons.math3.util;
019
020import java.io.IOException;
021import java.io.ObjectInputStream;
022import java.io.Serializable;
023import java.util.ConcurrentModificationException;
024import java.util.NoSuchElementException;
025
026/**
027 * Open addressed map from int to double.
028 * <p>This class provides a dedicated map from integers to doubles with a
029 * much smaller memory overhead than standard <code>java.util.Map</code>.</p>
030 * <p>This class is not synchronized. The specialized iterators returned by
031 * {@link #iterator()} are fail-fast: they throw a
032 * <code>ConcurrentModificationException</code> when they detect the map has been
033 * modified during iteration.</p>
034 * @version $Id: OpenIntToDoubleHashMap.java 1421448 2012-12-13 19:45:57Z tn $
035 * @since 2.0
036 */
037public class OpenIntToDoubleHashMap implements Serializable {
038
039    /** Status indicator for free table entries. */
040    protected static final byte FREE    = 0;
041
042    /** Status indicator for full table entries. */
043    protected static final byte FULL    = 1;
044
045    /** Status indicator for removed table entries. */
046    protected static final byte REMOVED = 2;
047
048    /** Serializable version identifier */
049    private static final long serialVersionUID = -3646337053166149105L;
050
051    /** Load factor for the map. */
052    private static final float LOAD_FACTOR = 0.5f;
053
054    /** Default starting size.
055     * <p>This must be a power of two for bit mask to work properly. </p>
056     */
057    private static final int DEFAULT_EXPECTED_SIZE = 16;
058
059    /** Multiplier for size growth when map fills up.
060     * <p>This must be a power of two for bit mask to work properly. </p>
061     */
062    private static final int RESIZE_MULTIPLIER = 2;
063
064    /** Number of bits to perturb the index when probing for collision resolution. */
065    private static final int PERTURB_SHIFT = 5;
066
067    /** Keys table. */
068    private int[] keys;
069
070    /** Values table. */
071    private double[] values;
072
073    /** States table. */
074    private byte[] states;
075
076    /** Return value for missing entries. */
077    private final double missingEntries;
078
079    /** Current size of the map. */
080    private int size;
081
082    /** Bit mask for hash values. */
083    private int mask;
084
085    /** Modifications count. */
086    private transient int count;
087
088    /**
089     * Build an empty map with default size and using NaN for missing entries.
090     */
091    public OpenIntToDoubleHashMap() {
092        this(DEFAULT_EXPECTED_SIZE, Double.NaN);
093    }
094
095    /**
096     * Build an empty map with default size
097     * @param missingEntries value to return when a missing entry is fetched
098     */
099    public OpenIntToDoubleHashMap(final double missingEntries) {
100        this(DEFAULT_EXPECTED_SIZE, missingEntries);
101    }
102
103    /**
104     * Build an empty map with specified size and using NaN for missing entries.
105     * @param expectedSize expected number of elements in the map
106     */
107    public OpenIntToDoubleHashMap(final int expectedSize) {
108        this(expectedSize, Double.NaN);
109    }
110
111    /**
112     * Build an empty map with specified size.
113     * @param expectedSize expected number of elements in the map
114     * @param missingEntries value to return when a missing entry is fetched
115     */
116    public OpenIntToDoubleHashMap(final int expectedSize,
117                                  final double missingEntries) {
118        final int capacity = computeCapacity(expectedSize);
119        keys   = new int[capacity];
120        values = new double[capacity];
121        states = new byte[capacity];
122        this.missingEntries = missingEntries;
123        mask   = capacity - 1;
124    }
125
126    /**
127     * Copy constructor.
128     * @param source map to copy
129     */
130    public OpenIntToDoubleHashMap(final OpenIntToDoubleHashMap source) {
131        final int length = source.keys.length;
132        keys = new int[length];
133        System.arraycopy(source.keys, 0, keys, 0, length);
134        values = new double[length];
135        System.arraycopy(source.values, 0, values, 0, length);
136        states = new byte[length];
137        System.arraycopy(source.states, 0, states, 0, length);
138        missingEntries = source.missingEntries;
139        size  = source.size;
140        mask  = source.mask;
141        count = source.count;
142    }
143
144    /**
145     * Compute the capacity needed for a given size.
146     * @param expectedSize expected size of the map
147     * @return capacity to use for the specified size
148     */
149    private static int computeCapacity(final int expectedSize) {
150        if (expectedSize == 0) {
151            return 1;
152        }
153        final int capacity   = (int) FastMath.ceil(expectedSize / LOAD_FACTOR);
154        final int powerOfTwo = Integer.highestOneBit(capacity);
155        if (powerOfTwo == capacity) {
156            return capacity;
157        }
158        return nextPowerOfTwo(capacity);
159    }
160
161    /**
162     * Find the smallest power of two greater than the input value
163     * @param i input value
164     * @return smallest power of two greater than the input value
165     */
166    private static int nextPowerOfTwo(final int i) {
167        return Integer.highestOneBit(i) << 1;
168    }
169
170    /**
171     * Get the stored value associated with the given key
172     * @param key key associated with the data
173     * @return data associated with the key
174     */
175    public double get(final int key) {
176
177        final int hash  = hashOf(key);
178        int index = hash & mask;
179        if (containsKey(key, index)) {
180            return values[index];
181        }
182
183        if (states[index] == FREE) {
184            return missingEntries;
185        }
186
187        int j = index;
188        for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
189            j = probe(perturb, j);
190            index = j & mask;
191            if (containsKey(key, index)) {
192                return values[index];
193            }
194        }
195
196        return missingEntries;
197
198    }
199
200    /**
201     * Check if a value is associated with a key.
202     * @param key key to check
203     * @return true if a value is associated with key
204     */
205    public boolean containsKey(final int key) {
206
207        final int hash  = hashOf(key);
208        int index = hash & mask;
209        if (containsKey(key, index)) {
210            return true;
211        }
212
213        if (states[index] == FREE) {
214            return false;
215        }
216
217        int j = index;
218        for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
219            j = probe(perturb, j);
220            index = j & mask;
221            if (containsKey(key, index)) {
222                return true;
223            }
224        }
225
226        return false;
227
228    }
229
230    /**
231     * Get an iterator over map elements.
232     * <p>The specialized iterators returned are fail-fast: they throw a
233     * <code>ConcurrentModificationException</code> when they detect the map
234     * has been modified during iteration.</p>
235     * @return iterator over the map elements
236     */
237    public Iterator iterator() {
238        return new Iterator();
239    }
240
241    /**
242     * Perturb the hash for starting probing.
243     * @param hash initial hash
244     * @return perturbed hash
245     */
246    private static int perturb(final int hash) {
247        return hash & 0x7fffffff;
248    }
249
250    /**
251     * Find the index at which a key should be inserted
252     * @param key key to lookup
253     * @return index at which key should be inserted
254     */
255    private int findInsertionIndex(final int key) {
256        return findInsertionIndex(keys, states, key, mask);
257    }
258
259    /**
260     * Find the index at which a key should be inserted
261     * @param keys keys table
262     * @param states states table
263     * @param key key to lookup
264     * @param mask bit mask for hash values
265     * @return index at which key should be inserted
266     */
267    private static int findInsertionIndex(final int[] keys, final byte[] states,
268                                          final int key, final int mask) {
269        final int hash = hashOf(key);
270        int index = hash & mask;
271        if (states[index] == FREE) {
272            return index;
273        } else if (states[index] == FULL && keys[index] == key) {
274            return changeIndexSign(index);
275        }
276
277        int perturb = perturb(hash);
278        int j = index;
279        if (states[index] == FULL) {
280            while (true) {
281                j = probe(perturb, j);
282                index = j & mask;
283                perturb >>= PERTURB_SHIFT;
284
285                if (states[index] != FULL || keys[index] == key) {
286                    break;
287                }
288            }
289        }
290
291        if (states[index] == FREE) {
292            return index;
293        } else if (states[index] == FULL) {
294            // due to the loop exit condition,
295            // if (states[index] == FULL) then keys[index] == key
296            return changeIndexSign(index);
297        }
298
299        final int firstRemoved = index;
300        while (true) {
301            j = probe(perturb, j);
302            index = j & mask;
303
304            if (states[index] == FREE) {
305                return firstRemoved;
306            } else if (states[index] == FULL && keys[index] == key) {
307                return changeIndexSign(index);
308            }
309
310            perturb >>= PERTURB_SHIFT;
311
312        }
313
314    }
315
316    /**
317     * Compute next probe for collision resolution
318     * @param perturb perturbed hash
319     * @param j previous probe
320     * @return next probe
321     */
322    private static int probe(final int perturb, final int j) {
323        return (j << 2) + j + perturb + 1;
324    }
325
326    /**
327     * Change the index sign
328     * @param index initial index
329     * @return changed index
330     */
331    private static int changeIndexSign(final int index) {
332        return -index - 1;
333    }
334
335    /**
336     * Get the number of elements stored in the map.
337     * @return number of elements stored in the map
338     */
339    public int size() {
340        return size;
341    }
342
343
344    /**
345     * Remove the value associated with a key.
346     * @param key key to which the value is associated
347     * @return removed value
348     */
349    public double remove(final int key) {
350
351        final int hash  = hashOf(key);
352        int index = hash & mask;
353        if (containsKey(key, index)) {
354            return doRemove(index);
355        }
356
357        if (states[index] == FREE) {
358            return missingEntries;
359        }
360
361        int j = index;
362        for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
363            j = probe(perturb, j);
364            index = j & mask;
365            if (containsKey(key, index)) {
366                return doRemove(index);
367            }
368        }
369
370        return missingEntries;
371
372    }
373
374    /**
375     * Check if the tables contain an element associated with specified key
376     * at specified index.
377     * @param key key to check
378     * @param index index to check
379     * @return true if an element is associated with key at index
380     */
381    private boolean containsKey(final int key, final int index) {
382        return (key != 0 || states[index] == FULL) && keys[index] == key;
383    }
384
385    /**
386     * Remove an element at specified index.
387     * @param index index of the element to remove
388     * @return removed value
389     */
390    private double doRemove(int index) {
391        keys[index]   = 0;
392        states[index] = REMOVED;
393        final double previous = values[index];
394        values[index] = missingEntries;
395        --size;
396        ++count;
397        return previous;
398    }
399
400    /**
401     * Put a value associated with a key in the map.
402     * @param key key to which value is associated
403     * @param value value to put in the map
404     * @return previous value associated with the key
405     */
406    public double put(final int key, final double value) {
407        int index = findInsertionIndex(key);
408        double previous = missingEntries;
409        boolean newMapping = true;
410        if (index < 0) {
411            index = changeIndexSign(index);
412            previous = values[index];
413            newMapping = false;
414        }
415        keys[index]   = key;
416        states[index] = FULL;
417        values[index] = value;
418        if (newMapping) {
419            ++size;
420            if (shouldGrowTable()) {
421                growTable();
422            }
423            ++count;
424        }
425        return previous;
426
427    }
428
429    /**
430     * Grow the tables.
431     */
432    private void growTable() {
433
434        final int oldLength      = states.length;
435        final int[] oldKeys      = keys;
436        final double[] oldValues = values;
437        final byte[] oldStates   = states;
438
439        final int newLength = RESIZE_MULTIPLIER * oldLength;
440        final int[] newKeys = new int[newLength];
441        final double[] newValues = new double[newLength];
442        final byte[] newStates = new byte[newLength];
443        final int newMask = newLength - 1;
444        for (int i = 0; i < oldLength; ++i) {
445            if (oldStates[i] == FULL) {
446                final int key = oldKeys[i];
447                final int index = findInsertionIndex(newKeys, newStates, key, newMask);
448                newKeys[index]   = key;
449                newValues[index] = oldValues[i];
450                newStates[index] = FULL;
451            }
452        }
453
454        mask   = newMask;
455        keys   = newKeys;
456        values = newValues;
457        states = newStates;
458
459    }
460
461    /**
462     * Check if tables should grow due to increased size.
463     * @return true if  tables should grow
464     */
465    private boolean shouldGrowTable() {
466        return size > (mask + 1) * LOAD_FACTOR;
467    }
468
469    /**
470     * Compute the hash value of a key
471     * @param key key to hash
472     * @return hash value of the key
473     */
474    private static int hashOf(final int key) {
475        final int h = key ^ ((key >>> 20) ^ (key >>> 12));
476        return h ^ (h >>> 7) ^ (h >>> 4);
477    }
478
479
480    /** Iterator class for the map. */
481    public class Iterator {
482
483        /** Reference modification count. */
484        private final int referenceCount;
485
486        /** Index of current element. */
487        private int current;
488
489        /** Index of next element. */
490        private int next;
491
492        /**
493         * Simple constructor.
494         */
495        private Iterator() {
496
497            // preserve the modification count of the map to detect concurrent modifications later
498            referenceCount = count;
499
500            // initialize current index
501            next = -1;
502            try {
503                advance();
504            } catch (NoSuchElementException nsee) { // NOPMD
505                // ignored
506            }
507
508        }
509
510        /**
511         * Check if there is a next element in the map.
512         * @return true if there is a next element
513         */
514        public boolean hasNext() {
515            return next >= 0;
516        }
517
518        /**
519         * Get the key of current entry.
520         * @return key of current entry
521         * @exception ConcurrentModificationException if the map is modified during iteration
522         * @exception NoSuchElementException if there is no element left in the map
523         */
524        public int key()
525            throws ConcurrentModificationException, NoSuchElementException {
526            if (referenceCount != count) {
527                throw new ConcurrentModificationException();
528            }
529            if (current < 0) {
530                throw new NoSuchElementException();
531            }
532            return keys[current];
533        }
534
535        /**
536         * Get the value of current entry.
537         * @return value of current entry
538         * @exception ConcurrentModificationException if the map is modified during iteration
539         * @exception NoSuchElementException if there is no element left in the map
540         */
541        public double value()
542            throws ConcurrentModificationException, NoSuchElementException {
543            if (referenceCount != count) {
544                throw new ConcurrentModificationException();
545            }
546            if (current < 0) {
547                throw new NoSuchElementException();
548            }
549            return values[current];
550        }
551
552        /**
553         * Advance iterator one step further.
554         * @exception ConcurrentModificationException if the map is modified during iteration
555         * @exception NoSuchElementException if there is no element left in the map
556         */
557        public void advance()
558            throws ConcurrentModificationException, NoSuchElementException {
559
560            if (referenceCount != count) {
561                throw new ConcurrentModificationException();
562            }
563
564            // advance on step
565            current = next;
566
567            // prepare next step
568            try {
569                while (states[++next] != FULL) { // NOPMD
570                    // nothing to do
571                }
572            } catch (ArrayIndexOutOfBoundsException e) {
573                next = -2;
574                if (current < 0) {
575                    throw new NoSuchElementException();
576                }
577            }
578
579        }
580
581    }
582
583    /**
584     * Read a serialized object.
585     * @param stream input stream
586     * @throws IOException if object cannot be read
587     * @throws ClassNotFoundException if the class corresponding
588     * to the serialized object cannot be found
589     */
590    private void readObject(final ObjectInputStream stream)
591        throws IOException, ClassNotFoundException {
592        stream.defaultReadObject();
593        count = 0;
594    }
595
596
597}