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