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    }