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