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