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