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  package org.apache.commons.math3.util;
18  
19  import java.io.IOException;
20  import java.io.ObjectInputStream;
21  import java.io.Serializable;
22  import java.lang.reflect.Array;
23  import java.util.ConcurrentModificationException;
24  import java.util.NoSuchElementException;
25  
26  import org.apache.commons.math3.Field;
27  import org.apache.commons.math3.FieldElement;
28  
29  /**
30   * Open addressed map from int to FieldElement.
31   * <p>This class provides a dedicated map from integers to FieldElements with a
32   * much smaller memory overhead than standard <code>java.util.Map</code>.</p>
33   * <p>This class is not synchronized. The specialized iterators returned by
34   * {@link #iterator()} are fail-fast: they throw a
35   * <code>ConcurrentModificationException</code> when they detect the map has been
36   * modified during iteration.</p>
37   * @param <T> the type of the field elements
38   * @version $Id: OpenIntToFieldHashMap.java 1421448 2012-12-13 19:45:57Z tn $
39   * @since 2.0
40   */
41  public class OpenIntToFieldHashMap<T extends FieldElement<T>> implements Serializable {
42  
43      /** Status indicator for free table entries. */
44      protected static final byte FREE    = 0;
45  
46      /** Status indicator for full table entries. */
47      protected static final byte FULL    = 1;
48  
49      /** Status indicator for removed table entries. */
50      protected static final byte REMOVED = 2;
51  
52      /** Serializable version identifier. */
53      private static final long serialVersionUID = -9179080286849120720L;
54  
55      /** Load factor for the map. */
56      private static final float LOAD_FACTOR = 0.5f;
57  
58      /** Default starting size.
59       * <p>This must be a power of two for bit mask to work properly. </p>
60       */
61      private static final int DEFAULT_EXPECTED_SIZE = 16;
62  
63      /** Multiplier for size growth when map fills up.
64       * <p>This must be a power of two for bit mask to work properly. </p>
65       */
66      private static final int RESIZE_MULTIPLIER = 2;
67  
68      /** Number of bits to perturb the index when probing for collision resolution. */
69      private static final int PERTURB_SHIFT = 5;
70  
71      /** Field to which the elements belong. */
72      private final Field<T> field;
73  
74      /** Keys table. */
75      private int[] keys;
76  
77      /** Values table. */
78      private T[] values;
79  
80      /** States table. */
81      private byte[] states;
82  
83      /** Return value for missing entries. */
84      private final T missingEntries;
85  
86      /** Current size of the map. */
87      private int size;
88  
89      /** Bit mask for hash values. */
90      private int mask;
91  
92      /** Modifications count. */
93      private transient int count;
94  
95      /**
96       * Build an empty map with default size and using zero for missing entries.
97       * @param field field to which the elements belong
98       */
99      public OpenIntToFieldHashMap(final Field<T>field) {
100         this(field, DEFAULT_EXPECTED_SIZE, field.getZero());
101     }
102 
103     /**
104      * Build an empty map with default size
105      * @param field field to which the elements belong
106      * @param missingEntries value to return when a missing entry is fetched
107      */
108     public OpenIntToFieldHashMap(final Field<T>field, final T missingEntries) {
109         this(field,DEFAULT_EXPECTED_SIZE, missingEntries);
110     }
111 
112     /**
113      * Build an empty map with specified size and using zero for missing entries.
114      * @param field field to which the elements belong
115      * @param expectedSize expected number of elements in the map
116      */
117     public OpenIntToFieldHashMap(final Field<T> field,final int expectedSize) {
118         this(field,expectedSize, field.getZero());
119     }
120 
121     /**
122      * Build an empty map with specified size.
123      * @param field field to which the elements belong
124      * @param expectedSize expected number of elements in the map
125      * @param missingEntries value to return when a missing entry is fetched
126      */
127     public OpenIntToFieldHashMap(final Field<T> field,final int expectedSize,
128                                   final T missingEntries) {
129         this.field = field;
130         final int capacity = computeCapacity(expectedSize);
131         keys   = new int[capacity];
132         values = buildArray(capacity);
133         states = new byte[capacity];
134         this.missingEntries = missingEntries;
135         mask   = capacity - 1;
136     }
137 
138     /**
139      * Copy constructor.
140      * @param source map to copy
141      */
142     public OpenIntToFieldHashMap(final OpenIntToFieldHashMap<T> source) {
143         field = source.field;
144         final int length = source.keys.length;
145         keys = new int[length];
146         System.arraycopy(source.keys, 0, keys, 0, length);
147         values = buildArray(length);
148         System.arraycopy(source.values, 0, values, 0, length);
149         states = new byte[length];
150         System.arraycopy(source.states, 0, states, 0, length);
151         missingEntries = source.missingEntries;
152         size  = source.size;
153         mask  = source.mask;
154         count = source.count;
155     }
156 
157     /**
158      * Compute the capacity needed for a given size.
159      * @param expectedSize expected size of the map
160      * @return capacity to use for the specified size
161      */
162     private static int computeCapacity(final int expectedSize) {
163         if (expectedSize == 0) {
164             return 1;
165         }
166         final int capacity   = (int) FastMath.ceil(expectedSize / LOAD_FACTOR);
167         final int powerOfTwo = Integer.highestOneBit(capacity);
168         if (powerOfTwo == capacity) {
169             return capacity;
170         }
171         return nextPowerOfTwo(capacity);
172     }
173 
174     /**
175      * Find the smallest power of two greater than the input value
176      * @param i input value
177      * @return smallest power of two greater than the input value
178      */
179     private static int nextPowerOfTwo(final int i) {
180         return Integer.highestOneBit(i) << 1;
181     }
182 
183     /**
184      * Get the stored value associated with the given key
185      * @param key key associated with the data
186      * @return data associated with the key
187      */
188     public T get(final int key) {
189 
190         final int hash  = hashOf(key);
191         int index = hash & mask;
192         if (containsKey(key, index)) {
193             return values[index];
194         }
195 
196         if (states[index] == FREE) {
197             return missingEntries;
198         }
199 
200         int j = index;
201         for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
202             j = probe(perturb, j);
203             index = j & mask;
204             if (containsKey(key, index)) {
205                 return values[index];
206             }
207         }
208 
209         return missingEntries;
210 
211     }
212 
213     /**
214      * Check if a value is associated with a key.
215      * @param key key to check
216      * @return true if a value is associated with key
217      */
218     public boolean containsKey(final int key) {
219 
220         final int hash  = hashOf(key);
221         int index = hash & mask;
222         if (containsKey(key, index)) {
223             return true;
224         }
225 
226         if (states[index] == FREE) {
227             return false;
228         }
229 
230         int j = index;
231         for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
232             j = probe(perturb, j);
233             index = j & mask;
234             if (containsKey(key, index)) {
235                 return true;
236             }
237         }
238 
239         return false;
240 
241     }
242 
243     /**
244      * Get an iterator over map elements.
245      * <p>The specialized iterators returned are fail-fast: they throw a
246      * <code>ConcurrentModificationException</code> when they detect the map
247      * has been modified during iteration.</p>
248      * @return iterator over the map elements
249      */
250     public Iterator iterator() {
251         return new Iterator();
252     }
253 
254     /**
255      * Perturb the hash for starting probing.
256      * @param hash initial hash
257      * @return perturbed hash
258      */
259     private static int perturb(final int hash) {
260         return hash & 0x7fffffff;
261     }
262 
263     /**
264      * Find the index at which a key should be inserted
265      * @param key key to lookup
266      * @return index at which key should be inserted
267      */
268     private int findInsertionIndex(final int key) {
269         return findInsertionIndex(keys, states, key, mask);
270     }
271 
272     /**
273      * Find the index at which a key should be inserted
274      * @param keys keys table
275      * @param states states table
276      * @param key key to lookup
277      * @param mask bit mask for hash values
278      * @return index at which key should be inserted
279      */
280     private static int findInsertionIndex(final int[] keys, final byte[] states,
281                                           final int key, final int mask) {
282         final int hash = hashOf(key);
283         int index = hash & mask;
284         if (states[index] == FREE) {
285             return index;
286         } else if (states[index] == FULL && keys[index] == key) {
287             return changeIndexSign(index);
288         }
289 
290         int perturb = perturb(hash);
291         int j = index;
292         if (states[index] == FULL) {
293             while (true) {
294                 j = probe(perturb, j);
295                 index = j & mask;
296                 perturb >>= PERTURB_SHIFT;
297 
298                 if (states[index] != FULL || keys[index] == key) {
299                     break;
300                 }
301             }
302         }
303 
304         if (states[index] == FREE) {
305             return index;
306         } else if (states[index] == FULL) {
307             // due to the loop exit condition,
308             // if (states[index] == FULL) then keys[index] == key
309             return changeIndexSign(index);
310         }
311 
312         final int firstRemoved = index;
313         while (true) {
314             j = probe(perturb, j);
315             index = j & mask;
316 
317             if (states[index] == FREE) {
318                 return firstRemoved;
319             } else if (states[index] == FULL && keys[index] == key) {
320                 return changeIndexSign(index);
321             }
322 
323             perturb >>= PERTURB_SHIFT;
324 
325         }
326 
327     }
328 
329     /**
330      * Compute next probe for collision resolution
331      * @param perturb perturbed hash
332      * @param j previous probe
333      * @return next probe
334      */
335     private static int probe(final int perturb, final int j) {
336         return (j << 2) + j + perturb + 1;
337     }
338 
339     /**
340      * Change the index sign
341      * @param index initial index
342      * @return changed index
343      */
344     private static int changeIndexSign(final int index) {
345         return -index - 1;
346     }
347 
348     /**
349      * Get the number of elements stored in the map.
350      * @return number of elements stored in the map
351      */
352     public int size() {
353         return size;
354     }
355 
356 
357     /**
358      * Remove the value associated with a key.
359      * @param key key to which the value is associated
360      * @return removed value
361      */
362     public T remove(final int key) {
363 
364         final int hash  = hashOf(key);
365         int index = hash & mask;
366         if (containsKey(key, index)) {
367             return doRemove(index);
368         }
369 
370         if (states[index] == FREE) {
371             return missingEntries;
372         }
373 
374         int j = index;
375         for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
376             j = probe(perturb, j);
377             index = j & mask;
378             if (containsKey(key, index)) {
379                 return doRemove(index);
380             }
381         }
382 
383         return missingEntries;
384 
385     }
386 
387     /**
388      * Check if the tables contain an element associated with specified key
389      * at specified index.
390      * @param key key to check
391      * @param index index to check
392      * @return true if an element is associated with key at index
393      */
394     private boolean containsKey(final int key, final int index) {
395         return (key != 0 || states[index] == FULL) && keys[index] == key;
396     }
397 
398     /**
399      * Remove an element at specified index.
400      * @param index index of the element to remove
401      * @return removed value
402      */
403     private T doRemove(int index) {
404         keys[index]   = 0;
405         states[index] = REMOVED;
406         final T previous = values[index];
407         values[index] = missingEntries;
408         --size;
409         ++count;
410         return previous;
411     }
412 
413     /**
414      * Put a value associated with a key in the map.
415      * @param key key to which value is associated
416      * @param value value to put in the map
417      * @return previous value associated with the key
418      */
419     public T put(final int key, final T value) {
420         int index = findInsertionIndex(key);
421         T previous = missingEntries;
422         boolean newMapping = true;
423         if (index < 0) {
424             index = changeIndexSign(index);
425             previous = values[index];
426             newMapping = false;
427         }
428         keys[index]   = key;
429         states[index] = FULL;
430         values[index] = value;
431         if (newMapping) {
432             ++size;
433             if (shouldGrowTable()) {
434                 growTable();
435             }
436             ++count;
437         }
438         return previous;
439 
440     }
441 
442     /**
443      * Grow the tables.
444      */
445     private void growTable() {
446 
447         final int oldLength      = states.length;
448         final int[] oldKeys      = keys;
449         final T[] oldValues = values;
450         final byte[] oldStates   = states;
451 
452         final int newLength = RESIZE_MULTIPLIER * oldLength;
453         final int[] newKeys = new int[newLength];
454         final T[] newValues = buildArray(newLength);
455         final byte[] newStates = new byte[newLength];
456         final int newMask = newLength - 1;
457         for (int i = 0; i < oldLength; ++i) {
458             if (oldStates[i] == FULL) {
459                 final int key = oldKeys[i];
460                 final int index = findInsertionIndex(newKeys, newStates, key, newMask);
461                 newKeys[index]   = key;
462                 newValues[index] = oldValues[i];
463                 newStates[index] = FULL;
464             }
465         }
466 
467         mask   = newMask;
468         keys   = newKeys;
469         values = newValues;
470         states = newStates;
471 
472     }
473 
474     /**
475      * Check if tables should grow due to increased size.
476      * @return true if  tables should grow
477      */
478     private boolean shouldGrowTable() {
479         return size > (mask + 1) * LOAD_FACTOR;
480     }
481 
482     /**
483      * Compute the hash value of a key
484      * @param key key to hash
485      * @return hash value of the key
486      */
487     private static int hashOf(final int key) {
488         final int h = key ^ ((key >>> 20) ^ (key >>> 12));
489         return h ^ (h >>> 7) ^ (h >>> 4);
490     }
491 
492 
493     /** Iterator class for the map. */
494     public class Iterator {
495 
496         /** Reference modification count. */
497         private final int referenceCount;
498 
499         /** Index of current element. */
500         private int current;
501 
502         /** Index of next element. */
503         private int next;
504 
505         /**
506          * Simple constructor.
507          */
508         private Iterator() {
509 
510             // preserve the modification count of the map to detect concurrent modifications later
511             referenceCount = count;
512 
513             // initialize current index
514             next = -1;
515             try {
516                 advance();
517             } catch (NoSuchElementException nsee) { // NOPMD
518                 // ignored
519             }
520 
521         }
522 
523         /**
524          * Check if there is a next element in the map.
525          * @return true if there is a next element
526          */
527         public boolean hasNext() {
528             return next >= 0;
529         }
530 
531         /**
532          * Get the key of current entry.
533          * @return key of current entry
534          * @exception ConcurrentModificationException if the map is modified during iteration
535          * @exception NoSuchElementException if there is no element left in the map
536          */
537         public int key()
538             throws ConcurrentModificationException, NoSuchElementException {
539             if (referenceCount != count) {
540                 throw new ConcurrentModificationException();
541             }
542             if (current < 0) {
543                 throw new NoSuchElementException();
544             }
545             return keys[current];
546         }
547 
548         /**
549          * Get the value of current entry.
550          * @return value of current entry
551          * @exception ConcurrentModificationException if the map is modified during iteration
552          * @exception NoSuchElementException if there is no element left in the map
553          */
554         public T value()
555             throws ConcurrentModificationException, NoSuchElementException {
556             if (referenceCount != count) {
557                 throw new ConcurrentModificationException();
558             }
559             if (current < 0) {
560                 throw new NoSuchElementException();
561             }
562             return values[current];
563         }
564 
565         /**
566          * Advance iterator one step further.
567          * @exception ConcurrentModificationException if the map is modified during iteration
568          * @exception NoSuchElementException if there is no element left in the map
569          */
570         public void advance()
571             throws ConcurrentModificationException, NoSuchElementException {
572 
573             if (referenceCount != count) {
574                 throw new ConcurrentModificationException();
575             }
576 
577             // advance on step
578             current = next;
579 
580             // prepare next step
581             try {
582                 while (states[++next] != FULL) { // NOPMD
583                     // nothing to do
584                 }
585             } catch (ArrayIndexOutOfBoundsException e) {
586                 next = -2;
587                 if (current < 0) {
588                     throw new NoSuchElementException();
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     /** Build an array of elements.
610      * @param length size of the array to build
611      * @return a new array
612      */
613     @SuppressWarnings("unchecked") // field is of type T
614     private T[] buildArray(final int length) {
615         return (T[]) Array.newInstance(field.getRuntimeClass(), length);
616     }
617 
618 }