    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
    018    package org.apache.commons.math3.util;
    019
    020    import java.io.IOException;
    021    import java.io.ObjectInputStream;
    022    import java.io.Serializable;
    023    import java.util.ConcurrentModificationException;
    024    import 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     */
    037    public 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    }