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