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: 746578 $ $Date: 2009-02-21 15:01:14 -0500 (Sat, 21 Feb 2009) $
037     * @since 2.0
038     */
039    public class OpenIntToDoubleHashMap implements Serializable {
040    
041        /** Serializable version identifier */
042        private static final long serialVersionUID = -3646337053166149105L;
043    
044        /** Load factor for the map. */
045        private static final float LOAD_FACTOR = 0.5f;
046    
047        /** Default starting size.
048         * <p>This must be a power of two for bit mask to work properly. </p>
049         */
050        private static final int DEFAULT_EXPECTED_SIZE = 16;
051    
052        /** Multiplier for size growth when map fills up.
053         * <p>This must be a power of two for bit mask to work properly. </p>
054         */
055        private static final int RESIZE_MULTIPLIER = 2;
056    
057        /** Number of bits to perturb the index when probing for collision resolution. */
058        private static final int PERTURB_SHIFT = 5;
059    
060        /** Status indicator for free table entries. */
061        protected static final byte FREE    = 0;
062    
063        /** Status indicator for full table entries. */
064        protected static final byte FULL    = 1;
065    
066        /** Status indicator for removed table entries. */
067        protected static final byte REMOVED = 2;
068    
069        /** Keys table. */
070        private int[] keys;
071    
072        /** Values table. */
073        private double[] values;
074    
075        /** States table. */
076        private byte[] states;
077    
078        /** Return value for missing entries. */
079        private final double missingEntries;
080    
081        /** Current size of the map. */
082        private int size;
083    
084        /** Bit mask for hash values. */
085        private int mask;
086    
087        /** Modifications count. */
088        private transient int count;
089    
090        /**
091         * Build an empty map with default size and using NaN for missing entries.
092         */
093        public OpenIntToDoubleHashMap() {
094            this(DEFAULT_EXPECTED_SIZE, Double.NaN);
095        }
096    
097        /**
098         * Build an empty map with default size
099         * @param missingEntries value to return when a missing entry is fetched
100         */
101        public OpenIntToDoubleHashMap(final double missingEntries) {
102            this(DEFAULT_EXPECTED_SIZE, missingEntries);
103        }
104    
105        /**
106         * Build an empty map with specified size and using NaN for missing entries.
107         * @param expectedSize expected number of elements in the map
108         */
109        public OpenIntToDoubleHashMap(final int expectedSize) {
110            this(expectedSize, Double.NaN);
111        }
112    
113        /**
114         * Build an empty map with specified size.
115         * @param expectedSize expected number of elements in the map
116         * @param missingEntries value to return when a missing entry is fetched
117         */
118        public OpenIntToDoubleHashMap(final int expectedSize,
119                                      final double missingEntries) {
120            final int capacity = computeCapacity(expectedSize);
121            keys   = new int[capacity];
122            values = new double[capacity];
123            states = new byte[capacity];
124            this.missingEntries = missingEntries;
125            mask   = capacity - 1;
126        }
127    
128        /**
129         * Copy constructor.
130         * @param source map to copy
131         */
132        public OpenIntToDoubleHashMap(final OpenIntToDoubleHashMap source) {
133            final int length = source.keys.length;
134            keys = new int[length];
135            System.arraycopy(source.keys, 0, keys, 0, length);
136            values = new double[length];
137            System.arraycopy(source.values, 0, values, 0, length);
138            states = new byte[length];
139            System.arraycopy(source.states, 0, states, 0, length);
140            missingEntries = source.missingEntries;
141            size  = source.size;
142            mask  = source.mask;
143            count = source.count;
144        }
145    
146        /**
147         * Compute the capacity needed for a given size.
148         * @param expectedSize expected size of the map
149         * @return capacity to use for the specified size
150         */
151        private static int computeCapacity(final int expectedSize) {
152            if (expectedSize == 0) {
153                return 1;
154            }
155            final int capacity   = (int) Math.ceil(expectedSize / LOAD_FACTOR);
156            final int powerOfTwo = Integer.highestOneBit(capacity);
157            if (powerOfTwo == capacity) {
158                return capacity;
159            }
160            return nextPowerOfTwo(capacity);
161        }
162    
163        /**
164         * Find the smallest power of two greater than the input value
165         * @param i input value
166         * @return smallest power of two greater than the input value
167         */
168        private static int nextPowerOfTwo(final int i) {
169            return Integer.highestOneBit(i) << 1;
170        }
171    
172        /**
173         * Get the stored value associated with the given key
174         * @param key key associated with the data
175         * @return data associated with the key
176         */
177        public double get(final int key) {
178    
179            final int hash  = hashOf(key);
180            int index = hash & mask;
181            if (containsKey(key, index)) {
182                return values[index];
183            }
184    
185            if (states[index] == FREE) {
186                return missingEntries;
187            }
188    
189            for (int perturb = perturb(hash), j = index; states[index] != FREE; perturb >>= PERTURB_SHIFT) {
190                j = probe(perturb, j);
191                index = j & mask;
192                if (containsKey(key, index)) {
193                    return values[index];
194                }
195            }
196    
197            return missingEntries;
198    
199        }
200    
201        /**
202         * Check if a value is associated with a key.
203         * @param key key to check
204         * @return true if a value is associated with key
205         */
206        public boolean containsKey(final int key) {
207    
208            final int hash  = hashOf(key);
209            int index = hash & mask;
210            if (containsKey(key, index)) {
211                return true;
212            }
213    
214            if (states[index] == FREE) {
215                return false;
216            }
217    
218            for (int perturb = perturb(hash), j = index; 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            for (int perturb = perturb(hash), j = index; states[index] != FREE; perturb >>= PERTURB_SHIFT) {
362                j = probe(perturb, j);
363                index = j & mask;
364                if (containsKey(key, index)) {
365                    return doRemove(index);
366                }
367            }
368    
369            return missingEntries;
370    
371        }
372    
373        /**
374         * Check if the tables contain an element associated with specified key
375         * at specified index.
376         * @param key key to check
377         * @param index index to check
378         * @return true if an element is associated with key at index
379         */
380        private boolean containsKey(final int key, final int index) {
381            return (key != 0 || states[index] == FULL) && keys[index] == key;
382        }
383    
384        /**
385         * Remove an element at specified index.
386         * @param index index of the element to remove
387         * @return removed value
388         */
389        private double doRemove(int index) {
390            keys[index]   = 0;
391            states[index] = REMOVED;
392            final double previous = values[index];
393            values[index] = missingEntries;
394            --size;
395            ++count;
396            return previous;
397        }
398    
399        /**
400         * Put a value associated with a key in the map.
401         * @param key key to which value is associated
402         * @param value value to put in the map
403         * @return previous value associated with the key
404         */
405        public double put(final int key, final double value) {
406            int index = findInsertionIndex(key);
407            double previous = missingEntries;
408            boolean newMapping = true;
409            if (index < 0) {
410                index = changeIndexSign(index);
411                previous = values[index];
412                newMapping = false;
413            }
414            keys[index]   = key;
415            states[index] = FULL;
416            values[index] = value;
417            if (newMapping) {
418                ++size;
419                if (shouldGrowTable()) {
420                    growTable();
421                }
422                ++count;
423            }
424            return previous;
425    
426        }
427    
428        /**
429         * Grow the tables.
430         */
431        private void growTable() {
432    
433            final int oldLength      = states.length;
434            final int[] oldKeys      = keys;
435            final double[] oldValues = values;
436            final byte[] oldStates   = states;
437    
438            final int newLength = RESIZE_MULTIPLIER * oldLength;
439            final int[] newKeys = new int[newLength];
440            final double[] newValues = new double[newLength];
441            final byte[] newStates = new byte[newLength];
442            final int newMask = newLength - 1;
443            for (int i = 0; i < oldLength; ++i) {
444                if (oldStates[i] == FULL) {
445                    final int key = oldKeys[i];
446                    final int index = findInsertionIndex(newKeys, newStates, key, newMask);
447                    newKeys[index]   = key;
448                    newValues[index] = oldValues[i];
449                    newStates[index] = FULL;
450                }
451            }
452    
453            mask   = newMask;
454            keys   = newKeys;
455            values = newValues;
456            states = newStates;
457    
458        }
459    
460        /**
461         * Check if tables should grow due to increased size.
462         * @return true if  tables should grow
463         */
464        private boolean shouldGrowTable() {
465            return size > (mask + 1) * LOAD_FACTOR;
466        }
467    
468        /**
469         * Compute the hash value of a key
470         * @param key key to hash
471         * @return hash value of the key
472         */
473        private static int hashOf(final int key) {
474            final int h = key ^ ((key >>> 20) ^ (key >>> 12));
475            return h ^ (h >>> 7) ^ (h >>> 4);
476        }
477    
478        
479        /** Iterator class for the map. */
480        public class Iterator {
481    
482            /** Reference modification count. */
483            private final int referenceCount;
484    
485            /** Index of current element. */
486            private int current;
487    
488            /** Index of next element. */
489            private int next;
490    
491            /**
492             * Simple constructor.
493             */
494            private Iterator() {
495    
496                // preserve the modification count of the map to detect concurrent modifications later
497                referenceCount = count;
498    
499                // initialize current index
500                next = -1;
501                try {
502                    advance();
503                } catch (NoSuchElementException nsee) {
504                    // ignored
505                }
506    
507            }
508    
509            /**
510             * Check if there is a next element in the map.
511             * @return true if there is a next element
512             */
513            public boolean hasNext() {
514                return next >= 0;
515            }
516    
517            /**
518             * Get the key of current entry.
519             * @return key of current entry
520             * @exception ConcurrentModificationException if the map is modified during iteration
521             * @exception NoSuchElementException if there is no element left in the map
522             */
523            public int key()
524                throws ConcurrentModificationException, NoSuchElementException {
525                if (referenceCount != count) {
526                    throw MathRuntimeException.createConcurrentModificationException("map has been modified while iterating");
527                }
528                if (current < 0) {
529                    throw MathRuntimeException.createNoSuchElementException("iterator exhausted");
530                }
531                return keys[current];
532            }
533    
534            /**
535             * Get the value of current entry.
536             * @return value of current entry
537             * @exception ConcurrentModificationException if the map is modified during iteration
538             * @exception NoSuchElementException if there is no element left in the map
539             */
540            public double value()
541                throws ConcurrentModificationException, NoSuchElementException {
542                if (referenceCount != count) {
543                    throw MathRuntimeException.createConcurrentModificationException("map has been modified while iterating");
544                }
545                if (current < 0) {
546                    throw MathRuntimeException.createNoSuchElementException("iterator exhausted");
547                }
548                return values[current];
549            }
550    
551            /**
552             * Advance iterator one step further.
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 void advance()
557                throws ConcurrentModificationException, NoSuchElementException {
558    
559                if (referenceCount != count) {
560                    throw MathRuntimeException.createConcurrentModificationException("map has been modified while iterating");
561                }
562    
563                // advance on step
564                current = next;
565    
566                // prepare next step
567                try {
568                    while (states[++next] != FULL) {
569                        // nothing to do
570                    }
571                } catch (ArrayIndexOutOfBoundsException e) {
572                    next = -2;
573                    if (current < 0) {
574                        throw MathRuntimeException.createNoSuchElementException("iterator exhausted");
575                    }
576                }
577    
578            }
579    
580        }
581    
582        /**
583         * Read a serialized object.
584         * @param stream input stream
585         * @throws IOException if object cannot be read
586         * @throws ClassNotFoundException if the class corresponding
587         * to the serialized object cannot be found
588         */
589        private void readObject(final ObjectInputStream stream)
590            throws IOException, ClassNotFoundException {
591            stream.defaultReadObject();
592            count = 0;
593        }
594    
595                
596    }