View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  
18  package org.apache.commons.math3.util;
19  
20  import java.io.IOException;
21  import java.io.ObjectInputStream;
22  import java.io.Serializable;
23  import java.util.ConcurrentModificationException;
24  import java.util.NoSuchElementException;
25  
26  /**
27   * Open addressed map from int to double.
28   * <p>This class provides a dedicated map from integers to doubles with a
29   * much smaller memory overhead than standard <code>java.util.Map</code>.</p>
30   * <p>This class is not synchronized. The specialized iterators returned by
31   * {@link #iterator()} are fail-fast: they throw a
32   * <code>ConcurrentModificationException</code> when they detect the map has been
33   * modified during iteration.</p>
34   * @version $Id: OpenIntToDoubleHashMap.java 1421448 2012-12-13 19:45:57Z tn $
35   * @since 2.0
36   */
37  public class OpenIntToDoubleHashMap implements Serializable {
38  
39      /** Status indicator for free table entries. */
40      protected static final byte FREE    = 0;
41  
42      /** Status indicator for full table entries. */
43      protected static final byte FULL    = 1;
44  
45      /** Status indicator for removed table entries. */
46      protected static final byte REMOVED = 2;
47  
48      /** Serializable version identifier */
49      private static final long serialVersionUID = -3646337053166149105L;
50  
51      /** Load factor for the map. */
52      private static final float LOAD_FACTOR = 0.5f;
53  
54      /** Default starting size.
55       * <p>This must be a power of two for bit mask to work properly. </p>
56       */
57      private static final int DEFAULT_EXPECTED_SIZE = 16;
58  
59      /** Multiplier for size growth when map fills up.
60       * <p>This must be a power of two for bit mask to work properly. </p>
61       */
62      private static final int RESIZE_MULTIPLIER = 2;
63  
64      /** Number of bits to perturb the index when probing for collision resolution. */
65      private static final int PERTURB_SHIFT = 5;
66  
67      /** Keys table. */
68      private int[] keys;
69  
70      /** Values table. */
71      private double[] values;
72  
73      /** States table. */
74      private byte[] states;
75  
76      /** Return value for missing entries. */
77      private final double missingEntries;
78  
79      /** Current size of the map. */
80      private int size;
81  
82      /** Bit mask for hash values. */
83      private int mask;
84  
85      /** Modifications count. */
86      private transient int count;
87  
88      /**
89       * Build an empty map with default size and using NaN for missing entries.
90       */
91      public OpenIntToDoubleHashMap() {
92          this(DEFAULT_EXPECTED_SIZE, Double.NaN);
93      }
94  
95      /**
96       * Build an empty map with default size
97       * @param missingEntries value to return when a missing entry is fetched
98       */
99      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 }