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.math.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  import org.apache.commons.math.MathRuntimeException;
27  
28  /**
29   * Open addressed map from int to double.
30   * <p>This class provides a dedicated map from integers to doubles with a
31   * much smaller memory overhead than standard <code>java.util.Map</code>.</p>
32   * <p>This class is not synchronized. The specialized iterators returned by
33   * {@link #iterator()} are fail-fast: they throw a
34   * <code>ConcurrentModificationException</code> when they detect the map has been
35   * modified during iteration.</p>
36   * @version $Revision: 746578 $ $Date: 2009-02-21 15:01:14 -0500 (Sat, 21 Feb 2009) $
37   * @since 2.0
38   */
39  public class OpenIntToDoubleHashMap implements Serializable {
40  
41      /** Serializable version identifier */
42      private static final long serialVersionUID = -3646337053166149105L;
43  
44      /** Load factor for the map. */
45      private static final float LOAD_FACTOR = 0.5f;
46  
47      /** Default starting size.
48       * <p>This must be a power of two for bit mask to work properly. </p>
49       */
50      private static final int DEFAULT_EXPECTED_SIZE = 16;
51  
52      /** Multiplier for size growth when map fills up.
53       * <p>This must be a power of two for bit mask to work properly. </p>
54       */
55      private static final int RESIZE_MULTIPLIER = 2;
56  
57      /** Number of bits to perturb the index when probing for collision resolution. */
58      private static final int PERTURB_SHIFT = 5;
59  
60      /** Status indicator for free table entries. */
61      protected static final byte FREE    = 0;
62  
63      /** Status indicator for full table entries. */
64      protected static final byte FULL    = 1;
65  
66      /** Status indicator for removed table entries. */
67      protected static final byte REMOVED = 2;
68  
69      /** Keys table. */
70      private int[] keys;
71  
72      /** Values table. */
73      private double[] values;
74  
75      /** States table. */
76      private byte[] states;
77  
78      /** Return value for missing entries. */
79      private final double missingEntries;
80  
81      /** Current size of the map. */
82      private int size;
83  
84      /** Bit mask for hash values. */
85      private int mask;
86  
87      /** Modifications count. */
88      private transient int count;
89  
90      /**
91       * Build an empty map with default size and using NaN for missing entries.
92       */
93      public OpenIntToDoubleHashMap() {
94          this(DEFAULT_EXPECTED_SIZE, Double.NaN);
95      }
96  
97      /**
98       * Build an empty map with default size
99       * @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 }