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